Asymptotically Efficient Lattice-Based Digital Signatures

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.

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)
Category
Public-key cryptography
Publication info
Keywords
signatureslattices
Contact author(s)
lyubash @ di ens fr
History
2018-10-01: last of 2 revisions
See all versions
Short URL
https://ia.cr/2013/746

CC BY

BibTeX

@misc{cryptoeprint:2013/746,
author = {Vadim Lyubashevsky and Daniele Micciancio},
title = {Asymptotically Efficient Lattice-Based Digital Signatures},
howpublished = {Cryptology ePrint Archive, Paper 2013/746},
year = {2013},
note = {\url{https://eprint.iacr.org/2013/746}},
url = {https://eprint.iacr.org/2013/746}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.