<p>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.</p>

<pre><code>s = r + e*x

where: 
e = H(r*G)
</code></pre>

<p>Validation works by ensuring: </p>

<pre><code>sG== R + e*P

where:
R = r*G
</code></pre>

<p>Assume that in this non-interactive model, the prover picks an <code>r</code> value <strong>in advance</strong>, and runs <code>R</code> through the hash function to determine its  corresponding <code>e</code> digest. Assume the prover is malicious, and is looking to trick a verifier into accepting a Schnorr signature without knowing the private key <code>x</code>. If the prover resuses this <code>e</code> value when constructing the signature, while also selecting an arbitrary <code>s</code> value,they could back out <code>sG = rG-eP</code>. 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?</p>

CC BY-SA 4.0
2019-04-29T18:09:34.253Z
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
CC BY-SA 4.0
2019-04-29T19:09:41.357Z
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
CC BY-SA 4.0
2019-04-29T19:28:22.300Z
Exactly. You can write it as `s = r - e*(P/G)`, but the `P/G` part can't be computed.
Pieter Wuille
<cryptography><schnorr-signatures>
Schnorr Fiat Shamir Transformation
Jayyy777
# Schnorr Fiat Shamir Transformation

(Asked by: username_0 on 2019-04-29)

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

where: 
e = H(r*G)

Validation works by ensuring: 
sG== R + e*P

where:
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?

**Tags:** cryptography, schnorr-signatures

> **Comments:**
> **username_1**: 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).  
> **username_0**: 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`?  
> **username_1**: Exactly. You can write it as `s = r - e*(P/G)`, but the `P/G` part can't be computed.  

---

## 0 answers

