In Schnorr's digital signature protocol (https://en.wikipedia.org/wiki/Schnorr_signature), the signing process (as described in wikipedia) requires the generation of a random bit $r$. I am wondering how necessary it is for this bit to in fact be randomly generated. For example, what if I generate my ith $r$ as $Q(i)$ for some degree $k$ polynomial $Q$. Would the signing protocol still be secure?
Note that the signature is $(s,e)$ where $s=k-xe$. If you can learn $k$ since it is predictable, then you can learn the secret signing key by computing $x = (s-k)/e$. Note that even without a concrete attack, the proof of security completely breaks down if the value $k$ is not chosen randomly.
Having said this, it is possible to change the scheme to be deterministic by including a random key $K$ for a PRF as part of the secret key and then generating the randomness needed to sign $M$ by computing $PRF_K(M)$. This actually is a good idea especially for DSA/ECDSA since repeating randomness there is a disaster The proof that this is good in general is not difficult (a reduction to the PRF).