You are looking at a specific version 20131220:160708 of this paper. See the latest version.

Paper 2013/856

Tightly-Secure Signatures From Lossy Identification Schemes

Michel Abdalla and Pierre-Alain Fouque and Vadim Lyubashevsky and Mehdi Tibouchi

Abstract

In this paper we present three digital signature schemes with tight security reductions. Our first signature scheme is a particularly efficient version of the short exponent discrete log based scheme of Girault et al. (J. of Cryptology 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 (Asiacrypt 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.

Note: Full, corrected version of the extended abstract presented at EUROCRYPT 2012.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2012
Keywords
Signature schemestight reductionsFiat-Shamir
Contact author(s)
mehdi tibouchi @ normalesup org
History
2013-12-20: received
Short URL
https://ia.cr/2013/856
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.