A little while ago, a colleague asked why we as a research community care so much about cryptography systems that are based on lattice problems. I didn’t have a good answer at the time but I have been reading these past couple of weeks and here’s what I now know.

There are a few ways to look at the issue. Firstly, it’s good to have crypto-systems that are based on a variety of hard computational problems so they are not all vulnerable in the same way. Secondly, lattice-based crypto-systems have lower encryption / decryption computational complexities in general, in the order of for k-bit keys compared to for popular crypto-systems that are based on the Integer Factorisation or the Discrete Logarithm problems. Thirdly, lattice-based crypto-systems are based on proven NP-hard problems like the Shortest Integer Problem, and that makes them secure even against quantum computers. Last but not least, interesting structures in lattice problems have led us to the discovery of Homomorphic Encryption, a new cryptographic research area with wide-ranging applications.

Let’s look at that third point in more details.

Note first that the Discrete Logarithm and Integer Factorisation problem classes, which underlie several well-known crypto-systems, are only known to be in NP, they are not known to be NP Complete or NP Hard. The way we understand their complexity is by looking at the average run-time complexity of the current best known (non-polynomial) algorithms for those two problem classes on randomly generated problem instances. Using that heuristic complexity measure, we can show that (1) there are special instances of those problems that can be solved in polynomial time but, in general, both problems can be solved only in sub-exponential time and (2) on average, most of the Discrete Logarithm and Integer Factorisation problem instances are as hard as each other. So we *believe* these two problems to be average-case hard problem classes, but we can’t prove that. Interestingly, we know there are quantum algorithms that can solve these two problems efficiently.

The above then begs the question of whether we can design crypto-systems based on known NP Hard problem classes. The challenge, of course, is that most NP Hard problem classes are only hard in the worst case but are efficiently solvable on many if not most cases. In constructing a (public-key) crypto-system using a problem class with average-case hardness like Integer Factorisation or Discrete Logarithm, it’s sufficient to show that the generation of a key pair (at random) and the solution of the private key corresponds to a problem instance , and we rely on average hardness to say is hard to solve with good probability. But in constructing a (public-key) crypto-system using a problem class with only known worst-case complexity, we need to do a bit more work, in that it’s not sufficient to generate a key pair (at random) and show the solution of the private key is a problem instance , we need to actually show that is one of the hard or worst cases in .

In other words, to build a crypto-system based on a worst-case hard problem class, we don’t just need to know the hard instances exist, but we need a way to explicitly generate the hard problem instances. And that’s a problem because we don’t know how to do that for most NP Hard problem classes. But this is what makes lattice problems interesting: we can show that they are both worst-case hard *and* we know how to generate those hard problem instances.

In particular, lattice problems like the Shortest Vector Problem (and related problems) have been proven to be NP Hard under the “randomised reduction hypothesis”, in which the class of polynomial-time algorithms is enlarged to include those that are not deterministic but will, with high probability, terminate in polynomial time with a correct result. And Miklos Ajtai, through his worst-case to average-case reduction technique, show how the hard lattice problem instances can be explicitly generated (through one-way functions). The NP-Hard-ness of these lattice problems is the reason why crypto-systems built on top of them are (likely) safe from quantum computing.

One final word on security. The proof-of-security of lattice-based crypto-systems, like many other crypto-systems, rests on the assumption that . This is widely believed to be the case, but the prominent computer scientist Donald Knuth has publicly stated he believes it may be the case that , but that many polynomial algorithms are effectively undiscoverable by us. His intuition is based on several well-known non-constructive proofs of polynomial algorithms, that is, proofs that show the existence of polynomial algorithms for solving certain apparently difficult computational problems for which actual explicit polynomial algorithms are unknown. (The reader is encouraged to take a look at this post and the Knuth interview with Lex Fridman to get more details: https://motls.blogspot.com/2020/01/donald-knuth-clarifies-why-pnp-seems.html). So it may well be that but the crypto-systems we know and love are still safe because we can only know polynomial algorithms for breaking these crypto-systems exist but we can’t explicitly construct them, and using Marcus Hutter’s Fastest and Shortest Algorithm for All Well-Defined Problems to construct such algorithms will still take way too long in practice…

References:

- Jeffrey Hoffstein, Jill Pipher, Joseph Silverman, An Introduction to Mathematical Cryptography, Springer, 2016
- Oded Goldreich, Foundations of Cryptography: Volume 1, Basic Tools, Cambridge University Press, 2007.