2
$\begingroup$

One of the conditions that a one-way function has to satisfy is the following:

$$Pr[A(f(x))\in f^{-1}(f(x))] \leq negl(n)$$

Now, suppose that we have the following function that's not one way: $$f(x) = x + 123$$ We know this isn't one-way since we can easily invert; that is: $$f^{-1}(x) = x - 123$$ But from the perspective of the adversary, if we have f(1) = 124, it would still essentially "brute-force" its way in order to find the inverse, right? In other words, the adversary would input random x's into f(x) until it finds a solution of 124 rather than formulating an inverse function (like a human normally would).

Is my understanding correct?

| improve this question | |
$\endgroup$
  • $\begingroup$ An intelligent adversary would notice the trivial pattern after two or three tries. Brute force is what you use when you have no better cryptanalytic tool at your disposal. $\endgroup$ – Stephen Touset Oct 9 '15 at 23:42
  • $\begingroup$ I see. But then, if we actually have a one-way function, the adversary would find it hard to invert regardless of whether or not the adversary is intelligent, which in that case, just entering random points would be its best bet. Right? And this is why the adversary should invert it with only a negligible probability in this case? $\endgroup$ – GraceTone Oct 9 '15 at 23:50
  • 3
    $\begingroup$ The adversary doesn't have to just evaluate $f$ on various inputs; it knows the function $f$. Since it knows that $f(x)=x+123$, given $y=f(x)$ for unknown $x$ it can just compute $y-123$ to invert. $\endgroup$ – Chris Peikert Oct 10 '15 at 0:25
  • 1
    $\begingroup$ According to Kerckhoff's principle, one always assumes that the adversary knows the function f. Also, he may do anything which helps him findinng a solution. $\endgroup$ – user27950 Oct 10 '15 at 7:20
2
$\begingroup$

As @Cryptostatis commented, Kerckoff's principle dictates that we must consider that the adversary knows the function.

More fundamentally, although the word “adversary” naturally suggests it must be a sentient being such as a human, remember that an adversary is in fact just an algorithm. The algorithm $A$ which on input $x$ returns $x-123$ inverts your function with probability $1$, demonstrating that your function is not one-way. How a human attacker would actually be able to "come up" with this algorithm is irrelevant, what matters is that such an algorithm exists.

| improve this answer | |
$\endgroup$

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.