# If a permutation $f$ is not one way, what can we say about $f^{p(n)}$?

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?

• Let's considet the identity function as f. – xagawa Nov 28 '19 at 9:13
• 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. – Ryan Nov 28 '19 at 12:01
• 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. – SEJPM Nov 28 '19 at 13:34
• 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$. – Ryan Nov 28 '19 at 14:11
• 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. – SEJPM Nov 28 '19 at 15:06

## 1 Answer

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$$,

\begin{align}f(x\mathbin\|0)&=x\mathbin\|1\\f(x\mathbin\|1)&=g(x)\mathbin\|0\end{align}

$$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

\begin{align}f^2(x\mathbin\|0)&=g(x)\mathbin\|0\\f^2(x\mathbin\|1)&=g(x)\mathbin\|1\end{align}

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.

• Straight from The Book :) – Krystian Nov 29 '19 at 13:57
• How would a permutation not be length preserving? – Maeher Dec 2 '19 at 8:18
• @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? – fgrieu Dec 2 '19 at 8:41