# The following exercise is given in our book and I don't know how to solve it. Could somebody show me how to do it?

$$\textbf{13.10 (Probabilistic full domain hash).}$$ Consider the following signature scheme $$\mathcal{S} = (G,S,V)$$ with the message space $$\mathcal{M}$$, and using a hash function $$H: \mathcal{M} \times \mathcal{R} \rightarrow \mathbb{Z}_n$$: $$$$\begin{split} G():= \{(n,d) \xleftarrow[]{R}\operatorname{RSAGen}(l,e), \ pk:=(n,e), \ sk:=(n,d), \ \text{output} (pk,sk)\};\\ S(sk,m) := \{r \xleftarrow[]{R} \mathcal{R}, \ y \leftarrow H(m,r), \ \sigma \leftarrow y^d \in \mathbb{Z}_n, \ \text{output} (\sigma, r)\};\\ V(pk,m,(\sigma,r)) := \{y \leftarrow H(m,r), \ \text{accept if }\; y = \sigma^e \; \text{and reject otherwise}\}. \end{split}$$$$

Show that this signature is secure if the RSA assumption holds for $$(l,e)$$, the quantity $$1/|\mathcal{R}|$$ is negligible, and $$H$$ is modeled as a random oracle. Moreover, the reduction to inverting RSA is tight.

$$\textbf{Disscusion:}$$ While $$\mathcal{S}'_{RSA-FDH}$$, from Section 13.5, also has a tight reduction, the construction here does not use a PRF. The cost is that signatures are longer because $$r$$ is included in the signature.

It is the Exercise 13.10 from the book "A graduate course in applied cryptography".

• Welcome to crypto.SE. Per our topicality rules you should explain what you tried and where you are stuck. If that's at understanding how the scheme described works, nothing will replace getting fluent with notations in the book by checking them one by one. – fgrieu Apr 6 at 11:44