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} $$

  • $\begingroup$ The expressions are equal. Unfold the definitions to see why (how are probability of an event/expectation of a discrete random variable defined?). $\endgroup$ – Ariel Mar 19 '18 at 13:01

The expressions are equivalent. To see why, unfold the expectation and use the fact that $x,r$ are independent.

$$ \mathop{\mathbb{E}}\limits_{x}\left[\Pr\limits_{r}\big(f(B(f(x),r))=f(x)\big)\right]= \sum\limits_{x}\Pr(x)\Pr\limits_{r}\big(f(B(f(x),r))=f(x)\big)= \sum\limits_{x}\Pr(x)\sum\limits_{r}\Pr(r)\mathbb{1}_{f(B(f(x),r))=f(x)}= \sum\limits_{x,r}\Pr(x,r)\mathbb{1}_{f(B(f(x),r))=f(x)}= \Pr\limits_{x,r}\big(f(B(f(x),r))=f(x)\big). $$

Note that both the second and the last equalities follow from the definition of the probability of an event over a discrete sample space (sum of the probabilities of elements in the event, or summing over the entire space while multiplying by the associated indicator function).


They're equivalent. In general, if $X$ is a 0-or-1 random variable, then $\mathbb{E}[X] = \mathbb{P}[X=1]$ holds. Also, if $E_{X,Y}$ is an event that depends on two independent random variables $X,Y$, then $\mathbb{P}_{X,Y}[E_{X,Y}] = \mathbb{E}_X[\mathbb{P}_Y[E_{X,Y}]]$. To see way, just expand the definitions, as Ariel suggests.

(Comment on the original version of the question, before it was edited: The former expression makes no sense. It doesn't type-check. When you write $\mathbb{P}[\cdots]$, the $\cdots$ has to be an event. $\mathbb{P}\big(f(B(f(x))) = f(x)\big)$ is not an event; it is a random variable. Check your sources -- I suspect you must have copied something down wrong.)

  • $\begingroup$ You're right. I think I fixed that error now. $\endgroup$ – Sebastian Oberhoff Mar 19 '18 at 4:52
  • $\begingroup$ But $\underset{r}{\mathbb{P}}\big(f(B(f(x),r)) = f(x)\big)$ isn't a 0-or-1 random variable. It can take on any value in the interval [0,1]. Also, I was able to convince myself that the two expressions are identical. But it didn't seem trivial to me and I definitely had to use the fact that $x$ and $r$ are uniformly random. How is this equality obvious? $\endgroup$ – Sebastian Oberhoff Mar 19 '18 at 20:21
  • $\begingroup$ @SebastianOberhoff, that's right! Keep reading; the part after the "Also, ..." explains what is going on in your specific example. $\endgroup$ – D.W. Mar 19 '18 at 22:59
  • $\begingroup$ I think I see it clearly now. I've added my own answer. $\endgroup$ – Sebastian Oberhoff Mar 19 '18 at 23:20
  • $\begingroup$ Note that $\mathbb{P}_{X,Y}[E_{X,Y}] = \mathbb{E}_X[\mathbb{P}_Y[E_{X,Y}]]$ requires independence. $\endgroup$ – Ariel Mar 19 '18 at 23:40

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.