In the Schnorr identity protocol, we can transform the interactive ZKP into a non-interactive one by replacing the role of the verifier (i.e. providing a random challenge value) with a hash function that uses the prover's encrypted nonce as input.

s = r + e*x

e = H(r*G)

Validation works by ensuring:

sG== R + e*P

R = r*G

Assume that in this non-interactive model, the prover picks an r value in advance, and runs R through the hash function to determine its corresponding e digest. Assume the prover is malicious, and is looking to trick a verifier into accepting a Schnorr signature without knowing the private key x. If the prover resuses this e value when constructing the signature, while also selecting an arbitrary s value,they could back out sG = rG-eP. Since the prover knows R, e and P, it seems as if they could convince a verifier that the signature is valid, without needing knowledge of the private key. What prevents this from happening?

  • Two comments: in a Schnorr signature (rather than just an identification attempt), a message is also included in the hash (so e = H(rG||msg)). Second, the uppercase letters in your protocol represent group elements in which the discrete logarithm problem is hard, so you can't solve sG = rG-eP for s (as that would require "dividing" by G, which is computationally infeasible). – Pieter Wuille Apr 29 '19 at 18:09
  • So basically it would be impossible to find an s value that balances, b/c sG=rG-eP ---> sG=rG-e*xG. Dividing out G leaves us with s=r+e*x which requires knowledge of x? – Jayyy777 Apr 29 '19 at 19:09
  • Exactly. You can write it as s = r - e*(P/G), but the P/G part can't be computed. – Pieter Wuille Apr 29 '19 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.