Generalized Centered Binomial Distribution for Bimodal Lattice Signatures
In CRYPTO 2013, Ducas et al. introduced a bimodal discrete Gaussian distribution into the Fiat-Shamir with abort paradigm, proposing a signature scheme called BLISS, which significantly improved rejection sampling efficiency and reduced the number of required abort steps compared to all previously p...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2025-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10817596/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841557049386729472 |
|---|---|
| author | Seungwoo Lee Joo Woo Jonghyun Kim Jong Hwan Park |
| author_facet | Seungwoo Lee Joo Woo Jonghyun Kim Jong Hwan Park |
| author_sort | Seungwoo Lee |
| collection | DOAJ |
| description | In CRYPTO 2013, Ducas et al. introduced a bimodal discrete Gaussian distribution into the Fiat-Shamir with abort paradigm, proposing a signature scheme called BLISS, which significantly improved rejection sampling efficiency and reduced the number of required abort steps compared to all previously proposed (uni-modal) lattice-based signature schemes. Although the theoretical structure of the bimodal distribution is elegant, the BLISS implementation suffers from several side-channel vulnerabilities. The primary issue arises from the fact that the probability mass function of the bimodal discrete Gaussian distribution is a transcendental function, which makes it difficult to implement solely with integers in constant-time. To address this issue, we introduce a new distribution called ‘Generalized Centered Binomial Distribution (GCBD)’ that can replace the (bimodal) discrete Gaussian distribution. As a generalized form of the centered binomial distribution (CBD), GCBD is simple and efficient in sampling integers from distributions with large standard deviations. GCBD sampling consists of sampling uniformly random bit-strings and integer addition/subtraction operations, allowing for efficient constant-time implementation. Furthermore, bimodal rejection sampling using GCBD can be implemented only with integer operations in constant-time, with the help of the Newton-Raphson method. By incorporating the bimodal GCBD rejection sampling into BLISS, we present a new variant of BLISS that can be implemented in constant-time, thereby eliminating the side-channel vulnerabilities associated with timing attacks. Finally, we compare the performance of our variant to GALACTICS, a previous constant-time implementation of BLISS. While the signing algorithm of our variant is about 3.3 times slower than that of GALACTICS, GCBD can serve as an alternative to the discrete Gaussian distribution for designing bimodal lattice signatures. |
| format | Article |
| id | doaj-art-d1be277c66f44a57aad27406e326f9cf |
| institution | Kabale University |
| issn | 2169-3536 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-d1be277c66f44a57aad27406e326f9cf2025-01-07T00:01:51ZengIEEEIEEE Access2169-35362025-01-01132203221410.1109/ACCESS.2024.352352110817596Generalized Centered Binomial Distribution for Bimodal Lattice SignaturesSeungwoo Lee0https://orcid.org/0009-0000-9985-1865Joo Woo1https://orcid.org/0000-0002-9415-5200Jonghyun Kim2https://orcid.org/0000-0003-0958-392XJong Hwan Park3https://orcid.org/0000-0003-2742-6119School of Cybersecurity, Korea University, Seoul, South KoreaSchool of Cybersecurity, Korea University, Seoul, South KoreaSchool of Cybersecurity, Korea University, Seoul, South KoreaDepartment of Computer Science, Sangmyung University, Seoul, South KoreaIn CRYPTO 2013, Ducas et al. introduced a bimodal discrete Gaussian distribution into the Fiat-Shamir with abort paradigm, proposing a signature scheme called BLISS, which significantly improved rejection sampling efficiency and reduced the number of required abort steps compared to all previously proposed (uni-modal) lattice-based signature schemes. Although the theoretical structure of the bimodal distribution is elegant, the BLISS implementation suffers from several side-channel vulnerabilities. The primary issue arises from the fact that the probability mass function of the bimodal discrete Gaussian distribution is a transcendental function, which makes it difficult to implement solely with integers in constant-time. To address this issue, we introduce a new distribution called ‘Generalized Centered Binomial Distribution (GCBD)’ that can replace the (bimodal) discrete Gaussian distribution. As a generalized form of the centered binomial distribution (CBD), GCBD is simple and efficient in sampling integers from distributions with large standard deviations. GCBD sampling consists of sampling uniformly random bit-strings and integer addition/subtraction operations, allowing for efficient constant-time implementation. Furthermore, bimodal rejection sampling using GCBD can be implemented only with integer operations in constant-time, with the help of the Newton-Raphson method. By incorporating the bimodal GCBD rejection sampling into BLISS, we present a new variant of BLISS that can be implemented in constant-time, thereby eliminating the side-channel vulnerabilities associated with timing attacks. Finally, we compare the performance of our variant to GALACTICS, a previous constant-time implementation of BLISS. While the signing algorithm of our variant is about 3.3 times slower than that of GALACTICS, GCBD can serve as an alternative to the discrete Gaussian distribution for designing bimodal lattice signatures.https://ieeexplore.ieee.org/document/10817596/Post-quantum cryptographylattice-based signaturesbimodalbinomial distribution |
| spellingShingle | Seungwoo Lee Joo Woo Jonghyun Kim Jong Hwan Park Generalized Centered Binomial Distribution for Bimodal Lattice Signatures IEEE Access Post-quantum cryptography lattice-based signatures bimodal binomial distribution |
| title | Generalized Centered Binomial Distribution for Bimodal Lattice Signatures |
| title_full | Generalized Centered Binomial Distribution for Bimodal Lattice Signatures |
| title_fullStr | Generalized Centered Binomial Distribution for Bimodal Lattice Signatures |
| title_full_unstemmed | Generalized Centered Binomial Distribution for Bimodal Lattice Signatures |
| title_short | Generalized Centered Binomial Distribution for Bimodal Lattice Signatures |
| title_sort | generalized centered binomial distribution for bimodal lattice signatures |
| topic | Post-quantum cryptography lattice-based signatures bimodal binomial distribution |
| url | https://ieeexplore.ieee.org/document/10817596/ |
| work_keys_str_mv | AT seungwoolee generalizedcenteredbinomialdistributionforbimodallatticesignatures AT joowoo generalizedcenteredbinomialdistributionforbimodallatticesignatures AT jonghyunkim generalizedcenteredbinomialdistributionforbimodallatticesignatures AT jonghwanpark generalizedcenteredbinomialdistributionforbimodallatticesignatures |