Cryptology ePrint Archive: Report 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.

Category / Keywords: implementation / Sampling, Discrete Gaussians, Lattice-based Cryptography

Original Publication (with minor differences): AFRICACRYPT 2019

Date: received 21 Jan 2019, last revised 10 May 2019

Contact author: michael walter at ist ac at

Available format(s): PDF | BibTeX Citation

Version: 20190510:105833 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]