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

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Post-Quantum CryptographyLattice Public Key CryptographyGaussian Sampling
Contact author(s)
mjos @ iki fi
History
2015-12-08: last of 41 revisions
2015-10-01: received
See all versions
Short URL
https://ia.cr/2015/953
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/953,
      author = {Markku-Juhani O.  Saarinen},
      title = {Gaussian Sampling Precision in Lattice Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2015/953},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/953}},
      url = {https://eprint.iacr.org/2015/953}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.