I have seen that the existence of weak OWFs implies the existence of strong OWFs. It comes from repeating the weak OWF polynomially many times on different random inputs.

However, I have a different question here : given a weak one-way permutation $f$, does the function $(f\circ f \circ f \circ \dots \circ f)$, where the composition happens polynomially many times, have to be a strong one way function? The first result seems to say this is untrue, because something like this would have worked in the previous case as well, but I'm unable to come up with a counterexample.

  • $\begingroup$ I do know that this is not true if the composition happens only finitely many times. How do I use the "polynomially many times" to my advantage, or can I use it? $\endgroup$ – астон вілла олоф мэллбэрг Sep 15 '17 at 4:28
  • $\begingroup$ Could you provide an example of the weak one way permutation you're working with? $\endgroup$ – Q-Club Sep 15 '17 at 5:51
  • $\begingroup$ @back_seat_driver I don't know of any concrete examples/candidates for a weak one way permutation. For the moment, I think I know that there exists a weak one way permutation that is NOT a strong one way permutation. From this , if I can get a statement of the following kind : If $f \circ f \circ ... \circ f$ is a strong OWF, then $f$ is a strong OWF as well, then I am done, right? $\endgroup$ – астон вілла олоф мэллбэрг Sep 15 '17 at 6:11
  • 1
    $\begingroup$ "If f∘f∘...∘f is a strong OWF, then f is a strong OWF as well." I don't think this is true generally. One way functions can be built with only reversible functions! Provided that you truncate/delete some of the information from the final output. It's hard to guess information you don't have despite the fact that it was produced. $\endgroup$ – Q-Club Sep 15 '17 at 6:50
  • $\begingroup$ @back_seat_driver All right. So then the question is, what am I expected to do? I am quite sure that if $f$ is a weak one way permutation that is not strong, then the resulting $g$ will only be weak and not strong. How would I show this? $\endgroup$ – астон вілла олоф мэллбэрг Sep 15 '17 at 8:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.