Published in

Springer, Journal of Cryptology, 3(29), p. 597-631, 2015

DOI: 10.1007/s00145-015-9203-7

Springer, Lecture Notes in Computer Science, p. 572-590, 2012

DOI: 10.1007/978-3-642-29011-4_34

Links

Tools

Export citation

Search in Google Scholar

Tightly Secure Signatures From Lossy Identification Schemes

Journal article published in 2012 by Michel Abdalla ORCID, Pierre-Alain Fouque, Vadim Lyubashevsky, Mehdi Tibouchi
This paper is made freely available by the publisher.
This paper is made freely available by the publisher.

Full text: Download

Green circle
Preprint: archiving allowed
Upload
Orange circle
Postprint: archiving restricted
Upload
Red circle
Published version: archiving forbidden
Policy details
Data provided by SHERPA/RoMEO

Abstract

In this paper, we present three digital signature schemes with tight security reductions in the random oracle model. Our first signature scheme is a particularly efficient version of the short exponent discrete log-based scheme of Girault et al. (J Cryptol 19(4):463–487, 2006). Our scheme has a tight reduction to the decisional short discrete logarithm problem, while still maintaining the non-tight reduction to the computational version of the problem upon which the original scheme of Girault et al. is based. The second signature scheme we construct is a modification of the scheme of Lyubashevsky (Advances in Cryptology—ASIACRYPT 2009, vol 5912 of Lecture Notes in Computer Science, pp 598–616, Tokyo, Japan, December 6–10, 2009. Springer, Berlin, 2009) that is based on the worst-case hardness of the shortest vector problem in ideal lattices. And the third scheme is a very simple signature scheme that is based directly on the hardness of the subset sum problem. We also present a general transformation that converts what we term lossy identification schemes into signature schemes with tight security reductions. We believe that this greatly simplifies the task of constructing and proving the security of such signature schemes.