Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Ring-LWE, signature, standard model

Original Publication (with major differences): IACR-CRYPTO-2014

Date: received 21 Jun 2014

Contact author: lducas at eng ucsd edu

Available format(s): PDF | BibTeX Citation

Note: Full version

Version: 20140626:205625 (All versions of this report)

Short URL: ia.cr/2014/495

Discussion forum: Show discussion | Start new discussion