Cryptanalysis of post-quantum lattice- and code-based primitives: practical records and theoretical improvements

我们的项目是致力于密码分析的后量子格为基础的和代码为基础的公钥加密方案。我们旨在解决的研究问题分为三类：NTRU密码系统的密码分析，作为基于格的方案的突出例子，McEliece密码系统的密码分析，作为基于代码的公钥加密方案的最重要例子，以及，第三，具有大接吻数的格的构造。我们选择NTRU密码系统作为最古老的，也许，从密码分析的角度来看，基于格的方案最不容易理解。我们的研究的目标是提供一个彻底的研究，由NTRU假设1提供的硬度保证。改进了NTRU上的各种组合攻击，包括中间相遇攻击; 2.对NTRU特有的攻击进行中型和大型实验，首次确定这些攻击的实际相关性; 3.对于McEliece密码系统，我们将最近对随机线性码解码的所有改进统一到一个开源实现中，为这一领域的进一步实际发展奠定了基础，回答了关于密码系统具体参数提供的安全保证的长期问题，并使更多的理解到近几年来进行的渐近工作的路线。我们把我们的结果塑造成一个公开可用的安全估计的形式，基于代码的计划，一个工具，从业者将需要的情况下，McEliece密码系统成为standardized.Our第三个方向构造格与大接吻数在理论和实践上都有影响。从理论上解决了最近构造的具有指数接吻数的格在指数上是否紧的问题。这个问题与密码分析并不像看起来那么遥远：具有大接吻数的格可以产生良好的球形码，而球形码又用于最短向量问题的快速算法中--这是基于格的密码分析中的主要问题。密码系统。我们调查的适用性格与大接吻数密码分析回答的问题，这些格是否承认快速解码算法。

Our project is dedicated to cryptanalysis of post-quantum lattice-based and code-based public-key encryption schemes. The research questions we aim to address are divided into three categories: cryptanalysis of the NTRU cryptosystem, as a prominent example of lattice-based schemes, cryptanalysis of the McEliece cryptosystem as the most important example of a code-based public-key encryption scheme, and, third, construction of lattices with a large kissing number.We choose the NTRU cryptosystem as one of the oldest yet, perhaps, least understood from the cryptanalytic point of view lattice-based scheme. The goal of our research is to provide a thorough study of the hardness guarantees offered by the NTRU assumption by 1. improving various combinatorial attacks on NTRU including meet-in-the-middle type of attacks; 2. conducting medium- and large-scale experiments on NTRU-specific attacks, establishing for the first time practical relevance of these attacks; 3. establishing quantum speed-ups for the proposed classical improvements.For the McEliece cryptosystem, we unify all the recent improvements on the decoding of random linear codes into an open-source implementation, laying the ground for further practical developments in this area, answering long-standing questions on security guarantees offered by concrete parameters of the cryptosystem, and bringing more understanding into the line of the asymptotical work conducted over the recent years. We shape our results into the form of a publicly available security estimator for code-based schemes, a tool that a practitioner would need in case the McEliece cryptosystem becomes standardized.Our third direction on constructing lattices with large kissing number has implications both in theory and practice. From the theoretical perspective, we aim at settling the question of whether the recent construction of lattices with exponential kissing number is tight in the exponent. This question is not that far form cryptanalysis as it may appear: lattices with large kissing number give raise to good spherical codes, which, in turn, are used inside fast algorithms for the shortest vector problem -- the main hammer in cryptanalysis of lattice-based cryptosystems. We investigate the applicability of lattices with large kissing number to cryptanalysis by answering the question of whether these lattices admit fast decoding algorithms.