The random oracle assumption is a useful tool in cryptographic proofs, and this is about a mistake I made on its technicalities.

In crypto we have hash functions. They take on bitstrings of any length, and output bitstrings of some fixed length. They are deterministic, but have random looking output, among other properties. They are a useful primitive in creating other protocols.

A random oracle is a hypothetical object. It can be queried, and given some input. If it has never seen the same input before, it ouputs some random string chosen uniformly random from its output domain. Then it writes down the input and random string pair. If it has been queried on an object it has seen before, it outputs the previous written down random string.

The random oracle assumption is that instead of using some real defined hash function, you use a generic hash function and say it is assumed to be a random oracle. You continue your proof using this and then your proof is complete, on this assumption. In practice, you use a real hash function like SHA256 instead of this hypothetical random oracle. This also helps with proofs age. If you assumed some constructed protocol was secure against a specific hash function, then later said hash function was broken (MD5, SHA1), the security of the rest of your protocol might be violated. Under the random oracle assumption, your proof of security of your protocol will remain unchanged, but you may need to update the hash function used in any real implementation.

Here is my idea. Assume a random oracle exists, then it can be shown that the real numbers are countable. What does this mean? For infinite sets, there are two cardinalities: countable, and uncountable. Uncountable sets are those which cannot be naturally ordered. Think like trying to sort the water in a bucket. There are a few definitions which are all equivalent, but here is the one I like. A set, say is uncountable if there exists no injective map . A set is countable if such a map exists. No such map exists for the real numbers. But what about just using a random oracle as our map? Is it injective? Yes, the random oracle always returns some value. The outputs are not guaranteed to be different just from the assumption, but for a real hash function, this is desired. So we can strenghten our random oracle for this assumption. Then such if such one could exist, then the real numbers would be countable, a contradiction.

Heres the problem with this argument. The assumed random oracle does not have uncountable domain. Most definitions online completely exclude any mention of domain and co-domain of a random oracle, including some textbooks. The closest thing I found was the original paper to introduce the random oracle assumption by Bellare and Rogaway. They have their random oracle defined as . The domain is countable, and here is the map. Let such that , that is, take the binary string, prefix a 1, and map it to its integer representation in base 2. Since this function is injective, the set of all finite bitstrings is countable. Fun fact, the output space they define is actually uncountable. Map with to as a binary representation. The codomain is then the interval which is uncountable. In their book ten or so years later, they make no mention of the input space, and have the output space as elements of the multiplicative (and finite) group .