Lattice signatures without trapdoors. (English) Zbl 1295.94111

Pointcheval, David (ed.) et al., Advances in cryptology – EUROCRYPT 2012. 31st annual international conference on the theory and applications of cryptographic techniques, Cambridge, UK, April 15–19, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-29010-7/pbk). Lecture Notes in Computer Science 7237, 738-755 (2012).
Summary: We provide an alternative method for constructing lattice-based digital signatures which does not use the “hash-and-sign” methodology of C. Gentry, C. Peikert and V. Vaikuntanathan [“Trapdoors for hard lattices and new cryptographic constructions” [extended abstract]. STOC 2008, ACM, New York, 197–206 (2008; Zbl 1231.68124)]. Our resulting signature scheme is secure, in the random oracle model, based on the worst-case hardness of the \(\sim 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 quite simple, 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.
For the entire collection see [Zbl 1239.94002].


94A60 Cryptography
68P25 Data encryption (aspects in computer science)


Zbl 1231.68124
Full Text: DOI