Let $f$ be a length preserving one way function. Show that $g(x)=f(x)|x_{[1:\log n]}$, where $|$ indicates concatenation and $x_{[1:\log n]}$ indicates the first $\log n$ bits of x, is also a one way function.

Can someone please give a starting hint for this problem?

I know I have to use a reduction to show that if $g$ can be inverted easily, then so can be $f$. In other words, when I am only given $f(x)$, I have to construct $g(x')$ for some $x'$, use the assumed inverter, get $x'$ and construct $x$ from $x'$. But due to the definition of $g$, I can't think of anything to start my approach.

  • $\begingroup$ Consider this: What's the probability that $\log n$ random bits will happen to be the correct prefix of a random $x$? $\endgroup$ – Maeher Feb 24 '18 at 1:27
  • $\begingroup$ Among all the length $\log n$ sequences of bits, only one can exactly match the prefix in $x$, so it is $\frac{1}{2^{\log n}}=\frac{1}{n}$, right? $\endgroup$ – crimson.lotus Feb 24 '18 at 7:29
  • $\begingroup$ Handwaving explanation: in trying to find $x$ from $g(x)$, the extra information given by $x_{[1:\log n]}$ is negligible compared to what's to be found. Hint for the formal proof: what's currently after "in other words" does not hold water. Rather, assume you have a polynomial time algorithm that finds $x$ from $g(x)$ with some probability, and devise one that finds $x$ from $f(x)$ with some probability (there's a difficulty there), and is in polynomial time too; that will be your proof. Further hint: repeatedly apply the algorithm inverting $g(x)$. $\endgroup$ – fgrieu Feb 24 '18 at 8:48

Your Answer

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

Browse other questions tagged or ask your own question.