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, 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