# Collision resistant hash function implies one-way function

I'm struggling to give a formal proof that $$CRH \implies OWF$$ using the definition below.

Intuitively, I see why a $$CRH$$ would be "hard to predict" and might be used as a $$PRF$$, but I'm unable to give a formal proof.

$$\mathcal{H} = \{\mathcal{H}_n = \{h:\{0,1\}^* \rightarrow \{0,1\}^n \}\}$$ is a $$CRH$$ if it can be efficiently sampled and $$\forall_{A;PPT} \exists_N \forall_{n>N} \Pr_{h \rightarrow H_n} [A(1^n, h) = (x, x') \land x \neq x' \land h(x) = h(x')] = neg(n)$$

Proving the existence of $$PRG$$ or $$PRF$$s would suffice.

Collision-resistance implies one-wayness. Proof by reduction: if you have an algorithm $$A$$ which is able to invert $$H: b^* \rightarrow b^n$$, we can build an algorithm $$B$$ which is able to find a collision (with almost the same time and probability). Here $$b$$ means $$\{0,1\}$$.

Let's consider only input strings of some length $$l\ge n$$. Notice that $$H$$ splits the set $$b^l$$ into the following $$2^n$$classes: $$\{C_h = \{x: x\in b^l \land H(x)=h \}\}_{h\in b^n}.$$ On expectation (if function behaves randomly), each class consists of $$k = 2^{l-n}$$ elements. But for our concrete function some of the classes could be empty, while some of them have more elements than others.

Algorithm $$B$$ behaves as follows:

1. Picks random $$x\in b^l$$ and evaluates $$h = H(x)$$.
2. Runs $$A$$ on input $$h$$: $$x' = A(h)$$.
3. If $$x \neq x'$$, returns a collision $$(x, x')$$. Goes to step 1 otherwise.

Easy to see that probability of success on step 3 is $$1 - \frac{1}{k}$$ (which is quite a lot, and you can increase $$k$$ or just make several rounds of algorithm to achieve any probability you want). The explanation is: when you're picking $$x$$ on first step, you're picking one of $${C_h}$$ with probability proportional to a number of elements in the class: $$Pr[C_h] = \frac{|C_h|}{2^l}$$. Then, on the step 3, probability of failure, i.e. $$x = x'$$, is $$1/|C_h|$$, taking into account uniformly random choosing of $$x$$ and the fact that $$A$$ "doesn't know" which element $$x$$ from the class $$C_h$$ you selected (you've given him just $$h$$). So, the common probability of failure is calculated as: $$Pr[\texttt{"failure"}] = \sum_{h\in b^n} {Pr[C_h] \cdot Pr[\texttt{"failure on C_h}"]} = \sum_{h\in b^n} {\frac{|C_h|}{2^l} \cdot \frac{1}{|C_h|}} = 2^n\cdot \frac{1}{2^l}.$$

Remark that we do not require any random properties of $$A$$ nor $$H$$. We achieve this probability estimate just using randomness of $$B$$ (uniformly random choosing of $$x$$ on step 1).