4
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\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 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 at 8:15

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.