In Efficient and Secure Pseudo-Random Number Generation by Vazirani & Vazirani, it is stated that every pseudorandom number generator which satisfies the XOR Condition can securely output $\log n$ bits (where $\ n = |N|$). Such a condition is satisfied by the Blum-Blum-Shub (whose trapdoor is based on the quadratic residuosity assumption), thus up to $\log \log N $ bits at each step can be extracted.

My question is of information theoretic interest: what exactly do they mean when they state that the boolean predicates (the output bits) $b_1,\ldots,b_k$ are inversion secure if there exists a Las Vegas algorithm T that runs in probabilistic polytime, i.e $T^{O_{b_{i},N}}[i, E_{N}(x)] = x$ (with $E_{N}(x)$ the one-way function), where $O_{b_{i},N}$ is a $\frac{1}{2} + \frac{1}{poly(n)}$ advantage oracle for $b_i$ with respect to N? Why the probability beyond 1/2 plus that $\varepsilon$-advantage, which, I assume, bounds the overall probability? So, if the XOR of each non-empty subset of these predicates is inversion secure, boolean predicates satisfy the XOR Condition.

I think it's pretty close with what Rabin function says:

If for a $\frac{1}{logN}$ fraction of the quadratic residues $q\pmod N$ one could find a square root of $q$, then one could factor $N$ in random polynomial time.

Still, where does $1/(\log N)$ come from?

  • $\begingroup$ Have you seen the interesting conversation in How many bits can be safely extracted from the BBS generator at each step?. And it's links? It is suggested therein that it's << log log N as 'security' is somewhat ill defined. $\endgroup$
    – Paul Uszak
    Commented May 15, 2019 at 11:54
  • $\begingroup$ @PaulUszak I saw it, yet I'm not questioning the number of bits that can be extracted from BBS, but why there must exist an oracle defined as such to be probed to make predicates inversion secure. $\endgroup$ Commented May 15, 2019 at 14:12

1 Answer 1


Took a while to grasp it, but with the help of a friend we came to a conclusion (and it turns out it was rather easy).

Recall that a function $f_n : \{0,1\}^{n} \mapsto \{0,1\}^{m(n)}$ is said to be one-way if for a positive polynomial $poly(\cdot)$, every randomized algorithm running in probabilistic polynomial time inverts $f_n$ with a negligible probability, i.e. $\Pr[A\:inverting\: f_n] < \frac{1}{poly(n)}$, with $n$ size of the input. This polynomial comes from the fact that for every possible computational path, the algorithm will follow it with a probability $2^{-n}$, which is bounded by $\mathcal O(\frac{1}{n^c})$ for every constant $c$. Clearly, we want the adversary's advantage to be as asymptotically small as possible.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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