4
$\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?

$\endgroup$
  • $\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$ – Bristol Aug 19 '15 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$ – Yevgeny Rosenthal Aug 19 '15 at 19:22
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.

$\endgroup$
  • $\begingroup$ I see. thanks a lot for your answer :). So my first reduction was correct, but your explanation clarified why it is. $\endgroup$ – Yevgeny Rosenthal Aug 20 '15 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$ – Yevgeny Rosenthal Aug 20 '15 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$ – Yevgeny Rosenthal Aug 20 '15 at 9:01
  • $\begingroup$ Is the adversary still passive, or are some of the $A_i$ dishonest too? $\endgroup$ – Bristol Aug 20 '15 at 9:04
  • $\begingroup$ They are all passive, they work according to the protocol. $\endgroup$ – Yevgeny Rosenthal Aug 20 '15 at 9:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.