Information-set decoding

2024.03.04: Shintaro Narisada, Shusaku Uemura, Hiroki Okada, Hiroki Furue, Yusuke Aikawa, Kazuhide Fukushima. "Revisiting the May–Meurer–Thomae algorithm — solving McEliece-1409 in one day."

2023.12.22: Sreyosi Bhattacharyya, Palash Sarkar. "Concrete time/memory trade-offs in generalised Stern's ISD algorithm." Indocrypt 2023.

2023.11.13: Length-1409 challenge solved

2023.10.12: Léo Ducas, Andre Esser, Simona Etinski, Elena Kirshanova. "Asymptotics and improvements of sieving for codes." Eurocrypt 2024.

2023.06.15: Daniel J. Bernstein, Tung Chou. "CryptAttackTester: high-assurance attack analysis." (Original name: "CryptAttackTester: formalizing attack analyses.")

2023.06.15: Naoto Kimura, Atsushi Takayasu, Tsuyoshi Takagi. "Memory-efficient quantum information set decoding algorithm." ACISP 2023.

2023.03.24: Yu Li, Li-Ping Wang. "Security analysis of the Classic McEliece, HQC and BIKE schemes in low memory."

2023.03.01: Shintaro Narisada, Kazuhide Fukushima, Shinsaku Kiyomoto. "Multiparallel MMT: faster ISD algorithm solving high-dimensional syndrome decoding problem." IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences.

2023.02.26: Solving the length-1347 McEliece challenge (with the PQCrypto 2008 software)

2023.02.21: Qian Guo, Thomas Johansson, Vu Nguyen. "A new sieving-style information-set decoding algorithm."

2022.12.28: Asuka Wakasugi, Mitsuru Tada. "Security analysis for BIKE, Classic McEliece and HQC against the quantum ISD algorithms."

2022.10.06: Andre Esser, Floyd Zweydinger. "New time-memory trade-offs for subset sum – Improving ISD in theory and practice." Eurocrypt 2023.

2022.10.06: Andre Esser. "Revisiting nearest-neighbor-based information set decoding."

2022.08.03: Kevin Carrier, Thomas Debris-Alazard, Charles Meyer-Hilfiger, Jean-Pierre Tillich. "Statistical decoding 2.0: reducing decoding to LPN." Asiacrypt 2022.

2022.07.26: Andre Esser, Sergi Ramos-Calderer, Emanuele Bellini, José Ignacio Latorre, Marc Manzano. "Hybrid decoding – classical-quantum trade-offs for information set decoding." PQCrypto 2022.

2022.07.04: Systematic experiments

2022.06.16: Comparing the PQCrypto 2008 ISD software to the Eurocrypt 2022 ISD software

2021.12.17: Andre Esser, Alexander May, Floyd Zweydinger. "McEliece needs a break—solving McEliece-1284 and Quasi-Cyclic-2918 with modern ISD." Eurocrypt 2022.

2021.12.09: Andre Esser, Sergi Ramos-Calderer, Emanuele Bellini, José I. Latorre, Marc Manzano. "An optimized quantum implementation of ISD on scalable quantum resources."

2021.09.20: Andre Esser, Emanuele Bellini. "Syndrome decoding estimator." PKC 2022.

2020.07.12: Thomas Debris-Alazard, Léo Ducas, Wessel P. J. van Woerden. "An algorithmic reduction theory for binary codes: LLL and more." IEEE Transactions on Information Theory. 2022.

2019.07.12: is online

2018.08.02: Elena Kirshanova. "Improved quantum information set decoding." PQCrypto 2018.

2017.11.27: Leif Both, Alexander May. "Decoding linear codes with high error rate and its impact for LPN security." PQCrypto 2018.

2017.09.18?: Leif Both, Alexander May. "Optimizing BJMM with nearest neighbors: full decoding in 2^{2n/21} and McEliece security." WCC 2017.

2017.03.01: Ghazal Kachigar, Jean-Pierre Tillich. "Quantum information set decoding algorithms." PQCrypto 2017.

2016.03.15: Rodolfo Canto Torres, Nicolas Sendrier. "Analysis of information set decoding for a sub-linear error weight." PQCrypto 2016.

2015.04.26?: Alexander May, Ilya Ozerov. "On computing nearest neighbors with applications to decoding of binary linear codes." Eurocrypt 2015.

