Improved Short Lattice Signatures in the Standard Model

Léo Ducas; Daniele Micciancio

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-LWE signature standard model
Contact author(s): lducas @ eng ucsd edu
History: 2014-06-26: received
Short URL: https://ia.cr/2014/495
License: 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},
      url = {https://eprint.iacr.org/2014/495}
}