「Chosen Message Attack on Multivariate Signature ELSA at Asiacrypt 2017」

［Journal of Information Processing Vol.27, pp.517-524］

［Abstract］

　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.