2
$\begingroup$

I was trying to prove that a given function is not a one way function and I was not sure how to do it because maybe I had unclear what a one way function was (OWF).

The definition that I have for a OWF is the following:

Easy to compute for all inputs: for all PPT A (probabilistic polynomial time algorithms), A(x) = f(x) $\forall x$

But hard to invert:

$$Pr[B(1^k, f(x)) = x' \ s.t. \ f(x) = f(x')] < neg(k)$$

for all probabilistic polynomial time adversaries.

However, the part that I was unclear about is, if EVERY f(x) has to be hard to invert, or if its ok for it to be easy to invert say for only and only two values (say f(x) and f($\neg x$) ). I guess I was a little confused about the "invertibility" part of the definition. Is there a problem if its easy to invert for some inputs?

Thanks in advance!

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ That information is exactly what your definition is missing. But in general when it comes to crypto we are interested in average-case one-way functions. Which means the probability is taken over the choice of x and therefore it is fine if the function is easy to invert for some inputs, as long as it is hard on average. $\endgroup$
    – Maeher
    Commented Feb 17, 2014 at 5:54
  • $\begingroup$ so what definition would you suggest? $\endgroup$
    – Charlie Parker
    Commented Feb 21, 2014 at 22:51
  • $\begingroup$ The "Easy to compute" part is clearly wrong since for any function $f$ we can define a PPT algorithm $A$ that simply output $\lnot f(0)$ for all $x$. That is, a PPT algorithm that is not equal to $f(x)$ at least for $x = 0$. The right definition should say "for some PPT A" instead of "for all PPT A". $\endgroup$
    – Hilder Vitor Lima Pereira
    Commented Jul 5, 2017 at 7:10

1 Answer 1

Reset to default
5
$\begingroup$

To prove that a function is not a OWF, you can exhibit an inversion algorithm and show that your inversion algorithm succeeds in inverting the OWF with non-negligible probability. In other words, if we randomly choose $x$, compute $f(x)$, feed $f(x)$ to your inversion algorithm, and let $x'$ denote the output of your algorithm, then you need to show that $\Pr[f(x')=f(x)]$ is non-negligible. Thus, this is average-case hardness, averaging over all possible inputs to the OWF.

Improve this answer
$\endgroup$
2
  • $\begingroup$ But it has to be for a random x, right? Also, what if the construction of the candidate OWF say g depends on another OWF say f (I don't want to give example because I want to solve the ones I have for myself), does that mean g is a OWFT if there is not OWF f that break g being a OWF? Because the one I have is a OWF for some stuff, but I can construct a specfic one that breaks g remaining being a OWF. $\endgroup$
    – Charlie Parker
    Commented Feb 18, 2014 at 1:39
  • $\begingroup$ @Pinocchio, yes, for a random $x$. Yes, my answer does not depend upon how $f$ is constructed; it applies regardless. $\endgroup$
    – D.W.
    Commented Feb 18, 2014 at 6:53

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