# Can you build a One Way function from a Collision Resistant Function Family?

The assumption is you have a Collision Resistant function(CRF) Family F. How do you use F to build a One Way function (OWF).

One Idea I have is to use 2 functions from the CRF Family. Both these functions have n input and n/2 output. You as a user inputs n bits ({0,1}^n) and get an output of n, by using 2 of these functions that output n/2 and concatenate them together to get n output.

This would work in creating a one-way function? or is the idea of a one-way function is that it needs to be able to be inverted, but that it is computationally difficult to do so, while a CRF you can not invert to the original answer?

• Doesn't collision resistance directly imply one-wayness? – fkraiem Nov 7 '16 at 7:06
• @fkraiem Yes in fact it does I was confusing myself. I simply needed a proof to show this. And I figured something out so thank you! – Konstantino Sparakis Nov 11 '16 at 18:02

So in fact, you can build a One-way function from a Collision Resistant Function.

Using a function family of CR functions F, we can create a one way function that works as follows:

pick function F from CRF family, F = ${f_k}$ $g =\ one\ way\ function$ $x_1\ and\ x_2$ picked from random

$g(x_1, x_2) = f_{x_1}(x_2),\ x_1$

The reason this works is because in order to break this one way function you would have to break the fact that $f_{x_1}$ is collision resistant.

Proof:

So let us assume there is an adversary A that can invert CR function $f_{x_1}(x)\rightarrow y$.

$A(y) \rightarrow x$ What A returns is a pre-image of x so it can be the original x or a collision.
So now lets assume there exists an A' that can use A to break our one way function. The way he will do so is by first allowing the random inputs of $x_1\ and\ x_2$.
$g(x_1, x_2)= f_{x_1}(x_2),\ x_1 \rightarrow y$

Now A' uses $A(y)\rightarrow x$ The output x is either = $x_1$ or a collision. With this A' has now successfully broken my scheme. But because we know that an adversary A that can find a collision/invert a collision resistant function does not exist in polynomial time we know our scheme is safe and one way because if one can not find a collision in polynomial time then one can not break the one wayness of my function in polynomial time.

• The logic in this answer is wrong. You use an adversary for the CRF to get an adversary for the one-way function - but that just shows that if it is a one-way function, then $f_k$ was collision resistant. You want / need to show the other direction. – tylo Nov 11 '16 at 18:36
• And in fact, according to this reference your direction is not sufficient. – tylo Nov 11 '16 at 18:51
• Truncate the output like sha-3? – Q-Club May 10 '17 at 21:21