「Chosen Message Attack on Multivariate Signature ELSA at Asiacrypt 2017」
Chosen Message Attack on Multivariate Signature ELSA at Asiacrypt 2017
［Journal of Information Processing Vol.27, pp.517-524］
One of the most efficient post-quantum signature schemes is Rainbow whose hardness is based on the multivariate quadratic polynomial (MQ) problem. ELSA, a new multivariate signature scheme proposed at Asiacrypt 2017, has a similar construction to Rainbow. Its advantages, compared to Rainbow, are its smaller secret key and faster signature generation. In addition, its existential unforgeability against an adaptive chosen-message attack has been proven under the hardness of the MQ-problem induced by a public key of ELSA with a specific parameter set in the random oracle model. The high efficiency of ELSA is derived from a set of hidden quadratic equations used in the process of signature generation. However, the hidden quadratic equations yield a vulnerability. In fact, a piece of information of these equations can be recovered by using valid signatures and an equivalent secret key can be partially recovered from it. In this paper, we describe how to recover an equivalent secret key of ELSA by a chosen message attack. Our experiments show that we can recover an equivalent secret key for the claimed 128-bit security parameter of ELSA on a standard PC in 177 seconds with 1326 valid signatures.
［Reasons for the award］
The authors prove and demonstrate that an efficient chosen message attack is possible on ELSA, which was proposed as a post-quantum signature scheme in 2017. ELSA’s hardness is based on the multivariate quadratic polynomial (MQ) problem. ELSA is computationally more efficient than Rainbow that is a second-round candidate of NIST Post-Quantum Cryptography Standardization Process and is also based on the MQ problem. The authors not only mathematically analyze a vulnerability of a constituent of ELSA, which is introduced for the efficiency, but also demonstrate by a computational experiment that it can practically be broken in a short time. They address an important security issue about a signature scheme that could be promising in the post-quantum era. In conclusion, this research work is highly novel and has practical implications, and thus, we selected this excellent paper for the Journal of Information Processing Outstanding Paper Award.
He received the PhD in Mathematics in 2006 from Kyushu University. He is currently an associate professor in Department of Mathematical Sciences, University of the Ryukyus. His research interests include Representation Theory, Number Theory and Cryptology.
He received the PhD in mathematics in 2016 from Kyushu University. He was a research fellow in Institute of Mathematics for Industry, Kyushu University from 2016 to 2018 and in Department of Mathematical Informatics, University of Tokyo from April to December in 2018. He is currently an assistant professor in Institute of Mathematics for Industry, Kyushu University. His research interests include number theory and multivariate cryptography.
He received the B.Sc. and M.Sc. degrees in mathematics from Nagoya University in 1993 and 1995, respectively. He had engaged in the research on network security at NTT Laboratories from 1995 to 2001. He received the PhD from Technical University of Darmstadt in 2001. He was an Assistant Professor in the Department of Computer Science at Technical University of Darmstadt until 2005. He is currently a Professor in Department of Mathematical Informatics, University of Tokyo. His current research interests are information security and cryptography. He has received DOCOMO Mobile Science Award in 2013, IEICE Achievement Award in 2013, and JSPS Prize in 2014. Dr. Takagi is a Program Chair of the 7th International Conference on Post-Quantum Cryptography PQCrypto 2016.