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

点击翻译按钮获取中文摘要

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.