سؤال

I've seen competing requirements in the definitions for one-way functions. Namely

$$ \underset{x,r}{\mathbb{P}}\big(f(B(f(x),r)) = f(x)\big) = o(n^{-c}) $$ and $$ \underset{x}{\mathbb{E}}\left[\underset{r}{\mathbb{P}}\big(f(B(f(x),r)) = f(x)\big)\right] = o(n^{-c}) $$

where $x\in\{0,1\}^n$ and $r = \text{poly}(n)$. $B$ is thought of as a randomized algorithm and $r$ are the random bits it's using.
Now I know that for the construction of pseudo-random generators from one-way permutations either of these definitions will do, but is the same true for the construction from general one-way functions? Are there cases that I should be aware of where these definitions aren't interchangeable?

Edit: Okay, here's my own explanation for why these expressions are equal. If we replace the entire mess $f(B(f(x),r)) = f(x)$ with the indicator random variable $p(x,r)$ then we can write: $$ \begin{split} \underset{x}{\mathbb{E}}\left[\underset{r}{\mathbb{P}}\big(p(x,r)=1\big)\right] & = \underset{x}{\mathbb{E}}\left[\underset{r}{\mathbb{E}}\left[p(x,r)\right]\right]\\ & = \underset{x,r}{\mathbb{E}}\left[p(x,r)\right]\\ & = \underset{x,r}{\mathbb{P}}\big(p(x,r) = 1\big)\,. \end{split} $$

لا يوجد حل صحيح

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى cs.stackexchange
scroll top