Cryptology ePrint Archive: Report 2015/1005

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

Wenbin Zhang and Chik How Tan

Abstract: 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.

Category / Keywords: public-key cryptography / post-quantum cryptography, multivariate public key cryptosystem, invariant subspace

Original Publication (with major differences): ICISC 2014

Date: received 15 Oct 2015

Contact author: tslzw at nus edu sg

Available format(s): PDF | BibTeX Citation

Version: 20151016:153646 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]