Classic McEliece: Papers

Information-set decoding

The most important attack strategy against the one-wayness of the original McEliece cryptosystem is information-set decoding (ISD), which was introduced by Prange in 1962 and studied in the following papers:

Qian Guo, Thomas Johansson, Vu Nguyen. "A new sieving-style information-set decoding algorithm." https://eprint.iacr.org/2023/247
Asuka Wakasugi, Mitsuru Tada. "Security analysis for BIKE, Classic McEliece and HQC against the quantum ISD algorithms." https://eprint.iacr.org/2022/1771
Andre Esser, Floyd Zweydinger. "New time-memory trade-offs for subset sum – Improving ISD in theory and practice." https://eprint.iacr.org/2022/1329
Andre Esser. "Revisiting nearest-neighbor-based information set decoding." https://eprint.iacr.org/2022/1328
Andre Esser, Sergi Ramos-Calderer, Emanuele Bellini, José Ignacio Latorre, Marc Manzano. "Hybrid decoding – classical-quantum trade-offs for information set decoding." https://eprint.iacr.org/2022/964
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
Andre Esser, Emanuele Bellini. "Syndrome decoding estimator." PKC 2022. https://eprint.iacr.org/2021/1243
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
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
Elena Kirshanova. "Improved quantum information set decoding." PQCrypto 2018. https://arxiv.org/abs/1808.00714v1
Ghazal Kachigar, Jean-Pierre Tillich. "Quantum information set decoding algorithms." PQCrypto 2017. https://arxiv.org/abs/1703.00263
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
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
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
Yann Hamdaoui, Nicolas Sendrier. "A non asymptotic analysis of information set decoding." 2013. https://eprint.iacr.org/2013/162
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
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
Daniel J. Bernstein, Tanja Lange, Christiane Peters. "Smaller decoding exponents: ball-collision decoding." Crypto 2011. https://eprint.iacr.org/2010/585
Nicolas Sendrier. "Decoding one out of many." PQCrypto 2011. https://eprint.iacr.org/2011/367
Daniel J. Bernstein. "Grover vs. McEliece." PQCrypto 2010. https://cr.yp.to/papers.html#grovercode
Matthieu Finiasz, Nicolas Sendrier. "Security bounds for the design of code-based cryptosystems." Asiacrypt 2009. https://eprint.iacr.org/2009/414
Daniel J. Bernstein, Tanja Lange, Christiane Peters, Henk C. A. van Tilborg. "Explicit bounds for generic decoding algorithms for code-based cryptography." WCC 2009.
Daniel J. Bernstein, Tanja Lange, Christiane Peters. "Attacking and defending the McEliece cryptosystem." PQCrypto 2008. https://eprint.iacr.org/2008/318
Thomas Johansson, Fredrik Jönsson. "On the complexity of some cryptographic problems based on the general decoding problem." IEEE Transactions on Information Theory. 2002.
Anne Canteaut, Nicolas Sendrier. "Cryptanalysis of the original McEliece cryptosystem." Asiacrypt 1998. https://www.rocq.inria.fr/secret/Anne.Canteaut/Publications/Canteaut_Sendrier98.pdf
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
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
Johan van Tilburg. "Security-analysis of a class of cryptosystems based on linear error-correcting codes." PhD thesis, Technische Universiteit Eindhoven. 1994.
Florent Chabaud. "Asymptotic analysis of probabilistic algorithms for finding short codewords." EUROCODE 1992, published 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.
John T. Coffey, Rodney M. Goodman, P. Farrell. "New approaches to reduced complexity decoding." Discrete and Applied Mathematics. 1991.
Ilya I. Dumer. "On minimum distance decoding of linear codes." Fifth joint Soviet-Swedish international workshop on information theory. 1991.
Johan van Tilburg. "On the McEliece public-key cryptosystem." Crypto 1988, published 1990.
John T. Coffey, Rodney M. Goodman. "The complexity of information set decoding." IEEE Transactions on Information Theory. 1990.
Ilya I. Dumer. "Two decoding algorithms for linear codes." Problemy Peredachi Informatsii. 1989. http://www.mathnet.ru/eng/ppi635
Jacques Stern. "A method for finding codewords of small weight." Coding Theory and Applications. 1989.
Evgueni A. Krouk. "Decoding complexity bound for linear block codes." Problemy Peredachi Informatsii. 1989. http://www.mathnet.ru/eng/ppi665
Jeffrey S. Leon. "A probabilistic algorithm for computing minimum weights of large error-correcting codes." IEEE Transactions on Information Theory. 1988.
Pil Joong Lee, Ernest F. Brickell. "An observation on the security of McEliece's public-key cryptosystem." Eurocrypt 1988.
Ilya I. Dumer. "On syndrome decoding of linear codes." Proceedings of the 9th All-Union Symposium on Redundancy in Information Systems. 1986.
George C. Clark, Jr., and J. Bibb Cain. "Error-correcting coding for digital communication." 1981. Credits Omura for an ISD attack.
Eugene Prange. "The use of information sets in decoding cyclic codes." IRE Transactions on Information Theory. 1962.

