DS ⇒ Selectively unforgeable DS

Fully-black-box reduction · standard model · folklore · security loss: none

Statement

Let be an EUF-CMA-unforgeable signature scheme. If its message space depends on only, itself is selectively unforgeable. Otherwise the message space contains two distinct messages that an efficient algorithm computes from . The restriction with , and has message space . It is -correct, since is correct for the messages so computed, and EUF-CMA-unforgeable: a forgery on an unqueried is a forgery for on , which was never queried because . In either case selective unforgeability follows with the same advantage for every forger — standard.

Sketch

An EUF-CMA forger runs the selective forger, which fixes its target message before receiving , forwards its signing queries, none of which is , and outputs with the forger’s signature.