Introduction

The $K$-Densest Lattice Problem ($K$-DSP) is one of a variety of theoretical mathematical problems that a small community of nerds have devoted the past two decades to solving. There are few papers written about $K$-DSP, and it would seem destined to remain in the farthest recesses of mathematical esoterica for eternity. However, due to developments in distant branches of technology (quantum physics), $K$-DSP and its friends have been dragged under the microscope of a group of information security researchers known as cryptographers.

Those developments are the introduction of quantum computing, which will have the capability to factor large numbers efficiently. A 2048 bit number - around 616 digits long in decimal - that could take 300 trillion years to factor on today’s supercomputers might only take hours on a quantum computer. And that would break RSA-2048, the algorithm currently protecting your browser session, indicated by the padlock in your address bar. It also protects the confidentiality of your data, and authenticates the identity of other machines on the internet.

The problem for cryptographers is that the hardness of factoring these long numbers is what much of our public key cryptography is based on, responsible for protecting almost all internet and tele-communications. Thus a search began to find new mathematical problems to base quantum-resistant cryptosystems on, and this is where lattices become relevant.

Lattices

A lattice is a repeating pattern of points… in $N$-dimensional space. In two dimensions it looks exactly like what you would expect - a grid of points, not necessarily square or rectangular, it could be hexagonal or in parallelograms. The points are evenly spaced and, in theory, could continue for infinity. Simple to explain, computing certain properties about these structures is a fiendish task. For example, pick a random point anywhere in space, and compute the nearest lattice point. Or pick a random lattice point, and find a close/closest lattice point to it. These are easy in two or three dimensions - you are probably picturing it now. But in hundreds of dimensions these problems become intractable to silicon-based supercomputers.

The problems above are known as the Closest Vector Problem (CVP) and the Shortest Vector Problem (SVP) respectively. The former has cryptosystems designed around it, which the US government have recently selected for standardization after a 6 year process. Related to SVP and CVP are a host of other lattice problems, like Bounded Distance Decoding (BDD), Shortest Integer Solution (SIS), Shortest Independent Vector Problem (SIVP), and the Densest Sublattice Problem (DSP) as well as approximate-, unique-, and gap- versions for many of them. Together they form a complex web, connected by arrows known as reductions. These reductions mean that if one can efficiently solve problem A, then one can treat the solver for A as a tool, and use it to efficiently solve another problem B. Solving one of the problems in the web could precipitate a domino-like collapse of the hardness of problems connected to it and the problems connected to those. Many lattice cryptosystems, such as Kyber and Dilithium, are based on the Learning With Errors (LWE) problem. Via such reductions, solving BDD, SVP, or CVP would lead to an attack on LWE thus breaking those cryptosystems.

These connections and reductions enable mathematicians to better understand the properties of lattices, and the structure that underpins similar problems.

$K$-DSP

What sets the study of lattices apart from many other mathematical areas is their geometric interpretation. You can practically visualize almost all of these problems, at least up to three dimensions. The densest sublattice problem asks to find the highest density lattice in any dimension smaller than that of the overall lattice (pack the most lattice points into a given space!)

Example

Let’s take the honeycomb lattice where each point is 1m from the nearest three lattice points, visualized below. Now imagine stacking pallets of these directly on top of one another, each pallet hovering 3m above the one below. In the resulting three dimensional lattice we can now examine two two-dimensional sublattices. Slicing along one axis and looking at the cross-section, we see long thin rectangles of width 1m and height 3m. Slicing along another axis, we see the honeycomb lattice once again, with points arranged in equilateral triangles of 1m side length. One can immediately see that the honeycomb lattice packs in many more points than the lattice of tall thin rectangles. Here we specified that we were looking for two-dimensional lattices, hence this would be a case of $2$-DSP. However in general DSP, the densities of lattices in different dimensions can be compared. So while the honeycomb lattice was the densest two-dimensional sublattice, there could be an even denser one-dimensional lattice. Simply put, a one-dimensional lattice is just points evenly spaced on a line, and the closer the points are, the denser the lattice. If this sounds similar, it is because $1$-DSP is actually the shortest vector problem, SVP! A short vector describes a dense $1$-dimensional lattice, or equivalently, density is a higher dimensional generalization of length for SVP.

