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
Version: This is version 2020.10.30 of the "Papers" web page.