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?

$\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$ Commented Dec 17, 2015 at 15:38

0

Your Answer

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

Browse other questions tagged or ask your own question.