Other attack strategies

The following papers study other ideas for attacking the one-wayness of the McEliece cryptosystem. Attack ideas that do not work against the cryptosystem are often presented as attacks against other cryptosystems.

Kevin Carrier, Thomas Debris-Alazard, Charles Meyer-Hilfiger, Jean-Pierre Tillich. "Statistical decoding 2.0: reducing decoding to LPN." 2022. https://arxiv.org/abs/2208.02201
Elena Kirshanova, Alexander May. "Decoding McEliece with a hint—secret Goppa key parts reveal everything." SCN 2022. https://eprint.iacr.org/2022/525
Anna-Lena Horlemann, Sven Puchinger, Julian Renner, Thomas Schamberger, Antonia Wachter-Zeh. "Information-set decoding with hints." Code-Based Cryptography 2021. https://eprint.iacr.org/2021/279
Thomas Debris-Alazard, Jean-Pierre Tillich. "Statistical decoding." 2017. https://arxiv.org/abs/1701.07416
Robert Niebuhr. "Statistical decoding of codes over Fq." PQCrypto 2011.
Jean-Charles Faugère, Valérie Gauthier, Ayoub Otmani, Ludovic Perret, Jean-Pierre Tillich. "A distinguisher for high rate McEliece cryptosystems." IEEE Transactions on Information Theory. 2010. https://eprint.iacr.org/2010/331
Christian Wieschebrink. "Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes." PQCrypto 2010.
Valerie Gauthier Umana, Gregor Leander. "Practical key recovery attacks on two McEliece variants." SCC 2010.
Jean-Charles Faugère, Ayoub Otmani, Ludovic Perret, Jean-Pierre Tillich. "Algebraic cryptanalysis of McEliece variants with compact keys." Eurocrypt 2010.
Marc P. C. Fossorier, Kazukuni Kobara, Hideki Imai. "Modeling bit flipping decoding based on nonorthogonal check sums with application to iterative decoding attack of McEliece cryptosystem." IEEE Transactions on Information Theory. 2007.
Raphael Overbeck. "Recognizing the structure of permuted reducible codes." WCC 2007.
Christian Wieschebrink. "An attack on a modified Niederreiter encryption scheme." PKC 2006.
Raphael Overbeck. "Statistical decoding revisited." ACISP 2006.
Pierre Loidreau, Nicolas Sendrier. "Weak keys in McEliece public-key cryptosystem." IEEE Transactions on Information Theory. 2001.
A. Al Jabri. "A statistical decoding algorithm for general linear block codes." Cirencester 2001.
Nicolas Sendrier. "Finding the permutation between equivalent linear codes: The support splitting algorithm." IEEE Transactions on Information Theory. 2000.
Vladimir M. Sidelnikov, Sergey O. Shestakov. "On insecurity of cryptosystems based on generalized Reed-Solomon codes." Discrete Mathematics and Applications. 1992.
J. Keith Gibson. "Equivalent Goppa codes and trapdoors to McEliece's public key cryptosystem." Eurocrypt 1991.

Chosen-ciphertext attacks

Classic McEliece uses a transformation designed to convert a deterministic perfectly correct one-way PKE scheme into a perfectly correct KEM that resists chosen-ciphertext attacks. The following papers study the necessity and sufficiency of this transformation:

Nina Bindel, Mike Hamburg, Kathrin Hövelmanns, Andreas Hülsing, Edoardo Persichetti. "Tighter proofs of CCA security in the quantum random oracle model." TCC 2019. https://eprint.iacr.org/2019/590
Daniel J. Bernstein, Edoardo Persichetti. "Towards KEM unification." 2018. https://cr.yp.to/papers.html#tightkem
Tsunekazu Saito, Keita Xagawa, Takashi Yamakawa. "Tightly-secure key-encapsulation mechanism in the quantum random oracle model." Eurocrypt 2018. https://eprint.iacr.org/2017/1005
Dennis Hofheinz, Kathrin Hövelmanns, Eike Kiltz. "A modular analysis of the Fujisaki-Okamoto transformation." TCC 2017. https://eprint.iacr.org/2017/604
Alexander W. Dent. "A designer's guide to KEMs." Cirencester 2003. https://eprint.iacr.org/2002/174
Eric R. Verheul, Jeroen M. Doumen, Henk C. A. van Tilborg. "Sloppy Alice attacks! Adaptive chosen ciphertext attacks on the McEliece public-key cryptosystem." Information, coding and mathematics. 2002.
Chris Hall, Ian Goldberg, Bruce Schneier. "Reaction attacks against several public-key cryptosystems." ICICS 1999.

Further papers

