Theoretical and Practical Cryptanalysis of McEliece and Related Code-Based Cryptographic Systems

• Applicant: Professor Dr. Alexander May
• Subject Area: Security and Dependability, Operating-, Communication- and Distributed Systems ; Theoretical Computer Science
• Term: since 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 517817836

The advancement in the construction of quantum computers over the last decades puts today’s cryptography at risk. The most widely used cryptographic systems are solely build on non post-quantum secure primitives, i.e., they can easily be broken using a sufficiently large quantum computer. One promising candidate that allows for secure communication even in the presence of large-scaled quantum computers is the McEliece cryptosystem, which is a code-based system that recently advanced to the fourth and final round of the ongoing standardization process for post-quantum secure public key cryptography launched by the National Institute for Standards and Technology (NIST). There are numerous open questions regarding the classical as well as quantum hardness of the McEliece cryptosystem. In this project we plan to tackle these open questions, whose answers contribute to the understanding of code-based primitives in general as well as a secure standard derivation for the post-quantum era. We will revisit and improve existing classical and quantum attacks to precisely estimate the hardness of proposed instantiations. Furthermore we investigate new attack strategies, based on the structure of the used codes within the McEliece system. Finally, we aim at practical implementations of our attacks on different hardware platforms to obtain new record computations from which we can safely extrapolate the hardness of cyrptographic-sized instances.

• DFG Programme: Research Grants
• International Connection: United Arab Emirates
• Cooperation Partner: Dr. Andre Esser