International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 01 October 2015

Markku-Juhani O. Saarinen
ePrint Report ePrint Report
Security parameters and attack countermeasures for Lattice-based

cryptosystems 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.

Expand

Additional news items may be found on the IACR news page.