3
$\begingroup$

Is there any notion of a periodic OWF?
I.e. an OWF $f$ that on every input $x$ in its domain it holds that $f(f(f\ldots f(x))\ldots )=x$ when $f$ applied many times, each time on the previous output.

Also, if we take some One Way Permutation, it must be periodic of course. So is it guaranteed that its period is longer than any polynomial (in the security parameter)? (that is, if its period is of some polynomial length - is its security broken?)

$\endgroup$
7
$\begingroup$

Security is clearly broken if there is a polynomial-length period with non-negligible probability (where by this I mean if a random point falls in a cycle with a poly-length period with non-negligible probability). In order to find a preimage, just go forward until you get back to the starting point, keeping the previous value each time.

$\endgroup$

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.