DS ⇔ Forward-secure signature
Statement
EUF-CMA-secure signature schemes exist if and only if, for every polynomially bounded , forward-secure signature schemes with periods exist — folklore. From a signature scheme : the key-evolving samples independent key pairs for and outputs and ; deletes the first remaining key, so that ; period signs with and verifies with . If is EUF-CMA-secure, the resulting scheme is forward-secure: for all efficient there is an efficient with . Conversely, the period- algorithms , and of a forward-secure scheme with periods form an EUF-CMA-secure signature scheme. Both constructions keep the message space and carry -correctness over, period by period — standard.
Sketch
A forward-security adversary that forges for period gives an EUF-CMA forger: guess , embed the challenge verification key as , answer period- signing queries with the signing oracle, and at the break-in in period hand over , which contains no key of index ; the guess is right with probability . Conversely, an EUF-CMA forger is run in period , after which the reduction updates once, breaks in during period , and outputs the forger’s message and signature for period .
Notes
- The verification key of this construction grows linearly in . BM99 describe generic constructions from any signature scheme with smaller keys, among them a binary tree of certificates of depth ; Kra00 gives another generic construction; MMM02 give efficient generic constructions in which need not be fixed at key generation.