You are looking at a specific version 20171018:150849 of this paper. See the latest version.

Paper 2011/537

Lattice Signatures Without Trapdoors

Vadim Lyubashevsky

Abstract

We provide an alternative method for constructing lattice-based digital signatures which does not use the ``hash-and-sign'' methodology of Gentry, Peikert, and Vaikuntanathan (STOC 2008). Our resulting signature scheme is secure, in the random oracle model, based on the worst-case hardness of the $\tilde{O}(n^{1.5})-SIVP$ problem in general lattices. The secret key, public key, and the signature size of our scheme are smaller than in all previous instantiations of the hash-and-sign signature, and our signing algorithm is also much simpler, requiring just a few matrix-vector multiplications and rejection samplings. We then also show that by slightly changing the parameters, one can get even more efficient signatures that are based on the hardness of the Learning With Errors problem. Our construction naturally transfers to the ring setting, where the size of the public and secret keys can be significantly shrunk, which results in the most practical to-date provably secure signature scheme based on lattices.

Note: Small mistakes corrected: Added sqrt(m) to the statement of Lemma 3.7. Changed >0 to >1 in item 3 of Lemma 4.4.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Full version of paper appearing at Eurocrypt 2012
Keywords
Lattice-Based CryptographyDigital SignaturesKnapsacksLearning With Errors
Contact author(s)
vadim lyubash @ gmail com
History
2017-10-18: last of 5 revisions
2011-10-03: received
See all versions
Short URL
https://ia.cr/2011/537
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.