Consider this variation of Schnorr's. The secret key also includes $s$ the seed

for a cryptographically secure pseudorandom generator $G.$ Let $G(s)=$

$k_1,k_2,$dots and when signing the $i^{th}$ message the signer uses $k_i.$

The above variation of Schnorr has the drawback of requiring the signer to

keep state $($to remember how many messages they have signed before in

order to use the correct $k_i$ and not reuse it$).$ Use the notion of pseudo$-$random

function to build on the above idea and remove the requirement to keep state.

Hint: In this new variation of Schnorr $s$ is now the key for a PRF$.$ When

signing message $M$ how can you use a PRF to generate a "random$-$

looking" $k$ to sign, without keeping state?