# $L^3$ Grover search of NTRU variants

I was reading a text on cryptology by Wayne Patterson and came across the $L^3$ algorithm which reduces integer lattices with respect to their base. I've also read on the NIST CFP A8 that attacks based on Grover's algorithm aren't really seen as viable. There is already research covering vulnerabilities in the group rings of NTRU variants, and additional research showing approximate closest vectors return approximate shortest vectors in polynomial time.

Page 70 from "Mathematical Cryptology for Computer Scientists and Mathematicians" by Wayne Patterson states: "The central algorithm developed (and proved to run in polynomial time) by Lenstra, Lenstra, and Lovasz is the reduced basis algorithm. The algorithm begins with any basis $\beta_{i}$ for an integer lattice, and eventually computes a reduced basis in the sense of the previous section." Page 72 then demonstrates how to apply the LLL algorithm in a Shamir attack against knapsacks.

Quoting again from Patterson, "These two theorems (6.1 and 6.2) taken together give an estimate on how close a vector of the reduced basis must be to the shortest (non-zero) vector in the entire lattice." pg. 70.

My question: Why would it be infeasible to encode the LLL reduction and group structures of NTRU variants as a search space in a Grover search to return an output that would break the NTRU schemes? This would be in line with the Coppersmith and Shamir lattice attack from section 4.2 in the linked article of NTRU Variants.

This seems in line with oracle access to a subroutine based on the linked research by Goldreich, et al.

Phrased differently, Can we know with certainty that LLL reductions and lattice attacks will not be made stronger if supplemented with Grover searches?

• Golderich et al. which paper do you mean? What do u mean, by If there is already an algorithm that reduces a lattice to its base vector? – 111 Feb 10 '17 at 0:40
• The Goldreich paper is the linked article in the "polynomial time" link. The algorithm that reduces a lattice to its base vector for SVP and CVP problems is the link in the $L^3$ algorithm link. – floor cat Feb 10 '17 at 18:40
• LLL provides a short vector not the shortest. The paper of Goldreich you mentioned, does not have to do anything with Grover algorithm, is a reduction of svp to cvp. Also, again it does not make sense to say : LLL reduces lattices to their base. – 111 Feb 10 '17 at 22:47
• The LLL algorithm allows one to reduce a vector, yes, and in tandem with this is the group structure paper in the NTRU link which approaches cryptanalysis of NTRU variants in group theoretic terms. Finally, the Goldreich paper presents a reduction of GapCVP to GapSVP allowing one to find an approximate shortest vector in polynomial time. My question pairs all of these research findings together under the purview of Grover's search algorithm. I'm not sure I understand the issue you are raising with respect to my question. – floor cat Feb 10 '17 at 22:57
• Page 70 from "Mathematical Cryptology for Computer Scientists and Mathematicians" by Wayne Patterson states: "The central algorithm developed (and proved to run in polynomial time) by Lenstra, Lenstra, and Lovasz is the reduced basis algorithm. The algorithm begins with any basis ${ \beta }_i$ for an integer lattice, and eventually computes a reduced basis in the sense of the previous section." Page 72 then demonstrates how to apply the $L^3$ algorithm in a Shamir attack against knapsacks. Not entirely relevant, but a demonstration of the $L^3$ as applied in an attack. – floor cat Feb 10 '17 at 23:05

Remark 1: Grover searching generally leads to a decrease in the time complexity for solving a hard problem from $T$ (classically) to at least $\sqrt{T}$ (quantumly). With $T$ scaling exponentially in the lattice dimension, this means we need to increase the lattice dimension by at most a factor $2$ to maintain security. Commonly such improvements in the runtime are not considered a "break" of the scheme.
• @floorcat I think in general, Grover searching only gives you at most a square root speedup, regardless of the precise problem you are solving, but I am not absolutely sure. At least for a standard search over a list of size $N$ in memory, there's a matching $\Omega(\sqrt{N})$ lower bound on the time complexity of any quantum algorithm. – TMM Feb 11 '17 at 18:59
• Thanks again. From what I've read you can combine Shor's algorithm with a Grover search for unknown T, but is still a square root speedup. It is possible for the number of calls to be $O \sqrt{\frac{N}{2}}$ . Combining Shor with Grover is explored in: arxiv.org/abs/quant-ph/9605034 – floor cat Feb 11 '17 at 19:23
• @floorcat $\sqrt{N/2} = \Omega(\sqrt{N})$. And Shor's algorithm is much more ambitious, in that it potentially reduces the complexity of a "hard" problem from (slightly sub)exponential to polynomial. Such an improvement would be considered a break, if it applies to lattice cryptography as well. – TMM Feb 11 '17 at 20:48