1
$\begingroup$

I've recently become very interested in post-quantum cryptography, specifically lattice-based cryptography. As of this posting there exists no quantum algorithm that can perform better at solving lattice problems than a conventional computer.

There are, however, algorithms that exist that theoretically can solve lattice problems, albeit slowly.

I'd like to study one or more of these algorithms myself to help me better understand lattice cryptography and lattices in general.

So, what is the most efficient lattice problem solving algorithm and why is it so efficient?

$\endgroup$
  • $\begingroup$ Your question is not clear... There are several lattice problems and for each of them, several algorithms. So which lattice problem are you talking about? It seems to be SVP... $\endgroup$ – Hilder Vítor Lima Pereira Jun 23 at 9:58
  • 1
    $\begingroup$ why is it so efficient is a very interesting question, but the accepted answer doesn't address it $\endgroup$ – Ella Rose Jun 23 at 13:27
2
$\begingroup$

What you want is probably a lattice reduction algorithm.

Lattice cryptography usually relies on the Closest Vector Problem (CVP) or the Shortest Vector Problem (SVP). Solving these involves the Lenstra–Lenstra–Lovász lattice basis reduction algorithm, or LLL. This algorithm is the quintessential lattice reduction algorithm, and is probably what you are looking for. This algorithm is used internally by other algorithms, such as Babai's nearest plane algorithm for CVP.

Note that the LLL algorithm is not able to reduce lattices in higher dimensions, which is the case with practical lattice cryptography. Instead, different algorithms are required, such as BKZ 2.0 for NTRU. However for the purpose of learning about lattice reductions, understanding LLL should be sufficient.

$\endgroup$
  • $\begingroup$ I've "passed by" LLL on the internet and have heard of Babai's nearest plane algorithm, which works well with nearly orthagonal bases but not well with nearly parallel bases, making the prior a good candidate for a private key and the latter a good candidate for a public key. I'll take a look at LLL to get the basis (no pun intended) of lattice reduction. Thank you for your answer, very succinct and informational! $\endgroup$ – Steve Mucci Jun 23 at 6:54
  • $\begingroup$ BKZ is not an exact algorithm! It finds an approximate solution to SVP and there is a trade-off between its running time and the quality of the approximation it outputs. $\endgroup$ – Hilder Vítor Lima Pereira Jun 23 at 10:03
  • $\begingroup$ LLL is kind of only a partial answer, you still have to know what to feed into it to get the desired answer, and figuring that information out appears something of an art form. Obviously if you're reading a paper that presents a solution to problem X using LLL, then it's not hard to know what to feed it into LLL because the paper will have the answer already. But if all you have are some values of a known relation and LLL, then you still have work to do before you can start LLL to solve the problem. $\endgroup$ – Ella Rose Jun 23 at 13:25
  • $\begingroup$ That's true, but OP is looking for something that can help them learn about lattice cryptography in general, not necessarily an algorithm that you can plug in the parameters and key material and expect it to spit out a private key. At least, that's my understanding of the question. If anyone has a better answer, do post it! $\endgroup$ – forest Jun 24 at 4:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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