Paper 2018/310

Chosen Message Attack on Multivariate Signature ELSA at Asiacrypt 2017

Yasufumi Hashimoto, Yasuhiko Ikematsu, and Tsuyoshi Takagi

Abstract

One of the most efficient post-quantum signature schemes is Rainbow whose harness 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
post-quantum cryptographymultivariate public-key cryptographychosen message attackRainbowELSA
Contact author(s)
ikematsu @ mist i u-tokyo ac jp
History
2018-04-03: received
Short URL
https://ia.cr/2018/310
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/310,
      author = {Yasufumi Hashimoto and Yasuhiko Ikematsu and Tsuyoshi Takagi},
      title = {Chosen Message Attack on Multivariate Signature ELSA at Asiacrypt 2017},
      howpublished = {Cryptology ePrint Archive, Paper 2018/310},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/310}},
      url = {https://eprint.iacr.org/2018/310}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.