# Signature security proof in the Random Oracle model

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.

• I think you can find the answer here. crypto.stackexchange.com/q/1407/30818 – Mahdi Sedaghat May 28 at 12:08
• @MahdiSedaghat those are different questions actually. I don't mind the difference between a model of random function and and actual specific implementation. I just mind the assumption that one may control its outputs. – Chipotle May 28 at 12:22

This was discussed by Coron in 1.

You are actually asking why the random oracle can't just be some uncontrollable ideal random oracle. In fact Bellare and Rogaway when introduced their Full Domain Hash scheme (FDH) in the seminal works 2,3 used this uncontrollable random oracle to analyze the security reduction for FDH.

The thing about using reductions to prove the security of, let's say a signature scheme, is that the reduction security depends greatly on the probability to break the underlying assumption, let's say the CDH assumption. So ideally, if the reduction enables to break CDH problem with probability 1 it means the signature scheme is pretty much secure as solving the CDH problem.

But what happens if this probability is much lower than 1? Well, the signature scheme security becomes rather weak.

As Coron mentions in 1, allowing $$\mathcal{A}$$ to control the random oracle gives a tighter security bound on the FDH signature scheme than the one shown by Bellare and Rogaway.

The main thing about the tighter bound is that it does not depends on the number of queries requested by the forger, but rather only on the number of queries for signatures (which in practice is much lower than the number of hash queries such forger can do). A better bound enables one to use more efficient signature scheme.

To conclude, using a specific hash function does not say that this is an assumption of the model, it is merely a way to make the bound tighter.

