Tag Info

A random oracle is described by the following model: There is a black box. In the box lives a gnome, with a big book and some dice. We can input some data into the box (an arbitrary sequence of bits). Given some input that he did not see beforehand, the gnome uses his dice to generate a new output, uniformly and randomly, in some conventional space (the ...

A random oracle is an ideal object; see this previous question for some details. 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 try it. For instance, consider the following encryption scheme: $H$ is a random oracle which outputs $n$-bit values. The key is a $K$, a string of ...

If you can show a reduction of a security property of your protocol to the security of a hash function is the standard model, you do not need the random oracle assumption. So a proof in the ROM does not have any general (positive) meaning in the SM; hence why it is controversial. About the only general thing you can say is that some (arguably highly ...

Your second question was about programmability. This hasn't been directly addressed yet by Thomas' answer or the comments, so I'll focus on that question only. Unfortunately I don't know of a simple primitive that is secure in the random oracle model that requires programmability, but I'll use one that is hopefully clear once I explain the background. It's ...

A random oracle is an idealization of a hash function $H$: if hash functions were perfect they would be random oracles. This is why it is always easier to consider a hash function a random oracle when one proves something about a larger scheme. Those are "proofs in the random oracle model". [1] That being said it is still possible to prove things using ...

Guillo-Quisquater scheme uses the Fiat-Shamir trick to convert a proof of knowledge into a signature. There is a paper out there about the security of such schemes in the random oracle model here which seems to give what you want.

Another approach is to assume that the hash function is collision-resistant, and see if you can prove your protocol is secure under this weaker assumption. For some protocols, it is possible, and then you're good. For others, it's not. (More precisely, you demonstrate that any successful attack on the protocol can be turned into an algorithm that produces ...

There's the common random string model (where hash functions can be modeled as having been picked from a family of functions using public coins). There are also "whatever-tractable random oracles", where adversaries also have an oracle that finds a whatever with respect to the random oracle. (Usually 'whatever' is one of ...

A "random oracle" is essentially a perfect hash function. It's a device that takes a message of any length and maps it randomly to a message of a fixed length such that the same input always produces the same output. Random oracles don't exist. For algorithms that require them, cryptographic hash functions are used instead. However, cryptographic hash ...