If a permutationFff is not one way, what can we say aboutFp(n)fp(n)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?
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.