What's the purpose of having the nonce commitment, R, in the challenge of of a Schnorr signature?
The only reason I can come up with is malleability. if R isn't part of the challenge and (R,s) is valid for a message m and key P, then (R+xG,s+x) is also valid for m and P.
Are there other issues than this?
I find it helps to start from the Schnorr identity protocol itself. There, the challenge e is sent by the verifier to the prover, *after* he has made the commitment R.
Then providing an s which satisfies sG = R + eP proves that you know an x such that s = r + ep.
(That this is a proof can be deduced using the concept of an 'extractor' from ZKPs).
However if the prover invents his own e, clearly this is useless: (1/n)
say he knows P but not the private key p. Then he can choose s and e at random, and "choose" R as sG -eP and claim that (R, s) "proves he knows p" when it obviously doesn't.
The idea of the Fiat Shamir transform is something like this: given an interactive proving protocol, you can essentially "make the challenge step be a non-backdatable transcript of the commit step", such that there is no longer a need for interactivity. ... (2/n)
@kalle
You go: commit step(s), (challenge=hash(commit step(s))), response all in one without involving the verifier.
Because the hash is one-way, nobody can calculate a challenge e without knowing what the choice of R (the commit) is first, so they cannot re-calculate it as sG -eP (in this specific schnorr case, but it generalises). (3/3)
@kalle occurs to me also, didactically, to avoid a bunch of waffle you could just say:
"we include R in the challenge so the signer can't modify it after they made the commitment".
Probably enough intuition in that brief phrase, for an intelligent reader to get the point.
@kalle
You might find interesting:
Boneh-Shoup chapter 19 (academic for sure but very thorough and good)
Section 4.1 of my writeup here (I'm trying to give the reader an intuition of what is going on in sigma protocols): https://github.com/AdamISZ/from0k2bp/blob/master/from0k2bp.pdf
Last (sorry for self-advertise) I think this is the best talk I gave by a long way, but few if any people saw it and unfortunately the filming isn't great: https://www.youtube.com/watch?v=mLZ7qVwKalE (most of first hour is about exactly what we're discussing).