Paper 2020/703
New Complexity Estimation on the Rainbow-Band-Separation Attack
Shuhei Nakamura, Yasuhiko Ikematsu, Yacheng Wang, Jintai Ding, and Tsuyoshi Takagi
Abstract
Multivariate public key cryptography is a candidate for post-quantum cryptography, and it allows generating particularly short signatures and fast verification.
The Rainbow signature scheme proposed by J. Ding and D. Schmidt is such a multivariate cryptosystem and is considered secure against all known attacks.
The Rainbow-Band-Separation attack recovers a secret key of Rainbow by solving certain systems of quadratic equations, and its complexity is estimated by the well-known indicator called the degree of regularity.
However, the degree of regularity generally is larger than the solving degree in experiments, and an accurate estimation cannot be obtained.
In this paper, we propose a new indicator for the complexity of the Rainbow-Band-Separation attack using the
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Multivariate public key cryptographyRainbow-Band-Separation attackdegree of regularity
- Contact author(s)
- nakamura shuhei @ nihon-u ac jp
- History
- 2020-06-11: received
- Short URL
- https://ia.cr/2020/703
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/703, author = {Shuhei Nakamura and Yasuhiko Ikematsu and Yacheng Wang and Jintai Ding and Tsuyoshi Takagi}, title = {New Complexity Estimation on the Rainbow-Band-Separation Attack}, howpublished = {Cryptology {ePrint} Archive, Paper 2020/703}, year = {2020}, url = {https://eprint.iacr.org/2020/703} }