Mental Models 4 Life

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 here’s what I now know.

There are a few ways to look at the issue.

1. It is useful to have cryptosystems that are based on a variety of hard computational problems so the different cryptosystems are not all vulnerable in the same way.
2. The computational aspects of lattice-based crytosystems are usually simple to understand and fairly easy to implement in practice.
3. Lattice-based cryptosystems have lower encryption/decryption computational complexities compared to popular cryptosystems that are based on the integer factorisation or the discrete logarithm problems.
4. Lattice-based cryptosystems enjoy strong worst-case hardness security proofs based on approximate versions of known NP-hard lattice problems.
5. Lattice-based cryptosystems are believed to be good candidates for post-quantum cryptography, since there are currently no known quantum algorithms for solving lattice problems that perform significantly better than the best known classical (non-quantum) algorithms, unlike for integer factorisation and (elliptic curve) discrete logarithm problems
6. Last but not least, interesting structures in lattice problems have led to significant advances in Homomorphic Encryption, a new research area with wide-ranging applications.

Let’s look at that fourth 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 worst-case 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). In practice, however, lattice-based cryptosystems are usually built on top of approximation versions of the Shortest Vector Problem called GapSVP for an approximation factor , and these GapSVP problems are only known to be NP-hard for very small values, but not for the typical values we use in practical constructions of cryptosystems. Having said all that, the best known algorithm for solving these GapSVP problems to within poly(n) factor has time complexity 2^O(n), which leads us to the following conjecture that underlines the security of lattice-based cryptography:

Conjecture: There is no polynomial time algorithm that approximates lattice problems to within polynomial factors.

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.