I am working on the following exercise:
Now, assume 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^{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)$$
I showed that the scheme works correctly. Now I need to show that the scheme is
- random message unforgeable under no message attacks (RUF-NMA)
- is not existentially unforgeable under chosen message attacks (EUF-CNMA)
Concerning point 1) I think that being able to guess the signature for a given message $m$ and a given public key $\mathit{pk}$ would violate the computational Diffie Hellmann assumption in symmetric bilinear groups (CDHSBG). But how could I write that down more formally?
Concerning 2) I suppose I have to find a suiting example for such an attack, but I am struggeling to find one.
Could you help me?