If $f$ is a one-way permutation, is $f \circ f$ also a one way permutation?

Question

A one-way permutation is a bijective one-way function. If $f$ is a one-way permutation, does this imply that $f \circ f$ also a one-way permutation?

What about $f \circ g$, where both $f$ and $g$ are one-way permutations?

Answer 1

The first question is a special case of the second, so let's deal with the second. Clearly, $f\circ g$ is still bijective (as composition of two bijective functions), so the question is whether it is also one-way.

Assume by contradiction it is not. This means that, given an element $y$, there exists an efficient algorithm to find the preimage $x$ of $y$ with regard to $f\circ g$: $$ f\circ g(x) = y\,. $$ But by definition of a one-way function, evaluating $g$ can be done efficiently. Therefore, combining the two, one gets an efficient algorithm which, given $y$, finds the preimage $x'$ of $y$ with regard to $f$: namely, $x' = g((f\circ g)^{-1}(y))$. This contradicts the fact that $f$ is one-way.

Therefore, $f\circ g$ is also a one-way permutation.

Note that by inspection of the proof, all that is needed is the weaker requirement that (i) $f$ is a one-way permutation, and (ii) $g$ is a permutation that can be evaluated efficiently (not necessarily one-way).

Answer 2

If $f$ and $g$ and $(f \circ g)^{-1} = g^{-1} \circ f^{-1}$ are easy to compute, then so are $f^{-1} = g \circ (f \circ g)^{-1}$ and $g^{-1} = (f \circ g)^{-1} \circ f$.