# Prove that a given signature scheme is secure under random message attacks

This is a follow up to my previous question.

Consider the following signature scheme:

$$\operatorname{KeyGen} (1^k$$) : On input of a security parameter $$k$$, choose a symmetric bilinear group with $$e : G \times G \rightarrow G_T$$ where the common group order of $$G$$ and $$G_T$$ is a prime of bitlength $$k$$. Further, let $$g$$ generate $$G$$. Choose $$\mathit{sk}$$ randomly from $$Z_p$$ and $$\mathit{pk} \leftarrow g^{\mathit{sk}}$$ and return $$(\mathit{sk}; \mathit{pk})$$.

$$\operatorname{Sign} (\mathit{sk};m)$$ : On input of a secret key $$\mathit{sk}$$ and a message $$m$$, output a signature $$\sigma \leftarrow m^{\mathit{sk}}$$.

$$\operatorname{Verify} (\mathit{pk}; m; \sigma)$$ : On input of a public key $$\mathit{pk}$$, a message $$m$$ and a signature $$\sigma$$, return $$1$$ if the following holds and $$0$$ otherwise: $$e(m; \mathit{pk}) = e(\sigma; g)$$

By the previous question I know that the above scheme is secure under no message attacks but insecure under chosen message attacks. Now I need to show that said scheme is secure under random message attacks or more formally that it has the property of Random Message Unforgeability Under Random Message Attacks (RUF-RMA).

I suppose that a good way to do that would be to do a reduction to the computational Diffie Hellmann assumption in symmetric bilinear groups (CDHSBG) I am unsure how to do such a proof under random message attacks; the "randomness" that influences such an attack confuses me. Could you help me?

• How is this question different from the last one? Mar 20, 2019 at 12:29
• In this question I ask about the same scheme, but this time under random message attacks. I thought I should make a new question, but I could also edit the old one if this would be better. Mar 20, 2019 at 12:34
• The only difference is that you now need to answer signature queries. However, you (as the reduction) get to choose the message, as long as you choose them uniformly at random. Given a $g^x$ used as a public key, how can you produce a uniform message $m=g^a$ and the corresponding signature $m^x$? Mar 20, 2019 at 14:27
• Sorry, but I can not follow you on that one. Mar 20, 2019 at 16:28
• If the message is $m=g^a$, what's the corresponding signature? And do you see any way of computing that using only the public key? Mar 20, 2019 at 16:41