Is ”generating transcripts that are indistinguishable from actual messages in a signature scheme” not universal forgery?

Question

In the Pointcheval paper “Security arguments for digital signatures and blind signatures”, they have proved the security of Schnorr signature for existential forgery under adaptively chosen-message attack.

The proof requires a simulator that can produce transcripts that are indistinguishable from the actual messages generated by the signer, without knowing the secret key.

I apologize if my understanding is wrong. Can someone shed some light on what they mean by simulating the transcripts without knowing the secret key?

Because – if that is possible – would it not become universal forgery?

Answer 1

Here and in many other signature schemes, $f$ is modeled as a "random oracle." This means that on each distinct input, $f$ outputs a uniformly random value in $\mathbb{Z}_q$ that is independent of all other outputs. (When queried on the same input multiple times, it always returns the same answer.)

The trick here is that the simulator has the power to "program" the output $f(m,r)$ to be the value of $e$ that the simulator chose. In the "real" world, an attacker cannot control the outputs of $f$ like the simulator can.

Many more details can be found in the classic Bellare and Rogaway paper "Random oracles are practical."

Answer 2

Well, the goal of their reductionists proof is to show that if there is an adversary against the signature scheme one is can use this adversary to extract the unknown secret key. Now, if the reduction would already know the secret key from the start this would make no sense. But how should the reduction then answer the signing queries of the adversary without the knowledge of the secret key?

This is where the programming of the random oracle jumps in (as @Chris Peikert already explained). The reduction programs the random oracle in a way such that it can answer the signature queries without knowing the secret key (in case of Schnorr signatures, if it chooses $e$ and $K$, sets $s=K$, computes $r=g^sy^s$ and then programs the oracle $f$ to the output $e:=f=(m,r)$, then you can easily convince yourself that $(r,s)$ is a valid signature for $m$). So, now the reduction can simulate signing queries and the distribution of these answers, i.e., signatures including $f$ values (note that if you program the oracle to output your randomly chosen $e$ this is what you expect from the random oracle $f$), is indistinguishable from those of real signatures that involved the signing key. This ensures that the adversary cannot detect that it is interacting with a simulated environment and not with the real challenger in the unforgeability game. Note however that the answering of the signing queries only works as the reduction can influence the output of the random oracle. In a real signature generation, the signer does not know how the result of $f(m,r)$ will look and thus has to follow the original signing protocol and is required to use the secret key to produce valid signatures. This is the power of programmable random oracles (which in the real protocol are instantiated by some hash function and one heuristically assumes that it behaves like a random oracle) .

So how does this help? Well, now as the reduction does not know the secret and can answer signing queries and if the adversary manages to output a forgery, it gets meaningful. If the reduction can then extract the secret key it knows something that it did not know before and in particular in case of Schnorr signatures has solved an instance of the discrete logarithm problem.