Paper 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.
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.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published by the IACR in JOC 2018
- Keywords
- signatureslattices
- Contact author(s)
- lyubash @ di ens fr
- History
- 2018-10-01: last of 2 revisions
- 2013-11-17: received
- See all versions
- Short URL
- https://ia.cr/2013/746
- License
-
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},
url = {https://eprint.iacr.org/2013/746}
}
