variant of Diffie–Hellman key exchange protocol

Question

Motivation

Consider the following variant of Diffie-Hellman key exchange protocol for two parties:

1. Assume Alice and Bob share $\mathbb{G}$ of order $q$ generated by $g$
2. Alice samples $a$ uniformly from $\mathbb{Z}^q$, and sends $h := g^a$ to Bob
3. Bob samples $b$ uniformly from $\mathbb{Z}^q$, and sends $h^b = g^{ab}$ to Alice
4. The shared key is $g^b$

Alice can calculate $g^b$ by raising $h^b$ that he received from Bob by $a^{-1}$ so he will get: $(h^b)^{a^{-1}} = (g^{ab})^{a^{-1}} = g^b$

My question is how to prove that the above protocol is secure (assuming DDH assumption holds?

I tried to prove it by reduction:

upon receiving $(\mathbb{G},q,g,g_1=g^x,g_2=g^y,g_3)$ run the above protocol s.t. Alex sends $g_1$ to Bob, then Bob returns $g_3$, and both will agree on key $g_2$. i.e. we simulate the case where: $a=x$ and $b=y$.

In case $g_3=g^{xy}$, then $(Transcript, Key) = (g^x,g^{xy},g^y)$

In case $g_3=g^z$ for $z$ sampled uniformly from $\mathbb{Z}^q$, then: $(Transcript, Key) = (g^x,g^z,g^y)$

The problem with my solution is that the difference between the two cases is in the distribution of $Transcript$ while $Key$ is the same, and this is different from what required in the definition.

In another try, I simulated the protocol s.t. Alice sends $g_1$, Bob sends $g_2$ and they agree on $g_3$, i.e. simulate the case: $a=x$ and $b=x^{-1}y$, but this will not work because the key the agree on will be $g^y\neq g^b=g^{x^{-1}y}$

Edit: General case

We have $A_1,...,A_T$ parties (where $T$ is polynomial) and $B$. the protocol is:

1. each $A_i$ sample some $a_i$ uniformly and send $h_i := g^{a_i}$ to $B$

2. upon receiving $h_1,...,h_T$, $B$ samples $b$ uniformly and sends $h_i^b$ to $A_i$

3. The key is $g^b$.

Any idea of how to prove the general protocol's security?

Answer 1

To show that the protocol is secure under DDH, we need a reduction $R$ that takes a triple as input and outputs a transcript and key such that

• if the triple is a DDH triple, then the transcript and key are distributed identically to a real execution of the protocol
• if the triple is random, then the transcript and key are distributed as if you ran a real protocol execution to get the transcript, but the key is random (and independent of the transcript)

The reduction $R$ takes a triple $(A,B,C)$ and sets Transcript=$(A,C)$ and Key=$B$.

If the triple is a DDH triple then there are values $x,y$ such that $(A,B,C)=(g^x,g^y,g^{xy})$. So $(A,C)$ is distributed uniformly in $G \times G$, which is exactly how a transcript of a protocol execution is distributed too. The key in a real execution is the unique value $k$ satisfying $k \otimes \alpha = \beta$ where $\alpha$ is Alice's message, $\beta$ is Bob's and $g^x \otimes g^y := g^{xy}$ (this is well-defined if you think about it). The reduction's key satisfies this property too since $C = A \otimes B$ is the definition of a DDH triple. So the reduction's transcript and key are identically distributed to real ones in this case.

If the triple is a random triple, then $(A, B, C)$ is uniform in $G^3$, i.e. each element is uniform in $G$ and independent of the other two. If you create a transcript together with a random key, then the transcript and key are distributed uniformly in $G^3$ too, so the reduction produces the correct distribution in this case too. Q.E.D.

Informally, think of the proof as follows: a DDH triple has two degrees of freedom, a random tuple has 3. A real transcript/key also has 2 degrees, a fake one 3. In both cases, the restriction that loses the third degree is that one element is a DH product $(\otimes)$ of the other two. So all your reduction has to do is match things up.

EDIT: General case

A transcript of a protocol looks like this (order may vary):

A1 to B: g^{a_1}
...
An to B: g^{a_n}
B to A1: g^{a_1.b}
...
B to An: g^{a_n.b}
shared key: g^b

A fake transcript (that is indistinguishable from a real one if it's secure) is the same except that the key at the end is $g^r$ for independent $r$. Note that even in a fake transcript, the same exponent $b$ is used for all messages from $B$.

Reduction $R$ takes a tuple $(A, B, C)$ and makes $n$ tuples by picking $u_i$ for $i$ from 1 to $n$ and sets $(A_i, B_i, C_i) = (A^{u_i}, B, C^{u_i})$. It then outputs the transcript $A_1, \ldots, A_n, C_1, \ldots, C_n, B$. If the orignal tuple was DDH, so are all these ones - so it is identical to a real transcript (in the real transcript, each $a_i$ introduces a degree of freedom; in the reduction, the $u_i$ do). And $B$ matches up too.

If the original tuple was random, $B$ is independent of everything else but the $A_i/C_i$ relations still hold so it's all distributed correctly.