SaTC: CORE: Small: Towards a scientific theory of lattice reduction

University Of Cincinnati Main Campus, Cincinnati OH

Investigators

Abstract

As the era of quantum computing draws near, there is an imminent need for our society to prepare for its immense impact on cybersecurity. Since quantum computers will be capable of breaking all the main cryptosystems we are heavily relying on today, it is necessary to develop new cryptosystems that are quantum-resistant, and the National Institute of Standard of Technology is the process to develop the post-quantum cryptographic standards. Lattice-based cryptography represents one of the most promising families of such quantum-resistant cryptosystems. However, despite its successes so far, there has been a severe lack of understanding as to how the basic components of lattice-based cryptography, namely lattices and reduction algorithms, operate. This knowledge gap is harmful in a number of ways, such as the compromise of the performance of lattice-based systems, the inaccurate and unreliable evaluation of their security, and even the potential threat to the very idea of lattice-based cryptography itself. The goal of the present proposal is to confront these problems by developing a solid theoretical foundation for lattice-based cryptography. Our theory will be applied systematically to improve the practice of lattice-based cryptography and to scientifically assess the security of lattice-based systems, thereby contributing to humanity's effort to prepare for the quantum era. This project largely consists of two parts that will be combined into one for a complete analysis of lattice reduction algorithms. First, the project will refine the number-theoretic tools used to study the statistics of lattice vectors. This was originally pioneered by the works of Siegel, Schmidt, and Rogers in the 1940-50's, but the current practice of lattice-based cryptography calls for the extensions of those tools to broader contexts, so as to be able to handle lattices defined over a general number field, or count sublattices of lesser rank rather than just lattice vectors. They will serve to replace the Gaussian heuristic in order to provide more accurate predictions of lattice behavior. Second, recently the PIs found that lattice reduction algorithms may be interpreted as sandpile models from statistical physics, and these two systems of very different origins behave in a remarkably similar way. This provides an exciting and promising approach to a scientific study of reduction algorithms, which is exactly what this project will pursue: apply the physical theory of sandpiles to reduction algorithms. Once this project establishes the explanatory and predictive power of both sets of results, the project will apply them to revising the security estimates of lattice-based cryptosystems and the current practices in parameter choices, in particular, for the lattice-based cryptosystems in the ongoing NIST post-quantum standardization process. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.