Quantum Algorithms

An algorithm by Peter Shor, leveraging properties of quantum physical systems, tells us that today’s cryptosystems, like RSA and ECC, will be vulnerable. In the search for replacements, we must now attack all options with all means available, to make certain that the underlying problems are hard, even for quantum computers. Concretely, cryptanalysts (the ones who break cryptosystems) trying to solve lattice problems will investigate the best classical algorithms, the best quantum algorithms, and they will also attack different problems in the web - remember that via a chain of reductions, breaking one niche problem can result in compromising a cryptosystem based on a different but related problem.

Quantum approaches to solving DSP and $K$-DSP were uninvestigated until recently. Following a line of work that embedded SVP solvers into quantum systems, we wondered if the same could be done for DSP, the more general analogue of SVP. A standard approach to quantum cryptanalysis is to take any unsorted search problem (think looking for a sock in a bag of laundry, versus sorted search which is like tracking down a library book by its Dewey Decimal code) and apply Grover’s algorithm. Grover’s quantum algorithm finds a solution after square root number of calls. Whereas searching (classically) for that sock in a bag of 10,000 laundry items will take on average 5,000 picks, using Grover’s quantum algorithm, only sqrt(10,000)=100 calls are required. We have simplified here for readability; the truth is that there are constants that mean that Grover’s algorithm will become beneficial only after a certain problem size. Asymptotically though, the square root scaling becomes dominant and Grover’s algorithm will be superior for large unsorted search problems when large fault-tolerant quantum computers are available.

One of the many frameworks used for quantum computation is called an Ising spin glass. Originally conceived to model the behaviour of magnetic materials, it arranges quantum bits, known as qubits, in a grid. The qubits, which can be measured as plus or minus one, are assigned energies depending on their own value and the value of their neighbours. Once measured, it looks like a grid of 1’s and -1’s, but during the course of the quantum algorithm the system remains in a superposition of all 2^n configurations, where n is the number of qubits in the grid.

Because the energies assigned are dependent on each qubit’s value and that of its neighbours, each configuration will have an energy associated with it. The whole description of the system energy is called a Hamiltonian. Physical systems tend to like low energy states, and this is true of quantum computers. When used for optimization, a large fault-tolerant quantum computer can be used to measure the system to be the lowest energy configuration with high probability. The task of practitioners is to massage their problem such that finding a low energy state results in a configuration that solves a particular problem.

Quantum $K$-DSP

Our construction of a quantum $K$-DSP algorithm depends on creating a thoughtful Hamiltonian. Instead of a single grid of qubits, we initialize $K$ grids of qubits. Each grid represents a point in the lattice, also known as a lattice vector. Together, K points in a lattice are enough to define a $K$-dimensional sublattice, so long as they are linearly independent. The volume of the $K$-dimensional sublattice is computed via a formula, equal to the determinant of the sublattice. A low volume corresponds to a high density, so we seek to minimize the volume. We encoded the Hamiltonian such that the energy of each configuration of the qubits was equal to the volume squared of the sublattice it described. Once done, it remains to plug the Hamiltonian into your quantum computation framework of choice. There are many, and include: adiabatic eigensolvers, quantum annealers, quantum approximate optimization algorithm, Grover search.

In solving complex combinatorial algorithms like the ones involving mathematical lattices, it is common for the best algorithms to be comprised of many smaller subroutines. For example, BKZ reduction is a powerful classical technique to solve lattice problems. It is an algorithm that optimizes lattice bases, and uses an SVP solver as a black box, updates its basis with the new short vectors, then repeats the process. We demonstrated how a quantum $K$-DSP solver would fit into an algorithm like BKZ as a subroutine. Results of this work can be found in the full manuscript. While certain operations make sense to run on quantum hardware, many operations will see no improvement over classical computation techniques, and the complexity of handling large quantum systems grows enormously relative to the size of the problem, so using quantum routines to solve more condensed sections of a problem will surely yield the most profitable results in the near and medium term. Applying borderline sci-fi future technology to tackle arcane geometric mathematical problems sounds like a pursuit for curiosity’s own sake, but this kind of work is what will keep your data safe from criminals and foreign governments in the decades to come.