Lattices and Homomorphic Encryption
This post is based on Vinod Vaikuntanathan’s talk (https://www.youtube.com/watch?v=5LGwaICJ5sw&ab_channel=InstituteforQuantumComputing).
An $n$-dimensional lattice is an integer combination of \(n\) basis vectors \(b_1, \dots, b_n\). One of the most famous problems in lattice theory is: given a basis \(b_1, \dots, b_n\), give the shortest nonzero vector \(v\) in the lattice. This problem is hard to solve.
| So, there is a relaxed version of the problem, called the \(\alpha\)-approximate shortest vector problem. This problem asks for any \(\tilde{v}\) such that $$ | \tilde{v} | \leq \alpha | v | $$. But… this problem is also hard! |
Can we use the hardness of these problems to do cryptography?
What do we mean by hardness here? We mean worst case hardness. That is, there is at least one hard instance. But for cryptography, you need lots of hard instances. That is, you need average-case hardness.
Ajtai in 1986 showed that if you can solve a class of lattice problems on average, then you can solve them in the worst case.
One of these problems is the so-called learning with errors problem. This problem is: given linear equations over a finite field \(\mathbb{Z}_q\), solve them. As an example: