Paper 2013/746

Asymptotically Efficient Lattice-Based Digital Signatures

Vadim Lyubashevsky and Daniele Micciancio


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.

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.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in JOC 2018
Contact author(s)
lyubash @ di ens fr
2018-10-01: last of 2 revisions
2013-11-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Vadim Lyubashevsky and Daniele Micciancio},
      title = {Asymptotically Efficient Lattice-Based Digital Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2013/746},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.