Paper 2014/495

Improved Short Lattice Signatures in the Standard Model

Léo Ducas and Daniele Micciancio

Abstract

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

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2014
Keywords
Ring-LWEsignaturestandard model
Contact author(s)
lducas @ eng ucsd edu
History
2014-06-26: received
Short URL
https://ia.cr/2014/495
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/495,
      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{https://eprint.iacr.org/2014/495}},
      url = {https://eprint.iacr.org/2014/495}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.