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:

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

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

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

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

• Raphael Overbeck. "Recognizing the structure of permuted reducible codes." WCC 2007.

• Christian Wieschebrink. "An attack on a modified Niederreiter encryption scheme." PKC 2006.

• Pierre Loidreau, Nicolas Sendrier. "Weak keys in McEliece public-key cryptosystem." IEEE Transactions on Information Theory. 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

• 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

• Daniel J. Bernstein, Tung Chou, Peter Schwabe. "McBits: fast constant-time code-based cryptography." CHES 2013. https://tungchou.github.io/papers/mcbits.pdf

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

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

• 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