SaTC: CORE: Small: Lattices, number theory, and distribution questions in cryptography

Modern cryptography faces the serious concern that quantum computers will one day break most of our presently-used cryptosystems. This would have catastrophic consequences to internet security and privacy. As a result, it is very important to develop and understand newer types of potentially quantum-resistant cryptosystems. Cryptosystems based on the mathematical notion of Euclidean lattices are presently the leading candidates for post-quantum cryptography. The proposal studies the mathematical underpinnings of these systems, as well as possible attacks on them. Specifically, the PI and collaborators will study distribution questions (such as biased outputs) related to the behavior of the LLL lattice basis reduction algorithm, one of the basic tools for attacking lattice-based cryptosystems. Estimating the security of lattice-based cryptosystems requires understanding the actual, average-case performance of the LLL algorithm and its variants, hence the interest in such an analysis. The PI and collaborators also plan to develop machinery from analytic number theory and automorphic forms to study the size of the smallest basis of a random lattice, which is also important for understanding average-case key sizes. Finally, the PI and collaborators will systematically study various practical aspects of implementations of elliptic curve cryptosystems, such as unusual biases in timings or other side-channel information. 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.