Signature security proof in the Random Oracle model

Question

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.

Answer 1

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.

Answer 2

(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

[BG]: Bennett and Gill. Relative to a Random Oracle A $P^A\neq NP^A\neq co\mathit{-}NP^A$ with Probability $1$

[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.

Answer 3

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}$.

Answer 4

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.