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.