You are looking at a specific version 20200611:145459 of this paper. See the latest version.

Paper 2020/703

New Complexity Estimation on the Rainbow-Band-Separation Attack

Shuhei Nakamura and Yasuhiko Ikematsu and Yacheng Wang and 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 $F_4$ algorithm, which gives a more precise estimation compared to one using the degree of regularity. This indicator is deduced by the two-variable power series $$\frac{\prod _{i=1}^m(1-t_1^{d_{i1}}t_2^{d_{i2}})}{(1-t_1)^{n_1}(1-t_2)^{n_2}},$$ which coincides with the one-variable power series at $t_1=t_2$ deriving the degree of regularity. Moreover, we show a relation between the Rainbow-Band-Separation attack using the hybrid approach and the HighRank attack. By considering this relation and our indicator, we obtain a new complexity estimation for the Rainbow-Band-Separation attack. Consequently, we are able to understand the precise security of Rainbow against the Rainbow-Band-Separation attack using the $F_4$ algorithm.

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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.