I'm currently looking at a compsci text containing the following definition:

Let $f : \{0,1\}^k \rightarrow \{0,1\}^k$ and $b : \{0,1\}^k \rightarrow \{0,1\}$ be computable in poly($k$) time. We say that $f$ is a one-way function with hard-core bit $b$ if, for all polynomial-time randomized algorithms $A$ and all constants $c$, $$ \underset{x\in\{0,1\}^k}{\mathbb{E}} \text{Pr}[A(f(x))=b(x)] = \frac{1}{2}+o(k^{-c}) $$

I find the left-hand side quite disorienting. If I were to unwrap the notation I'd arrive at something like this:

$$ \sum_{x\in\{0,1\}^k}\text{Pr}\big[\{x\in\{0,1\}^k\big|A(f(x))=b(x)\}\big]\cdot2^{-k} $$

The $x$ is bound twice?


The randomness in the $\Pr$ is over the behavior of $A$, while the randomness in the expectation is over the choice of $x$.

  • $\begingroup$ Right, that makes sense now that I think about it. $\endgroup$ – Sebastian Oberhoff Mar 13 '18 at 18:26

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.