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." https://eprint.iacr.org/2024/393

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

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. https://eprint.iacr.org/2023/1577

2023.06.15: Daniel J. Bernstein, Tung Chou. "CryptAttackTester: high-assurance attack analysis." (Original name: "CryptAttackTester: formalizing attack analyses.") https://eprint.iacr.org/2023/940

2023.06.15: Naoto Kimura, Atsushi Takayasu, Tsuyoshi Takagi. "Memory-efficient quantum information set decoding algorithm." ACISP 2023. https://link.springer.com/chapter/10.1007/978-3-031-35486-1_20

2023.03.24: Yu Li, Li-Ping Wang. "Security analysis of the Classic McEliece, HQC and BIKE schemes in low memory." https://eprint.iacr.org/2023/428

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. https://www.jstage.jst.go.jp/article/transfun/advpub/0/advpub_2022CIP0023/_pdf

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." https://eprint.iacr.org/2023/247

2022.12.28: Asuka Wakasugi, Mitsuru Tada. "Security analysis for BIKE, Classic McEliece and HQC against the quantum ISD algorithms." https://eprint.iacr.org/2022/1771

2022.10.06: Andre Esser, Floyd Zweydinger. "New time-memory trade-offs for subset sum – Improving ISD in theory and practice." Eurocrypt 2023. https://eprint.iacr.org/2022/1329

2022.10.06: Andre Esser. "Revisiting nearest-neighbor-based information set decoding." https://eprint.iacr.org/2022/1328

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

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. https://eprint.iacr.org/2022/964

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. https://eprint.iacr.org/2021/1634

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." https://eprint.iacr.org/2021/1608

2021.09.20: Andre Esser, Emanuele Bellini. "Syndrome decoding estimator." PKC 2022. https://eprint.iacr.org/2021/1243

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. https://eprint.iacr.org/2020/869

2019.07.12: decodingchallenge.org is online

2018.08.02: Elena Kirshanova. "Improved quantum information set decoding." PQCrypto 2018. https://arxiv.org/abs/1808.00714v1

2017.11.27: Leif Both, Alexander May. "Decoding linear codes with high error rate and its impact for LPN security." PQCrypto 2018. https://eprint.iacr.org/2017/1139

2017.09.18?: Leif Both, Alexander May. "Optimizing BJMM with nearest neighbors: full decoding in 2^{2n/21} and McEliece security." WCC 2017. https://www.cits.ruhr-uni-bochum.de/imperia/md/content/may/paper/bjmm+.pdf

2017.03.01: Ghazal Kachigar, Jean-Pierre Tillich. "Quantum information set decoding algorithms." PQCrypto 2017. https://arxiv.org/abs/1703.00263

2016.03.15: Rodolfo Canto Torres, Nicolas Sendrier. "Analysis of information set decoding for a sub-linear error weight." PQCrypto 2016. https://hal.inria.fr/hal-01244886v1/document

2015.04.26?: Alexander May, Ilya Ozerov. "On computing nearest neighbors with applications to decoding of binary linear codes." Eurocrypt 2015. https://www.cits.ruhr-uni-bochum.de/imperia/md/content/may/paper/codes.pdf

2013.03.26: Yann Hamdaoui, Nicolas Sendrier. "A non asymptotic analysis of information set decoding." 2013. https://eprint.iacr.org/2013/162

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. https://www.cits.ruhr-uni-bochum.de/imperia/md/content/may/paper/isd-extended.pdf

2011.12.04?: Alexander May, Alexander Meurer, Enrico Thomae. "Decoding random linear codes in O(2^0.054n)." Asiacrypt 2011. https://www.cits.ruhr-uni-bochum.de/imperia/md/content/may/paper/decoding.pdf

2011.07.10: Nicolas Sendrier. "Decoding one out of many." PQCrypto 2011. https://eprint.iacr.org/2011/367

2010.11.18: Daniel J. Bernstein, Tanja Lange, Christiane Peters. "Smaller decoding exponents: ball-collision decoding." Crypto 2011. https://eprint.iacr.org/2010/585

2009.11.23: Daniel J. Bernstein. "Grover vs. McEliece." PQCrypto 2010. https://cr.yp.to/papers.html#grovercode

2009.09.01: Matthieu Finiasz, Nicolas Sendrier. "Security bounds for the design of code-based cryptosystems." Asiacrypt 2009. https://eprint.iacr.org/2009/414

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. https://research.tue.nl/en/publications/curves-codes-and-cryptography (chapter 5)

2008.10.20: Original parameters from 1978 (designed for 2⁶⁴ security) broken

2008.08.02: Daniel J. Bernstein, Tanja Lange, Christiane Peters. "Attacking and defending the McEliece cryptosystem." PQCrypto 2008. https://eprint.iacr.org/2008/318

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. https://www.rocq.inria.fr/secret/Anne.Canteaut/Publications/Canteaut_Sendrier98.pdf

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. https://www.rocq.inria.fr/secret/Anne.Canteaut/Publications/Canteaut_Chabaud98.pdf

1994: Anne Canteuat, Herve Chabanne. "A further improvement of the work factor in an attempt at breaking McEliece's cryptosystem." EUROCODE 1994. https://hal.inria.fr/inria-00074443

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. http://www.mathnet.ru/eng/ppi635

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. http://www.mathnet.ru/eng/ppi665

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.