1
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 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$
    – Yehuda Lindell
    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$
    – Yehuda Lindell
    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

Reset to default
2
$\begingroup$

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.

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

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