# One way function existence

Let $$x = (x_1, x_2,...,x_n)\in\{0,1\}^n$$ for $$n\in\mathbb{N}$$. Prove that if one-way functions (OWFs) exist, then there exists a one-way function $$f$$ such that for every bit $$i\in[1,n]$$ there exists an algorithm $$A_i$$ such that:

$$\Pr[A_i(f(x)) = x_i] \geq \frac{1}{2} + \frac{1}{2n}$$

I'm having trouble understanding this.

• Note that verbatim questions are considered off topic, please indicate what you've tried and what you don't get. Jun 1 at 23:29
• Are you sure this is the question? This is almost word for word an exercise I give for homework, except that the probability has to be greater than $\frac12 + \frac{1}{2n}$. Jun 2 at 6:26
• @YehudaLindell if I'm reading the edit history correctly, the question was originally posed with $\frac{1}{2n}$ but edited by Mark to read $\frac{1}{2^n}$. Jun 2 at 7:38
• @Maeher Then the edit by Mark is incorrect. The question should be $\frac{1}{2n}$ and that's what makes the question interesting. However, we should ask if it is homework... Jun 2 at 9:05
• Someone with the same assignment, word for word, same initial typos (and then two more) just confirmed it has $\frac{1}{2} + \frac{1}{2n}$, not $\frac{1}{2} + \frac{1}{2^n}$.
– fgrieu
Jun 2 at 15:30

It's asked to exhibit a smurf (OWF, whatever that is) that wins coin throws (experiments which outcome is determined by the $$=$$ ) with probability at least some bound ($$\Pr[\ldots] \geq \ldots$$ ). It's assumed smurfs exist, known targets for the coin throws (the $$x_i$$ ), and we have leeway to organize the coin throws (by deciding the algorithms).