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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ He mentions in the paper that it's for a security of ~100 bits $\endgroup$– BinouMar 31, 2020 at 13:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
