Proving that the length-preserving OWF does not have polynomially bounded cycle

Archies

2/8/24, 1:27 AM

Here a cycle is the smallest positive integer such that $f^i(x) = x$. Formally we want to prove that if $f$ is OWF then $\forall p(.)$ and sufficiently large $n$, $Exp(cyc_f(U_n))>p(n)$ where $n$ is length of input.

I understand that by applying Markov's inequality we get that, if $Exp(cyc_f(U_n))>p(n)$ then for every polynomial $q(.)$, we have $Pr(cyc_f(U_n)) > q(n).p(n)] < 1/q(n)$.

If I try a proof by contradiction, it means that if $f$ is OWF then there exists polynomial $q(.)$, and we have $Pr(cyc_f(U_n)) > q(n).p(n)] \geq 1/q(n)$. Any help is appreciated

1 + 0

one-way-function

Score:2

Crypto

Mark

2/8/24, 3:26 AM

First, note that you generally want a proof by contrapositive, not contradiction. To prove $A\implies B$ by contrapositive, we prove $\lnot B\implies \lnot A$. Here, $A$ is "$f$ is an OWF", and $B$ is "$f$'s expected cycle length is super-polynomial". Therefore, we want to prove that if $f$'s expected cycle length is bounded by some polynomial, then $f$ is not an OWF. You can prove something is not an OWF by constructing an inverter that works with non-negligible probability.

With those clarifications, I'll give you the following hint

If you know that an element $x$ has a cycle of length at most $p(x)$, i.e. $f^{i}(x) = x$ for some $i \leq p(n)$, how can you efficiently map from $f(x)\mapsto x$?

After answering this, you will need to argue that even knowing that on average (over $x$) the above holds suffices to build a good enough (to violate $f$ being a OWF) inverter.

+ 1

Archies

2/8/24, 8:22 AM

Thank you very much

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Proving that the length-preserving OWF does not have polynomially bounded cycle

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.