The May-Ozerov Algorithm for Syndrome Decoding is “Galactic”

Charles Bouillaguet; Claire Delaplace; Mickaël Hamdad

doi:10.62056/akjbksuc2

The May-Ozerov Algorithm for Syndrome Decoding is “Galactic”

Authors

Charles Bouillaguet, Claire Delaplace, Mickaël Hamdad

Charles Bouillaguet

Sorbonne Université, CNRS, LIP6, Paris, France
charles dot bouillaguet at lip6 dot fr

Claire Delaplace

Laboratoire MIS, Université de Picardie Jules Verne, Amiens, France
claire dot delaplace at u-picardie dot fr

Mickaël Hamdad

Sorbonne Université, CNRS, LIP6, Paris, France
Laboratoire MIS, Université de Picardie Jules Verne, Amiens, France
mickael dot hamdad at lip6 dot fr

Keywords: Code-based Cryptography Decoding algorithm Concrete security

Abstract

In 2015, May and Ozerov proposed a new method to solve the Nearest Neighbor Problem. They also observed that it could be used as a subroutine in various Information Set Decoding (ISD) algorithms for arbitrary linear codes. This led to an asymptotic improvement in their complexity. However, the proposed improvement has been widely perceived as impractical because of the huge hidden factors in its asymptotic complexity. The main contribution of this article is to provide a sound foundation for this claim. We show that it is indeed “galactic”, namely that it only improves upon much simpler methods when instances are so large that they fill the whole universe.

More precisely, we argue that for the May-Ozerov ISD algorithm to require less operations than a technique based on the Stern ISD algorithm, the length of the code has to be greater than 1,874,400 with a number of operation beyond 2 to the power 63489, making it practically useless.

References

[AFS05]

Daniel Augot, Matthieu Finiasz, and Nicolas Sendrier. A Family of Fast Syndrome Based Cryptographic Hash Functions. In Ed Dawson and Serge Vaudenay, editors, Progress in Cryptology - Mycrypt 2005, First International Conference on Cryptology in Malaysia, Kuala Lumpur, Malaysia, September 28-30, 2005, Proceedings, volume 3715 of Lecture Notes in Computer Science, pages 64–83. 2005. Springer. DOI: 10.1007/11554868_6

Google Scholar ePrint

[BCL⁺17]

Daniel J. Bernstein, Tung Chou, Tanja Lange, Ingo von Maurich, Rafael Misoczki, Ruben Niederhagen, Edoardo Persichetti, Christiane Peters, Peter Schwabe, Nicolas Sendrier, Jakub Szefer, and Wen Wang. Classic McEliece. 2017.

Google Scholar ePrint

[BJMM12]

Anja Becker, Antoine Joux, Alexander May, and Alexander Meurer. Decoding Random Binary Linear Codes in $2^{n/20}$: How $1 + 1 = 0$ Improves Information Set Decoding. In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology - EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Proceedings, volume 7237 of Lecture Notes in Computer Science, pages 520–536. 2012. Springer. DOI: 10.1007/978-3-642-29011-4_31

Google Scholar ePrint

[BLP08]

Daniel J. Bernstein, Tanja Lange, and Christiane Peters. Attacking and Defending the McEliece Cryptosystem. In Johannes Buchmann and Jintai Ding, editors, Post-Quantum Cryptography, Second International Workshop, PQCrypto 2008, Cincinnati, OH, USA, October 17-19, 2008, Proceedings, volume 5299 of Lecture Notes in Computer Science, pages 31–46. 2008. Springer. DOI: 10.1007/978-3-540-88403-3_3

Google Scholar ePrint

[BLP11]

Daniel J. Bernstein, Tanja Lange, and Christiane Peters. Smaller Decoding Exponents: Ball-Collision Decoding. In Phillip Rogaway, editor, Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings, volume 6841 of Lecture Notes in Computer Science, pages 743–760. 2011. Springer. DOI: 10.1007/978-3-642-22792-9_42

Google Scholar ePrint

[BMVT78]

Elwyn Berlekamp, Robert McEliece, and Henk Van Tilborg. On the inherent intractability of certain coding problems (Corresp.). IEEE Transactions on Information Theory, 24(3):384–386, 1978. DOI: 10.1109/TIT.1978.1055873

Google Scholar ePrint

[CW90]

Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9(3):251-280, 1990. Computational algebraic complexity editorial DOI: https://doi.org/10.1016/S0747-7171(08)80013-2

Google Scholar ePrint

[Dub10]

