3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ By "security", I presume that you mean the real key is indistinguishable from a random one to a passive attacker - I don't think this protocol is actively/MITM secure, for example. Your first reduction actually looks ok to me, I don't understand what the problem is? $\endgroup$ Commented Aug 19, 2015 at 15:33
  • $\begingroup$ you are right regarding the meaning of 'security'. the problem in my first reduction -as I think- is that in both cases (when $g_3=g^{xy}$ and $g_3=g^z$ ) the difference was in the $Transport$ and not in the $Key$, while in the definition of security, the adversary should receive in both cases a valid $Transport$ and in first case real key while in the other it should receive a key distributed uniformly $\endgroup$ Commented Aug 19, 2015 at 19:22

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I see. thanks a lot for your answer :). So my first reduction was correct, but your explanation clarified why it is. $\endgroup$ Commented Aug 20, 2015 at 8:46
  • $\begingroup$ one more thing. my original question was a general case of the above: I have $A_1,...,A_T$ (T is polynomial), each $A_i$ sends $h_i=g^{a_i}$ to $B$ (for some $a_i$ chosen uniformly), then $B$ returns $h_i^b$ to $A_i$ for each $i$. I started with the case above to try to prove security for the case $T=1$. but I didn't see how to generalize the reduction above. $\endgroup$ Commented Aug 20, 2015 at 8:56
  • $\begingroup$ I thought about the following generalization: choose some $i$ uniformly, let $A_j$ for $j \neq i$ sample $a_j$ uniformly and send $g^{a_j}$ to $B$. while $A_i$ sends $g^x$ (the first element of DDH triple). then $B$ returns $g_2^{a_j}=g^{{a_j}y}$ to $A_j$ for all $j \neq i$, and returns $g_3$ to $A_i$. But I'm not sure this is a correct reduction, because $Transcript$ should be of the form: $(g^{a_1},...,g^{a_T},g^{{a_1}b},...,g^{{a_T}b})$. while in case $g_3 \neq g^{xy}$ (i.e. was random), the output $Transcript$ of the reduction will not be of the form above $\endgroup$ Commented Aug 20, 2015 at 9:01
  • $\begingroup$ Is the adversary still passive, or are some of the $A_i$ dishonest too? $\endgroup$ Commented Aug 20, 2015 at 9:04
  • $\begingroup$ They are all passive, they work according to the protocol. $\endgroup$ Commented Aug 20, 2015 at 9:05

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.