2
$\begingroup$

Today I saw this question again which presents an unusual variant of the Diffie-Hellman key exchange. Having thought about it for a while I could find out how functionally works, but have essentially little cue whether it actuappy provides security.

My question is now:
Does the below stated Diffie-Hellman-like key exchange protocol enjoy similar security properties as normal Diffie-Hellman?


First the variables: Let $(\mathbb G,g,q)$ be a multiplicatively-written group where the discrete logarithm problem is hard with prime order $q$ and generator $g$. Let $a,b,x,y \stackrel{$}{\gets} \{0,\ldots,q-1\}$ be sampled uniformly at random. Let $A=g^a, B=g^b$. Let $a,x$ only be known to Alice and $b,y$ only be known to Bob. Let $a,b$ be static and $x,y$ be ephemeral across multiple sessions. Let $K=g^{x+y}$ be the shared secret, which can be computed by both parties after the exchange. Now define the following messages (the letters on the left denote Alice and Bob): \begin{align} A\to B&:B^x=g^{bx}\\ B\to A&:A^y=g^{ay}\\ \end{align}

If you are questioning functional correctness at this point note that Alice can trivially compute $g^x$, knowing $x$, and can compute $g^y$ as $(A^y)^{a^{-1}\bmod q}$, yielding $K=g^x\cdot g^y$. The computation for Bob goes analogous.

$\endgroup$
  • $\begingroup$ Yes, I know this is terribly inefficient with all the exponentiations going on and yes I know the formulation of the actual question is not optimal, but I couldn't find a better formulation :( $\endgroup$ – SEJPM Jan 22 '18 at 17:23
5
$\begingroup$

This problem (in the computational sense) is equivalent to the CDH problem [1].

This problem can be summarized as "given $g, A, A^y, B, B^x$, compute $g^x \cdot g^y$

Given a CDH oracle, we can solve this with two queries; we get the inputs $g, A, A^y, B, B^x$, and we give the CDH oracle the values $B, B^x, g$, and it'll give us the value $g^x$; we do the same to get $g^y$, and a simple multiplication gives us $g^x \cdot g^y$

Conversely, given an oracle that solves this problem, we can solve the CDH problem; we get the inputs $C, C^x, D$, we select an arbitrary $E, y$ values, and give the oracle the tuple $D, E, E^y, C, C^x$; it'll return the value $D^x \cdot D^y$. We then multiply that by $D^{-y}$, and that gives us the answer to the CDH problem $D^x$


Now, addressing the decisional problem would appear to be trickier; it's easy enough to show how to solve the DDH problem with an oracle that solves the decisional version of this problem; however, I don't see an obvious way to use a DDH oracle to solve this problem.


[1]: Note: for the CDH problem, I won't be using the usual formulation "given $g, g^x, g^y$, return $g^{xy}$, instead, I'll be using the equivalent "given $g, g^x, h$ return $h^x$. That formulation would appear to be make the proof a bit cleaner...

$\endgroup$
  • $\begingroup$ I think decisional version is DLIN Assumption introduced by Boneh et al. and is harder than DDH - there are groups where it holds even when DDH is easy (like in pairings settings) $\endgroup$ – Przemko Robakowski Jan 22 '18 at 20:48
  • $\begingroup$ @YehudaLindell I don't see how can you do that. Decisional version can be summarized: Given $g,A,A^y,B,B^x,V$ check if $V=g^{x+y}$. How do you construct DDH tuple that solves this? You don't know (neither can change) $a,b,x,y$ $\endgroup$ – Przemko Robakowski Jan 23 '18 at 10:14
  • $\begingroup$ @PrzemkoRobakowski Sorry; I think I got confused. $\endgroup$ – Yehuda Lindell Jan 23 '18 at 10:25
1
$\begingroup$

Here is a reduction to DDH. We will show that if there exists a PPT distinguisher $D$ and a non-negligible function $\epsilon(n)$ such that $$ \left|\Pr[D(g,A,A^y,B,B^x,g^{x+y})=1] - \Pr[D(g,A,A^y,B,B^x,g^z)=1]\right| = \epsilon(n) $$ where the probability is over the random choice of $x,y,a,b,z$ (and $A=g^a$, $B=g^b$). We construct a distinguisher $D'$ for DDH. $D'$ receives $(g,h,h_1,h_2)$ and wishes to distinguish between the case that there exists a (random) $y$ such that $h_1=g^y$ and $h_2=h^y$ or where $h_1$ and $h_2$ are independently random.

$D'$ chooses random $b,x$, computes $B=g^b,g^x,B,B^x$, sets $A=h$, invokes $D$ on input $(g,A,h_2,B,B^x,g^x\cdot h_1)$ and outputs whatever $D$ outputs. We have the following:

  1. If there exists $y$ such that $h_1=g^y$ and $h_2=h^y$, then (recalling that $A=h$): $$ (g,A,h_2,B,B^x,g^x\cdot h_1) = (g,A,A^y,B,B^x,g^x\cdot g^y)=(g,A,A^y,B,B^x,g^{x+y}). $$
  2. If $h_1,h_2$ are independently random, then writing $h_1=g^r$ and $h_2=h^y$, we have: $$ (g,A,h_2,B,B^x,g^x\cdot h_1) = (g,A,A^y,B,B^x,g^x\cdot g^r)=(g,A,A^y,B,B^x,g^z), $$ where the last equality holds by writing $z=x+r$ (note that since $r$ is independent of everything else, $x+r$ is distributed like an independently random $z$).

We therefore conclude that for a non-negligible function $$ \left|\Pr[D'(g,h,g^y,h^y)=1] - \Pr[D'(g,h,g^r,h^y)=1]\right| = \epsilon(n) $$ in contradiction to the assumption that the DDH assumption is hard.

$\endgroup$
  • $\begingroup$ Do I understand correctly that you use $D$ to solve tuple provided to $D'$ here? If yes isn't it the opposite reduction so from DDH to this problem and it proves that this problem is at least as hard as DDH but not the other way around? $\endgroup$ – Przemko Robakowski Jan 23 '18 at 9:13
  • $\begingroup$ @PrzemkoRobakowski That was exactly my aim - to show the if DDH is hard then this problem is hard. That means that we can have confidence that this variant is indeed hard. $\endgroup$ – Yehuda Lindell Jan 23 '18 at 9:22
  • $\begingroup$ @PrzemkoRobakowski By the way, what I answered is also exactly the question. Is this problem as secure as Diffie-Hellman? $\endgroup$ – Yehuda Lindell Jan 23 '18 at 9:50
  • $\begingroup$ Question was mainly about computational version of this problem I think. And I agree that your reduction is good in showing that decisional version is at least as secure as DDH (but not as secure!). My main concern was about wording as this is not reduction to DDH but from DDH to this problem. $\endgroup$ – Przemko Robakowski Jan 23 '18 at 10:18
  • 1
    $\begingroup$ @PrzemkoRobakowski I disagree. The question explicitly asks if this is a secure key exchange, and that requires a decisional definition. $\endgroup$ – Yehuda Lindell Jan 23 '18 at 10:26

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.