0
$\begingroup$

In paper Lattice Signatures Without Trapdoors(Lyubashevsky2012), $n$ is the security parameter, why the authors set $n$ as 512 but not 80/100/112 to get 80-bit security/100-bit/112-bit security?

enter image description here

$\endgroup$
  • $\begingroup$ He mentions in the paper that it's for a security of ~100 bits $\endgroup$ – Binou Mar 31 at 13:04
6
$\begingroup$

A similar question could be asked about RSA --- why use 2048-bit RSA, and not 80-bit RSA?

The answer of course is due to cryptanalytic estimates. In particular, one estimates how difficult the underlying problem is (for factoring, it's roughly $\exp(O(\sqrt[3]{n}))$, and then sets the security parameter such that it takes $\approx 2^{80}$ bit operations to break.

For LWE-based schemes, Albrecht et al. have created the LWE-estimator. This is both a summary of state-of-the-art (at the time, in 2015) attacks on lattice schemes, along with a Sage module (which has been updated since then) that allows you to plug in the parameters of your scheme, and it will estimate the concrete security level.

These estimates are of course just estimates, and its an active area of research to try to get better estimates of the concrete security of lattice-based cryptography. But parameters themselves are chosen such that, when state of the art attacks are applied, it takes $2^{80}$ (or $2^{100}$ or $2^{112}$) bit operations to break the scheme.

| improve this answer | |
$\endgroup$

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.