In this How to show composition of one way function is not such? question, the accepted answer uses g(x,y) as a one way function. But, for a given output of g(x,y) = 0|x| of length l (say), isn't the output of g(any x of length l, 0l) the same as the earlier output? Isn't this a possible preimage of 0|x|?


1 Answer 1


"for a given output of g(x,y) = 0|x| of length l (say)," "the output of g(any x of length l, 0l)"
is "the same as the earlier output", which means that is "a possible preimage of 0|x|".
Accordingly, for ​ $g\hspace{-0.04 in}\circ \hspace{-0.03 in}f$ ​ to be one-way, it had better be the case that

$\operatorname{Prob}_{\langle \hspace{.02 in}x,y\rangle \hspace{.02 in}\leftarrow \hspace{.02 in}\left(\hspace{-0.03 in}\{\hspace{-0.02 in}0,1\hspace{-0.02 in}\}^{\hspace{.02 in}L}\hspace{-0.03 in}\right)^{\hspace{.05 in}2}}\hspace{-0.1 in}\left[g(x,\hspace{-0.04 in}y) = 0^{\hspace{.03 in}L}\hspace{-0.0 in}\right] \;\;\;$ is negligible.

  • $\begingroup$ For the ten billionth time, all the spaces you insert into your LaTeX markup make your answer illegible on other people's screens. Are you using some kind of graphical equation editor to produce that code? $\endgroup$ Commented Feb 7, 2017 at 11:45
  • $\begingroup$ Could the equation be edited please? It's tough to understand that bit. Thank You $\endgroup$
    – rasalghul
    Commented Feb 8, 2017 at 18:16

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.