
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Cryptanalysis of the Multivariate Signature Scheme Proposed in PQCrypto 2013
Yasufumi HASHIMOTO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E99A
No.1
pp.5865 Publication Date: 2016/01/01 Online ISSN: 17451337
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, postquantum cryptography,
Full Text: PDF>>
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 nondegenerate 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 minrank attack are applicable on YTS, and the running times are exponential time for the first and the second attacks and subexponential 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 140bits security against minrank attack in around fifteen seconds.

