11
$\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?

Improve this question
$\endgroup$
1
  • 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, 2015 at 15:38

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.