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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Citaat (Scopus)

Uittreksel

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.

TaalEngels
TitelPublic-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings
RedacteurenM. Abdalla, R. Dahab
Plaats van productieBerlin
UitgeverijSpringer
Pagina's728-757
Aantal pagina's30
ISBN van geprinte versie9783319765778
DOI's
StatusGepubliceerd - 2018
Evenement21st IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2018) - Rio de Janeiro, Brazilië
Duur: 25 mrt 201829 mrt 2018
Congresnummer: 21
https://pkc.iacr.org/2018/

Publicatie series

NaamLecture Notes in Computer Science
Volume10769
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Congres

Congres21st IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2018)
Verkorte titelPKC2018
LandBrazilië
StadRio de Janeiro
Periode25/03/1829/03/18
Internet adres

Vingerafdruk

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

Trefwoorden

    Citeer dit

    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 (editors), Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings (blz. 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. redacteur / M. Abdalla ; R. Dahab. Berlin : Springer, 2018. blz. 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 (redactie), 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, blz. 728-757, Rio de Janeiro, Brazilië, 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. redactie / M. Abdalla; R. Dahab. Berlin : Springer, 2018. blz. 728-757 (Lecture Notes in Computer Science; Vol. 10769).

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer 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, redacteurs, Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings. Berlin: Springer. 2018. blz. 728-757. (Lecture Notes in Computer Science). Beschikbaar vanaf, DOI: 10.1007/978-3-319-76581-5_25