Cryptology ePrint Archive: Report 2015/953
Gaussian Sampling Precision in Lattice Cryptography
Markku-Juhani O. Saarinen
Abstract: 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 further propose new experimental parameters for practical
Gaussian samplers for use in Lattice Cryptography.
Category / Keywords: Post-Quantum Cryptography, Lattice Public Key Cryptography, Gaussian Sampling
Date: received 30 Sep 2015, last revised 8 Dec 2015
Contact author: mjos at iki fi
Available format(s): PDF | BibTeX Citation
Version: 20151208:154619 (All versions of this report)
Short URL: ia.cr/2015/953
[ Cryptology ePrint archive ]