Intuitively I think not because assuming the bit string $x_1,x_2 \sim \{0,1\}^{n/2}$, $x_1 \wedge x_2$ is not uniformly random so if $g$ were still a one-way function then the fact that the definition of one way function requires the input string $x$ to be uniformly random seems unneeded.

But I'm not sure how to construct the $f$ required. I tried the usual $f(x) = 0^{n/2}||f(x_{[1:n/2]})$ but got stuck.

  • $\begingroup$ Welcome to crypto-SE. I suggest you edit the question, adding the definition of One Way Function assumed in the context. This may help you, and will show the level of formalism expected. $\endgroup$
    – fgrieu
    Feb 10, 2023 at 8:03
  • 1
    $\begingroup$ HINT: Suppose that you could invert $g$ with non-negligible probability, could you use this ability to create pseudo-inversions of $f$? $\endgroup$
    – Daniel S
    Feb 10, 2023 at 8:15


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.