Cryptanalysis for 2-Layer TriRainbow

Kato, Taku; Shuhei Nakamura

doi:10.51094/jxiv.369

##article.authors##

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

DOI:

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

キーワード:

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

抄録

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 2³² for version 1, and 2⁷⁰ 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.

利益相反に関する開示

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

ダウンロード *前日までの集計結果を表示します

ダウンロード実績データは、公開の翌日以降に作成されます。

引用文献

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