Random oracle

36 points by Promarged 8 years ago | 9 comments

I've always been intrigued by the way that certain Wikipedia pages can show up on the front page of HN. They always feel so...lacking in motivation. Maybe that's why they languish without discussion :). There's no straightforward explanation of why the random oracle model is a thing in this article, or why cryptographers don't always just use the standard model.

The standard model of cryptography is the basic, default model in which security is a function of the computational time and power required by an adversary to break the cryptosystem. This conception is purely complexity theoretic: we have e.g. a construction based on a hash function, and we want to make sure there is no polynomial time algorithm for breaking it so long as the hash function is preimage and collision resistant. The construction is "provably secure" if we can prove there exists no such algorithm when the hash function has the requisite properties. Then we say the cryptosystem is "secure in the standard model."

Provable security in the standard model is difficult to achieve - we can't always extrapolate the complexity theoretic security of a cryptosystem from the underlying security of its hash function. We could give it our best effort and still use it since it seems hard to break, but that's not a sound basis for cryptanalysis. Instead, the random oracle model is an "idealized model" that offers a compromise between the strict security of the standard model and shrugging our shoulders. This lets us determine that, as long as the model approximates an ideal version of the cryptosystem, we have some measure of assurance that there really is rigorous security involved - some proof is better than no proof.

To use the random oracle model, we replace the hash function in question (ostensibly, pseudorandom) with a truly random function - its "ideal" version. We do this by modeling a black box which every participant in the cryptosystem can query but which no participant can peer inside. A query is an input binary string, and the oracle returns an output binary string when queried. Although the output of each query is truly random, it's consistent: repeating a query results in the same output as the original. Then a proof of security in the random oracle model indicates that any weakness present in the standard model is a weakness lying between the pseudorandomness of the hash function and the ideal randomness of the oracle function.

Much as we don't need the true randomness of a one-time pad for practically secure encryption, and can opt instead for the computational assurances of the standard model, the random oracle model posits that a sufficiently secure hash function is "secure enough" even if it isn't truly random.

robertk 8 years ago | |

Just curious, why the anonymous response? You clearly have read Goldreich, which is enough entropy to narrow down your identity to about 1000 people in the world.

throwawaymath 8 years ago | | |

This account isn't intended to be perfectly anonymous. I just use it to maintain plausible deniability and dissociate my real name from HN debates :)

amingilani 8 years ago |

Is there output size fixed? Because in that case, if I feed it an array of inputs larger than the output size, it'll logically have to throw a collision. At that point, how is it better than a hash function?

Forgive the naivety of my question. I'm self-taught.

matthewdgreen 8 years ago | |

Random oracles are a model for reasoning about hash functions, so generally speaking they have the same “API” as whatever type of hash function you’d use in the real world. Most commonly that means they take in an arbitrary-length input and output a fixed-size digest. So yes, by the pigeonhole principle they will have collisions.

One major difference is that “the oracle implements a random function” implicitly guarantees several security properties that otherwise you’d have to assume as complexity assumptions. For example, a random function has collision resistance due to the simple fact that outputs are distributed randomly and therefore finding a collision should take (on average!) many queries to the oracle. With standard hash functions, you have to assume collision resistance.

lxe 8 years ago |

From what I gather it's basically like an infinite shuffled deck of cards. For every position in deck (input), you get a card (output).

unixhero 8 years ago | |

Umm. I think that is too simplistic because it does not include a way to get the same shuffled deck if you ask it a previous query.

From what I gather it is like a procedurally generated massive open world game, where every time you ask for a new place to go, you get a new randomly generated place. The random oracle olso lets you return to all the previous places. By effectively making the same query, and getting identical answers from previous queries. In that way you can to old cities, planets, worlds.

Now, someone do a car analogy! :-)

lxe 7 years ago | | |

> it does not include a way to get the same shuffled deck if you ask it a previous query.

You put the card back in the same place in the deck (just look at the card... don't take it out). You always get the same random card for the same "index" (where upper bound in infinite) or "key" or "query".