Worst-Case hardness of lattice problems 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 &quot;Shortest Vector Problem (SVP)&quot;. 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 &quot;worst&quot; related with &quot;shortest vector&quot; but I was wrong. Could you explain this?
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.)