### Tighter Reductions for Forward-Secure Signature Schemes

Michel Abdalla, Fabrice Benhamouda, and David Pointcheval

##### Abstract

In this paper, we revisit the security of factoring-based signature schemes built via the Fiat-Shamir transform and show that they can admit tighter reductions to certain decisional complexity assumptions such as the quadratic-residuosity, the high-residuosity, and the $\phi$-hiding assumptions. We do so by proving that the underlying identification schemes used in these schemes are a particular case of the lossy identification notion recently introduced by Abdalla et al. at Eurocrypt 2012. Next, we show how to extend these results to the forward-security setting based on ideas from the Itkis-Reyzin forward-secure signature scheme. Unlike the original Itkis-Reyzin scheme, our construction can be instantiated under different decisional complexity assumptions and has a much tighter security reduction. Finally, we show that the tighter security reductions provided by our proof methodology can result in concrete efficiency gains in practice, both in the standard and forward-security setting, as long as the use of stronger security assumptions is deemed acceptable. All of our results hold in the random oracle model.

Available format(s)
Category
Public-key cryptography
Publication info
DOI
10.1007/978-3-642-36362-7_19
Keywords
Forward-securitysignatureslossy identification
Contact author(s)
fabrice ben hamouda @ ens fr
History
Short URL
https://ia.cr/2015/196

CC BY

BibTeX

@misc{cryptoeprint:2015/196,
author = {Michel Abdalla and Fabrice Benhamouda and David Pointcheval},
title = {Tighter Reductions for Forward-Secure Signature Schemes},
howpublished = {Cryptology ePrint Archive, Paper 2015/196},
year = {2015},
doi = {10.1007/978-3-642-36362-7_19},
note = {\url{https://eprint.iacr.org/2015/196}},
url = {https://eprint.iacr.org/2015/196}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.