Skip to Main content Skip to Navigation
Book sections

Autotomic Signatures

David Naccache 1, 2 David Pointcheval 2, 1, 3
1 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, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : Digital signature security is classically defined as an interaction between a signer , a verifier and an attacker A . A submits adaptively to a sequence of messages m 1,…,m q to which replies with the signatures U = {σ 1,…,σ q }. Given U, A attempts to produce a forgery, i.e. a pair (m′,σ′) such that and σ′∉U . The traditional approach consists in hardening against a large query bound q. Interestingly, this is one specific way to prevent A from winning the forgery game. This work explores an alternative option. Rather than hardening , we weaken A by preventing him from influencing ’s input: upon receiving m i , will generate a fresh ephemeral signature key-pair , use to sign m i , erase , and output the signature and a certificate on computed using the long-term key . In other words, will only use his permanent secret to sign inputs which are beyond A ’s control (namely, freshly generated public-keys). As the are ephemeral, q = 1 by construction. We show that this paradigm, called autotomic signatures, transforms weakly secure signature schemes (secure against generic attacks only) into strongly secure ones (secure against adaptively chosen-message attacks). As a by-product of our analysis, we show that blending public key information with the signed message can significantly increase security.
Document type :
Book sections
Complete list of metadata
Contributor : Brigitte Briot <>
Submitted on : Thursday, January 29, 2015 - 10:13:42 AM
Last modification on : Tuesday, May 4, 2021 - 2:06:02 PM




David Naccache, David Pointcheval. Autotomic Signatures. David Naccache. Cryptography and Security: From Theory to Applications : Essays Dedicated to Jean-Jacques Quisquater on the Occasion of His 65th Birthday, 6805, Springer, pp.143-155, 2012, LNCS - Lecture Notes in Computer Science, 978-3-642-28367-3. ⟨10.1007/978-3-642-28368-0_12⟩. ⟨hal-01110874⟩



Record views