eprint.iacr.org will be offline for approximately an hour for routine maintenance again at 10pm UTC on Wednesday, April 17.

Paper 2017/746

On the Tightness of Forward-Secure Signature Reductions

Michel Abdalla, Fabrice Benhamouda, and David Pointcheval


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. Moreover, we also 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. Finally, we investigate the design of forward-secure signature schemes whose security reductions are fully tight.

Note: An abridged version of this paper appeared in the proceedings of PKC 2013. In this version, we give more precise and formal security definitions and statements, we include complete proofs of security, and we provide new impossibility and existential results for tight forward-secure signature schemes. Please see the publication note at the end of the introduction for more details.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in PKC 2013
Forward-securitysignatureslossy identification
Contact author(s)
fabrice benhamouda @ normalesup org
2017-08-07: received
Short URL
Creative Commons Attribution


      author = {Michel Abdalla and Fabrice Benhamouda and David Pointcheval},
      title = {On the Tightness of Forward-Secure Signature Reductions},
      howpublished = {Cryptology ePrint Archive, Paper 2017/746},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/746}},
      url = {https://eprint.iacr.org/2017/746}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.