BLISS signature scheme
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, digital signature ensures that a message is authentically from a specific person who has the private key to create such signature, and such signature can be verified using the corresponding public key. Current signature schemes relies on one of integer factorization, discrete logarithm, and elliptic curve discrete logarithm problem, 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 given at NIST has therefore anticipated that BLISS be further refined and become a potential candidate for standardization.
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.
- 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.