1
$\begingroup$

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?

enter image description here

$\endgroup$
  • $\begingroup$ Does the answer to this question clarify things for you? $\endgroup$ – Ilmari Karonen Feb 20 '16 at 17:57
  • $\begingroup$ 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 :( $\endgroup$ – graphtheory92 Feb 20 '16 at 18:04
3
$\begingroup$

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.

$\endgroup$

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.