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

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

1 Citation (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.

LanguageEnglish
Title of host publicationPublic-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings
EditorsM. Abdalla, R. Dahab
Place of PublicationBerlin
PublisherSpringer
Pages728-757
Number of pages30
ISBN (Print)9783319765778
DOIs
StatePublished - 2018
Event21st IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2018) - Rio de Janeiro, Brazil
Duration: 25 Mar 201829 Mar 2018
Conference number: 21
https://pkc.iacr.org/2018/

Publication series

NameLecture Notes in Computer Science
Volume10769
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2018)
Abbreviated titlePKC2018
CountryBrazil
CityRio de Janeiro
Period25/03/1829/03/18
Internet address

Fingerprint

Signature Scheme
Time Constant
Tables
Rejection Sampling
Sampling
Security Proof
Side Channel Attacks
Timing
Signature
Analogue
Side channel attack

Keywords

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

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). Berlin: Springer. DOI: 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 / M. Abdalla ; R. 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’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 = "M. Abdalla and R. Dahab",
booktitle = "Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings",
address = "Germany",

}

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. DOI: 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. / M. Abdalla; R. Dahab. Berlin : Springer, 2018. p. 728-757 (Lecture Notes in Computer Science; Vol. 10769).

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

TY - GEN

T1 - Rounded Gaussians

T2 - fast and secure constant-time sampling for lattice-based crypto

AU - Hülsing,Andreas

AU - Lange,Tanja

AU - Smeets,Kit

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

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

PB - Springer

CY - Berlin

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). Available from, DOI: 10.1007/978-3-319-76581-5_25