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 | M. Abdalla, R. Dahab |
| Place of Publication | Berlin |
| Publisher | Springer |
| Pages | 728-757 |
| Number of pages | 30 |
| ISBN (Print) | 9783319765778 |
| DOIs | |
| 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 | Brazil |
| City | Rio de Janeiro |
| Period | 25/03/18 → 29/03/18 |
| Internet address |
Fingerprint
Keywords
- BLISS
- Constant-time implementations
- Gaussian sampling
- Lattice-based cryptography
- Post-quantum cryptography
- Signatures
Cite this
}
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 proceeding › Conference contribution › Academic › peer-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
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, M.
A2 - Dahab, R.
PB - Springer
CY - Berlin
ER -