As a study case, I consider the BLS signature scheme, but the following question is relevant in the general context of security proofs in the Random Oracle model.
Let us briefly recall BLS signature scheme:
Let $e:G \times G \to G_t$ be a bilinear group scheme. Let $g$ be a generator of the group $G$, and let $a \in \mathbb{Z}^*_p$ be a random field element. We denote by $H$ a function that serves as a random oracle.
- Keys: secret key is $a$, public key is $(g, g^a)$.
- Sign: compute $m \mapsto (m, \sigma = H(m)^a)$.
- Verify: check the equality $e(g, \sigma) = e(g^a, H(m))$.
The authors prove that this scheme is secure (or more specifically - secure against existential forgery under adaptive chosen message attack) by describing an algorithm $\mathcal{A}$ that given a forging entity $\mathcal{F}$ breaks computational Diffie-Hellman in $G$.
The proof assumes that the algorithm $\mathcal{A}$ emulates the random oracle, meaning that every query by $\mathcal{F}$ to $H$ is actually answered by $\mathcal{A}$. My question is, isn't this a very, very strong assumption?
If instead we assume that the random oracle is some third party that both $\mathcal{A}$ and $\mathcal{F}$ can only query but not affect (like in every real-world use case) than this proof completely breaks.
Also, if we provide a security reduction without this strong assumption, our reduction might be far more efficient.