2
$\begingroup$

I just started work on lattice-based cryptography and I could not understand the concept of worst-case to average-case reduction.

We generally say, Average Case Hardness: Random instance of a problem is hard to solve. Worst-Case Hardness: Hard to solve every instance of the problem (even if most instances are easy)

So far, so good

But I could not establish the relationship between lattices and worst-case hardness concept. Let's say our problem is "Shortest Vector Problem (SVP)". I know it is a hard problem and we can prove the security of lattice-based cryptosystems based on hardness of this -or other related problems- problem.

My question is: What is the instances of this problem? Lattices? Given bases? or shortest vector of that lattice? Firstly, I thought "worst" related with "shortest vector" but I was wrong. Could you explain this?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

An instance of the (approximate) Shortest Vector Problem is simply a basis of some lattice. The desired output is any (approximately) shortest nonzero vector of that lattice. To solve this problem in the worst case, an algorithm must produce the desired output given any basis of any arbitrary lattice. (Other lattice problems have similar instances, usually including a basis and sometimes other information, like an arbitrary target point in the case of the Closest Vector Problem.)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks. Then why do we need to solve these problems for any given basis? For example, we say finding short integer solutions is as hard as shortest independent vector problem of some corresponding lattice. How do we know that the input basis -input of problem- is among hard instances? $\endgroup$
    – NB_1907
    Mar 31, 2021 at 21:38
  • 2
    $\begingroup$ Consider a trivial algorithm that only works when the input basis’s first vector is a shortest nonzero lattice vector: it just returns that vector. We certainly should not consider this an algorithm for SVP! Instead, we require the algorithm to find a shortest lattice vector, no matter what lattice basis it is given as input. On your last question: we cannot tell whether any particular basis is among the hard instances, but this doesn’t matter—any algorithm solving SIS on random instances can be converted into one that solves certain lattice problems when given any basis of any lattice. $\endgroup$
    – Chris Peikert
    Apr 1, 2021 at 1:14

Your Answer

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

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