Consider a permutation $f:\{0,1\}^*\rightarrow \{0,1\}^*$, which is not a one-way function, i.e. there exists an efficient probabilistic adversary $\mathcal{A}$ and some polynomial $q(n)$ such that for infinitely many $n$

\begin{equation} \mathrm{Pr}[\mathcal{A}(f(x)) = x] > \frac{1}{q(n)}, \end{equation} where the probability is over the internal randomness of $\mathcal{A}$ and $x$ drawn uniformly at random from $\{0,1\}^n$.

I would now like to prove that $f^{p(n)}$ is not a one way function, for any polynomial $p(n)$. Is this true for all permutations $f$ which are not one way?

My intuition was that this would be true, and that one could prove this by showing that $\tilde{\mathcal{A}} = \mathcal{A}^{p(n)}$ is a suitable adversary for $f^{p(n)}$. However, I can't get this to work. Is there a clever way to prove this, or is the statement I am trying to prove actually false?

  • 1
    $\begingroup$ Let's considet the identity function as f. $\endgroup$
    – xagawa
    Nov 28, 2019 at 9:13
  • $\begingroup$ I would like to understand whether for all permutations $f$ which are not one way, $f^{p(n)}$ is also not one way. The identity function is an example of a specific permutation $f$ which is not one way, and for which $f^{p(n)}$ is also not one way for all $p(n)$. As such, it doesn't provide a counter example to the conjecture, it just provides one example of a specific function which has this property - I would really like to understand if this holds for all permutations which are not one way. I have edited the question slightly to make this clear. $\endgroup$
    – Ryan
    Nov 28, 2019 at 12:01
  • $\begingroup$ I think this statement might be false because an adversary only needs to be successful for infinitely many $n$ and not all of them, so a non OWP f could be constructed as "return the first n-1 bits" if $n$ is even and "run this actual OWP $\pi$" if $n$ is odd, then this would be a non-OWF because for every second length there is an inverter but inverting twice is hard. $\endgroup$
    – SEJPM
    Nov 28, 2019 at 13:34
  • 1
    $\begingroup$ I don't think this construction works as a counter-example, because for $n$ even we have that $f:\{0,1\}^n \rightarrow \{0,1\}^{n-1}$, and therefore $f$ is not a permutation for even $n$. $\endgroup$
    – Ryan
    Nov 28, 2019 at 14:11
  • $\begingroup$ You are right, I was not precise enough on the permutation part, at least the above is still an instructive counter-example for the more general non-OWF case even if it doesn't work for non-OWPs. Maybe there is still a way to change the length of the output if we design a clever permutation say for every two or three consecutive bitlengths. $\endgroup$
    – SEJPM
    Nov 28, 2019 at 15:06

1 Answer 1


If a permutation $f$ is not one way, we can not conclude about the one-wayness of $f^{p(n)}$. In fact, even $f^2$ could be one-way, if there are one-way length-preserving permutations that is.

Constructive proof: assume $g:\{0,1\}^*\rightarrow \{0,1\}^*$ is a length-preserving OWP, not invertible starting with rank $m$. Define $f$ from $g$ such that, for any bitstring $x$,


$f$ is a permutation. It is trivially invertible for half its inputs of any fixed width, thus is not a OWP.

$f^2$ is also a permutation, with


An hypothetical algorithm that inverts $f^2$ starting at width $n>m$ could be used to invert $g$ at width $n-1\ge m$. With $g$ being a OWF, there is no such algorithm. Hence $f^2$ is one-way.

  • $\begingroup$ Straight from The Book :) $\endgroup$
    – Kris
    Nov 29, 2019 at 13:57
  • $\begingroup$ How would a permutation not be length preserving? $\endgroup$
    – Maeher
    Dec 2, 2019 at 8:18
  • $\begingroup$ @Maeher: how about the transformation $h:\{0,1\}^*\rightarrow \{0,1\}^*$ which leaves all bitstrings unchanged, except the all-zero bitstrings (including empty), with that of length $2k$ and $2k+1$ exchanged? $\endgroup$
    – fgrieu
    Dec 2, 2019 at 8:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.