Lattice Reduction in Cryptography and Number Theory

University Of California-Davis, Davis CA

Investigators

Abstract

Modern cryptography allows us to send private information online by rendering it unreadable except to those who can solve some underlying hard math problem (for which the intended receiver has a helpful "secret key"). But now there is a concern that many commonly used hard problems can be solved efficiently by rapidly developing quantum computers. This has prompted a search for problems that resist quantum attacks, and one promising candidate is that of finding short vectors in a lattice from a given basis. Indeed, there are many newly proposed cryptosystems whose security hinges upon the hardness of lattice reduction, specifically ideal lattice reduction, where the lattice corresponds to the so-called Minkowski embedding of an ideal in a number field. It is at this intersection between cryptography and number theory where a large part of this project lies. The PI is investigating a new algorithm for finding short vectors in ideal lattices as well as a separate family of lattices that might be efficient to work with (like ideal lattices) yet possess a hardness guarantee (unlike ideal lattices). These pursuits have the potential to further our progress toward a post-quantum secure cyberspace, and they come with many coding and computational components that provide opportunities for student involvement. The new algorithm under investigation generalizes a complex continued fraction algorithm recently introduced by the PI, which is novel in that it functions over non-Euclidean imaginary quadratic rings. The generalized (to arbitrary number fields) version finds nonzero elements of an input ideal that have a relatively small absolute field norm. This reduces the task of finding short ideal lattice vectors to the task of approximating with Dirichlet's log unit lattice, which is independent of the input ideal. Both the speed and output quality of the PI's algorithm depend crucially on an initial choice of some finite set of integers from the associated number field. The existence of a "good" initial set likely depends on the field, and the PI intends to determine which fields are more amenable to the algorithm than others. Multiquadratic and cyclotomic fields are of particular interest. (It is already known that a theoretical quantum computer can efficiently find ideal elements that are small with respect to the field norm; the PI's algorithm is classical, not quantum.) Another main goal of this project is to scrutinize the potential use of "simultaneous approximation lattices" for cryptography. The PI has shown that the problem of finding short vectors in an arbitrary lattice reduces to finding short vectors in simultaneous approximation lattices. That is a hardness guarantee not currently possessed by ideal lattices. The benefit of simultaneous approximation versus generic lattices is the number of integers needed to define them: just one more than the dimension of the lattice. This may lead to increased efficiency for lattice-based cryptosystems, but the PI must first determine how much larger the integers defining a simultaneous approximation lattice must be in order to maintain the same level of security as one of its generic counterparts. 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.