Autotomic Signatures

International audienceDigital 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