DS ⇔ Forward-secure signature

Equivalence · fully-black-box reduction · standard model · folklore · security loss: a factor T from guessing the forgery period, from DS to forward-secure signature; none in the other direction

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.