 Solution

Choose any candidate digital signature $s$, compute $y=g(pk,s)$, and invoke the granted algorithm to find $x$ with $h(x)=y$. Output $(x,s)$. Every chosen $s$ now leads to a valid message, with no need to search for a digest on which inversion happens to work.

This is stronger coverage than the generic failure discussed in solution, but it does not by itself give a universal forgery. For a target message $x_{\ast }$ fixed beforehand, the adversary needs $s$ satisfying $g(pk,s)=h(x_{\ast })$, which inverts the trapdoor map $g$. Inverting $h$ instead produces some message for a chosen digest and does not compute that $s$.

Nor does an arbitrary preimage algorithm necessarily produce a message different from $x_{\ast }$ when invoked on $h(x_{\ast })$: it may return $x_{\ast }$ itself. Thus a universal forgery under a chosen-message signature attack needs an additional alternative-preimage guarantee, precisely the distinction supplied in solution.