International Association
for Cryptologic Research

Security parameters and attack countermeasures for Lattice-based

cryptosystems have not yet matured to the level that we now expect

from RSA and Elliptic Curve implementations.

Many modern Ring-LWE and other lattice-based public key algorithms

require high precision random sampling from the Discrete Gaussian

distribution. The sampling procedure often represents the biggest

implementation bottleneck due to its memory and computational requirements.

We examine the stated requirements of precision for Gaussian

samplers, where statistical distance to the theoretical distribution is

typically expected to be below $2^{-90}$ or $2^{-128}$ for

90 or 128 ``bit\'\' security level.

We argue that such precision is excessive and give precise

theoretical arguments why half of the precision of the security parameter

is almost always sufficient. This leads to faster and more

compact implementations; almost halving implementation size in both

hardware and software.

We observe that many of the proposed algorithms for discrete Gaussian

sampling may leak significant amounts of secret information in easily

mounted timing attacks. We further offer new recommendations for practical

samplers.