Preprint / Version 1

Cryptanalysis for 2-Layer TriRainbow

##article.authors##

  • Taku Kato Chigasaki-shi, Kanagawa
  • Shuhei Nakamura Department of Computer and Information Sciences, Ibaraki University

DOI:

https://doi.org/10.51094/jxiv.369

Keywords:

Post-quantum cryptography, Multivariate public key cryptography, Rainbow, TriRainbow

Abstract

TriRainbow is proposed by Ganguly and Saxena as a variant of the multi-layered scheme Rainbow.They show that TriRainbow is as efficient as Rainbow, but resistants to known attacks breaking Rainbow.In this paper, we propose efficient attacks against 2-layer TriRainbow by combining two known attacks against Rainbow.As a result, the complexity of our attack against SL1 TriRainbow is only 232 for version 1, and 270 for version 2. Moreover, our experiment shows that an equivalent key of TriRainbow version 1 with the parameter (q,v,o,t)=(16,36,32,32) is computed in a few minutes with a laptop.  

Conflicts of Interest Disclosure

The authors declare no conflicts of interest associated with this manuscript.

Downloads *Displays the aggregated results up to the previous day.

Download data is not yet available.

References

Beullens, W.: Improved Cryptanalysis of UOV and Rainbow. In: Canteaut, A., Standaert, F.X. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 348–373. Springer International Publishing, Cham (2021)

Beullens, W.: Breaking Rainbow Takes a Weekend on a Laptop. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, vol. 13508, pp. 464–479. Springer Nature Switzerland, Cham (2022)

Bosma, W., C.J., Playoust, C.: The Magma algebra system. I. The user language. J. Symbolic Comput. 24, 235–265 (1997)

Ding, J., Schmidt, D.: Rainbow, A New Multivariable Polynomial Signature Scheme. In: Ioannidis, J., Keromytis, A., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 164–175. Springer Berlin Heidelberg, Berlin, Heidelberg (2005)

Ding, J., Yang, B.Y., Chen, C.H.O., Chen, M.S., Cheng, C.M.: New Differential- Algebraic Attacks and Reparametrization of Rainbow. In: Bellovin, S.M., Gennaro, R., Keromytis, A., Yung, M. (eds.) ACNS 2008. LNCS, vol. 5037, pp. 242–257. Springer Berlin Heidelberg, Berlin, Heidelberg (2008)

Ganguly, A., Saxena, N.: A new multivariate digital-signature scheme by mixing oil-vinegar with triangles (accessed 21 April 2023), https://www.cse.iitk.ac.in/users/nitin/papers/TriRainbow.pdf

Kipnis, A., Patarin, J., Goubin, L.: Unbalanced Oil and Vinegar Signature Schemes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 206–222. Springer Berlin Heidelberg, Berlin, Heidelberg (1999)

Michael R. Garey, D.S.J.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA (1979)

Shor, P.W.: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 26(5), 1484–1509 (1997)

National Institute of Standards and Technology: Post-Quantum Cryptography, https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization

National Institute of Standards and Technology: Post-Quantum Cryptography, Round 3 Submissions, https://csrc.nist.gov/projects/post- quantum-cryptography/round-3-submissions

Downloads

Posted


Submitted: 2023-04-25 11:10:56 UTC

Published: 2023-04-28 00:43:08 UTC
Section
Information Sciences

License

Copyright (c) 2023 Taku Kato
Shuhei Nakamura

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.