Paper 2020/703
New Complexity Estimation on the RainbowBandSeparation Attack
Shuhei Nakamura, Yasuhiko Ikematsu, Yacheng Wang, Jintai Ding, and Tsuyoshi Takagi
Abstract
Multivariate public key cryptography is a candidate for postquantum 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 RainbowBandSeparation attack recovers a secret key of Rainbow by solving certain systems of quadratic equations, and its complexity is estimated by the wellknown 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 RainbowBandSeparation 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 twovariable power series $$\frac{\prod _{i=1}^m(1t_1^{d_{i1}}t_2^{d_{i2}})}{(1t_1)^{n_1}(1t_2)^{n_2}},$$ which coincides with the onevariable power series at $t_1=t_2$ deriving the degree of regularity. Moreover, we show a relation between the RainbowBandSeparation attack using the hybrid approach and the HighRank attack. By considering this relation and our indicator, we obtain a new complexity estimation for the RainbowBandSeparation attack. Consequently, we are able to understand the precise security of Rainbow against the RainbowBandSeparation attack using the $F_4$ algorithm.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 Multivariate public key cryptographyRainbowBandSeparation attackdegree of regularity
 Contact author(s)
 nakamura shuhei @ nihonu ac jp
 History
 20200611: 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 RainbowBandSeparation Attack}, howpublished = {Cryptology ePrint Archive, Paper 2020/703}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/703}}, url = {https://eprint.iacr.org/2020/703} }