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.

  • 1
    $\begingroup$ Consider $g(x)=f(x) \oplus x$ $\endgroup$ – CodesInChaos Aug 26 '17 at 12:15
  • $\begingroup$ 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. $\endgroup$ – Teresa Lisbon Aug 26 '17 at 12:41
  • $\begingroup$ 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. $\endgroup$ – CodesInChaos Aug 26 '17 at 12:43
  • $\begingroup$ @CodesInChaos Fine, thank you. If you write an answer I will accept it. $\endgroup$ – Teresa Lisbon Aug 26 '17 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.
  • 1
    $\begingroup$ 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. $\endgroup$ – Teresa Lisbon Aug 27 '17 at 4:42
  • $\begingroup$ One example is where you start with a random permutation and truncate its output, which is the way SHA-3 was constructed. $\endgroup$ – CodesInChaos Aug 27 '17 at 8:21
  • $\begingroup$ Thank you. I actually thought more about this, and managed to construct the example you suggested. Thanks again. $\endgroup$ – Teresa Lisbon Aug 27 '17 at 12:10
  • $\begingroup$ 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. $\endgroup$ – Teresa Lisbon Aug 27 '17 at 23:28
  • $\begingroup$ How do you show that there exists a OWF $f$ such that $f(x) \bigoplus x$ is also OWF? (suppose OWFs exist of course) $\endgroup$ – Mygod Sep 1 '17 at 23:51

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.