---
_id: '6726'
abstract:
- lang: eng
text: 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.
article_processing_charge: No
author:
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Walter M. Sampling the integers with low relative error. In: Buchmann J, Nitaj
A, Rachidi T, eds. Progress in Cryptology – AFRICACRYPT 2019. Vol 11627.
LNCS. Cham: Springer Nature; 2019:157-180. doi:10.1007/978-3-030-23696-0_9'
apa: 'Walter, M. (2019). Sampling the integers with low relative error. In J. Buchmann,
A. Nitaj, & T. Rachidi (Eds.), Progress in Cryptology – AFRICACRYPT 2019
(Vol. 11627, pp. 157–180). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-23696-0_9'
chicago: 'Walter, Michael. “Sampling the Integers with Low Relative Error.” In Progress
in Cryptology – AFRICACRYPT 2019, edited by J Buchmann, A Nitaj, and T Rachidi,
11627:157–80. LNCS. Cham: Springer Nature, 2019. https://doi.org/10.1007/978-3-030-23696-0_9.'
ieee: 'M. Walter, “Sampling the integers with low relative error,” in Progress
in Cryptology – AFRICACRYPT 2019, vol. 11627, J. Buchmann, A. Nitaj, and T.
Rachidi, Eds. Cham: Springer Nature, 2019, pp. 157–180.'
ista: 'Walter M. 2019.Sampling the integers with low relative error. In: Progress
in Cryptology – AFRICACRYPT 2019. vol. 11627, 157–180.'
mla: Walter, Michael. “Sampling the Integers with Low Relative Error.” Progress
in Cryptology – AFRICACRYPT 2019, edited by J Buchmann et al., vol. 11627,
Springer Nature, 2019, pp. 157–80, doi:10.1007/978-3-030-23696-0_9.
short: M. Walter, in:, J. Buchmann, A. Nitaj, T. Rachidi (Eds.), Progress in Cryptology
– AFRICACRYPT 2019, Springer Nature, Cham, 2019, pp. 157–180.
conference:
end_date: 2019-07-11
location: Rabat, Morocco
name: 'AFRICACRYPT: International Conference on Cryptology in Africa'
start_date: 2019-07-09
date_created: 2019-07-29T12:25:31Z
date_published: 2019-06-29T00:00:00Z
date_updated: 2023-02-23T12:50:15Z
day: '29'
department:
- _id: KrPi
doi: 10.1007/978-3-030-23696-0_9
ec_funded: 1
editor:
- first_name: J
full_name: Buchmann, J
last_name: Buchmann
- first_name: A
full_name: Nitaj, A
last_name: Nitaj
- first_name: T
full_name: Rachidi, T
last_name: Rachidi
intvolume: ' 11627'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2019/068
month: '06'
oa: 1
oa_version: Preprint
page: 157-180
place: Cham
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Progress in Cryptology – AFRICACRYPT 2019
publication_identifier:
eisbn:
- 978-3-0302-3696-0
isbn:
- 978-3-0302-3695-3
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: Sampling the integers with low relative error
type: book_chapter
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 11627
year: '2019'
...