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.

Related but answered question here.


1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.