A model used in cryptographic security proofs, in which concrete primitives such as hash functions are replaced with a "random oracle": a hypothetical black box that maps its inputs to truly random outputs, but in such a way that the same input always yields the same output.

learn more… | top users | synonyms

47
votes
1answer
7k views

What is the “Random Oracle Model” and why is it controversial?

What is the "Random Oracle Model"? Is it an "assumption" akin to the hardness of factoring and discrete log? Or something else? And why do some researchers have a strong distrust of this model?
15
votes
2answers
1k views

Random oracle model proofs and programmability

Proving the security of a scheme with the random oracle model (ROM) involves two steps: first you prove that the scheme is secure in an idealized world where a random oracle exists, and then you ...
11
votes
2answers
295 views

Are there any real protocols secure in the random oracle model that have been broken in practice?

Has any protocol ever been proven secure in the random oracle model and then broken in practice, despite the use of a good hash function in the actual implementation?
11
votes
1answer
154 views

Explanation and proof of a well-know probabilistic lemma

Pointcheval and Stern in their paper on "Security proofs for Signature Schemes" state the following "well-known" probabilistic lemma: Let $A \subset X \times Y$, such that $\mathrm{Pr}[A(x, y)] \...
8
votes
4answers
483 views

Automated security protocol verification tool for eCK model

I want a tool that (runs on Win7 and) can perform automated verification of a protocol in the eCK security model as described in Microsoft Research's paper "Stronger Security of Authenticated Key ...
7
votes
1answer
779 views

understanding forking lemma

Every time when I read a paper that has digital signature, when it comes to prove the security of a digital signature scheme, many chances that the author will use the forking lemma. The forking ...
7
votes
1answer
2k views

Difference between Hash function and Random Oracle

Going through the blog post, I was under the impression that any cryptographic scheme which makes use of hash function is said to be using random oracle. But, I have come across one construction of ...
7
votes
2answers
125 views

Instantiating a random oracle

I am studying about RO model and just got this question that what are the factors that make it not possible to instantiate a RO with a Hash function. To give a reference on how far I know about them ...
7
votes
1answer
208 views

Is there a security proof for the Triple-DES construction in the ideal cipher model?

Suppose one has an ideal block cipher $E \: : \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^k \times \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w \: \to \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w \;...
7
votes
1answer
183 views

Secret key and Decryption oracle in the revised Fujisaki-Okamoto transformation

Recently, Fujisaki and Okamoto provided a revised version of the Fujisaki-Okamoto transformation [1], a generic transformation for achieving IND-CCA2 security in the Random Oracle model. This new ...
7
votes
1answer
153 views

Why does it matter for a signature scheme to be without random oracles?

There is a profusion of articles proposing signature schemes without random oracles (see for yourself). What does that mean, and why does it matter?
6
votes
1answer
660 views

How random is the shared secret in the Diffie Hellman key agreement

How random is the value $ZZ$ in the DH protocol? This question was triggered by this somewhat naïve implementation in I2P shown by Sergei at Stackoverflow. Obviously $ZZ$ is distinguishable from a ...
6
votes
1answer
301 views

Entropy when iterating cryptographic hash functions