Brice Colombier, Vincent Grosso, Pierre-Louis Cayrel, Vlad-Florin Drăgoi. "Horizontal correlation attack on Classic McEliece." https://eprint.iacr.org/2023/546
Vincent Grosso, Pierre-Louis Cayrel, Brice Colombier, Vlad-Florin Dragoi. "Punctured syndrome decoding problem: Efficient side-channel attacks against Classic McEliece." https://eprint.iacr.org/2023/308
Yihong Zhu, Wenping Zhu, Chen Chen, Min Zhu, Zhengdong Li, Shaojun Wei, Leibo Liu. "Compact GF(2) systemizer and optimized constant-time hardware sorters for Key Generation in Classic McEliece." https://eprint.iacr.org/2022/1277
Tobias Hemmert, Alexander May, Johannes Mittmann, Carl Richard Theodor Schneider. "How to backdoor (Classic) McEliece and how to guard against backdoors." PQCrypto 2022. https://eprint.iacr.org/2022/362
Qian Guo, Andreas Johansson, Thomas Johansson. "A key-recovery side-channel attack on Classic McEliece implementations." CHES 2022. https://doi.org/10.46586/tches.v2022.i4.800-827
Daniel J. Bernstein. "Understanding binary-Goppa decoding." 2022. https://cr.yp.to/papers.html#goppadecoding
Po-Jen Chen, Tung Chou, Sanjay Deshpande, Norman Lahr, Ruben Niederhagen, Jakub Szefer, Wen Wang. "Complete and improved FPGA implementation of Classic McEliece." CHES 2022. https://doi.org/10.46586/tches.v2022.i3.71-113
Ming-Shing Chen, Tung Chou. "Classic McEliece on the ARM Cortex-M4." CHES 2021. https://doi.org/10.46586/tches.v2021.i3.125-148
Pierre-Louis Cayrel, Brice Colombier, Vlad-Florin Dragoi, Alexandre Menu, Lilian Bossuet. "Message-recovery laser fault injection attack on the Classic McEliece cryptosystem." EUROCRYPT 2021. https://eprint.iacr.org/2020/900
Johannes Roth, Evangelos G. Karatsiolis, Juliane Krämer. "Classic McEliece implementation with low memory footprint." CARDIS 2020. https://eprint.iacr.org/2021/138
Daniel J. Bernstein. "Verified fast formulas for control bits for permutation networks." 2020. https://cr.yp.to/papers.html#controlbits
Andreas Hülsing, Kai-Chun Ning, Peter Schwabe, Florian Weber, Philip R. Zimmermann. "Post-quantum WireGuard." IEEE S&P 2021. https://eprint.iacr.org/2020/379
Norman Lahr, Ruben Niederhagen, Richard Petri, Simona Samardjiska. "Side channel information set decoding using iterative chunking." Asiacrypt 2020. https://eprint.iacr.org/2019/1459
Daniel J. Bernstein, Tanja Lange. "McTiny: fast high-confidence post-quantum key erasure for tiny network servers." USENIX Security 2020. https://mctiny.org
Wen Wang, Jakub Szefer, Ruben Niederhagen. "FPGA-based Niederreiter cryptosystem using binary Goppa codes." PQCrypto 2018. https://eprint.iacr.org/2017/1180
Tung Chou. "McBits revisited." CHES 2017. https://tungchou.github.io/papers/mcbits_revisited.pdf
Cong Chen, Thomas Eisenbarth, Ingo von Maurich, Rainer Steinwandt. "Masking large keys in hardware: a masked implementation of McEliece." SAC 2015. https://eprint.iacr.org/2015/924
Daniel J. Bernstein, Tung Chou, Peter Schwabe. "McBits: fast constant-time code-based cryptography." CHES 2013. https://tungchou.github.io/papers/mcbits.pdf
Roberto M. Avanzi, Simon Hoerder, Dan Page, Michael Tunstall. "Side-channel attacks on the McEliece and Niederreiter public-key cryptosystems." Journal of Cryptographic Engineering. 2011. https://eprint.iacr.org/2010/479
Falko Strenzke. "A timing attack against the secret permutation in the McEliece PKC." PQCrypto 2010.
Stefan Heyse. "Low-Reiter: Niederreiter encryption scheme for embedded microcontrollers." PQCrypto 2010.
Thomas Eisenbarth, Tim Güneysu, Stefan Heyse, Christof Paar. "MicroEliece: McEliece for embedded devices." CHES 2009.
Raphael Overbeck, Nicolas Sendrier. "Code-based cryptography." Post-Quantum Cryptography. 2009.
Falko Strenzke, Erik Tews, H. Gregor Molter, Raphael Overbeck, Abdulhadi Shoufan. "Side channels in the McEliece PKC." PQCrypto 2008.
Bhaskar Biswas, Nicolas Sendrier. "McEliece cryptosystem implementation: theory and practice." PQCrypto 2008.
Daniela Engelbert, Raphael Overbeck, Arthur Schmidt. "A summary of McEliece-type cryptosystems and their security." Journal of Mathematical Cryptology. 2007. https://eprint.iacr.org/2006/162
Harald Niederreiter. "Knapsack-type cryptosystems and algebraic coding theory." Problems of Control and Information Theory. 1986.
Robert J. McEliece. "A public-key cryptosystem based on algebraic coding theory." 1978. https://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF

Version: This is version 2023.04.18 of the "Papers" web page.