5
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • $\begingroup$ 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? $\endgroup$
    – 111
    Feb 10, 2017 at 0:40
  • $\begingroup$ 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. $\endgroup$
    – floor cat
    Feb 10, 2017 at 18:40
  • $\begingroup$ 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. $\endgroup$
    – 111
    Feb 10, 2017 at 22:47
  • $\begingroup$ 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. $\endgroup$
    – floor cat
    Feb 10, 2017 at 22:57
  • $\begingroup$ 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. $\endgroup$
    – floor cat
    Feb 10, 2017 at 23:05

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you. For Remark 1 are you also considering Grover's search for unknown solutions? $\endgroup$
    – floor cat
    Feb 11, 2017 at 18:55
  • 1
    $\begingroup$ @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. $\endgroup$
    – TMM
    Feb 11, 2017 at 18:59
  • $\begingroup$ 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 $\endgroup$
    – floor cat
    Feb 11, 2017 at 19:23
  • 2
    $\begingroup$ @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. $\endgroup$
    – TMM
    Feb 11, 2017 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.