Consider a cryptographic hash function that maps $n$-bit strings to $n$-bit strings: $$ \DeclareMathOperator{\H}{H} \DeclareMathOperator{\SHA}{SHA-256} \H(x) : \left\{0,1\right\}^{n} \mapsto \left\{0,...
5
votes
2answers
239 views

Is the following symmetric design secure?

Assume: $O$ be a reversible random permutation oracle on a finite set and $O^{-1}$ the inverse permutation (pretty much equivalent to a random permutation: What is the difference between a bijective ...
5
votes
1answer
517 views

One-Way property of Random Oracle

I'm currently working on a proof in the Random Oracle model, and could not find the formal argument on why the random oracle is one-way (i.e. for an Oracle $O$, it is easy to calculate $x=O(n)$, but ...
5
votes
2answers
293 views

When is the Random Oracle model (not) necessary?

Hash functions are often used in cryptographic schemes and protocols, and that doesn't necessarily mean that their proofs are on the Random Oracle model. That leads to the following question: What is ...
4
votes
1answer
470 views

How does Random Oracle and Standard Model differ? [duplicate]

I am new to Crypto field. Many papers are boasting of not using Random Oracle model. Instead, those prove security in Standard Model. I am surprised how do these models differ. Can anyone please ...
4
votes
2answers
389 views

Hash function based on block cipher (and proof of security in the PRP model)

Do there exist proofs of security for primitives like hash functions (based on a block cipher) in the PRP model. I often see proofs in the random oracle model (for hash function based on compression ...
4
votes
1answer
172 views

Does security under ROM imply exactly what?

I'm not sure I understand really the implications of proofs of security in the random oracle model. Does a proof of security in ROM translate to a reduction of security of the crypto-system to the ...
4
votes
1answer
48 views

Padding schemes for asymmetric encryption with provable security in the standard model

Most padding schemes for asymmetric encryption (OAEP, OAEP+) are only proven secure in the random oracle model. Although no attacks are known, it would be nice to find a padding scheme with provable ...
4
votes
1answer
149 views

Length-preserving all-or-nothing transform

Is there any known way to construct a length-preserving all-or-nothing transform? In other words, a secure all-or-nothing transform where the length of the output is the same as the length of the ...
3
votes
2answers
290 views

Is a random oracle controled by the challenger?

When proving a Crypto scheme security under random oracle model, is the random oracle always controlled by the challenger? What if the Hash is only used by the adversary?
3
votes
1answer
567 views

Why are protocols often proven secure under the random oracle model instead of a hash assumption?

Is this true that whenever you design a protocol using a hash function, you must prove its security under the random oracle? I mean, is it possible to devise a protocol $P$ using a function $H$, and ...
3
votes
1answer
138 views

Simulation aborted because the adversary doesn't use the random oracle

I'm trying to construct a proof for an encryption scheme in the Random Oracle model. This encryption scheme is like a PKE scheme but with an additional function that kind of "alters" ciphertexts ...
3
votes
1answer
132 views

What does “learnable with oracle queries” mean?

I came across the following quotes in reading papers on obfuscation (1, ibid, and 2): The next result follows from the fact that point functions are not exactly learnable (since a uniformly chosen ...
3
votes
1answer
44 views

May I use Random Oracle for Inversed Look-up?

Consider there is a protocol in real world calling a random oracle $\mathcal{H}$ for a priavte input $k$. Then in the ideal world, after the calling of $r \leftarrow \mathcal{H}(k)$ by a honest party, ...
3
votes
1answer
52 views

How is a hash function that implements random oracle model collision resistance?

ROM is considered as collision resistance. Does ROM assume there is an infinite set of output, or assume the output set is always larger than the input set? Because by the pigeonhole principle, ROM is ...
3
votes
0answers
93 views

Unlinkability of Merkle-Damgård hash function results

Question: Are multiple outputs of a Merkle-Damgård hash function (or specifically SHA-256, if this can only be said for a specific algorithm) on unknown data unlinkable? If yes: Can this be formally ...
2
votes
1answer
55 views

Random oracles and independence

I'm reading an unpublished paper in which the author makes the following conclusions several times: Assumptions: finite probability space, $H$ is a random oracle, $X$ and $Y$ are two (not necessarily ...
2
votes
1answer
174 views

Is this modified Schnorr signature scheme secure?

Signing Let y = g^x, which is your public/private keypair. Let r = g^v, for random v Let c = H(M) Let z = (v + cx) mod q The signature is the pair (r,z) Verifying g^z = ry^c mod p We further ...
2
votes
1answer
74 views

Proven secure scheme under random oracle

Currently I am trying to understand random oracle model in order to make a small presentation about it but I seem to be very confused about it. Since it's an hypothetical model without a real life ...
2
votes
1answer
76 views

Does the time to evaluate a hash function depend on the function input size?

Suppose we have a (variable-input size) hash function modeled as a random oracle. Can it be consistent to say that the time to evaluate this function depends on the input size ?
2
votes
1answer
107 views

Is it OK to substitute a PRF for a random oracle?

Random oracles don't exist, but aren't PRFs essentially indistinguishable from them? So why can't we substitute pseudorandom functions wherever we use random oracles? And if we can do this, why is ...
2
votes
1answer
227 views

Is Guillou-Quisquater existentially unforgeable against adaptive message attack under a random oracle model?

First of all, the Guillou-Quisquater digital signature scheme is: Note everything is $\bmod n$. Message is denoted by $m$. Private key: $s$ Public key: Hash function $H$, $e$, $L=s^e\...
2
votes
0answers
51 views

How to force an adversary to call a certain oracle?

Consider there is a protocol in real world, which uses a random oracle $\mathcal{H}$. In the ideal world, after the calling of $\mathcal{H}$ by some parties, intuitively I want the simulator gets some ...
2
votes
0answers
122 views

Formal proof of theorem concerning the Random Oracle Model

Reading a book on cryptography by Douglas R. Stinson I've met the following theorem, which is stated without proof (see here). Thereby, $\mathcal{F^{X,Y}}$ denotes the set of all functions from $\...
2
votes
0answers
158 views

Obfuscating point-like functions

There are standard schemes for obfuscating a point function; I'm wondering if we know how to obfuscate a slight generalization of a point function. I'll elaborate more precisely. Definition 1. A ...
2
votes
0answers
181 views

How can I prove that this encryption scheme from a random oracle is secure?

I am reading this example: A random oracle is an ideal object. What makes a random oracle convenient for proofs is the part about knowing nothing on the output for a given input if you do not ...
1
vote
2answers
204 views

Acceptable assumptions when proving security

Considering the output of a cryptographic primitive, like an encryption scheme (CBC, ...), a hash function or even the output of any schemes based on number theoretic assumptions, is it reasonable (...
1
vote
1answer
114 views

What is the difference between a bijective random oracle and a random permutation?

Assume $S$ be a finite set $O$ be a random oracle from $S$ to $S$, such that $O$ is bijective $f$ be a random permutation of $S$ Is there any difference between $O$ and $f$? Does it makes any ...
1
vote
1answer
55 views

Differences between OWP and OWF and their IND-CPA security

I am learning about one way permutations and one way functions and am not sure of the differences if there are any. Also in the random oracle model are they both IND-CPA secure?
1
vote
1answer
83 views

On modeling a random oracle hash function which maps $\mathbb{G}_1 \rightarrow \mathbb{G}_2$

How can one model a random oracle hash function which maps $\mathbb{G}_1 \rightarrow \mathbb{G}_2$? (Assume $\mathbb{G}_1$ and $\mathbb{G}_2 $ to be additive and multiplicative groups of prime order $...
1
vote
1answer
39 views

Is there any benefit to using a randomly chosen replacement strategy on a string before or after encrypting it?

This is more of a mental exercise for me than anything else. I've thought about doing something like this before, mostly to make a broken cipher a little more difficult to decrypt to plain text. I've ...
1
vote
1answer
35 views

Explanation of protocol secure under random oracle but insecure with any hash fuction

It is known that there is a protocol that is secure in the random oracle model, but where any real hash function makes the protocol insecure. The proof is constructive, but I could not understand the ...
1
vote
0answers
65 views

Why security proof uses random oracles in identity-based encryption?

In identity-based encryption, users decrypt the ciphertext by using private keys. Without private key, no one will be able to decrypt.In security proofs like here, random oracles are used with the ...
1
vote
0answers
184 views

Zero Knowledge Non Interactive Proof with random oracle

I am trying to write an assay about Non Interactive Zero-Knowledge proofs and would like to take the simple discrete logarithm problem example fallowing the Feige-Fiat-Shamir heuristics. I understand ...
1
vote
0answers
60 views

Forward Secrecy with pseudorandom functions

Let $H_1$, $H_2$ be keyed hash functions (e.g. $H_i(x) = SHA_{256}(s_i||x)$ for pseudorandom $s_1$, $s_2$). Let $s_n = H_1^k(s_0)$, $k_n = H_2(s_n)$, where $s_0$ is a secret (pseudorandomly chosen ...
1
vote
0answers
171 views

Hash function with values in a multiplicative group of prime order [closed]

I have to implement a cryptographic protocol which involves a cryptographic hash function $H: \{0,1\}^* \to G$. It is viewed as random oracle. $G$ is a multiplicative group of prime order. I want to ...
0
votes
1answer
52 views

What is the difference between a random oracle and a probabilistic algorithm? [closed]

What is the difference between a random oracle and a probabilistic algorithm?
0
votes
0answers
37 views

Independence of answers to queries sent to a random oracle

Assume we have an algorithm which asks random oracle $\mathcal{O}$ $Q$ queries $u_1, \ldots, u_Q$. All queries are unique, $u_i \neq u_j$ for $i \neq j$. Queries $u_i$ are random variables, too. What ...