Welcome to the resource topic for 2015/1005
Title:
Cryptanalysis of Yasuda, Takagi and Sakurai’s Signature Scheme Using Invariant Subspaces
Authors: Wenbin Zhang, 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.
ePrint: https://eprint.iacr.org/2015/1005
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .