A Security Analysis of Restricted Syndrome Decoding Problems
Authors
Ward Beullens, Pierre Briaud, Morten Øygarden
Ward Beullens
IBM Research Europe, Zürich, Switzerland
wbe at zurich dot ibm dot com
wbe at zurich dot ibm dot com
Pierre Briaud
Simula UiB, Bergen, Norway
pierre at simula dot no
pierre at simula dot no
Morten Øygarden
Simula UiB, Bergen, Norway
morten dot oygarden at simula dot no
morten dot oygarden at simula dot no
Abstract
Restricted syndrome decoding problems (R-SDP and R-SDP($G$)) provide an interesting basis for post-quantum cryptography. Indeed, they feature in CROSS, a submission in the ongoing process for standardizing post-quantum signatures.
This work improves our understanding of the security of both problems. Firstly, we propose and implement a novel collision attack on R-SDP($G$) that provides the best attack under realistic restrictions on memory. Secondly, we derive precise complexity estimates for algebraic attacks on R-SDP that are shown to be accurate by our experiments. We note that neither of these improvements threatens the updated parameters of CROSS.
References
[AAC+22]
Gorjan Alagic, Daniel Apon, David Cooper, Quynh Dang, Thinh Dang, John Kelsey, Jacob Lichtinger, Yi-Kai Liu, Carl Miller, Dustin Moody, Rene Peralta, Ray Perlner, Angela Robinson, and Daniel Smith-Tone. Status report on the third round of the NIST post-quantum cryptography standardization process. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) 8413.. 2022.
[Art10]
Michael Artin. Algebra. Pearson Education 2010. Second Edition
[Bar04]
Magali Bardet. Étude des systèmes algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie. PhD thesis, Université Paris VI, December 2004.
[BBB+23]
Marco Baldi, Alessandro Barenghi, Sebastian Bitzer, Patrick Karl, Felice Manganiello, Alessio Pavoni, Gerardo Pelosi, Paolo Santini, Jonas Schupp, Freeman Slaughter, Antonia Wachter-Zeh, and Violetta Weger. CROSS: Codes and Restricted Objects Signature Scheme. Submission to the NIST Post-Quantum Cryptography Standardization Project. 2023.
[BBC+20]
Marco Baldi, Massimo Battaglioni, Franco Chiaraluce, Anna-Lena Horlemann-Trautmann, Edoardo Persichetti, Paolo Santini, and Violetta Weger. A New Path to Code-based Signatures via Identification Schemes with Restricted Errors. CoRR, 2020. DOI: 10.48550/arXiv.2008.06403
[BBP+24]
Marco Baldi, Sebastian Bitzer, Alessio Pavoni, Paolo Santini, Antonia Wachter-Zeh, and Violetta Weger. Zero Knowledge Protocols and Signatures from the Restricted Syndrome Decoding Problem. In IACR International Conference on Public-Key Cryptography, pages 243–274. 2024. Springer. DOI: 10.1007/978-3-031-57722-2_8
[BCP97]
Wieb Bosma, John Cannon, and Catherine Playoust. The Magma algebra system. I. The user language. J. Symbolic Comput., 24(3-4):235–265, 1997. Computational algebra and number theory (London, 1993) DOI: 10.1006/jsco.1996.0125
[Bet12]
Luk Bettale. Cryptanalyse algébrique : outils et applications. PhD thesis, Université Pierre et Marie Curie - Paris 6, 2012.
[BFP09]
Luk Bettale, Jean-Charles Faugère, and Ludovic Perret. Hybrid approach for solving multivariate systems over finite fields. Journal of Mathematical Cryptology, 3(3):177–197, 2009. DOI: 10.1515/JMC.2009.009
[BFS05]
Magali Bardet, Jean-Charles Faugère, and Bruno Salvy. Asymptotic Behaviour of the Index of Regularity of Semi-Regular Quadratic Polynomial Systems. In MEGA 2005, pages 1-17. May 2005.
[B{\O }23]
Pierre Briaud and Morten Øygarden. A New Algebraic Approach to the Regular Syndrome Decoding Problem and Implications for PCG Constructions. In EUROCRYPT 2023, pages 391–422. 2023. Springer. DOI: 10.1007/978-3-031-30589-4_14
[BS24]
Charles Bouillaguet and Julia Sauvage. Preliminary Cryptanalysis of the Biscuit Signature Scheme. IACR Communications in Cryptology, April 2024. DOI: 10.62056/aemp-4c2h
[CG23]
Alessio Caminata and Elisa Gorla. Solving degree, last fall degree, and related invariants. Journal of Symbolic Computation, 114:322–335, 2023. DOI: 10.1016/j.jsc.2022.05.001
[CLO13]
David Cox, John Little, and Donal O'Shea. Ideals, Varieties, and Algorithms: an Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer Science & Business Media 2013.
[CMT23]
Alain Couvreur, Rocco Mora, and Jean-Pierre Tillich. A new approach based on quadratic forms to attack the McEliece cryptosystem. In ASIACRYPT 2023, Guangzhou, China. December 2023. Springer. DOI: 10.1007/978-981-99-8730-6_1 68 pages (Long version)
[CVE10]
Pierre-Louis Cayrel, Pascal Véron, and Sidi Mohamed El Yousfi Alaoui. A Zero-Knowledge Identification Scheme Based on the q-ary Syndrome Decoding Problem. In Selected Areas in Cryptography, pages 171-186, Waterloo, Canada. August 2010. Springer. DOI: 10.1007/978-3-642-19574-7_12
[Dum91]
Ilya Dumer. On minimum distance decoding of linear codes. In Proc. 5th Joint Soviet-Swedish Int. Workshop Inform. Theory, pages 50–52, Moscow. 1991.
[Fau99]
Jean-Charles Faugère. A new efficient algorithm for computing Gröbner bases (F$_4$). Journal of pure and applied algebra, 139(1-3):61–88, 1999. DOI: 10.1016/S0022-4049(99)00005-5
[Fau02]
Jean-Charles Faugère. A new efficient algorithm for computing Gröbner bases without reduction to zero (F$_5$). In Proceedings of the 2002 international symposium on Symbolic and algebraic computation, pages 75–83. 2002. DOI: 10.1145/780506.780516
[FS86]
Amos Fiat and Adi Shamir. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In CRYPTO 1986, pages 186–194. 1986. Springer. DOI: 10.1007/3-540-47721-7_12
[Ste89]
Jacques Stern. A method for finding codewords of small weight. In Gérard Cohen and Jacques Wolfmann, editors, Coding Theory and Applications, pages 106–113, Berlin, Heidelberg. 1989. Springer Berlin Heidelberg. DOI: 10.1007/BFb0019850
[vW99]
Paul C. van Oorschot and Michael J. Wiener. Parallel collision search with cryptanalytic applications. Journal of Cryptology, 12:1–28, 1999. DOI: 10.1007/PL00003816
PDF
History
Submitted: 2024-07-08
Accepted: 2024-09-02
Published: 2024-10-07
Accepted: 2024-09-02
Published: 2024-10-07
How to cite
Ward Beullens, Pierre Briaud, and Morten Øygarden, A Security Analysis of Restricted Syndrome Decoding Problems. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/a06cy7qiu.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.