# Is there proof to the relation between the gap Diffie-Hellman problem and the the Cha-Cheon signature scheme?

I am trying to prove that:

"If the gap Diffie-Hellman problem is easy, then the Cha-Cheon signature scheme will be broken."

Can you help me to prove it? Is there any proof to the relation between the gap Diffie-Hellman problem and the the Cha-Cheon signature scheme?

My related question: Can you help me design a simple communication protocol?

-

I have to make two assumptions regarding your question first.

• I assume you speak of the ID-based signature scheme from "An Identity-Based Signature from Gap Diffie-Hellman Groups".
• You mean "If the computational Diffie Hellman problem (CDHP) is easy..." (the scheme works in Gap Diffie Hellman (GDH) groups, but the security proof relies on the CDHP.

Ok, now we briefly recall the scheme (I use the notation of the paper): In this scheme we have a GDH group $G$ of order $\ell$ generated by $P$. Note that in a GDH group the decisional Diffie-Hellman problem is easy, but the CDHP is assumed to be hard (such groups can for instance be realized using pairing friendly elliptic curve groups).

The master public key is $P_{pub}=sP$ where $s$ is random element in $Z_\ell$ and $s$ is kept secret by the system.

A users secret is $D_{ID}=sH_2(ID)$ and $ID\in\{0,1\}^*$ the users identifier and $H_2$ maps strings to $G$. The users public key is $Q_{ID}=H_2(ID)$.

A signature is the tuple $(U,V)$ with $U=rQ_{ID}$ for random $r\in Z_\ell$ and $V=(r+h)D_{ID}$ with $h=H_1(m,U)$ where $H_1$ is a hash function maps to $Z_\ell$.

Now signature verification amounts to checking whether $(P,P_{pub},U+hQ_{ID},V)$ is a valid Diffie- Hellman tuple. Now, this means that it is of the form $(P,aP,bP,cP)$ with $c\equiv ab\pmod \ell$.

Let us rewrite $(P,P_{pub},U+hQ_{ID},V)$ to $(P,sP,rQ_{ID}+hQ_{ID},(r+h)D_{ID})$. Now, we see that the last element can be rewritten to $(r+h)D_{ID}=rsQ_{ID}+hsQ_{ID}=s(rQ_{ID}+hQ_{ID})$, which shows the correctness. This means that a honestly computed signature is a valid Diffie-Hellman tuple.

Now forging would require to break the CDHP in $G$, i.e., one can efficiently compute $abP$ given $P,aP,bP$.

Forgery:

Observe, that $U$ and $hQ_{ID}$ can be computed by anybody. Now let us view $(P,sP,U+hQ_{ID})$ as an CDHP instance. Now, assume the $CDHP$ in $G$ is easy. This means that we can compute $s(U+hQ_{ID})$ given $(P,sP,U+hQ_{ID})$.

Now lets us inspect $s(U+hQ_{ID})$. We see that

$s(U+hQ_{ID})=sU+hsQ_{ID}=srQ_{ID}+hsQ_{ID}=rD_{ID}+hD_{ID}=(h+r)D_{ID}$.

Note that this is exactly a $V$ for a valid signature.

Total break:

Note that one can also totally break the scheme if the CDHP is easy, as one can compute $D_{ID}$ from $P_{pub}$ and $Q_{ID}$. Then you can also compute any signature you want.

Consequently, if the CDHP is easy, the signature scheme does not work anymore.

Hope that helps.

-
Nice answer. [+1] –  e-sushi Oct 24 '13 at 16:38