Is $f(f(x))$ a one way function?

Question

I found from a book the following proof.

Although I understand the initial construction, I don't understand the last sentence that proves the statement.

• Why $f(f(x))$, in the paper $h(h(x))$, is always equal to $0^{2n}$
• Is this what they are saying?
• Why is it clearly not a one way function?

---

Answer 1

Note: While writing this answer, I discovered what seems to be a gap in the proof given in the cited lecture notes. I'll thus present a slightly modified version of the proof below, and discuss the discrepancy a bit at the end.

Let's start with a quick recap, since your quote and summary of the lecture notes leaves out some important bits.

The formal definition of a one-way function, slightly expanded from Definition 5 in your lecture notes, is:

A function (family) $f: \{0,1\}^n \to \{0,1\}^m$ is one-way if and only if it can be computed by a polynomial-time algorithm, and if there is no probibilistic polynomial-time algorithm capable of finding preimages for it with non-negligible probability.

In other words, for $f$ to be one-way, there can be no probabilistic algorithm $A$ that could, given the output $y = f(x)$ for some randomly chosen input $x \in \{0,1\}^n$ and a maximum run-time polynomial in $n+m$, find an input $x'$ (possibly, but not necessarily, equal the original input $x$) such that $f(x') = y$ with a probability that is more than a negligible function of $n$.

An informal summary of this, dispensing with all the formalism of asymptotic complexity theory, would simply be that $f$ is one-way if there is no practical way, given a random output of $f$, to find an input that yields that output when given to $f$.

Based on this definition, we can show that:

• Padding the output of $f$ with, say, a bunch of zeroes doesn't affect whether it is one-way. (By definition, the adversary will always receive a valid output, so they can just strip away the zeros and then proceed as if they were attacking the original, unpadded function.)

• Also, adding a bunch of extra dummy bits to the inputs of $f$, which don't affect the output, doesn't change whether $f$ is one-way. (Since the dummy input bits don't affect the output, the adversary can choose those dummy bits any way it likes; but finding the correct values for the other, non-dummy input bits is still exactly as hard as finding a preimage for the original, unmodified function.)

(These technically hold only if the amount of padding / ignored bits added is a polynomial function of the original input + output length, but that's plenty enough for our purposes: $n \mapsto 2n$ is certainly a polynomial function.)

So, given an (arbitrary) one-way function $f$ with $n$-bit inputs and outputs, we can construct another one-way function $h$ with twice the input and output length like this:

1. Let $x^*$ be the first $n$ bits of the input $x$ to $h$. Ignore the rest of the input.

2. Compute $y^* = f(x^*)$.

3. Prepend an arbitrary constant $n$-bit string $c$ (e.g. $c = 000...0$) to $y^*$, and output the resulting $2n$-bit string $y = c \,\|\, y^*$ as $h(x)$.

Now, by construction, this function $h$ is one-way, since finding preimages for it is at least as hard as finding preimages for $f$. (Of course, the security parameters for $f$ and $h$ differ by a factor of 2, but that makes no difference asymptotically; a polynomial function of $2n$ is a polynomial function of $n$.)

But also by construction, the first $n$ bits of the output of $h$ are always constant, while the remaining output bits depend only on the first $n$ bits of the input. Thus, $h(h(x)) = c \,\|\, f(c)$ for all $x$, and so finding preimages for $h(h(x))$ is trivial (since literally any input will do).

---

Now, the construction given in the lecture notes you cite goes a little bit further, explicitly defining $h$ to yield an all-zero output whenever the first $n$ input bits are zero (and always setting the first $n$ bits of the output to zero otherwise).

While not strictly necessary (we'll get constant output from $h(h(x))$ anyway), this doesn't actually harm the one-wayness of $h$ either. In fact, we can show that modifying $h$ so that it always outputs a constant value for a negligibly small fraction of the total input space doesn't affect its one-wayness (and that $1/2^n$ is, indeed, a negligibly small fraction as $n$ tends to infinity).

However, where the lecture notes go wrong is when they try to justify this by claiming that:

"A generalization of the previous theorem (fixing values in a one-way function) shows that $h$ is also a one-way function. (In short, we are only fixing the values of $\frac{2^n}{2^{2n}} = \frac1{2^n}$ of all of the possible values of $x$. Since we are only fixing a negligible fraction of the possible values of $x$, the same proof with slight modifications still applies.)"

In fact, this claim is false. As a simply counterexample, consider the modified function $h'$ defined as:

1. Split the $2n$-bit input $x$ into two $n$-bit strings $x_1$ and $x_2$.

2. If $x_1 = c$, return $h'(x) = c \,\|\, x_2 = x$.

3. Otherwise, return $h'(x) = c \,\|\, f(x_1)$.

Clearly, $h'(x) = h(x)$ for all but a negligibly small fraction of the inputs (namely, those that begin with the $n$-bit constant string $c$). Yet $h'$ is obviously not a one-way function, since any valid output $y = h'(x)$ always begins with $c$, and so is its own preimage!

Of course, this doesn't invalidate the actual claim, since the function $h$ actually constructed in the notes is in fact one-way (provided that $f$ is one-way). Still, if these notes are from a course you're studying in, you might want to mention this gap in the proof to your instructor.