# How can a hash function that implements random oracle model have collision resistance?

ROM is considered to be collision resistant. Does ROM assume there is an infinite set of outputs, or assume the output set is always larger than the input set? Because by the pigeonhole principle, ROM is guaranteed a collision given a large enough set of input, even when the output is generated randomly.

• "Collision resistance" does not mean "Collision free", necessarily. Maybe that is a contributor as to the confusion? Being hard to find to find isn't the same thing as non-existence. Jun 25 '16 at 16:25

• No, there is no such function that has no collisions, since the range is finite. That is certainly not what's assumed in ROM. You assume that the function has uniform distribution on its finite size output set [256 bitlength strings, for example]. Then, the best case happens, i.e., collisions don't become likely until you have $\sqrt{2^{256}}$ or so input queries, due to the birthday paradox. May 14 '19 at 0:17
The random oracle model posits a finite domain and a finite codomain; otherwise the space of functions would be infinite and there could not be a uniform distribution on them. If $$f\colon A \to S$$ is a uniform random function into a set $$S$$ of $$n$$ elements (e.g., $$S$$ is the set of $$t$$-bit strings, so that $$n = 2^t$$), then $$f(x)$$ is independent for each distinct $$x$$, and $$\Pr[f(x) = h] = 1/n$$ for each $$x$$ and $$h$$.
When we combine these two properties—$$x \ne x'$$ implies $$f(x)$$ and $$f(x')$$ are independent, and $$\Pr[f(x) = h] = 1/n$$—we can conclude from a standard birthday argument that any algorithm making $$q$$ queries to a random oracle has probability at most $$q^2/n$$ encountering a collision. Following Ramanujan, Knuth, etc., the expected number of queries before a collision is $$1 + \sum_{k=0}^{n - 1} \prod_{i=1}^k \biggl(1 - \frac i n \biggr) = 1 + \sum_{k=1}^n \frac{n!}{(n - k)! \, n^k} \approx \sqrt{n \pi/2}.$$ Consequently, the expected query cost of any algorithm to break a cryptosystem like RSASSA-PSS signature by finding a collision in a $$t$$-bit random oracle is about $$2^{t/2}$$—which for typical values of $$t$$ like 256 is far beyond the capacity of humanity to carry out.