Fiat-Shamir with aborts: applications to lattice and factoring-based signatures. (English) Zbl 1267.94125

Matsui, Mitsuru (ed.), Advances in cryptology – ASIACRYPT 2009. 15th international conference on the theory and application of cryptology and information security, Tokyo, Japan, December 6–10, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-10365-0/pbk). Lecture Notes in Computer Science 5912, 598-616 (2009).
Summary: We demonstrate how the framework that is used for creating efficient number-theoretic ID and signature schemes can be transferred into the setting of lattices. This results in constructions of the most efficient to-date identification and signature schemes with security based on the worst-case hardness of problems in ideal lattices. In particular, our ID scheme has communication complexity of around 65,000 bits and the length of the signatures produced by our signature scheme is about 50,000 bits. All prior lattice-based identification schemes required on the order of millions of bits to be transferred, while all previous lattice-based signature schemes were either stateful, too inefficient, or produced signatures whose lengths were also on the order of millions of bits. The security of our identification scheme is based on the hardness of finding the approximate shortest vector to within a factor of \(\tilde{O}(n^2)\) in the standard model, while the security of the signature scheme is based on the same assumption in the random oracle model. Our protocols are very efficient, with all operations requiring \(\tilde{O}(n)\) time.
We also show that the technique for constructing our lattice-based schemes can be used to improve certain number-theoretic schemes. In particular, we are able to shorten the length of the signatures that are produced by Girault’s factoring-based digital signature scheme.
For the entire collection see [Zbl 1177.94014].


94A62 Authentication, digital signatures and secret sharing


Full Text: DOI