Cryptology ePrint Archive: Report 2013/746

Asymptotically Efficient Lattice-Based Digital Signatures

Vadim Lyubashevsky and Daniele Micciancio

Abstract: We present a general framework that converts certain types of linear collision-resistant hash functions into one-time signatures. Our generic construction can be instantiated based on both general and ideal (e.g. cyclic) lattices, and the resulting signature schemes are provably secure based on the worst-case hardness of approximating the shortest vector (and other standard lattice problems) in the corresponding class of lattices to within a polynomial factor. When instantiated with ideal lattices, the time complexity of the signing and verification algorithms, as well as key and signature size is almost linear (up to poly-logarithmic factors) in the dimension n of the underlying lattice. Since no sub-exponential (in n) time algorithm is known to solve lattice problems in the worst case, even when restricted to ideal lattices, our construction gives a digital signature scheme with an essentially optimal performance/security trade-off.

Category / Keywords: public-key cryptography / signatures, lattices

Original Publication (with major differences): IACR-TCC-2008

Date: received 13 Nov 2013, last revised 22 Dec 2013

Contact author: lyubash at di ens fr

Available format(s): PDF | BibTeX Citation

Note: A preliminary version of this work appeared at TCC 2008. This is an expanded and simplified version of that work.

Version: 20131223:043015 (All versions of this report)

Short URL: ia.cr/2013/746

Discussion forum: Show discussion | Start new discussion