2

If Alice wants to prove to Bob she is the holder of private key x, without exposing x, they can use the Schnorr identification protocol which has the public function sG = kG + exG and the private scalar function s = k +ex. In these functions, G is the static generator point, k is a hidden nonce chosen by Alice to protect x from being revealed to Bob, and e is a nonce chose by Bob so that he can trust kG (can't be calculated by someone pretending to hold x).

This all makes sense to me, but I am curious if there is a reason that e is multiplied with x instead of just following the same addition operator as k. So the equations would become sG = kG + eG + xG and s = k + e + x. k has a very valid reason to use addition, that is how x remains hidden. I can't think of a meaningful difference for the goal of the protocol if e is multiplied or added, maybe I missing a core concept?

1

1 Answer 1

4

This is trivial to forge.

Just to make sure we're on the same page, this is your protocol:

Alice has private key x, Bob has public key Q:

  • Alice generates k, computes R = kG, and sends R to Bob.
  • Bob generates e, and sends it to Alice.
  • Alice computes s = k + e + x, and sends it to Bob.
  • Bob verifies that sG = R + eG + Q.

Mallory is running your modified protocol with Bob, trying to pretend to be Alice.

  • Mallory generates a random k and sends R = kG - Q to Bob.
  • Bob generates e and sends it to Mallory.
  • Mallory computes s = k + e and sends it to Bob.
  • Bob verifies that sG = R + eG + Q. This will always hold.

Thus, Mallory successfully impersonated Alice, without having access to x.

1
  • Ah I see, thanks!
    – yonson
    Commented Jan 30 at 23:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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