(This is to complement Avilan's answer on a more philosophical level.)

In the random-oracle model (ROM for short) [BR], all parties are assumed to have oracle-access to a public random function $$H$$. The security of a protocol is then argued relative to this random oracle $$H$$, and then in practice $$H$$ is instantiated by an appropriate hash function (say, SHA3) with the hope that security still holds. A proof in the ROM serves only as an indication that the protocol is secure, and therefore it is sometimes considered in cryptographic circles to be a heuristic. This caution is justified by certain (artificial) examples where this approach is not sound (i.e., instantiating $$H$$ with any concrete hash function results in an unsound protocol: cf. [CGH] for more details). Therefore proofs without random oracles -- i.e., in the "standard model" -- are preferred.

The short answer to your question is that sometimes the only way we know how to prove security (and in some cases tight security) is by assuming the control of the random oracle. Ideally, one would like to establish security in a setting where all parties have oracle-access to $$H$$ --- i.e., no one party controls the random oracle (e.g. like in [BG]). That said, it seems that for certain applications in a cryptographic setting the reduction/challenger has to assume control of the random oracle. There have been attempts at precisely formulating what one means by "control": e.g., the (in)ability of the reduction/challenger to "program" the random oracle was considered in [F+], and the (in)ability of the reduction/challenger to "observe" the queries that the adversary makes was studied in [AR].

Although, by [CGH], we cannot hope to instantiate all applications of the random oracle with a concrete (standard-model) hash function, there has been some success in instantiating random oracles in certain families of applications. For example, the random oracle in [BLS] can be replaced by a "programmable" hash function [HK], which in turn can be constructed assuming either CDH or QR. For a more recent example, "correlation-intractable" hash functions [CGH] have been used to instantiate the Fiat-Shamir transformation in the standard model [C+], which has resulted in exciting new results (eg. NIZK from LWE [PS]).

[AR]: Ananth and Bhaskar. Non Observability in the Random Oracle Model

[BR]: Bellare and Rogaway. Random Oracles are Practical: A Paradigm for Designing Efficient Protocols

[CGH]: Canetti, Goldreich and Halevi. The Random Oracle Methodology, Revisited

[C+]: Canetti et al. Fiat-Shamir from Simpler Assumptions

[F+]: Fischlin et al. Random Oracles With(out) Programmability

[HK]: Hofheinz and Kiltz. Programmable Hash Functions and their Applications

[PS]: Peikert and Sheihan Non-Interactive Zero Knowledge for NP from (Plain) LWE.

• I gather from your reply that this is indeed a strong assumption, only made so it would be easier to give a security proof. Is that correct? – Chipotle Jun 2 at 6:50
• @MelafefonChamutz That's correct. – Occams_Trimmer Jun 2 at 11:13

The words "controls"(in the question) and "manipulates"(in the paper) can be somehow misleading as to what is happening. Often in literature this is rather formulated as: emulates a random oracle, etc...

One could quote the paper(with modifications) as follows:

Given a forger $$\mathcal{F}$$ for the $$GDH$$ group $$G$$, we build an algorithm $$\mathcal{A}$$ that uses $$\mathcal{F}$$ to break $$CDH$$ on $$G$$. $$\mathcal{A}$$ is given a challenge $$(g, g^a, g^b)$$. It uses this challenge to construct a public key that it provides to $$\mathcal{F}$$. It then allows $$\mathcal{F}$$ to run. At times, $$\mathcal{F}$$ makes queries to two oracles, one for message hashes and one for message signatures. These oracles are puppets of $$\mathcal{A}$$, which it emulates in constructiveways. Finally, if all goes well, the forgery which $$\mathcal{F}$$ outputs is transformed by $$\mathcal{A}$$ into an answer to the $$CDH$$ challenge

The key idea is that $$\mathcal{A}$$ will emulate a consistent $$BLS$$ interaction towards $$\mathcal{F}$$ so that it can use the results of the interaction in a meaningful way to break $$CDH$$.

Let's look at how it is done in the proof:

$$\mathcal{A}$$ is described in s serie of games. Looking only at game 1 should help to get a good intuition, the same reasoning can be adapted to the other games. In game 1, for all queries to $$H$$ with message $$M_i$$, $$\mathcal{A}$$ respond with $$h_i$$. The values $$h_i$$ are generated as follows: $$r_i \xleftarrow{\} \mathbb{Z}^*_p \\h_i \leftarrow g^{r_i}$$

As mentioned in the paragraph before the description of game 1; $$\mathcal{A}$$ does some bookkeeping in order to emulate a consitent $$BLS$$ game:

This behavior is actually a faithful emulation of a random oracle since a random oracle $$H: \{0, 1\}^*\rightarrow G^*$$ would work as follows: for $$M \in \{0, 1\}^*$$ that wasn't requested before output and "save" $$H(M) = g_M$$ for $$g_M$$ taken uniformly at random in $$G^*$$. Now the uniform distribution of the $$r_i$$'s implies the uniform distribution of the $$h_i$$'s. Hence $$\mathcal{A}$$ is emulating a legit random oracle towards $$\mathcal{F}$$.

Aside: this is a widely used proof technique to prove the security of a system(e.g IND-CPA encryption) based on the security of another system(e.g IND-ROR, Real Or Random challenge).

One would use a distinguisher $$D^{IND-CPA}$$ to build a distinguisher $$D^{IND-ROR}$$. $$D^{IND-ROR}$$ will be built in a way that it emulates a CPA game to $$D^{IND-CPA}$$.

• Sure, emulates, not controls. What I'm wondering is whether or not this is a unrealistically strong assumption – Chipotle May 29 at 11:04
• The question or controlling a RO is of great interest and the first answer provides good material for that. However in the BLS case, we could look at how the RO is actually controlled. And we can see that what is provided is indeed a RO that behaves the same as a RO that "belongs" to a third party(which was your question) – Marc Ilunga May 29 at 12:32
• The RO in BLS behaves the same as a RO emulated by third party only in the eyes of the forger. That's a key difference. – Chipotle May 29 at 14:13
• @MelafefonChamutz what do you mean by only in the eyes of the forger? Maybe it's help if you could say how you define a RO and how would a RO that belongs to a third party behave. – Marc Ilunga May 29 at 14:16
• If we wanted to be precise, then of course they don't behave the same since we can assume that the controlled RO has a filter system attached to it that limits the number of queries to $q_H$. But then one would argue that up to $q_H$ queries, the controlled oracle behaves like a RO independently of who it interacts with. – Marc Ilunga May 29 at 15:48

Suppose you have a forgery procedure which takes a public key, calls SHA-256, interacts with an automatic PGP mail system, does some horrible computation, and returns an attempted forgery:

import hashlib
import smtplib

def forge(pubkey):
... hashlib.sha256(m0) ... smtplib.sendmail(m1) ...
return (forged_msg, forged_sig)


We can take the text of this program, and rearrange it a little:

def forge0(hash, sign, pubkey):
... hash(m0) ... sign(m1) ...
return (forged_msg, forged_sig)

def forge(pubkey):
import hashlib
import smtplib
def hash(m): return hashlib.sha256(m).digest()
def sign(m): smtplib.sendmail(...) ... return signature
return forge0(hash, sign, pubkey)


There's nothing magic here: we just did a little refactoring to get the same procedure, with the hashing oracle and the signing oracle clearly identified as parameters in the algorithm forge0. (The hashing oracle is the ‘random oracle’.) All that forge does is wire up forge0 to the oracles.

The theorem is a statement something like this:

Theorem. Let hash be uniformly distributed among all functions of its domain and codomain, and let sign is a correct signing procedure. If forge0(hash, sign, pubkey) returns a forgery with probability $$\varepsilon$$ and computational cost $$C$$, then there is an algorithm cdh(gx, gy) which if given $$g^x$$ and $$g^y$$ returns $$g^{xy}$$ with probability $$\varepsilon' = f(\varepsilon)$$ and computational cost $$C' = g(C)$$.

(Sometimes the theorem is broken into two parts—a theorem about success probability, and a theorem about computational cost, since computational cost can be slippery.)

The proof of the theorem is usually a statement of the cdh algorithm. It works by constructing a hashing procedure whose input/output pairs have exactly the same distribution as a uniform random function, as in the random oracle model, and constructing a signing procedure that works—but as side effects, these procedures also record information related to $$g^x$$ and $$g^y$$ that, together with the resulting forgery, lead to the computation of the DH shared secret $$g^{xy}$$!

def cdh(gx, gy):
def hash(m): ...
def sign(m): ...
... (m1, s1) = forge(hash, sign, gx) ...
... (m2, s2) = forge(hash, sign, gy) ...
return gxy


Example, with RSA-FDH, along with further discussion of the random oracle model and its place in modern cryptography.

• In the last sentence, did you mean "lead to the computation of CDH!"? – Marc Ilunga Jun 1 at 13:12
• @MarcIlunga Clearer? – Squeamish Ossifrage Jun 1 at 14:44
• Yes, thank you ;) – Marc Ilunga Jun 1 at 17:50
• Hi, thanks for your reply. However, I don't see how it addresses the key issue of the question. Could you clarify? – Chipotle Jun 2 at 6:41
• The issue I perceive is that your question is rather many question. One aspect has to do with programmability of ROs. To which other answers are pretty good. The other aspect has to do with instantiation of ROs. To which many answers have pointed out the general impossibility result. Lastly there is the question of the instantiation of the RO in the BLS proof to which you will almost certainly receive an answer like this or mine. Namely that there is no magic happening in the BLS proof. So up to you to know which aspects matters most. :) – Marc Ilunga Jun 2 at 10:31