From the Inside: Lattices: Algorithms, Complexity, and Cryptography

by Daniele Micciancio

What's the best way to stack oranges (or cannonballs or any other spherical objects) in a pile? If you have ever visited a farmers market, you are probably familiar with the pyramidal, layered arrangement where each ball sits exactly above the center of three neighboring balls at the lower layer. These regular arrangements of points are called lattices and come up very naturally in the study of geometric questions, like determining the densest possible packing of spheres in space.

Perhaps more surprisingly, lattices come up in the solution of many other problems in science and mathematics not directly related to geometry. The mathematical study of point lattices, as we know it today, has its roots in the pioneering work of Minkowski, about a century ago. He used lattices to build a bridge between geometry and algebraic number theory. As many standard notions from algebraic number theory can be described in terms of lattices, this allows ideas, techniques, and intuition from geometry to be used to answer questions about numbers in a seemingly different domain.

Today, the use of lattices has expanded well beyond algebraic number theory, with important applications in coding theory, cryptanalysis, combinatorial optimization, crystallography, theoretical computer science, and much more. The goal of the Spring 2020 Simons Institute research program on Lattices: Algorithms, Complexity, and Cryptography was to bring together researchers from all the different areas that make use of lattices and facilitate the exchange of ideas, perspectives, techniques, recent developments, and open problems in a field that comprises several subcommunities that normally work in isolation from each other.

A classic mathematical question in the study of lattices is, given the mathematical description of a lattice, determine its "minimum distance," i.e., the smallest distance between any two points in the lattice. As you look at this question through the lens of computer science, the question becomes, given a lattice, can you efficiently compute its minimum distance? The question is of great significance in many applications.

For example, in coding theory, lattices are used for noise-tolerant communication, with messages encoded as distinct points in a lattice. In this setting, the minimum distance is related to the error-correction capability of the code: How much noise can be added to a point before it may get confused with some other message?

In optimization problems, the minimum distance typically corresponds to the optimal solution that one is looking for. In cryptanalysis, shortest/closest lattice vectors (i.e., vectors achieving the minimum distance from each other or from a given target point) often reveal (or serve as) the private key of an encryption scheme, or other secret information.

While applications are often very different, the mathematical structure of lattices and the algorithms to operate on them are the same. In fact, the same lattice algorithms used to solve integer programming (a classic and very general combinatorial optimization problem) have been used now and again to break cryptographic constructions by encoding them as the problem of finding a short vector in a lattice.

The lattices program at the Simons Institute started with a boot camp in January 2020, followed by three thematic workshops scheduled about a month apart from each other. The boot camp featured introductory talks from different areas, aimed at familiarizing all participants with the main themes of the program and establishing a common vocabulary. It included tutorial presentations on the mathematics of lattices, their algorithms, computational complexity, cryptographic constructions, cryptanalysis, and lattice constructions from algebraic number theory. Interestingly, algebraic number theory, the original motivation for the study of lattices in mathematics, is receiving much attention today because algebraic lattices are used in the constructions of the most efficient lattice-based cryptographic schemes known to date.

The construction of cryptographic functions is currently one of the most attractive applications of lattices, due to their conjectured resistance against quantum attacks. The lattice program was scheduled in parallel with another semester-long Simons Institute program, on The Quantum Wave in Computing, to facilitate interaction between the two research groups. So the boot camp served also as a good introduction to lattice problems (especially as used in cryptography) for the quantum computing program participants.

The boot camp was followed by a thematic workshop in February on lattice algorithms, geometry, and computational complexity. This workshop attracted researchers from many areas outside cryptography and featured talks on a diverse selection of topics ranging from high-dimensional geometry and integer programming to coding theory and algorithms for algebraic lattices. The workshop took place the week before the quantum algorithms workshop from the quantum computing program, and a two-day mini-workshop on the quantum cryptanalysis of post-quantum cryptography was strategically scheduled in between as a bridge between the two main workshops.

The last two workshops focused first on the theoretical and then practical aspects of lattice cryptography. These two workshops were held virtually, using teleconferencing technology, as the coronavirus pandemic struck the world and shelter-in-place orders were issued in Berkeley and many other places around the globe. But under the momentum built during the first two months of the lattice program, research activities continued unchallenged, with no less energy or enthusiasm, as researchers participated from their homes through videoconferencing.

Activities included not only the two remaining thematic workshops but also weekly lattice seminars every Tuesday and Thursday, a Quantum Crypto for Dummies reading group aimed at bringing cryptographers up to speed with quantum computation, as well as social events. Program participants kept meeting (virtually) for tea time, a well-established tradition at the Simons Institute, and even started a Cooks, in Theory series, where researchers share dishes from around the world. The last meeting featured slices of zucchini and tomatoes arranged into beautiful lattice structures before going into the oven to turn into a delicious tian. Perhaps one day, quantum teleportation will allow us to share and taste the fruits of our efforts during teleconferences. But even without that, participants were able to admire the lattice structure of each other’s culinary creations and enjoy a virtual dinner together.

 

 

Related articles

Related stories

,