Similar to this question, but having two seperate inputs for each length preserving one way function $f$ and $g$, i.e. $h: \lbrace 0,1 \rbrace^{2\kappa} \to \lbrace 0,1 \rbrace^{2\kappa}, h(x) = f(x_1)||g(x_2)$ where $x_1$ and $x_2$ are two $\kappa$ bit split halves of x.

I think $h$ will be one way, but am not sure on the appropriate reduction to demonstrate this.

I think I don't need to show that the probability of an attacker decrypting this being negligible in polynomial time but rather reduce to problems of one-wayness of $f$ and $g$ and knowing that they are one way should demonstrate that in fact $h$ is one way

  • 1
    $\begingroup$ This seems like a good candidate for a proof by contradiction. Assume you were able to invert $h(x_1 || x_2)$ (with non-negligible probability). Are you then able to leverage this ability to invert either $f(x_1)$ or $g(x_2)$ (with non-negligible probability)? $\endgroup$
    – Morrolan
    Commented Mar 21, 2022 at 8:16


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.