2
$\begingroup$

The PKC is in this way:

Alice and Bob fix a publicly known prime $p$, and all of the other numbers used are private (unless sent). Alice takes her message $m$, chooses a random exponent $a$, and sends the number $u = m^a\pmod p$ to Bob. Bob chooses a random exponent $b$ and sends $v = u ^ b = m^{ab}\pmod p$ back to Alice. Knowing the inverse of $a\pmod{p-1}$, Alice then computes $w = v ^ {a^{-1}} = m^{b}\pmod p$ and sends $w$ to Bob. Finally, Bob also computes $w ^ {b^{-1}} = m\pmod p$ and recovers the value of Alice's message.

I know a disadvantage of this PKC over ElGamal, that more times of data exchange is needed in order to send a single message. Are there any advantages of this cryptosystem over ElGamal? In particular, can Eve break it if she can solve the discrete logarithm problem? Can Eve break it if she can solve Diffie-Hellman problem?

$\endgroup$
2
  • $\begingroup$ In the calculation for $w$, $u$ should be $v$. $\endgroup$ – Aman Grewal May 20 '20 at 11:55
  • $\begingroup$ @AmanGrewal I edited the question. Thank you very much. $\endgroup$ – Kooranifar May 20 '20 at 13:30
1
$\begingroup$

Can Eve break it if she can solve Diffie-Hellman problem?

Yes, at least, the computational Diffie-Hellman problem. This problem is "given the triplet $h, h^x, h^y$, recover $h^{xy}$"

Let us assume that Eve has an Oracle that solves this problem. Then, she sets $h=m^{ab}$, $h^x = m^b = (m^{ab})^{a^{-1}}$ and $h^y = m^a = (m^{ab})^{b^{-1}}$, and passes $h, h^x, h^y$ to her Oracle. The Oracle returns with $h^{xy} = (m^{ab})^{a^{-1}b^{-1}} = m$, problem solved.

And, if she can break the Discrete Log problem, she can solve the CDH problem, so this answers that question as well.

N.B. The protocol you listed is known as the "Shamir Three Pass Protocol", and is currently viewed more as a curiosity rather than something that solves some problem better than other solutions.

$\endgroup$
1
  • $\begingroup$ Thanks a lot, I didn't expect that the protocol is that famous; great piece of info. $\endgroup$ – Kooranifar May 25 '20 at 12:32

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.