DS ⇒ Selectively unforgeable DS
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.