# Is the concatenation of two one-way functions a one-way function?

Suppose we are given two one way functions $f$ and $g$. We define a new function h that is the concatenation of f and g. That is, $h(x)=f(x), g(x)$, where the comma indicates concatenation. We want to figure out whether this is a one way function or not. My teacher tells me this is not true generally. I know it is true if $f=g$, but otherwise I am clueless. I'd love some help.

• Consider $g(x)=f(x) \oplus x$ Commented Aug 26, 2017 at 12:15
• Oh right. Then it is easy to invert the function h. But is h invertible more or less often? That is how I was asked the question. Commented Aug 26, 2017 at 12:41
• I think you're misunderstanding your teacher. "not true in general" means that there is at least one case where it's false. It doesn't mean that the majority of cases (whatever that'd even mean) is false. Commented Aug 26, 2017 at 12:43
• @CodesInChaos Fine, thank you. If you write an answer I will accept it. Commented Aug 26, 2017 at 12:45

But is h invertible more or less often? That is how I was asked the question.

When mathematicians say "This statement is not true generally" (or similar wordings) they mean "There exist cases for which the statement is false". So your teacher is talking about the statement "For all $f$ and $g$ which are one-way functions $h(x)=f(x),g(x)$ is also a one-way function" and says that this general statement is false, even if it might be true for some choices of $f$ and $g$.

Looking at this specific statement:

• There are choices where it's true. You already found the trivial $f=g$.
• There are choices where it's false. When $g(x)=f(x)\oplus x$, $h$ is never a one-way function, since you can recover $x=f(x) \oplus g(x)$ from $h(x)$ (technically you still have to show that there exist $f$ and $g$ of with this relation that are both one-way functions).
• In practical terms, if you don't choose $f$ and $g$ deliberately to produce a weak $h$, $h$ will normally also be an OWF, but mathematicians avoid such vague and difficult to formalize claims.
• Okay, so the next question is : how do I choose $f$ such that both $f$ and $g$ above are one way functions? I do know examples where $f$ is a one way function but $f(x) \oplus x$ is not, but I don't know examples of when both are one way functions. Commented Aug 27, 2017 at 4:42
• One example is where you start with a random permutation and truncate its output, which is the way SHA-3 was constructed. Commented Aug 27, 2017 at 8:21
• Thank you. I actually thought more about this, and managed to construct the example you suggested. Thanks again. Commented Aug 27, 2017 at 12:10
• Sorry to get back again. I am not allowed to use permutations. I need a more trivial example of the above phenomena. Although I have understood what you have said, we have not learnt one way permutations in class. Commented Aug 27, 2017 at 23:28
• How do you show that there exists a OWF $f$ such that $f(x) \bigoplus x$ is also OWF? (suppose OWFs exist of course) Commented Sep 1, 2017 at 23:51