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 verification 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 (in the same form): IACR-JOC-2018

Date: received 13 Nov 2013, last revised 1 Oct 2018

Contact author: lyubash at di ens fr

Available format(s): PDF | BibTeX Citation

Note: A version of this work appeared at TCC 2008. This is an expanded and simplified version of that work that appears in JoC 2018.

Version: 20181001:062200 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]