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:

• Daniel J. Bernstein, Tung Chou. "CryptAttackTester: high-assurance attack analysis." Crypto 2024. https://eprint.iacr.org/2023/940 Original title: "CryptAttackTester: formalizing attack analyses."

• Shintaro Narisada, Shusaku Uemura, Hiroki Okada, Hiroki Furue, Yusuke Aikawa, Kazuhide Fukushima. "Solving McEliece-1409 in one day — cryptanalysis with the improved BJMM algorithm." ISC 2024. https://eprint.iacr.org/2024/393 Original title: "Revisiting the May–Meurer–Thomae algorithm — solving McEliece-1409 in one day."

• Léo Ducas, Andre Esser, Simona Etinski, Elena Kirshanova. "Asymptotics and improvements of sieving for codes." Eurocrypt 2024. https://eprint.iacr.org/2023/1577

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

• 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

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

• Qian Guo, Thomas Johansson, Vu Nguyen. "A new sieving-style information-set decoding algorithm." 2023. https://eprint.iacr.org/2023/247

• 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

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

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

• Andre Esser. "Revisiting nearest-neighbor-based information set decoding." 2022. 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." PQCrypto 2022. 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.

• Kévin Carrier, Thomas Debris-Alazard, Charles Meyer-Hilfiger, Jean-Pierre Tillich. "Reduction from sparse LPN to LPN, Dual Attack 3.0." Eurocrypt 2024. https://eprint.iacr.org/2023/1852

• Alain Couvreur, Rocco Mora, Jean-Pierre Tillich. "A new approach based on quadratic forms to attack the McEliece cryptosystem." Asiacrypt 2023. https://eprint.iacr.org/2023/950

• Freja Elbro, Christian Majenz. "An algebraic attack against McEliece-like cryptosystems based on BCH codes." ITW 2023. https://eprint.iacr.org/2022/1715

• Kevin Carrier, Thomas Debris-Alazard, Charles Meyer-Hilfiger, Jean-Pierre Tillich. "Statistical decoding 2.0: reducing decoding to LPN." Asiacrypt 2022. https://arxiv.org/abs/2208.02201

• Elena Kirshanova, Alexander May. "Breaking Goppa-based McEliece with hints." SCN 2022; Information and Computation 2023. https://eprint.iacr.org/2022/525 Previous title: "Decoding McEliece with a hint—secret Goppa key parts reveal everything."

• 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

• Hugues Randriambololona. "The syzygy distinguisher." https://eprint.iacr.org/2024/1193

• Sebastian Bitzer, Jeroen Delvaux, Elena Kirshanova, Sebastian Maaßen, Alexander May, Antonia Wachter-Zeh. "How to lose some weight - a practical template syndrome decoding attack." 2024. https://eprint.iacr.org/2024/621

• Daniel J. Bernstein. "Understanding binary-Goppa decoding." IACR Communications in Cryptology. 2024. https://cr.yp.to/papers.html#goppadecoding

• Daniel Fallnich, Christian Lanius, Shutao Zhang, Tobias Gemmeke. "Efficient ASIC architecture for low latency Classic McEliece decoding." CHES 2024. https://tches.iacr.org/index.php/TCHES/article/view/11434

• Vatistas Kostalabros, Jordi Ribes-González, Oriol Farràs, Miquel Moretó, Carles Hernandez. "A safety-critical, RISC-V SoC integrated and ASIC-ready Classic McEliece accelerator." ARC 2024. https://link.springer.com/chapter/10.1007/978-3-031-55673-9_20

• Yihong Zhu, Wenping Zhu, Chen Chen, Min Zhu, Zhengdong Li, Shaojun Wei, Leibo Liu. "Mckeycutter: a high-throughput key generator of Classic McEliece on hardware." DAC 2023. https://ieeexplore.ieee.org/abstract/document/10247918

• Xinyuan Qiao, Suwen Song, Jing Tian, Zhongfeng Wang. "Efficient decryption architecture for Classic McEliece." ISQED 2023. https://ieeexplore.ieee.org/abstract/document/10129325

• Cyrius Nugier, Vincent Migliore. "Acceleration of Classic McEliece post-quantum cryptosystem with cache processing." IEEE Micro 2023. https://hal.science/hal-04232870/

• Boly Seck, Pierre-Louis Cayrel, Vlad-Florin Dragoi, Idy Diop, Morgan Barbier, Jean Belo Klamti, Vincent Grosso, Brice Colombier. "A side-channel attack against Classic McEliece when loading the Goppa polynomial." Africacrypt 2023. https://bcolombier.fr/assets/publis_PDF/2023/Seck_AFRICACRYPT_2023.pdf

• Marcus Brinkmann, Chitchanok Chuengsatiansup, Alexander May, Julian Nowakowski, Yuval Yarom. "Leaky McEliece: secret key recovery from highly erroneous side-channel information." 2023. https://eprint.iacr.org/2023/1536

• Brice Colombier, Vincent Grosso, Pierre-Louis Cayrel, Vlad-Florin Drăgoi. "Horizontal correlation attack on Classic McEliece." 2023. 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." COSADE 2023. https://eprint.iacr.org/2023/308

• Shaofen Chen, Haiyan Lin, Wenjin Huang, Yihua Huang. "Hardware design and implementation of Classic McEliece post-quantum cryptosystem based on FPGA." HPEC 2022. https://ieeexplore.ieee.org/abstract/document/9926295

• Jiaming Zhang, Dongsheng Liu, Jiahao Lu, Aobo Li, Changwen Mo, Jiye Tian, Hai Li. "Implementation of Classic McEliece key generation based on Goppa binary code." ICSICT 2022. https://ieeexplore.ieee.org/abstract/document/9963372

• Martin Brain, Carlos Cid, Rachel Player, Wrenna Robson. "Verifying Classic McEliece: examining the role of formal methods in post-quantum cryptography standardisation." CBCrypto 2022. https://eprint.iacr.org/2023/010

• Minjoo Sim, Siwoo Eum, Hyeokdong Kwon, Hyunjun Kim, Hwajeong Seo. "Optimized implementation of encapsulation and decapsulation of Classic McEliece on ARMv8." 2022. https://eprint.iacr.org/2022/1706

• Rainer Urian, Raphael Schermann. "Classic McEliece key generation on RAM constrained devices." 2022. https://eprint.iacr.org/2022/1613

• Sabine Pircher, Johannes Geier, Julian Danner, Daniel Mueller-Gritschneder, Antonia Wachter-Zeh. "Key-recovery fault injection attack on the Classic McEliece KEM." 2022. https://eprint.iacr.org/2022/1529

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

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

• Brice Colombier, Vlad-Florin Drăgoi, Pierre-Louis Cayrel, Vincent Grosso. "Profiled side-channel attack on cryptosystems based on the binary syndrome decoding problem." 2022. https://eprint.iacr.org/2022/125

• Ming-Shing Chen, Tung Chou. "Classic McEliece on the ARM Cortex-M4." CHES 2021. https://doi.org/10.46586/tches.v2021.i3.125-148 https://eprint.iacr.org/2021/492

• 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