論文

査読有り
2014年

Cryptanalysis of the Multivariate Signature Scheme Proposed in PQCrypto 2013

POST-QUANTUM CRYPTOGRAPHY, PQCRYPTO 2014
  • Yasufumi Hashimoto

8772
開始ページ
108
終了ページ
125
記述言語
英語
掲載種別
研究論文(国際会議プロシーディングス)
出版者・発行元
SPRINGER-VERLAG BERLIN

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 subexponential time for the third attack. In the present paper, we give a new attack on YTS using an approach similar to the diagonalization of a matrix. Our attack works in polynomial time and it actually recovers equivalent secret keys of YTS having 140-bits security againt min-rank attack in several minutes.

リンク情報
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000345511100007&DestApp=WOS_CPL
URL
https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84921816391&origin=inward
ID情報
  • ISSN : 0302-9743
  • Web of Science ID : WOS:000345511100007

エクスポート
BibTeX RIS