Paper 2015/1005 Original: eprint.iacr.org/2015/1005 ↗

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

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.