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|?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
"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$ Commented Feb 8, 2017 at 18:16