Cryptology ePrint Archive: Report 2015/953

Gaussian Sampling Precision and Information Leakage 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 significantly faster and more compact implementations. We also observe that many of the proposed algorithms for discrete Gaussian sampling are not constant-time and may leak significant amounts of secret information in easily mounted timing attacks. We further offer new recommendations for practical samplers.

Category / Keywords: Gaussian Sampling, Timing attacks, Lattice Side-Channel Attacks, Quantum Resistant Cryptography.

Date: received 30 Sep 2015, last revised 7 Oct 2015

Contact author: mjos at iki fi

Available format(s): PDF | BibTeX Citation

Version: 20151007:172000 (All versions of this report)

Short URL: ia.cr/2015/953

Discussion forum: Show discussion | Start new discussion