Paper 2015/1005

Cryptanalysis of Yasuda, Takagi and Sakurai's Signature Scheme Using Invariant Subspaces

Wenbin Zhang and Chik How Tan


In PQCrypto 2013 Yasuda, Takagi and Sakurai proposed an interesting signature scheme of efficiency $O(n^2)$ with parameter $(q=6781, n=121)$ claimed to have 140-bit security level. Later on almost at the same time two independent and different attacks were then proposed by Y. Hashimoto in PQCrypto 2014 and by the authors in ICISC 2014. Hashimoto's attack has complexity $O(n^4)$ and breaks $(q=6781, n=121)$ in several minutes. In this paper, we make an essential extension of our work in ICISC 2014. We develop for the our previous method a thorough and rigorous mathematical theory by applying intensively the theory of invariant subspaces, then work out a much better attack with complexity $O(n^4)$, and especially implement it successfully. Our new attack efficiently recovers equivalent private keys of many randomly generated instances, especially breaking $(q=6781, n=121)$ in only about 14.77 seconds, much faster than Y. Hashimoto's attack. The approach developed here might have further applications.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Major revision. ICISC 2014
post-quantum cryptographymultivariate public key cryptosysteminvariant subspace
Contact author(s)
tslzw @ nus edu sg
2015-10-16: received
Short URL
Creative Commons Attribution


      author = {Wenbin Zhang and Chik How Tan},
      title = {Cryptanalysis of Yasuda, Takagi and Sakurai's Signature Scheme Using Invariant Subspaces},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1005},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.