2
$\begingroup$

In lattice cryptography it seems like giving out long vectors for a lattice that can be drawn from much shorter vectors (generating an identical lattice) is somehow useful for public-private key schemes and similar. Why exactly is it hard to find short vectors if given long vectors, can't the lattice just be generated and then the shorter vectors discovered super easily?

$\endgroup$
  • $\begingroup$ From wiki; Ajtai showed that the SVP problem was NP-hard, and The time complexity of known algorithms that find the exact solution are at least exponential in the dimension of the lattice. $\endgroup$ – kelalaka Nov 18 '18 at 20:38
  • $\begingroup$ The proof is based on reduction to Exact Set Cover which is known to be NP-complete, see the lecture notes of Vaikuntanathan $\endgroup$ – kelalaka Nov 18 '18 at 21:19
  • $\begingroup$ Why is it exponential in the dimension the lattice is in? Are the long vectors like.... super long? So long that for it to begin to draw the pattern of the shortest vector, you would have to plot a lot of points? $\endgroup$ – oRinga Nov 18 '18 at 21:20
  • $\begingroup$ In all visualizations the long vectors are just... twice the length of the shortest one, so if you plot those you only need a couple of them for the shortest one to appear $\endgroup$ – oRinga Nov 18 '18 at 21:21
  • $\begingroup$ You just thinking in two dimension. $2^2 =4 $, consider $n$ dimension $2^n$ $\endgroup$ – kelalaka Nov 18 '18 at 21:27

Your Answer

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

Browse other questions tagged or ask your own question.