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

doi:10.1007/978-3-662-43414-7_20

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 proceeding › Conference contribution › Academic › peer-review

40 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 language	English
Title of host publication	Selected Areas in Cryptography - SAC 2013 (20th International Conference, Burnaby BC, Canada, August 14-16, 2013. Revised Selected Papers)
Editors	T. Lange, K. Lauter, P. Lisonek
Place of Publication	Berlin
Publisher	Springer
Pages	402-417
ISBN (Print)	978-3-662-43413-0
DOIs	https://doi.org/10.1007/978-3-662-43414-7_20
Publication status	Published - 2014
Event	20th International Conference on Selected Areas in Cryptography (SAC 2013) - Burnaby, Canada Duration: 14 Aug 2013 → 16 Aug 2013 Conference number: 20

Publication series

Name	Lecture Notes in Computer Science
Volume	8282
ISSN (Print)	0302-9743

Conference

Conference	20th International Conference on Selected Areas in Cryptography (SAC 2013)
Abbreviated title	SAC 2013
Country/Territory	Canada
City	Burnaby
Period	14/08/13 → 16/08/13

Access to Document

10.1007/978-3-662-43414-7_20

Cite this

Buchmann, J., Cabarcas, D., Göpfert, F., Hülsing, A. T., & Weiden, P. (2014). Discrete Ziggurat: A time-memory trade-off for sampling from a Gaussian distribution over the integers. In T. Lange, K. Lauter, & P. Lisonek (Eds.), Selected Areas in Cryptography - SAC 2013 (20th International Conference, Burnaby BC, Canada, August 14-16, 2013. Revised Selected Papers) (pp. 402-417). (Lecture Notes in Computer Science; Vol. 8282). Springer. https://doi.org/10.1007/978-3-662-43414-7_20

Buchmann, J. ; Cabarcas, D. ; Göpfert, F. et al. / Discrete Ziggurat: A time-memory trade-off for sampling from a Gaussian distribution over the integers. Selected Areas in Cryptography - SAC 2013 (20th International Conference, Burnaby BC, Canada, August 14-16, 2013. Revised Selected Papers). editor / T. Lange ; K. Lauter ; P. Lisonek. Berlin : Springer, 2014. pp. 402-417 (Lecture Notes in Computer Science).

@inproceedings{f6acbe6083cd426dbe4d16656dc85120,

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

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.",

author = "J. Buchmann and D. Cabarcas and F. G{\"o}pfert and A.T. H{\"u}lsing and P. Weiden",

year = "2014",

doi = "10.1007/978-3-662-43414-7_20",

language = "English",

isbn = "978-3-662-43413-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "402--417",

editor = "T. Lange and K. Lauter and P. Lisonek",

booktitle = "Selected Areas in Cryptography - SAC 2013 (20th International Conference, Burnaby BC, Canada, August 14-16, 2013. Revised Selected Papers)",

address = "Germany",

note = "20th International Conference on Selected Areas in Cryptography (SAC 2013), SAC 2013 ; Conference date: 14-08-2013 Through 16-08-2013",

}

Buchmann, J, Cabarcas, D, Göpfert, F, Hülsing, AT & Weiden, P 2014, Discrete Ziggurat: A time-memory trade-off for sampling from a Gaussian distribution over the integers. in T Lange, K Lauter & P Lisonek (eds), Selected Areas in Cryptography - SAC 2013 (20th International Conference, Burnaby BC, Canada, August 14-16, 2013. Revised Selected Papers). Lecture Notes in Computer Science, vol. 8282, Springer, Berlin, pp. 402-417, 20th International Conference on Selected Areas in Cryptography (SAC 2013), Burnaby, British Columbia, Canada, 14/08/13. https://doi.org/10.1007/978-3-662-43414-7_20

Discrete Ziggurat: A time-memory trade-off for sampling from a Gaussian distribution over the integers. / Buchmann, J.; Cabarcas, D.; Göpfert, F. et al.
Selected Areas in Cryptography - SAC 2013 (20th International Conference, Burnaby BC, Canada, August 14-16, 2013. Revised Selected Papers). ed. / T. Lange; K. Lauter; P. Lisonek. Berlin: Springer, 2014. p. 402-417 (Lecture Notes in Computer Science; Vol. 8282).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Buchmann, J.

AU - Cabarcas, D.

AU - Göpfert, F.

AU - Hülsing, A.T.

AU - Weiden, P.

N1 - Conference code: 20

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-662-43414-7_20

DO - 10.1007/978-3-662-43414-7_20

M3 - Conference contribution

SN - 978-3-662-43413-0

T3 - Lecture Notes in Computer Science

SP - 402

EP - 417

BT - Selected Areas in Cryptography - SAC 2013 (20th International Conference, Burnaby BC, Canada, August 14-16, 2013. Revised Selected Papers)

A2 - Lange, T.

A2 - Lauter, K.

A2 - Lisonek, P.

PB - Springer

CY - Berlin

T2 - 20th International Conference on Selected Areas in Cryptography (SAC 2013)

Y2 - 14 August 2013 through 16 August 2013

ER -

Buchmann J, Cabarcas D, Göpfert F, Hülsing AT, Weiden P. Discrete Ziggurat: A time-memory trade-off for sampling from a Gaussian distribution over the integers. In Lange T, Lauter K, Lisonek P, editors, Selected Areas in Cryptography - SAC 2013 (20th International Conference, Burnaby BC, Canada, August 14-16, 2013. Revised Selected Papers). Berlin: Springer. 2014. p. 402-417. (Lecture Notes in Computer Science). doi: 10.1007/978-3-662-43414-7_20

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

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this