# Weak one way functions from strong one way functions

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?

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

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.
• $g$ is certainly not one-way. But I'm asking about weak one way functions. – qweruiop Mar 3 '17 at 19:32
• 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. – Yehuda Lindell Mar 4 '17 at 19:28