Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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!

share|improve this question
4  
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. –  Maeher Feb 17 at 5:54
    
so what definition would you suggest? –  Pinocchio Feb 21 at 22:51
add comment

1 Answer 1

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.

share|improve this answer
    
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. –  Pinocchio Feb 18 at 1:39
    
@Pinocchio, yes, for a random $x$. Yes, my answer does not depend upon how $f$ is constructed; it applies regardless. –  D.W. Feb 18 at 6:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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