# DH Key Exchange Protocol (one-out-of two)

Now given this problem, for part 1) I have solved it as follows, (I hope I am correct). The basic idea is this:

1. I Have two prime numbers g and p and I tell you what they are.
2. You choose a secret number (a), you compute ga mod p and send that result back to me. (call it A).
3. I do the same, and call my number b and B respectively. So I compute gb mod p and send you the result B.
4. You take the number that I sent and perform the same operation,Ba mod p.
5. And likewise for me: Ab mod p.

Therefore step 5 is the same is as Step 4 due to modular exponentiation giving us the shared secret key (could also be between Alice and Bob).

(ga mod p)b mod p = gab mod p (gb mod p)a mod p = gba mod p

Now for Part 2 and Part 3 I am not sure how to solve this - so any help would be kindly appreciated - please as I have an exam question that will be similar. Thanks guys!

Sonia.

For question 1, Alice computes $k_0 = B^a, k_1 = (B/A)^a$, and Bob computes a key $k = A^b$. If $c=0$, then $B = g^b$, hence $k_0 = B^a = g^{ab} = A^b = k$; else, if $c=1$, then $B = Ag^b$, hence $k_1 = (B/A)^a = g^{ab} = A^b = k$. In any case, both players have a shared key (either $(k_0,k)$ or $(k_1,k)$).

For question 2, let me give you some hints. Bob generates $B$ according to one of two distributions: (I write $b \gets_{\mathsf{R}} \mathbb{Z}_p$ to indicate that $b$ is taken uniformly at random over $\mathbb{Z}_p$), $D_0 = \{b \gets_{\mathsf{R}}\mathbb{Z}_p: B \gets g^b\}$ and $D_1 = \{b \gets_{\mathsf{R}}\mathbb{Z}_p: B \gets Ag^b\}$. What can you tell about those two distributions? Why cannot one distinguish them, even with unlimited computational power? Additional hint: $A = g^a$; what can be said about the distribution of exponents $a+b \bmod p$ when $b$ is taken at random from $\mathbb{Z}_p$, but $a$ is fixed?

For question 3, let us suppose that there is a player, Bob, that is able to compute both $k_0$ and $k_1$ with some fixed probability $\epsilon$ after performing a one-out-of-two key exchange with Alice. Suppose now that you are given a challenge for the computational Diffie-Hellman problem: you receive the description of a group $\mathbb{G}$, as well as a tuple $(g, X= g^x, Y = g^y)$. You break the CDH assumption if you manage to return $Z = g^{xy}$ with some non-negligible probability. Therefore, your goal is now to construct a $Z$ which will have a good probability (related to $\epsilon$) to be equal to $g^{xy}$, by interacting with Bob: you'll play a one-of-of-two key exchange with him, using carefully chosen elements from the CDH challenge instead of picking group elements according to the specification of the key exchange. Then, you'll reconstruct $g^{xy}$ with good probability using the keys $k_0,k_1$ that Bob returns (recall that they have a probability $\epsilon$ to be the correct keys).

I've given many details, so you should be able to figure out how to properly answer the question by now. If you are still blocked, if there is something you do not understand, please do not hesitate to mention it and I'll provide further insights.

EDIT: further insights for question 3.

Suppose now you received $(g, X= g^x, Y = g^y)$. We will play Alice's role in a one-out-of-two key exchange. As you remarked in your comment, we cannot gain anything from the values $B=g^b$ chosen by Bob - as it is chosen by the adversary, he can always compute it. However, we can gain something from the fact that Bob will compute both $k_0 = B^a$ and $k_1 = (B/A)^a$: we can deduce $A^a$ from that by computing $k_0/k_1$. Note that $A^a = g^{a^2}$.

Let me sum up: we have an adversary Bob, to which we can send some $A = g^a$ and who eventually returns two keys. At the end of the interaction with Bob, by computing $k_0/k_1$, we recover $g^{a^2}$ (with probability at least $\epsilon$, as this is the probability that both keys are correct).

So, we can now see Bob as an oracle which returns $g^{a^2}$ when we send it $g^{a}$. Given such an oracle, solving the CDH problem is a standard exercise. Can you see how it is done? The trick is simply: use the identity $ab = 1/2((a+b)^2 - a^2 - b^2)$. Now, from the "exponent squaring oracle" and $g^x,g^y$, you should be able to find out $g^{xy}$.

If you still do not see how to solve the exercise, I'll give you the entire solution, but it's way more interesting and useful for you if you figure it out for yourself.

• Not really understanding q3. I thought CDH was for unknown x and y, but Bob knows x, so couldnt he work out one of the keys like you did for $k_0$ in q1. Could you perhaps make an edit to show it in steps on what to do? – user153882 Dec 12 '16 at 0:53
• @GeoffroyCouteau - Thank you so very much for such a helpful and detailed answer. I am sorry I could not answer you earlier as I was in the hospital with my mother. I sincerely appreciate your help in this question. Grand Merci! Sonia. – Cryptocool100 Dec 12 '16 at 1:35
• It's always a pleasure to help :) @user153882: I've edited the answer with further details. CDH is indeed for unknown $x$ and $y$, so we have to follow a slightly indirect path toward the solution. Tell me if it's still not clear enough! – Geoffroy Couteau Dec 12 '16 at 9:24
• @GeoffroyCouteau thanks for the update, it has been extremely helpful. I kind of understand and have been using this. So we can find out $g^{ab}$ by $g^{ab} =g^{\frac12 ((a+b)^2-a^2-b^2)}$. To solve the RHS, Bob knows $g^b$ so he can get $g^{b^2}$ and $\frac{k_0}{k_1}=g^{a^2}$, that takes care of most of the equation but then how can he get the $g^{(a+b)^2}$ part – user153882 Dec 12 '16 at 19:14
• @GeoffroyCouteau nvm, I found the missing piece on here lemma 21.1.9 if anyone is still looking for the answer, looks like you didnt need to find $g^{(a+b)^2}$ – user153882 Dec 13 '16 at 22:07