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?
