Cryptology ePrint Archive: Report 2013/383
Lattice Signatures and Bimodal Gaussians
Léo Ducas and Alain Durmus and Tancrède Lepoint and Vadim Lyubashevsky
Abstract: Our main result is a construction of a lattice-based digital signature scheme that represents an improvement, both in theory and in practice, over today's most efficient
lattice schemes. The novel scheme is obtained as a result of a modification of the rejection sampling algorithm that is at the heart of Lyubashevsky's signature scheme (Eurocrypt, 2012) and several other lattice primitives. Our new rejection sampling algorithm which samples from a bimodal Gaussian distribution, combined with a modified
scheme instantiation, ends up reducing the standard deviation of the resulting
signatures by a factor that is asymptotically square root in the security
parameter. The implementations of our signature scheme for security levels of
128, 160, and 192 bits compare very favorably to existing schemes such as
RSA and ECDSA in terms of efficiency. In addition, the new scheme has shorter
signature and public key sizes than all previously proposed lattice signature
schemes.
As part of our implementation, we also designed several novel algorithms which
could be of independent interest. Of particular note, is a new algorithm for
efficiently generating discrete Gaussian samples over Z^n. Current
algorithms either require many high-precision floating point exponentiations
or the storage of very large pre-computed tables, which makes them completely
inappropriate for usage in constrained devices. Our sampling algorithm
reduces the hard-coded table sizes from linear to logarithmic as compared to
the time-optimal implementations, at the cost of being only a small factor
slower.
Category / Keywords: public-key cryptography / digital signatures, public-key cryptography, lattice techniques
Original Publication (with major differences): IACR-CRYPTO-2013
Date: received 12 Jun 2013, last revised 10 Dec 2013
Contact author: tancrede lepoint at cryptoexperts com
Available format(s): PDF | BibTeX Citation
Version: 20131210:164427 (All versions of this report)
Short URL: ia.cr/2013/383
[ Cryptology ePrint archive ]