---
_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. <i>Progress in Cryptology – AFRICACRYPT 2019</i>. Vol 11627.
    LNCS. Cham: Springer Nature; 2019:157-180. doi:<a href="https://doi.org/10.1007/978-3-030-23696-0_9">10.1007/978-3-030-23696-0_9</a>'
  apa: 'Walter, M. (2019). Sampling the integers with low relative error. In J. Buchmann,
    A. Nitaj, &#38; T. Rachidi (Eds.), <i>Progress in Cryptology – AFRICACRYPT 2019</i>
    (Vol. 11627, pp. 157–180). Cham: Springer Nature. <a href="https://doi.org/10.1007/978-3-030-23696-0_9">https://doi.org/10.1007/978-3-030-23696-0_9</a>'
  chicago: 'Walter, Michael. “Sampling the Integers with Low Relative Error.” In <i>Progress
    in Cryptology – AFRICACRYPT 2019</i>, edited by J Buchmann, A Nitaj, and T Rachidi,
    11627:157–80. LNCS. Cham: Springer Nature, 2019. <a href="https://doi.org/10.1007/978-3-030-23696-0_9">https://doi.org/10.1007/978-3-030-23696-0_9</a>.'
  ieee: 'M. Walter, “Sampling the integers with low relative error,” in <i>Progress
    in Cryptology – AFRICACRYPT 2019</i>, 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.” <i>Progress
    in Cryptology – AFRICACRYPT 2019</i>, edited by J Buchmann et al., vol. 11627,
    Springer Nature, 2019, pp. 157–80, doi:<a href="https://doi.org/10.1007/978-3-030-23696-0_9">10.1007/978-3-030-23696-0_9</a>.
  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'
...