0
$\begingroup$

I'm stuck in a simple question about weak one way functions.

Suppose $f(x)$ is strong one way, is $g(x)=f(x)_0$, i.e. taking the first bit of $f(x)$ a weak one way function? Intuitively, it is, because for any adversary $\mathcal{A}$ the probability of inverting $g$ is $\frac{1}{2} + \epsilon$. So it seems safe to say $g$ is $\frac{2}{3}$-one way.

But apparently one cannot reduce inverting $g$ to inverting $f$, which leaves me no way to prove that statement by reduction. Am I getting it wrong?

|improve this question
$\endgroup$
  • $\begingroup$ What is $\epsilon$? and why does the probability of inverting $g$ equal $1/2 + \epsilon$? $\endgroup$ – fkraiem Mar 3 '17 at 7:17
  • 2
    $\begingroup$ By the way, it is clear that $g$ is not necessarily weak one-way, since it can be constant. $\endgroup$ – fkraiem Mar 3 '17 at 7:31
1
$\begingroup$

No, $g$ is certainly not even weakly one-way. In particular, in order to invert $g$ you just need to be able to sample a $y$ such that the first bit of $f(y)$ equals the first bit of $f(x)$. Now, since one-way functions work on random input, it is clearly not hard to sample an input with the same first input bit as $f(x)$, since $x$ was randomly chosen.

|improve this answer
$\endgroup$
  • $\begingroup$ $g$ is certainly not one-way. But I'm asking about weak one way functions. $\endgroup$ – qweruiop Mar 3 '17 at 19:32
  • $\begingroup$ I mean that it is certainly not even weakly one-way. You can easily find with probability almost 1. Simply sample a random $y$ a polynomial number of times and hope that you get one that matches the needed bit. $\endgroup$ – Yehuda Lindell Mar 4 '17 at 19:28

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.