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

过去几十年来量子计算机建设的进步使今天的密码学处于危险之中。最广泛使用的密码系统仅建立在非后量子安全原语上，即，使用足够大的量子计算机就可以很容易地破解它们。一个有希望的候选者，即使在大规模量子计算机的存在下也可以进行安全通信，这是一个基于代码的系统，最近进入了第四轮也是最后一轮正在进行的后量子安全公钥密码学标准化过程由美国国家标准与技术研究所（NIST）发起。关于McEliece密码系统的经典和量子硬度有许多悬而未决的问题。在这个项目中，我们计划解决这些开放的问题，其答案有助于理解基于代码的原语，以及后量子时代的安全标准推导。我们将重新审视和改进现有的经典和量子攻击，以精确估计所提出的实例的硬度。此外，我们调查新的攻击策略，在McEliece系统中使用的代码的结构的基础上。最后，我们的目标是在不同的硬件平台上实现我们的攻击，以获得新的记录计算，从中我们可以安全地推断出的硬度的图形大小的实例。

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.