From Regev's paper in 2005, we know that for applying worst-case to average-case reduction to an lwe cryptosystem, one should use error distributions with standard deviation $s$ bigger than $2\sqrt{n}$. Why this condition is not regarded by Lindner & Peikert parameters (e.g. n=128 & s=6.77)?

  • 3
    $\begingroup$ Isn't it just for efficiency reasons? Even without a worst-case to average-case reduction, you can have parameters for which no attack is known, hence it is natural to set up for such parameters to get a practical scheme. $\endgroup$ Mar 6, 2017 at 18:34
  • $\begingroup$ I'm not sure whether this is for efficiency reasons or not?! $\endgroup$
    – Hamidreza
    Apr 12, 2017 at 6:41
  • 1
    $\begingroup$ Do you have a link to the Lindner & Peikert article you're referencing? There was a period where lattice crypto was considered too inefficient for practical, large-scale use so the changes could have been made for optimization (as has been pointed out). $\endgroup$
    – floor cat
    Apr 17, 2017 at 20:40
  • 1
    $\begingroup$ @hamidreza On the contrary, we don't know that. There's still a sizable gap between the hypotheses of the worst-case hardness theorems and the best known attacks for, say, cyclotomic rings. (The gap is even larger in the regime where only a few Ring-LWE samples are provided to the attacker, which is the case for basic RLWE encryption.) $\endgroup$ Apr 19, 2017 at 13:55
  • 1
    $\begingroup$ @hamidreza It's a remarkable and unique property that other problems used in crypto don't seem to have. And it helps us identify the "right" average-case problems, like LWE, to use and study, which is very nontrivial for lattices. (Many ad-hoc problems have turned out to be fundamentally broken.) $\endgroup$ Apr 24, 2017 at 12:26


Your Answer

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