Moshe Dubiner. Bucketing coding and information theory for the statistical high-dimensional nearest-neighbor problem. IEEE Transactions on Information Theory, 56(8):4166–4179, 2010. DOI: 10.1109/TIT.2010.2050814

Google Scholar ePrint

[EB22]

Andre Esser and Emanuele Bellini. Syndrome Decoding Estimator. In Goichiro Hanaoka, Junji Shikata, and Yohei Watanabe, editors, Public-Key Cryptography - PKC 2022 - 25th IACR International Conference on Practice and Theory of Public-Key Cryptography, Virtual Event, March 8-11, 2022, Proceedings, Part I, volume 13177 of Lecture Notes in Computer Science, pages 112–141. 2022. Springer. DOI: 10.1007/978-3-030-97121-2_5

Google Scholar ePrint

[EMZ22]

Andre Esser, Alexander May, and Floyd Zweydinger. McEliece Needs a Break - Solving McEliece-1284 and Quasi-Cyclic-2918 with Modern ISD. In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology - EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part III, volume 13277 of Lecture Notes in Computer Science, pages 433–457. 2022. Springer. DOI: 10.1007/978-3-031-07082-2_16

Google Scholar ePrint

[FJR22]

Thibauld Feneuil, Antoine Joux, and Matthieu Rivain. Syndrome Decoding in the Head: Shorter Signatures from Zero-Knowledge Proofs. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part II, volume 13508 of Lecture Notes in Computer Science, pages 541–572. 2022. Springer. DOI: 10.1007/978-3-031-15979-4_19

Google Scholar ePrint

[FS96]

Jean-Bernard Fischer and Jacques Stern. An Efficient Pseudo-Random Generator Provably as Secure as Syndrome Decoding. 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, pages 245–255. 1996. Springer. DOI: 10.1007/3-540-68339-9_22

Google Scholar ePrint

[IM98]

Piotr Indyk and Rajeev Motwani. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In Jeffrey Scott Vitter, editor, Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 604–613. 1998. ACM. DOI: 10.1145/276698.276876

Google Scholar ePrint

[KWZ95]

Richard M. Karp, Orli Waarts, and Geoffrey Zweig. The Bit Vector Intersection Problem (Preliminary Version). In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pages 621–630. 1995. IEEE Computer Society. DOI: 10.1109/SFCS.1995.492663

Google Scholar ePrint

[LB88]

Pil Joong Lee and Ernest F. Brickell. An Observation on the Security of McEliece's Public-Key Cryptosystem. In Christoph G. Günther, editor, Advances in Cryptology - EUROCRYPT '88, Workshop on the Theory and Application of of Cryptographic Techniques, Davos, Switzerland, May 25-27, 1988, Proceedings, volume 330 of Lecture Notes in Computer Science, pages 275–280. 1988. Springer. DOI: 10.1007/3-540-45961-8_25

Google Scholar ePrint

[LR13]

Richard J. Lipton and Kenneth W. Reagan. David Johnson: Galactic Algorithms. In People, Problems, and Proofs: Essays from Gödel's Lost Letter: 2010, pages 109–112. 2013. Springer. DOI: 10.1007/978-3-642-41422-0_20

Google Scholar ePrint

[McE78]

Robert J. McEliece. A Public-Key Cryptosystem Based On Algebraic Coding Theory. Deep Space Network Progress Report, 44:114-116, January 1978.

Google Scholar ePrint

[MGF⁺23]

Carlos Aguilar Melchor, Shay Gueron, Thibauld Feneuil, James Howe, Edoardo Persichetti, David Joseph, Nicolas Gama, Antoine Joux, Tovohery H. Randrianarisoa, Matthieu Rivain, and Dongze Yue. The Syndrome Decoding in the Head (SD-in-the-Head) Signature Scheme. May 2023.

Google Scholar ePrint

[MMT11]

Alexander May, Alexander Meurer, and Enrico Thomae. Decoding Random Linear Codes in $\widetilde{O}\left(2^{0.054 n}\right)$. In Dong Hoon Lee and Xiaoyun Wang, editors, Advances in Cryptology - ASIACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011. Proceedings, volume 7073 of Lecture Notes in Computer Science, pages 107–124. 2011. Springer. DOI: 10.1007/978-3-642-25385-0_6

Google Scholar ePrint

[MO15]

Alexander May and Ilya Ozerov. On Computing Nearest Neighbors with Applications to Decoding of Binary Linear Codes. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I, volume 9056 of Lecture Notes in Computer Science, pages 203–228. 2015. Springer. DOI: 10.1007/978-3-662-46800-5_9

