1
$\begingroup$

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|?

$\endgroup$
1
$\begingroup$

"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.

$\endgroup$
  • $\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$ – David Richerby Feb 7 '17 at 11:45
  • $\begingroup$ Could the equation be edited please? It's tough to understand that bit. Thank You $\endgroup$ – rasalghul Feb 8 '17 at 18:16

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.