6
$\begingroup$

Given that $f$ is a OWF and $|f(x)|=|x|$ for all $x$, is $g(x)=f(x)\oplus x$ necessarily also a OWF?

$\endgroup$
13
$\begingroup$

While poncho's answer gives an interesting example, why this can go wrong in practice, it does not necessarily answer the question from a theoretical point of view. After all, we don't know whether $f(x) = AES_k(x) \oplus x$ is one-way. (Even if it might be reasonable to assume that.)

So, let's give a theoretical example. Assume that a one-way function $h$ exists where in- and output length are the same. We call this length $n/2$. I.e. we have a one-way function $$h : \{0,1\}^{n/2} \to \{0,1\}^{n/2}.$$

From this function, we now construct a new function $$f : \{0,1\}^{n} \to \{0,1\}^{n}$$ as follows: $$f(x_1\Vert x_2) = 0^{n/2}\Vert h(x_1),$$ where $|x_1|=|x_2|=n/2$.

It is easy to show via reduction that $f$ is one-way whenever $h$ is one-way. Let $\mathcal{A}$ be an attacker against the one-wayness of $f$, then we construct an attacker $\mathcal{B}$ against the one-wayness of $h$ as follows: Upon input of $y$, $\mathcal{B}$ invokes $\mathcal{A}$ on input $0^{n/2}\Vert y$. Eventually, $\mathcal{A}$ outputs $x_1'\Vert x_2'$ and $\mathcal{B}$ outputs $x_1'$.

It is trivial to see that if $\mathcal{A}$ runs in polynomial time (in input length $n$) then $\mathcal{B}$ also runs in polynomial time (in input length $n/2$).

It is also easy to see the following holds: $$\Pr[\mathcal{B}(y) \in h^{-1}(y)] = \Pr[\mathcal{A}(0^{n/2}\Vert y) \in f^{-1}(0^{n/2}\Vert y)].$$ Therefore it follows that $f$ is one-way whenever $h$ is.

Now lets use this function $f$ in the proposed construction:

$$g(x) = f(x)\oplus x = (0^{n/2}\Vert h(x_1) ) \oplus x_1\Vert x_2 = x_1\Vert (h(x_1)\oplus x_2)$$

This is obviously not one-way. An attacker upon seeing an image $x_1\Vert y$ can simply output $x_1\Vert (y\oplus h(x_1))$ as a valid preimage.

$\endgroup$
  • $\begingroup$ I think $x_{\hspace{.02 in}1}$ should be replaced with $x_{\hspace{.02 in}1}'$. $\:$ Also, one can let the construction have slightly better $\hspace{.4 in}$ efficiency in general by letting $\hspace{.04 in}f$'s input and output lengths be $m$ and $n$ instead of $n/2$ and $n/2$. $\hspace{.64 in}$ $\endgroup$ – user991 Feb 8 '15 at 12:30
  • $\begingroup$ Thanks, fixed the $x_1$ mixup. About the generality, yes that is true, as long as the length of $x_1$ is superlogarithmic, everything should be fine. But as this is a counter example, I think it's fine to be more specific. $\endgroup$ – Maeher Feb 8 '15 at 12:34
  • $\begingroup$ Of course, this is only a counter-example if one-way functions exist at all. $\endgroup$ – Paŭlo Ebermann Feb 8 '15 at 12:46
  • 1
    $\begingroup$ @PaŭloEbermann If one-way functions don't exist then the question is vacuous since it is predicated on $f$ being a one-way function :) $\endgroup$ – Thomas Feb 8 '15 at 13:12
  • 4
    $\begingroup$ If one-way functions do not exist, then the statement is trivially true, because it is an all quantified statement about the empty set. $\endgroup$ – Maeher Feb 8 '15 at 14:22
6
$\begingroup$

No, you can find $f$ such that $f(x)$ is a OWF, but $f(x)\oplus x$ is not.

One example would be $f(x) = AES_k(x) \oplus x$ (for a public key $k$, perhaps the all-zeros key). $f(x)$ is believed to be one way; as there is no known practical way, given a value $y$, to find an $x$ with $f(x) = y$. However, $g(x) = f(x) \oplus x = AES_k(x)$ is easy to invert (because we know the AES key $k$).

$\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.