4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Doesn't collision resistance directly imply one-wayness? $\endgroup$ – fkraiem Nov 7 '16 at 7:06
  • $\begingroup$ @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! $\endgroup$ – Konstantino Sparakis Nov 11 '16 at 18:02
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – tylo Nov 11 '16 at 18:36
  • 1
    $\begingroup$ And in fact, according to this reference your direction is not sufficient. $\endgroup$ – tylo Nov 11 '16 at 18:51
  • $\begingroup$ Truncate the output like sha-3? $\endgroup$ – Q-Club May 10 '17 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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