Paper 2014/495

Improved Short Lattice Signatures in the Standard Model

Léo Ducas and Daniele Micciancio


We present a signature scheme provably secure in the standard model (no random oracles) based on the worst-case complexity of approximating the Shortest Vector Problem in ideal lattices within polynomial factors. The distinguishing feature of our scheme is that it achieves short signatures (consisting of a single lattice vector), and relatively short public keys (consisting of O(log n) vectors.) Previous lattice schemes in the standard model with similarly short signatures, due to Boyen (PKC 2010) and Micciancio and Peikert (Eurocrypt 2012), had substantially longer public keys consisting of Ω(n) vectors (even when implemented with ideal lattices). We also present a variant of our scheme that further reduces the public key size to just O(log log n) vectors and allows for a tighther security proof by making the signer stateful.

Note: Full version

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2014
Ring-LWEsignaturestandard model
Contact author(s)
lducas @ eng ucsd edu
2014-06-26: received
Short URL
Creative Commons Attribution


      author = {Léo Ducas and Daniele Micciancio},
      title = {Improved Short Lattice Signatures in the Standard Model},
      howpublished = {Cryptology ePrint Archive, Paper 2014/495},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.