Cryptanalysis of the Multivariate Signature Scheme Proposed in PQCrypto 2013

Yasufumi HASHIMOTO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A   No.1   pp.58-65
Publication Date: 2016/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.58
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: 
Keyword: 
multivariate public key cryptosystems,  signature scheme,  quadratic forms,  post-quantum cryptography,  

Full Text: PDF(370.6KB)>>
Buy this Article




Summary: 
In PQCrypto 2013, Yasuda, Takagi and Sakurai proposed a new signature scheme as one of multivariate public key cryptosystems (MPKCs). This scheme (called YTS) is based on the fact that there are two isometry classes of non-degenerate quadratic forms on a vector space with a prescribed dimension. The advantage of YTS is its efficiency. In fact, its signature generation is eight or nine times faster than Rainbow of similar size. For the security, it is known that the direct attack, the IP attack and the min-rank attack are applicable on YTS, and the running times are exponential time for the first and the second attacks and sub-exponential time for the third attack. In the present paper, we give a new attack on YTS whose approach is to use the diagonalization of matrices. Our attack works in polynomial time and it actually recovers equivalent secret keys of YTS having 140-bits security against min-rank attack in around fifteen seconds.