Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
So Grover's algorithm, also known as the quantum search algorithm, can find an entry, with a high probability, in an unstructured database.
Well can't we consider the basis of a lattice problem an unstructured database, and the lattice point we are looking for the entry in that unstructured database? Could Grover's algorithm break lattice encryption?
The best attack on the exact shortest vector problem for an arbitrary lattice (to which essentially all lattice reduction attacks on lattice-based schemes reduce in some way) is some variant of sieving, and one can apply a Grover-style quantum search to speed it up, although the improvement is more modest than quadratic. Precisely, the best attack in dimension $n$ has heuristic classical complexity $2^{0.292n + o(n)}$ and heuristic quantum complexity $2^{0.265n + o(n)}$ (and both are provably optimal with existing techniques). So there is an improvement thanks to Grover, but not a very large one.
The standard reference is Thijs Laarhoven's Ph.D. thesis. See also this paper of Laarhoven, Mosca and van der Pol which is specifically devoted to the problem of estimating the improvement of sieving with quantum search (although with a slightly suboptimal variant of sieving, hence the slightly worse complexity estimates compared to the state of the art).
Grover’s algorithm can in-principle be applied to any cipher by posing it as a satisfiability (SAT) problem.
Define the function f(x,k)={0,1}, which evaluates to 1 when applying the decryption algorithm to ciphertext (x) using key (k) yields a plaintext that passes some legitimacy test.
In this form we may apply Grover’s algorithm to search over key-space for a key that evaluates to 1. This structure is generic as any cipher can be expressed this way.
However, this does not mean that Grover’s algorithm can “break” lattice-based (or any post-quantum) cipher. When we use the word “break” it is implied that this means efficiently (otherwise I’d be able to break post-quantum crypto using my bare hands). Upon applying the quadratic savings afforded by Grover’s algorithm to an exponentially hard problem it remains exponentially hard, but with a reduced exponent that can be offset by increasing key length.
