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

Coding Theory and Cryptology

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

41 Citaten (Scopus)

1 Downloads (Pure)

Samenvatting

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.

Originele taal-2	Engels
Titel	Selected Areas in Cryptography - SAC 2013 (20th International Conference, Burnaby BC, Canada, August 14-16, 2013. Revised Selected Papers)
Redacteuren	T. Lange, K. Lauter, P. Lisonek
Plaats van productie	Berlin
Uitgeverij	Springer
Pagina's	402-417
ISBN van geprinte versie	978-3-662-43413-0
DOI's	https://doi.org/10.1007/978-3-662-43414-7_20
Status	Gepubliceerd - 2014
Evenement	20th International Conference on Selected Areas in Cryptography (SAC 2013) - Burnaby, Canada Duur: 14 aug. 2013 → 16 aug. 2013 Congresnummer: 20

Publicatie series

Naam	Lecture Notes in Computer Science
Volume	8282
ISSN van geprinte versie	0302-9743

Congres

Congres	20th International Conference on Selected Areas in Cryptography (SAC 2013)
Verkorte titel	SAC 2013
Land/Regio	Canada
Stad	Burnaby
Periode	14/08/13 → 16/08/13
Ander	20th International Conference on Selected Areas in Cryptography

Toegang tot document

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

Citeer dit

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 (editors), Selected Areas in Cryptography - SAC 2013 (20th International Conference, Burnaby BC, Canada, August 14-16, 2013. Revised Selected Papers) (blz. 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). redacteur / T. Lange ; K. Lauter ; P. Lisonek. Berlin : Springer, 2014. blz. 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 (redactie), 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, blz. 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). redactie / T. Lange; K. Lauter; P. Lisonek. Berlin: Springer, 2014. blz. 402-417 (Lecture Notes in Computer Science; Vol. 8282).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › 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, redacteurs, Selected Areas in Cryptography - SAC 2013 (20th International Conference, Burnaby BC, Canada, August 14-16, 2013. Revised Selected Papers). Berlin: Springer. 2014. blz. 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

Samenvatting

Publicatie series

Congres

Toegang tot document

Vingerafdruk

Citeer dit