0
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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? $\endgroup$ – Maeher Mar 20 '19 at 10:49
  • $\begingroup$ 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 $\endgroup$ – 3nondatur Mar 20 '19 at 11:01
  • 1
    $\begingroup$ 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. $\endgroup$ – Maeher Mar 20 '19 at 11:09
  • $\begingroup$ 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? $\endgroup$ – 3nondatur Mar 20 '19 at 11:19
  • 1
    $\begingroup$ I'm unsure what you mean by that last part. $\endgroup$ – Maeher Mar 20 '19 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.