Collaborative Research: CISE-ANR: CNS Core: Small: Cryptographic Hardness of Module Lattices

Public-key cryptography is used in nearly all forms of modern communication to provide authentication and privacy. However, the availability of large-scale general-purpose quantum computers will undermine the security of currently deployed public-key cryptographic mechanisms, including protocols protecting the vast majority of today’s Internet traffic.

Given the steady progress and advances in quantum computing, it is critical and pressing to investigate the mathematical and complexity-theoretic foundations for public-key cryptography that resists attacks by quantum computers. The goal of this project is to study the security of the primary candidates for quantum-resistant public-key cryptography, whose security rests on the computational intractability of certain computational problems related to mathematical objects called module lattices.

In addition to furthering the understanding of cryptographic protocols that are likely to be in widespread use in the near future, the project will generate educational materials that will be of interest both to the theoretical computer science community and to the security community. It will also generate open-source software for lattice algorithms and algebraic number theory.

In more detail, the primary candidates for quantum-resistant public-key cryptography rely on the presumed intractability of the problem of finding short non-zero vectors (SVP) over lattices with different module structures. This project aims to provide a clearer understanding of this problem and related problems. The project plans to achieve this by developing both improved reductions between different module lattice problems and improved dedicated algorithms.

Specific directions include (1) investigating algorithms for SVP over ideal lattices (i.e., lattices that correspond to ideals over the ring of integers of a number field) that lead to an approximation factor below the current best approximation factor (without pre-processing on the number field) of roughly 2^{sqrt(n)}, with n being the lattice dimension; (2) understanding the precise complexity of the cryptographically important NTRU variant of SVP, its relation with other average-case versions of SVP, and potential attacks; (3) better understanding the apparent hardness “transition” between SVP over ideal lattices (i.e., rank-1 module lattices, which seems to be significantly easier than SVP over arbitrary lattices) and SVP over rank-2 module lattices (whose hardness is necessary for the security of many cryptographic schemes); and (4) continuing to contribute to efficient and robust open-source software for lattice algorithms and algebraic number theory.

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.