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
A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature, where the prerequisites are satisfied, gives a recipient very high confidence that the message was created b ...
ensures that a message is authentically from a specific person who has the
private key
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
to create such a signature, and can be verified using the corresponding
public key
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
. Current signature schemes rely either on
integer factorization
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization.
When the numbers are suf ...
,
discrete logarithm
In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b' ...
or
elliptic curve
In mathematics, an elliptic curve is a smooth, projective, algebraic curve of genus one, on which there is a specified point . An elliptic curve is defined over a field and describes points in , the Cartesian product of with itself. If ...
discrete logarithm problem, all of which can be effectively attacked by a
quantum computer
Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...
. 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.
presentationonce anticipated that BLISS would become a potential candidate for standardization, however it was not submitted to NIST.
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
In post-quantum cryptography, ring learning with errors (RLWE) is a computational problem which serves as the foundation of new cryptographic algorithms, such as NewHope, designed to protect against cryptanalysis by quantum computers and also to ...
*
Ring Learning with Errors Signature
References
{{reflist
* 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
Post-quantum cryptography
Lattice-based cryptography
Public-key cryptography