# Is $f(x) = g(x) ⊕ g(\bar{x})$ a one-way function where $g(x)$ is a OWF?

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?

• 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 – user3043904 Sep 19 '18 at 19:09
• 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. – fgrieu Sep 19 '18 at 21:11
• If $g(x)= g(\bar{x})$ than it is clear. Does, however, such $g(x)$ an OWF? – kelalaka Sep 19 '18 at 21:44
• 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? – Mikero Sep 20 '18 at 4:44
• @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. – fkraiem Sep 20 '18 at 6:35

## 2 Answers

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.

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