A Security Analysis of Restricted Syndrome Decoding Problems

Ward Beullens; Pierre Briaud; Morten Øygarden

doi:10.62056/a06cy7qiu

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

Pierre Briaud

Simula UiB, Bergen, Norway
pierre at simula dot no

Morten Øygarden

Simula UiB, Bergen, Norway
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.

Google Scholar ePrint

[Art10]

Michael Artin. Algebra. Pearson Education 2010. Second Edition

Google Scholar ePrint

[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.

Google Scholar ePrint

[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.

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[Bet12]

Luk Bettale. Cryptanalyse algébrique : outils et applications. PhD thesis, Université Pierre et Marie Curie - Paris 6, 2012.

Google Scholar ePrint

[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

Google Scholar ePrint

[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.

Google Scholar ePrint

[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

Google Scholar ePrint

[BS24]

Charles Bouillaguet and Julia Sauvage. Preliminary Cryptanalysis of the Biscuit Signature Scheme. IACR Communications in Cryptology, April 2024. DOI: 10.62056/aemp-4c2h

Google Scholar ePrint

[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

Google Scholar ePrint

[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.

Google Scholar ePrint

[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)

Google Scholar ePrint

[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

Google Scholar ePrint

[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.

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a06cy7qiu

History

Submitted: 2024-07-08
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.