1
$\begingroup$

In Regev's lecture there is "In contrast, virtually all other cryptographic constructions are based on some average-case assumptions. For example, in cryptographic constructions based on factoring, the assumption is that it is hard to factor numbers chosen from a certain distribution. But how should we choose this distribution? Obviously, we should not use numbers with small factors (such as even number), but perhaps there are other numbers that we should avoid? In cryptographic constructions based on worst-case hardness, such questions do not even arise."

I do not understand the meaning of "In cryptographic constructions based on worst-case hardness, such questions do not even arise." According to my understanding, in cryptographic constructions based on worst-case hardness we based the cryptography scheme on hard subsets in which the problem is hard, so we should also avoid we based the cryptography scheme on subsets in which the problem is easy.

$\endgroup$
4
$\begingroup$

According to my understanding, in cryptographic constructions based on worst-case hardness we based the cryptography scheme on hard subsets in which the problem is hard, so we should also avoid we based the cryptography scheme on subsets in which the problem is easy.

I think the idea of the statement is more along the following line:

"For most cryptographic schemes we have no proof that the distribution we use in practice is actually as hard to solve as the hardest ones we could come up with. With lattices however we have a proof that the sampling strategy we use generates problems that are just as hard to solve as the hardest instances we could come up with."

So the statement is about the average case for lattices being provably as difficult as the worst-case.

$\endgroup$
1
  • 2
    $\begingroup$ +1 good answer. Just the last sentence that is kind of disturbing me a little because what we actually know is that "average" instances of LWE (or SIS) are as difficult as the worst case of lattices problems (like SIVP). $\endgroup$ May 3 '20 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.