Let $g$ be a one-way function, and let $f(x) = g(x) ⊕ g(\bar{x})$ (where the bar over x denotes bitwise complement). Is $f$ necessarily a one-way function?

  • $\begingroup$ I've thought about this approach but haven't been able to find one that works yet. I think I need to exploit the properties of the xor operation in some way by constructing $g$, though I'm stumped on how to (I think the fact that $f(x) = f(\bar{x})$ is going to be a helpful fact, but not sure how to leverage this fact in the construction of $g$). I thought about letting $g(x)=x_{1} || h(x_{2})$, (where $h$ is a OWF and $x = x_{1} || x_{2}$), but this didn't yield anything useful.. also considered $g(x)=x_{1} ⊕ h(x_{2})$, but again, this doesn't lead to anything useful $\endgroup$ – user3043904 Sep 19 '18 at 19:09
  • 1
    $\begingroup$ Hint1 (polished): can you find a counterexample? Like some OWF $g$ which makes $f$ a trivially not OWF function? Bonus if you construct that $g$ from any OWF $h$ with the same input/output sets. Hint2: constant functions are not OWF. Hint3: $\oplus$ is the group law of a Boolean group. $\endgroup$ – fgrieu Sep 19 '18 at 21:11
  • $\begingroup$ If $ g(x)= g(\bar{x})$ than it is clear. Does, however, such $g(x)$ an OWF? $\endgroup$ – kelalaka Sep 19 '18 at 21:44
  • 3
    $\begingroup$ My favorite hint: if the answer to your question is yes (constructing $f$ from $g$ always results in a OWF), then you can apply that construction again to $f$ and get yet another OWF. Is that what happens? $\endgroup$ – Mikero Sep 20 '18 at 4:44
  • 2
    $\begingroup$ @fgrieu Note that using an assumed OWF $h$ as a black-box is the only way to construct an OWF $g$, since no concrete function is known to be one-way, so no bonus points for that. $\endgroup$ – fkraiem Sep 20 '18 at 6:35

Expanding on @Mikero's comment above: First, lets assume that a one-way function $h : \{0,1\}^n \to \{0,1\}^n$ exists.

Then assume towards contradiction that $f(x) = g(x) \oplus g(\bar{x})$ is a one-way function if $g$ is a one-way function. Then in particular $f'(x) = h(x) \oplus h(\bar{x})$ must be a one-way function. And further it follows that \begin{align} f''(x) =\;& f'(x) \oplus f'(\bar{x})\\ =\;& (h(x) \oplus h(\bar{x})) \oplus (h(\bar{x}) \oplus h(x))\\ =\;& (h(x) \oplus h(x)) \oplus (h(\bar{x}) \oplus h(\bar{x}))\\ =\;& 0^n \end{align}

would be a one-way function, which it is clearly not as it is a constant function.

| improve this answer | |

This can be useful in other contexts as well.

Proposition. If one-way functions exist, then there is a one-way function $f$ such that $f(x) = f(\overline x)$ for all $x$.

Proof sketch. Let $F$ be a one-way function and $f$ be such that $f(x) = F(x)$ if the first bit of $x$ is $1$ and $f(x) = F(\overline x)$ otherwise. It is evident that $f(x) = f(\overline x)$ for all $x$. To show that $f$ is one-way, consider an adversary $\mathcal A$ that, for infinitely many $n$, successfully inverts $f$ on inputs of length $n$ with probability at least $1/p(n)$ for some polynomial $p$. Then, for the same infinitely many $n$, $\mathcal A$ inverts $F$ on inputs of length $n$ with probability at least $1/(2\cdot p(n))$.

| improve this answer | |

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.