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

34
votes
1answer
5k 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?
5
votes
1answer
231 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 ...
6
votes
1answer
478 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 ...
7
votes
1answer
554 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 ...
11
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 ...
8
votes
4answers
397 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 ...
4
votes
1answer
110 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 ...
4
votes
1answer
150 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 ...
3
votes
1answer
395 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 ...
1
vote
1answer
90 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 ...
2
votes
0answers
91 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 ...