Paper 2013/838

An improved compression technique for signatures based on learning with errors

Shi Bai and Steven D. Galbraith


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.

Note: This is the full version of the paper, with additional proofs and information and discussion.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. MAJOR revision.J. Benaloh (Ed.), CT-RSA 2014, LNCS 8366 (2014) 28--47.
Lattice-based signatureslearning with errors
Contact author(s)
S Galbraith @ math auckland ac nz
2014-01-22: revised
2013-12-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shi Bai and Steven D.  Galbraith},
      title = {An improved compression technique for signatures based on learning with errors},
      howpublished = {Cryptology ePrint Archive, Paper 2013/838},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.