9
$\begingroup$

I just started to study lattice Cryptography.

I'm now studying worst-case to average-case reduction for SIS.

In previous question, "worst means any and average means random".

And I wonder why the Shortest Independent Vectors Problem(SIVP) is the worst-case problem.

And, does SIVP means that

"For 'any' given lattice basis B, it is hard to find n linearly independent short vectors in L(B)"?

The definitions that I saw didn't have the word 'any'.

Does the word 'any' is involved in the sentence even though it is not explicitly mentioned? I'm guessing that SIVP is a worst-case problem because of 'any'.

If it is correct, does

"For a given 'randomly' chosen lattice basis B, it is hard to find n linearly independent short vectors in L(B)"

is an average-case problem?

$\endgroup$
  • 2
    $\begingroup$ Yes, you are correct. To solve SIVP, an algorithm must work for any given input basis $B$. One can also formulate an average-case variant of SIVP, where the input basis is generated at random according to some probability distribution. $\endgroup$ – Chris Peikert Dec 17 '15 at 15:38

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.