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.

  • 3
    $\begingroup$ Note that verbatim questions are considered off topic, please indicate what you've tried and what you don't get. $\endgroup$
    – Maarten Bodewes
    Commented Jun 1, 2021 at 23:29
  • 4
    $\begingroup$ 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}$. $\endgroup$ Commented Jun 2, 2021 at 6:26
  • $\begingroup$ @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}$. $\endgroup$
    – Maeher
    Commented Jun 2, 2021 at 7:38
  • 3
    $\begingroup$ @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... $\endgroup$ Commented Jun 2, 2021 at 9:05
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – fgrieu
    Commented Jun 2, 2021 at 15:30

1 Answer 1


I'm taking this as an exercise in understanding the meaning of mathematical statements/problems.

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).

Pick any smurf, and organize how the smurf throws one-sided coins.

  • 1
    $\begingroup$ I like the smurf comparison. But this is also valid for a lot of assumptions underneath this entire field. $\endgroup$ Commented Jun 3, 2021 at 5:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.