# Prove that a signature scheme is RUF-NMA and not EUF-CMA

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

1. random message unforgeable under no message attacks (RUF-NMA)
2. 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?

• 1) You need to come up with a reduction that transforms any attacker agains RUF-NMA into an algorithm that can solve CDH. Hint: Given $g^x$ and $g^y$, how do you need to choose $pk$ and $m$, such that the signature equals $g^{xy}$. 2) Given two signatures $\sigma_1=m_1^{sk}$ and $\sigma_2=m_2^{sk}$ do you see any way to combine them into a signature of a new message? – Maeher Mar 20 '19 at 10:49
• Concerning 2) : I suppose you mean that $\sigma_1 \cdot \sigma_2$ is the signature of $m_1 \cdot m_2$ right? Concerning 1) I do not understand why you say "choose m" since we are considering a no message attack here – 3nondatur Mar 20 '19 at 11:01
• 2) Indeed. 1) You in this scenario are the reduction. You have access to a supposed attacker against RUF-NMA security. This attacker expects as input a public key and a message. You can choose those inputs, as long as you take care that they are correctly distributed. – Maeher Mar 20 '19 at 11:09
• I think I got it now: Since $\sigma := m^{sk} =$ $g^{a \cdot sk}$ for some $a \in Z_p$ $= g^a \cdot g^{sk} = g^a \cdot pk$ by definition of $pk$ we found a CDH solver right? – 3nondatur Mar 20 '19 at 11:19
• I'm unsure what you mean by that last part. – Maeher Mar 20 '19 at 11:22