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? – Maeher Mar 20 '19 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. – 3nondatur Mar 20 '19 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$? – Maeher Mar 20 '19 at 14:27
• Sorry, but I can not follow you on that one. – 3nondatur Mar 20 '19 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? – Maeher Mar 20 '19 at 16:41