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

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? • Does the answer to this question clarify things for you? – Ilmari Karonen Feb 20 '16 at 17:57
• even his last sentence "However, f(f(x))=0n/2∥h(0n/2)f(f(x))=0n/2∥h(0n/2) is constant, independently of xx (except for its length nn), and thus finding pre-images is trivial." is what I don't get :( – graphtheory92 Feb 20 '16 at 18:04

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.