BLISS signature scheme explained

BLISS (short for Bimodal Lattice Signature Scheme) is a digital signature scheme proposed by Léo Ducas, Alain Durmus, Tancrède Lepoint and Vadim Lyubashevsky in their 2013 paper "Lattice Signature and Bimodal Gaussians".

In cryptography, a digital signature ensures that a message is authentically from a specific person who has the private key to create such a signature, and can be verified using the corresponding public key. Current signature schemes rely either on integer factorization, discrete logarithm or elliptic curve discrete logarithm problem, all of which can be effectively attacked by a quantum computer. BLISS on the other hand, is a post-quantum algorithm, and is meant to resist quantum computer attacks.

Compared to other post-quantum schemes, BLISS claims to offer better computational efficiency, smaller signature size, and higher security. A presentation once anticipated that BLISS would become a potential candidate for standardization, however it was not submitted to NIST. NIST's criteria for selecting schemes to standardize includes side-channel resistance. However, BLISS and derivative schemes like GALACTICS have shown vulnerabilities to a number of side-channel and timing attacks. ^{[1] [2] [3] [4]}

Features

• Lower Rejection Rate: As a Fiat-Shamir lattice signature scheme, BLISS improves upon previous ones by replacing uniform and discrete Gaussian sampling with bimodal samples, thereby reducing sampling rejection rate.
• Memory-Efficient Gaussian Sampling: In the paper describing BLISS, the authors constructed a discrete Gaussian sampler of arbitrary standard deviation, from a sampler of a fixed standard deviation then rejecting samples based on pre-computed Bernoulli constants.
• Signature Compression: As the coefficients of the signature polynomials are distributed according to discrete Gaussian, the final signature can be compressed using Huffman coding.

See also

• Ring Learning with Errors
• Ring Learning with Errors Signature

References

• https://web.archive.org/web/20151006213007/http://bliss.di.ens.fr/
• https://eprint.iacr.org/2013/383.pdf
• http://csrc.nist.gov/groups/ST/post-quantum-2015/papers/session9-oneill-paper.pdf

Notes and References

1. Leon Groot Bruinderink, Andreas Hülsing, Tanja Lange, and Yuval Yarom. [Flush, Gauss, and Reload -- A Cache Attack on the BLISS Lattice-Based Signature Scheme.] Cryptographic Hardware and Embedded Systems - 18th International Conference (2016): 323-345
2. Tibouchi, Mehdi and Alexandre Wallet. [One Bit is All It Takes: A Devastating Timing Attack on BLISS’s Non-Constant Time Sign Flips.] Journal of Mathematical Cryptology 15(1) (2020): 131-142
3. Thomas Espitau, Pierre-Alain Fouque, Benoit Gerard, and Mehdi Tibouchi. [Side-Channel Attacks on BLISS Lattice-Based Signatures -- Exploiting Branch Tracing Against strongSwan and Electromagnetic Emanations in Microcontrollers.] Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (2017): 1857–1874
4. Soundes Marzougui, Nils Wisiol, Patrick Gersch, Juliane Krämer, andJean-Pierre Seifert. [Machine-Learning Side-Channel Attacks on the GALACTICS Constant-Time Implementation of BLISS.] Proceedings of the 17th International Conference on Availability, Reliability and Security (2022) 34: 1–11