from Hacker News

Random oracle

by Promarged on 7/2/18, 8:27 AM with 9 comments

  • by throwawaymath on 7/3/18, 8:28 PM

    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.

  • by amingilani on 7/4/18, 1:28 PM

    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.

  • by lxe on 7/4/18, 12:43 AM

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