Communications in Cryptology IACR CiC

Preliminary Cryptanalysis of the Biscuit Signature Scheme

Authors

Charles Bouillaguet, Julia Sauvage
Charles Bouillaguet ORCID
Sorbonne Université, CNRS, LIP6, Paris, France
charles dot bouillaguet at lip6 dot fr
Julia Sauvage ORCID
Sorbonne Université, CNRS, LIP6, Paris, France
julia dot sauvage at lip6 dot fr
Keywords: algebraic attack multivariate crypto biscuit signature scheme

Abstract

Biscuit is a recent multivariate signature scheme based on the MPC-in-the-Head paradigm. It has been submitted to the NIST competition for additional signature schemes. Signatures are derived from a zero-knowledge proof of knowledge of the solution of a structured polynomial system. This extra structure enables efficient proofs and compact signatures. This short note demonstrates that it also makes these polynomial systems easier to solve than random ones. As a consequence, the original parameters of Biscuit failed to meet the required security levels and had to be upgraded.

References

[ACF+15]
Martin R. Albrecht, Carlos Cid, Jean-Charles Faugère, Robert Fitzpatrick, and Ludovic Perret. Algebraic algorithms for LWE problems. ACM Commun. Comput. Algebra, 49(2):62, 2015. https://doi.org/10.1145/2815111.2815158.
Google Scholar ePrint
[AG11]
Sanjeev Arora and Rong Ge. New algorithms for learning in presence of errors. In Luca Aceto, Monika Henzinger, and Jir\'ı Sgall, editors, Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I, volume 6755 of Lecture Notes in Computer Science, 403–415. Springer, 2011. https://doi.org/10.1007/978-3-642-22006-7_34.
Google Scholar ePrint
[Ash90]
R.B. Ash. Information Theory. Dover books on advanced mathematics. Dover Publications, 1990. ISBN 9780486665214.
Google Scholar ePrint
[AW21]
Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, 522–539. SIAM, 2021. https://doi.org/10.1137/1.9781611976465.32.
Google Scholar ePrint
[Bar04]
Magali Bardet. Étude des systèmes algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie. PhD thesis, Pierre and Marie Curie University, Paris, France, 2004.
Google Scholar ePrint
[BFP09]
Luk Bettale, Jean-Charles Faugère, and Ludovic Perret. Hybrid approach for solving multivariate systems over finite fields. J. Math. Cryptol., 3(3):177–197, 2009. https://doi.org/10.1515/JMC.2009.009.
Google Scholar ePrint
[BFP12]
Luk Bettale, Jean-Charles Faugère, and Ludovic Perret. Solving polynomial systems over finite fields: improved analysis of the hybrid approach. In Joris van der Hoeven and Mark van Hoeij, editors, International Symposium on Symbolic and Algebraic Computation, ISSAC'12, Grenoble, France - July 22 - 25, 2012, 67–74. ACM, 2012. https://doi.org/10.1145/2442829.2442843.
Google Scholar ePrint
[BFR23]
Ryad Benadjila, Thibauld Feneuil, and Matthieu Rivain. Mq on my mind: post-quantum signatures from the non-structured multivariate quadratic problem. 2023.
Google Scholar ePrint
[BFS15]
Magali Bardet, Jean-Charles Faugère, and Bruno Salvy. On the complexity of the F5 gröbner basis algorithm. J. Symb. Comput., 70:49–70, 2015. https://doi.org/10.1016/j.jsc.2014.09.025.
Google Scholar ePrint
[BFSS13]
Magali Bardet, Jean-Charles Faugère, Bruno Salvy, and Pierre-Jean Spaenlehauer. On the complexity of solving quadratic boolean systems. J. Complex., 29(1):53–75, 2013. https://doi.org/10.1016/J.JCO.2012.07.001.
Google Scholar ePrint
[BKPV23]
Luk Bettale, Delaram Kahrobaei, Ludovic Perret, and Javier Verbel. Biscuit. Technical Report, National Institute of Standards and Technology, 2023.
Google Scholar ePrint
[BKPV24]
Luk Bettale, Delaram Kahrobaei, Ludovic Perret, and Javier A. Verbel. Biscuit: new mpcith signature scheme from structured multivariate polynomials. In Christina Pöpper and Lejla Batina, editors, Applied Cryptography and Network Security - 22nd International Conference, ACNS 2024, Abu Dhabi, United Arab Emirates, March 5-8, 2024, Proceedings, Part I, volume 14583 of Lecture Notes in Computer Science, 457–486. Springer, 2024. https://doi.org/10.1007/978-3-031-54770-6_18.
Google Scholar ePrint
[BMSV22]
Emanuele Bellini, Rusydi H. Makarim, Carlo Sanna, and Javier A. Verbel. An estimator for the hardness of the MQ problem. In Lejla Batina and Joan Daemen, editors, Progress in Cryptology - AFRICACRYPT 2022: 13th International Conference on Cryptology in Africa, AFRICACRYPT 2022, Fes, Morocco, July 18-20, 2022, Proceedings, volume 13503 of Lecture Notes in Computer Science, 323–347. Springer Nature Switzerland, 2022. https://doi.org/10.1007/978-3-031-17433-9_14.
Google Scholar ePrint
[Buc65]
B. Buchberger. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal (An Algorithm for Finding the Basis Elements in the Residue Class Ring Modulo a Zero Dimensional Polynomial Ideal). PhD thesis, Mathematical Institute, University of Innsbruck, Austria, 1965.
Google Scholar ePrint
[CCNY12]
Chen-Mou Cheng, Tung Chou, Ruben Niederhagen, and Bo-Yin Yang. Solving quadratic equations with XL on parallel architectures. In Emmanuel Prouff and Patrick Schaumont, editors, Cryptographic Hardware and Embedded Systems - CHES 2012 - 14th International Workshop, Leuven, Belgium, September 9-12, 2012. Proceedings, volume 7428 of Lecture Notes in Computer Science, 356–373. Springer, 2012. https://doi.org/10.1007/978-3-642-33027-8_21.
Google Scholar ePrint
[CDL+11]
Changbo Chen, James H. Davenport, François Lemaire, Marc Moreno Maza, Bican Xia, Rong Xiao, and Yuzhen Xie. Computing the real solutions of polynomial systems with the regularchains library in maple. ACM Commun. Comput. Algebra, 45(3/4):166–168, 2011. https://doi.org/10.1145/2110170.2110174.
Google Scholar ePrint
[CGP03]
Nicolas T. Courtois, Louis Goubin, and Jacques Patarin. SFLASHv3, a fast asymmetric signature scheme. 2003.
Google Scholar ePrint
[CHR+16]
Ming-Shing Chen, Andreas Hülsing, Joost Rijneveld, Simona Samardjiska, and Peter Schwabe. From 5-pass \emph MQ-based identification to \emph MQ-based signatures. In Jung Hee Cheon and Tsuyoshi Takagi, editors, Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part II, volume 10032 of Lecture Notes in Computer Science, 135–165. 2016. https://doi.org/10.1007/978-3-662-53890-6_5.
Google Scholar ePrint
[CKPS00]
Nicolas T. Courtois, Alexander Klimov, Jacques Patarin, and Adi Shamir. Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In Bart Preneel, editor, Advances in Cryptology - EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14-18, 2000, Proceeding, volume 1807 of Lecture Notes in Computer Science, 392–407. Springer, 2000. https://doi.org/10.1007/3-540-45539-6_27.
Google Scholar ePrint
[CLO91]
David A. Cox, John Little, and Donal O'Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, (Undergraduate Texts in Mathematics). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 1991. ISBN 0387356509.
Google Scholar ePrint
[Cop94]
Don Coppersmith. Solving homogeneous linear equations over GF(2) via block wiedemann algorithm. Mathematics of Computation, 62(205):333–350, 1994.
Google Scholar ePrint
[EVZB23]
Andre Esser, Javier Verbel, Floyd Zweydinger, and Emanuele Bellini. $\texttt CryptographicEstimators$: a software library for cryptographic hardness estimation. 2023.
Google Scholar ePrint
[Fau02]
Jean-Charles Faugère. A New Efficient Algorithm for Computing Gröbner Bases Without Reduction to Zero (F5). In T. Mora, editor, ISSAC '02: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, 75–83. New York, NY, USA, July 2002. ACM Press. https://doi.org/10.1145/780506.780516.
Google Scholar ePrint
[FJ03]
Jean-Charles Faugère and Antoine Joux. Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using gröbner bases. In Dan Boneh, editor, Advances in Cryptology - CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings, volume 2729 of Lecture Notes in Computer Science, 44–60. Springer, 2003. https://doi.org/10.1007/978-3-540-45146-4_3.
Google Scholar ePrint
[GJ79]
M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. ISBN 0-7167-1044-7.
Google Scholar ePrint
[KPG99]
Aviad Kipnis, Jacques Patarin, and Louis Goubin. Unbalanced oil and vinegar signature schemes. In Jacques Stern, editor, Advances in Cryptology - EUROCRYPT '99, International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, May 2-6, 1999, Proceeding, volume 1592 of Lecture Notes in Computer Science, 206–222. Springer, 1999. https://doi.org/10.1007/3-540-48910-X_15.
Google Scholar ePrint
[KZ20]
Daniel Kales and Greg Zaverucha. An attack on some signature schemes constructed from five-pass identification schemes. In Stephan Krenn, Haya Schulmann, and Serge Vaudenay, editors, Cryptology and Network Security - 19th International Conference, CANS 2020, Vienna, Austria, December 14-16, 2020, Proceedings, volume 12579 of Lecture Notes in Computer Science, 3–22. Springer, 2020. https://doi.org/10.1007/978-3-030-65411-5_1.
Google Scholar ePrint
[Pat96]
Jacques Patarin. Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms. In Ueli M. Maurer, editor, Advances in Cryptology - EUROCRYPT '96, International Conference on the Theory and Application of Cryptographic Techniques, Saragossa, Spain, May 12-16, 1996, Proceeding, volume 1070 of Lecture Notes in Computer Science, 33–48. Springer, 1996. https://doi.org/10.1007/3-540-68339-9_4.
Google Scholar ePrint
[SCH+19]
Simona Samardjiska, Ming-Shing Chen, Andreas Hulsing, Joost Rijneveld, and Peter Schwabe. MQDSS. Technical Report, National Institute of Standards and Technology, 2019.
Google Scholar ePrint
[VGO+20]
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C J Carey, İlhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261–272, 2020. https://doi.org/10.1038/s41592-019-0686-2.
Google Scholar ePrint
[YDH+15]
Takanori Yasuda, Xavier Dahan, Yun-Ju Huang, Tsuyoshi Takagi, and Kouichi Sakurai. A multivariate quadratic challenge toward post-quantum generation cryptography. ACM Commun. Comput. Algebra, 49(3):105–107, 2015. https://doi.org/10.1145/2850449.2850462.
Google Scholar ePrint

PDFPDF Open access

DOI: https://doi.org/10.62056/aemp-4c2h
History
Submitted: 2024-01-09
Accepted: 2024-03-05
Published: 2024-04-09
How to cite

Charles Bouillaguet and Julia Sauvage, "Preliminary Cryptanalysis of the Biscuit Signature Scheme," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/aemp-4c2h.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.