Paper 2019/068

Sampling the Integers with Low Relative Error

Michael Walter

Abstract

Randomness is an essential part of any secure cryptosystem, but many constructions rely on distributions that are not uniform. This is particularly true for lattice based cryptosystems, which more often than not make use of discrete Gaussian distributions over the integers. For practical purposes it is crucial to evaluate the impact that approximation errors have on the security of a scheme to provide the best possible trade-off between security and performance. Recent years have seen surprising results allowing to use relatively low precision while maintaining high levels of security. A key insight in these results is that sampling a distribution with low relative error can provide very strong security guarantees. Since floating point numbers provide guarantees on the relative approximation error, they seem a suitable tool in this setting, but it is not obvious which sampling algorithms can actually profit from them. While previous works have shown that inversion sampling can be adapted to provide a low relative error (Pöppelmann et al., CHES 2014; Prest, ASIACRYPT 2017), other works have called into question if this is possible for other sampling techniques (Zheng et al., Eprint report 2018/309). In this work, we consider all sampling algorithms that are popular in the cryptographic setting and analyze the relationship of floating point precision and the resulting relative error. We show that all of the algorithms either natively achieve a low relative error or can be adapted to do so.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Minor revision.AFRICACRYPT 2019
Keywords
SamplingDiscrete GaussiansLattice-based Cryptography
Contact author(s)
michael walter @ ist ac at
History
2019-05-10: revised
2019-01-25: received
See all versions
Short URL
https://ia.cr/2019/068
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/068,
      author = {Michael Walter},
      title = {Sampling the Integers with Low Relative Error},
      howpublished = {Cryptology ePrint Archive, Paper 2019/068},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/068}},
      url = {https://eprint.iacr.org/2019/068}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.