Consider the following cryptography scheme:

We are given a prime $p$. Alice wants to send the plaintext $m \pmod p$ to Bob. Alice chooses $a$ s.t. $\text{gcd}(a,p-1)=1$, and sends Bob, $u = m^a \pmod p$. Bob chooses $b$ s.t. $\text{gcd}(b,p-1)=1$, and sends Alice, $v = u^b \pmod p$. Now Alice sends Bob, $w = v^{a^{-1}} \pmod p$, where $a^{-1}$ is the inverse of $a$ modulo $p-1$. Bob now calculates $w^{b^{-1}}$ to get back $m$.

Now I want to know if we have a passive adversary Eve who is able to solve the Diffie-Hellman Problem, gain access to $(u,v,w)$, can she get back $m$.

Now I want to know if we have a passive adversary Eve who is able to solve the Diffie-Hellman Problem, gain access to $(u,v,w)$, can she get back $m$.

Yes. But first you may want to note that this is the classic three-pass protocol, also called Shamir 3-pass protocol or Massey-Omura protocol which has been shown by Sakurai and Shizuya in 1998 to (sorry for the paywall) in general require a stronger assumption than (C/D)DH for security.

But now for the attack, which is directly derived from the above security relation result. First note that $u=m^a,w=m^b,v=m^{ab}$ and that $p$ is known. So now suppose that you have an oracle $\mathcal O$ that given $(g^a,g^b,g,p)$ returns $g^{ab}$ that is a classic Computational Diffie-Hellman (DDH) Oracle. Now for a second, call $v=g$ and note that $u=g^{b^{-1}}$ and $w=g^{a^{-1}}$. Now feed $(u,w,v,p)$ to the oracle and get $g^{a^{-1}b^{-1}}=(m^{ab})^{a^{-1}b^{-1}}=m$ back.

If you "only" have a Decisional Diffie-Hellman (DDH) oracle, note that you can still guess a message $m$, that is guess the return value of the above CDH oracle if there are only a few possible messages (not excluded in general in cryptography) and thus confirm your guess.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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