IACR News item: 01 October 2015
Markku-Juhani O. Saarinen
ePrint Reportcryptosystems have not yet matured nearly to the level that we now expect
from RSA, Elliptic Curve implementations.
Many modern Ring-LWE and other lattice-based public key algorithms
require high precision random sampling from the Discrete Gaussian
distribution. We examine stated requirements of precision of Gaussian
samplers, where statistical distance to the theoretical discrete
Gaussian distribution is expected to be below $2^{-90}$. We note that
for lightweight targets the sampling procedure often represents the
biggest implementation bottleneck due to its memory and computational
requirements. We argue that this precision is excessive and give precise
arguments from distribution identity testing theory why a square root
precision of the security parameter is almost always sufficient.
We also observe that many of the proposed algorithms for discrete Gaussian
sampling are not constant-time or straight-line programs, and leak
significant amounts of secret information in easily exploitable timing
attacks.
Additional news items may be found on the IACR news page.