3
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Consider $g(x)=f(x) \oplus x$ $\endgroup$ Aug 26, 2017 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$ Aug 26, 2017 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$ Aug 26, 2017 at 12:43
  • $\begingroup$ @CodesInChaos Fine, thank you. If you write an answer I will accept it. $\endgroup$ Aug 26, 2017 at 12:45

1 Answer 1

4
$\begingroup$

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.
$\endgroup$
5
  • 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$ Aug 27, 2017 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$ Aug 27, 2017 at 8:21
  • $\begingroup$ Thank you. I actually thought more about this, and managed to construct the example you suggested. Thanks again. $\endgroup$ Aug 27, 2017 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$ Aug 27, 2017 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, 2017 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.