Discrete Ziggurat: A time-memory trade-off for sampling from a Gaussian distribution over the integers

J. Buchmann, D. Cabarcas, F. Göpfert, A.T. Hülsing, P. Weiden

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

30 Citations (Scopus)
1 Downloads (Pure)

Abstract

Several lattice-based cryptosystems require to sample from a discrete Gaussian distribution over the integers. Existing methods to sample from such a distribution either need large amounts of memory or they are very slow. In this paper we explore a different method that allows for a flexible time-memory trade-off, offering developers freedom in choosing how much space they can spare to store precomputed values. We prove that the generated distribution is close enough to a discrete Gaussian to be used in lattice-based cryptography. Moreover, we report on an implementation of the method and compare its performance to existing methods from the literature. We show that for large standard deviations, the Ziggurat algorithm outperforms all existing methods.
Original languageEnglish
Title of host publicationSelected Areas in Cryptography - SAC 2013 (20th International Conference, Burnaby BC, Canada, August 14-16, 2013. Revised Selected Papers)
EditorsT. Lange, K. Lauter, P. Lisonek
Place of PublicationBerlin
PublisherSpringer
Pages402-417
ISBN (Print)978-3-662-43413-0
DOIs
Publication statusPublished - 2014
Event20th International Conference on Selected Areas in Cryptography (SAC 2013) - Burnaby, Canada
Duration: 14 Aug 201316 Aug 2013
Conference number: 20

Publication series

NameLecture Notes in Computer Science
Volume8282
ISSN (Print)0302-9743

Conference

Conference20th International Conference on Selected Areas in Cryptography (SAC 2013)
Abbreviated titleSAC 2013
CountryCanada
CityBurnaby
Period14/08/1316/08/13

Fingerprint Dive into the research topics of 'Discrete Ziggurat: A time-memory trade-off for sampling from a Gaussian distribution over the integers'. Together they form a unique fingerprint.

Cite this