Google Scholar ePrint

[NUO⁺24]

Shintaro Narisada, Shusaku Uemura, Hiroki Okada, Hiroki Furue, Yusuke Aikawa, and Kazuhide Fukushima. Solving McEliece-1409 in One Day - Cryptanalysis with the Improved BJMM Algorithm. In Nicky Mouha and Nick Nikiforakis, editors, Information Security - 27th International Conference, ISC 2024, Arlington, VA, USA, October 23-25, 2024, Proceedings, Part II, volume 15258 of Lecture Notes in Computer Science, pages 3–23. 2024. Springer. DOI: 10.1007/978-3-031-75764-8_1

Google Scholar ePrint

[Riv74]

Ronald L. Rivest. On the Optimality of Elia's Algorithm for Performing Best-Match Searches. In Jack L. Rosenfeld, editor, Information Processing, Proceedings of the 6th IFIP Congress 1974, Stockholm, Sweden, August 5-10, 1974, pages 678–681. 1974. North-Holland.

Google Scholar ePrint

[Ste88]

Jacques Stern. A method for finding codewords of small weight. In Gérard D. Cohen and Jacques Wolfmann, editors, Coding Theory and Applications, 3rd International Colloquium, Toulon, France, November 2-4, 1988, Proceedings, volume 388 of Lecture Notes in Computer Science, pages 106–113. 1988. Springer. DOI: 10.1007/BFb0019850

Google Scholar ePrint

[Ste93]

Jacques Stern. A New Identification Scheme Based on Syndrome Decoding. In Douglas R. Stinson, editor, Advances in Cryptology - CRYPTO '93, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22-26, 1993, Proceedings, volume 773 of Lecture Notes in Computer Science, pages 13–21. 1993. Springer. DOI: 10.1007/3-540-48329-2_2

Google Scholar ePrint

[Top01]

Flemming Topsøe. Bounds for entropy and divergence for distributions over a two-element set.. JIPAM. Journal of Inequalities in Pure and Applied Mathematics, 2(2):Paper No. 25, 13 p., 2001.

Google Scholar ePrint

[Wel71]

Terry A. Welch. Bounds on information retrieval efficiency in static file structures. Project MAC Report MAC-TR-88. June 1971.

Google Scholar ePrint

PDF Open access

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

History

Submitted: 2025-01-13
Accepted: 2025-03-11
Published: 2025-04-08

How to cite

Charles Bouillaguet, Claire Delaplace, and Mickaël Hamdad, The May-Ozerov Algorithm for Syndrome Decoding is “Galactic”. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/akjbksuc2.

License

Copyright is held by the author(s)

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

@article{10.62056/akjbksuc2,
         author={Charles Bouillaguet and Claire Delaplace and Mickaël Hamdad},
         title={The May-Ozerov Algorithm for Syndrome Decoding is “Galactic”},
         volume={2},
         number={1},
         year={2025},
         date={2025-04-08},
         issn={3006-5496},
         doi={10.62056/akjbksuc2},
         journal={{IACR} Communications in Cryptology},
         publisher={International Association for Cryptologic Research}
}

TY  - JOUR
AU  - Charles Bouillaguet
AU  - Claire Delaplace
AU  - Mickaël Hamdad
PY  - 2025
TI  - The May-Ozerov Algorithm for Syndrome Decoding is “Galactic”
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 2
IS  - 1
DO  - 10.62056/akjbksuc2
UR  - https://doi.org/10.62056/akjbksuc2
AB  - <p>  In 2015, May and Ozerov proposed a new method to solve the Nearest Neighbor   Problem. They also observed that it could be used as a subroutine in various   Information Set Decoding (ISD) algorithms for arbitrary linear codes. This led to an   asymptotic improvement in their complexity. However, the proposed improvement   has been widely perceived as impractical because of the huge hidden factors in   its asymptotic complexity. The main contribution of this article is to provide   a sound foundation for this claim. We show that it is indeed “galactic”,   namely that it only improves upon much simpler methods when instances are so   large that they fill the whole universe.</p><p>  More precisely, we argue that for the May-Ozerov ISD algorithm to require less   operations than a technique based on the Stern ISD algorithm, the length of   the code has to be greater than 1,874,400 with a number of   operation beyond 2 to the power 63489, making it practically useless. </p>
ER  -

Charles Bouillaguet, Claire Delaplace, and Mickaël Hamdad, The May-Ozerov Algorithm for Syndrome Decoding is “Galactic”. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/akjbksuc2.