$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?
Currently there is (at least) one paper in the lattice literature regarding speeding up lattice basis reduction with Grover search: A Faster Lattice Reduction Method Using Quantum Search. Indirectly, there have also been a few theoretical improvements to subroutines of lattice basis reduction, such as speeding up solving exact SVP with quantum search.

In practice though, the current fastest method in high dimensions is probably BKZ, using lattice enumeration with extreme pruning as the exact SVP subroutine. For this combination of methods, I do not believe anyone ever came up with a significant speedup based on Grover searching, as both methods do not involve a straightforward search over a long, predefined list.

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.

Remark 2: All of the security estimates for cryptography are just that: estimates. There is no proof that no (classical or quantum) algorithm can quickly solve problems which we now presume are hard to solve. We just don't know any fast ways to solve these problems. So we do not know with certainty that cryptography is secure, classically or quantumly.