10
$\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 Shortest Independent Vectors Problem(SIVP) is 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 worst-case problem because of 'any'.

If it is correct, does

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

is 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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.