Cryptology ePrint Archive: Report 2013/838
An improved compression technique for signatures based on learning with errors
Shi Bai and Steven D. Galbraith
Abstract: We present a new approach to the compression technique of Lyubashevsky et al for lattice-based signatures based on learning with errors (LWE).
Our ideas seem to be particularly suitable for signature schemes whose security, in the random oracle model, is based on standard worst-case computational assumptions. Our signatures are shorter than any previous proposal for provably-secure signatures based on standard lattice problems: at the 128-bit level we improve signature size from (more than) 16500 bits to around 9000 to 12000 bits.
Category / Keywords: secret-key cryptography / Lattice-based signatures, learning with errors
Original Publication (with major differences): J. Benaloh (Ed.), CT-RSA 2014, LNCS 8366 (2014) 28--47.
Date: received 11 Dec 2013, last revised 22 Jan 2014
Contact author: S Galbraith at math auckland ac nz
Available format(s): PDF | BibTeX Citation
Note: This is the full version of the paper, with additional proofs and information and discussion.
Version: 20140122:212655 (All versions of this report)
Short URL: ia.cr/2013/838
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]