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

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

7 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 languageEnglish
Title of host publicationPublic-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings
EditorsMichel Abdalla, Ricardo Dahab
Place of PublicationBerlin
PublisherSpringer
Pages728-757
Number of pages30
ISBN (Print)9783319765778
DOIs
Publication statusPublished - 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

Keywords

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

Fingerprint Dive into the research topics of 'Rounded Gaussians: fast and secure constant-time sampling for lattice-based crypto'. Together they form a unique fingerprint.

Cite this