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
    Jun 1 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$ Jun 2 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
    Jun 2 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$ Jun 2 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
    Jun 2 at 15:30

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$ Jun 3 at 5:38

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.