# How do these alternative definitions of one-way functions compare?

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

• The expressions are equal. Unfold the definitions to see why (how are probability of an event/expectation of a discrete random variable defined?). – 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.)

• You're right. I think I fixed that error now. – Sebastian Oberhoff Mar 19 '18 at 4:52
• 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? – Sebastian Oberhoff Mar 19 '18 at 20:21
• @SebastianOberhoff, that's right! Keep reading; the part after the "Also, ..." explains what is going on in your specific example. – D.W. Mar 19 '18 at 22:59
• I think I see it clearly now. I've added my own answer. – Sebastian Oberhoff Mar 19 '18 at 23:20
• Note that $\mathbb{P}_{X,Y}[E_{X,Y}] = \mathbb{E}_X[\mathbb{P}_Y[E_{X,Y}]]$ requires independence. – Ariel Mar 19 '18 at 23:40