6
$\begingroup$

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?

| improve this question | |
$\endgroup$
  • 1
    $\begingroup$ Let's considet the identity function as f. $\endgroup$ – xagawa Nov 28 '19 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 '19 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 '19 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 '19 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 '19 at 15:06
9
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Straight from The Book :) $\endgroup$ – Krystian Nov 29 '19 at 13:57
  • $\begingroup$ How would a permutation not be length preserving? $\endgroup$ – Maeher Dec 2 '19 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 '19 at 8:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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