Collaborative Research: FRGMS: Small Root Discriminants in Number Theory and Cryptography

This project is about using recent advances in mathematics to improve lattice based cryptography. Lattice based cryptography is a foundation for advanced cryptographic schemes that are resistant to attacks by quantum computers. Secure cryptography is essential for digital communication, for example for ensuring the safe transfer of sensitive financial data. The new mathematical advance behind this project is the efficient construction of lattices that have both addition and multiplication operations and that are more densely packed than the ones now typically used in cryptography. The central goals of the project are to improve these constructions, to develop faster algorithms to operate on these lattices, and to build more efficient cryptographic applications using them. The technical advances in this project concern number fields with small root discriminants. This project will study the computational complexity of constructing such number fields and of performing arithmetic operations in them. Prior work on infinite families of number fields with small root discriminants has focused on existence theorems. This project will build on work of two of the P.I.s on efficient explicit constructions of such families. The goal is to improve these constructions using a variety of mathematical techniques including Galois cohomology, explicit Chebotarev theorems and recent advances on Hilbert's 12th problem via p-adic methods and modular forms. Another goal is to develop fast Fourier methods for performing arithmetic operations of the kind needed in cryptography. The relevance of number fields with small root discriminants was noted by Peikert and Rosen in 2006. They showed that such fields lead to very small connection factors relating the difficulty of solving the worst case of the short vector problem to the difficulty of solving the average case of the short integer solution problem. The cryptographic protocols to be studied using the rings of integers of the above fields include collision resistant hash functions, homomorphic commitment schemes, streaming authenticated data structures, zero-knowledge proof systems, and some types of digital signature schemes. 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.