2013.03.26: Yann Hamdaoui, Nicolas Sendrier. "A non asymptotic analysis of information set decoding." 2013.

2012.04.15?: Anja Becker, Antoine Joux, Alexander May, Alexander Meurer. "Decoding random binary linear codes in 2^{n/20}: How 1+1=0 improves information set decoding." Eurocrypt 2012.

2011.12.04?: Alexander May, Alexander Meurer, Enrico Thomae. "Decoding random linear codes in O(2^0.054n)." Asiacrypt 2011.

2011.07.10: Nicolas Sendrier. "Decoding one out of many." PQCrypto 2011.

2010.11.18: Daniel J. Bernstein, Tanja Lange, Christiane Peters. "Smaller decoding exponents: ball-collision decoding." Crypto 2011.

2009.11.23: Daniel J. Bernstein. "Grover vs. McEliece." PQCrypto 2010.

2009.09.01: Matthieu Finiasz, Nicolas Sendrier. "Security bounds for the design of code-based cryptosystems." Asiacrypt 2009.

2009.05.10?: Daniel J. Bernstein, Tanja Lange, Christiane Peters, Henk C. A. van Tilborg. "Explicit bounds for generic decoding algorithms for code-based cryptography." WCC 2009. (chapter 5)

2008.10.20: Original parameters from 1978 (designed for 264 security) broken

2008.08.02: Daniel J. Bernstein, Tanja Lange, Christiane Peters. "Attacking and defending the McEliece cryptosystem." PQCrypto 2008.

2002: Thomas Johansson, Fredrik Jönsson. "On the complexity of some cryptographic problems based on the general decoding problem." IEEE Transactions on Information Theory. 2002.

1998: Anne Canteaut, Nicolas Sendrier. "Cryptanalysis of the original McEliece cryptosystem." Asiacrypt 1998.

1998: Anne Canteaut, Florent Chabaud. "A new algorithm for finding minimum-weight words in a linear code: application to McEliece's cryptosystem and to narrow-sense BCH codes of length 511." IEEE Transactions on Information Theory. 1998.

1994: Anne Canteuat, Herve Chabanne. "A further improvement of the work factor in an attempt at breaking McEliece's cryptosystem." EUROCODE 1994.

1994: Johan van Tilburg. "Security-analysis of a class of cryptosystems based on linear error-correcting codes." PhD thesis, Technische Universiteit Eindhoven. 1994.

1993: Herve Chabanne, Bernard Courteau. "Application de la méthode de décodage itérative d'Omura à la cryptanalyse du système de McEliece." 1993.

1992: Florent Chabaud. "Asymptotic analysis of probabilistic algorithms for finding short codewords." EUROCODE 1992, published 1993.

1991: John T. Coffey, Rodney M. Goodman, P. Farrell. "New approaches to reduced complexity decoding." Discrete and Applied Mathematics. 1991.

1991: Ilya I. Dumer. "On minimum distance decoding of linear codes." Fifth joint Soviet-Swedish international workshop on information theory. 1991.

1990: Johan van Tilburg. "On the McEliece public-key cryptosystem." Crypto 1988, published 1990.

1990: John T. Coffey, Rodney M. Goodman. "The complexity of information set decoding." IEEE Transactions on Information Theory. 1990.

1989: Ilya I. Dumer. "Two decoding algorithms for linear codes." Problemy Peredachi Informatsii. 1989.

1989: Jacques Stern. "A method for finding codewords of small weight." Coding Theory and Applications. 1989.

1989: Evgueni A. Krouk. "Decoding complexity bound for linear block codes." Problemy Peredachi Informatsii. 1989.

1988: Jeffrey S. Leon. "A probabilistic algorithm for computing minimum weights of large error-correcting codes." IEEE Transactions on Information Theory. 1988.

1988: Pil Joong Lee, Ernest F. Brickell. "An observation on the security of McEliece's public-key cryptosystem." Eurocrypt 1988.

1986: Ilya I. Dumer. "On syndrome decoding of linear codes." Proceedings of the 9th All-Union Symposium on Redundancy in Information Systems. 1986.

1981: George C. Clark, Jr., and J. Bibb Cain. "Error-correcting coding for digital communication." 1981. Credits Omura for an ISD attack.

1962: Eugene Prange. "The use of information sets in decoding cyclic codes." IRE Transactions on Information Theory.