On the Tightness of Forward-Secure Signature Reductions

Michel Abdalla 1, 2, 3, 4 Fabrice Benhamouda 5 David Pointcheval 1, 2, 3, 4
4 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria de Paris
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 ϕ ϕ -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.
Type de document :
[Research Report] Report 2017/746, IACR Cryptology ePrint Archive. 2017
Liste complète des métadonnées

Contributeur : Michel Abdalla <>
Soumis le : mardi 19 décembre 2017 - 10:27:44
Dernière modification le : vendredi 16 mars 2018 - 14:44:02


  • HAL Id : hal-01667150, version 1




Michel Abdalla, Fabrice Benhamouda, David Pointcheval. On the Tightness of Forward-Secure Signature Reductions. [Research Report] Report 2017/746, IACR Cryptology ePrint Archive. 2017. 〈hal-01667150〉



Consultations de la notice