Rounded Gaussians: fast and secure constant-time sampling for lattice-based crypto

Andreas Hülsing; Tanja Lange; Kit Smeets

doi:10.1007/978-3-319-76581-5_25

Rounded Gaussians: fast and secure constant-time sampling for lattice-based crypto

Andreas Hülsing, Tanja Lange, Kit Smeets

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

9 Citations (Scopus)

Abstract

This paper suggests to use rounded Gaussians in place of discrete Gaussians in rejection-sampling-based lattice signature schemes like BLISS or Lyubashevsky’s signature scheme. We show that this distribution can efficiently be sampled from while additionally making it easy to sample in constant time, systematically avoiding recent timing-based side-channel attacks on lattice-based signatures. We show the effectiveness of the new sampler by applying it to BLISS, prove analogues of the security proofs for BLISS, and present an implementation that runs in constant time. Our implementation needs no precomputed tables and is twice as fast as the variable-time CDT sampler posted by the BLISS authors with precomputed tables.

Original language	English
Title of host publication	Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings
Editors	Michel Abdalla, Ricardo Dahab
Place of Publication	Berlin
Publisher	Springer
Pages	728-757
Number of pages	30
ISBN (Print)	9783319765778
DOIs	https://doi.org/10.1007/978-3-319-76581-5_25
Publication status	Published - 2018
Event	21st IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2018) - Rio de Janeiro, Brazil Duration: 25 Mar 2018 → 29 Mar 2018 Conference number: 21 https://pkc.iacr.org/2018/

Publication series

Name	Lecture Notes in Computer Science
Volume	10769
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	21st IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2018)
Abbreviated title	PKC2018
Country/Territory	Brazil
City	Rio de Janeiro
Period	25/03/18 → 29/03/18
Internet address	https://pkc.iacr.org/2018/

Keywords

BLISS
Constant-time implementations
Gaussian sampling
Lattice-based cryptography
Post-quantum cryptography
Signatures

Access to Document

10.1007/978-3-319-76581-5_25

https://eprint.iacr.org/2017/1025

Cite this

Hülsing, A., Lange, T., & Smeets, K. (2018). Rounded Gaussians: fast and secure constant-time sampling for lattice-based crypto. In M. Abdalla, & R. Dahab (Eds.), Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings (pp. 728-757). (Lecture Notes in Computer Science; Vol. 10769). Springer. https://doi.org/10.1007/978-3-319-76581-5_25

Hülsing, Andreas ; Lange, Tanja ; Smeets, Kit. / Rounded Gaussians : fast and secure constant-time sampling for lattice-based crypto. Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings. editor / Michel Abdalla ; Ricardo Dahab. Berlin : Springer, 2018. pp. 728-757 (Lecture Notes in Computer Science).

@inproceedings{78f6cf7dcb934feb95779aa5ff924b34,

title = "Rounded Gaussians: fast and secure constant-time sampling for lattice-based crypto",

abstract = "This paper suggests to use rounded Gaussians in place of discrete Gaussians in rejection-sampling-based lattice signature schemes like BLISS or Lyubashevsky{\textquoteright}s signature scheme. We show that this distribution can efficiently be sampled from while additionally making it easy to sample in constant time, systematically avoiding recent timing-based side-channel attacks on lattice-based signatures. We show the effectiveness of the new sampler by applying it to BLISS, prove analogues of the security proofs for BLISS, and present an implementation that runs in constant time. Our implementation needs no precomputed tables and is twice as fast as the variable-time CDT sampler posted by the BLISS authors with precomputed tables.",

keywords = "BLISS, Constant-time implementations, Gaussian sampling, Lattice-based cryptography, Post-quantum cryptography, Signatures",

author = "Andreas H{\"u}lsing and Tanja Lange and Kit Smeets",

year = "2018",

doi = "10.1007/978-3-319-76581-5_25",

language = "English",

isbn = "9783319765778",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "728--757",

editor = "Michel Abdalla and Ricardo Dahab",

booktitle = "Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings",

address = "Germany",

note = "21st IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2018), PKC2018 ; Conference date: 25-03-2018 Through 29-03-2018",

url = "https://pkc.iacr.org/2018/",

}

Hülsing, A , Lange, T & Smeets, K 2018, Rounded Gaussians: fast and secure constant-time sampling for lattice-based crypto. in M Abdalla & R Dahab (eds), Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings. Lecture Notes in Computer Science, vol. 10769, Springer, Berlin, pp. 728-757, 21st IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2018), Rio de Janeiro, Brazil, 25/03/18. https://doi.org/10.1007/978-3-319-76581-5_25

Rounded Gaussians : fast and secure constant-time sampling for lattice-based crypto. / Hülsing, Andreas ; Lange, Tanja; Smeets, Kit.

Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings. ed. / Michel Abdalla; Ricardo Dahab. Berlin : Springer, 2018. p. 728-757 (Lecture Notes in Computer Science; Vol. 10769).

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

TY - GEN

T1 - Rounded Gaussians

T2 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2018)

AU - Hülsing, Andreas

AU - Lange, Tanja

AU - Smeets, Kit

N1 - Conference code: 21

PY - 2018

Y1 - 2018

N2 - This paper suggests to use rounded Gaussians in place of discrete Gaussians in rejection-sampling-based lattice signature schemes like BLISS or Lyubashevsky’s signature scheme. We show that this distribution can efficiently be sampled from while additionally making it easy to sample in constant time, systematically avoiding recent timing-based side-channel attacks on lattice-based signatures. We show the effectiveness of the new sampler by applying it to BLISS, prove analogues of the security proofs for BLISS, and present an implementation that runs in constant time. Our implementation needs no precomputed tables and is twice as fast as the variable-time CDT sampler posted by the BLISS authors with precomputed tables.

AB - This paper suggests to use rounded Gaussians in place of discrete Gaussians in rejection-sampling-based lattice signature schemes like BLISS or Lyubashevsky’s signature scheme. We show that this distribution can efficiently be sampled from while additionally making it easy to sample in constant time, systematically avoiding recent timing-based side-channel attacks on lattice-based signatures. We show the effectiveness of the new sampler by applying it to BLISS, prove analogues of the security proofs for BLISS, and present an implementation that runs in constant time. Our implementation needs no precomputed tables and is twice as fast as the variable-time CDT sampler posted by the BLISS authors with precomputed tables.

KW - BLISS

KW - Constant-time implementations

KW - Gaussian sampling

KW - Lattice-based cryptography

KW - Post-quantum cryptography

KW - Signatures

UR - http://www.scopus.com/inward/record.url?scp=85044005900&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-76581-5_25

DO - 10.1007/978-3-319-76581-5_25

M3 - Conference contribution

AN - SCOPUS:85044005900

SN - 9783319765778

T3 - Lecture Notes in Computer Science

SP - 728

EP - 757

BT - Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings

A2 - Abdalla, Michel

A2 - Dahab, Ricardo

PB - Springer

CY - Berlin

Y2 - 25 March 2018 through 29 March 2018

ER -

Hülsing A , Lange T, Smeets K. Rounded Gaussians: fast and secure constant-time sampling for lattice-based crypto. In Abdalla M, Dahab R, editors, Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings. Berlin: Springer. 2018. p. 728-757. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-76581-5_25

Rounded Gaussians: fast and secure constant-time sampling for lattice-based crypto

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this