Paper Info
Title
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) 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) 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), 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.
Year
Venue
Field
2015
IACR Cryptology ePrint Archive
Discrete mathematics,Security level,Mathematical theory,Cryptanalysis,Linear subspace,Invariant (mathematics),Essential extension,Mathematics
DocType
Volume
Citations 
Journal
2015
0
PageRank 
References 
Authors
0.34
9
2
Name
Order
Citations
PageRank
Wenbin Zhang1248.22
Chik How Tan249954.60