[Oct'06. Based on discussion with Johan Hastad and Hugo Krawczyk] Unfortunately, the current presentation of Sec 2.5.3 does not facilitate deriving good security bounds. Actually, the blame is not in modularity, but rather in careless modularity. Below are two alternative derivation of better security bounds (yielding essentially the same result). 1st ALTERNATIVE (SIMPLER BUT SLIGHTLY LESS CONVINCING) The key observation is that the argument of Prop 2.5.7 can be applied directly to the case of a random XOR/set (rather than to a fixed set as done in the text). In this case, the prediction advantage of the GL-bit will be the expected prediction advantage for a random XOR. Things "take care" of themselves, and there is no need to find a good set. That is, if we select a random set then sometimes we have a good advtantage and sometimes not, but on average we have a good advantage. 2nd ALTERNATIVE (MORE CONVINCING) [Let us chnage notations from $\ell$ to $m$, and from $I$ to $S$.] Loosely speaking, Lemma 2.5.8 says that if you can distinguish the output (of the hard-core fumnction) from uniform in time $t$ and gap $\delta$ then you can predict the XOR of a random subset of the bits in time $t+O(n)$ w.p. $0.5+\e$, where $\e=\delta/(2^m-1)$. [We call $\e$ the advantage (in predicting).] The point is that a careless analysis asserts that there exists a set with such an advantage, but then invoking Prop 2.5.7 introduces another overhead factor of $2^m$ (in searching for that set). However, it cannot be that there is a single set with such an advantage; it is rather the case that there is a tradeoff between the number of sets and the advantage that these sets have... Indeed, a (standrad) non-careless analysis will proceed as follows. For a set $S$, denote by $\e_S$ the advatage (over 0.5) that we have in predicting XOR for the set $S$. We know that $E_S[\e_S] = \e$. Let $I_j=(2^{j-1}\e, 2^j\e]$ and $\ell=\log_2(1/\e)$. Then there exists $j\in\{0,1,...,\ell\}$ such that $\prob_S[\e_S \in I_j] \geq 2^{-j-1}/(\ell+1)$. Furthermore, such a set $S$ (with $\e_S \in I_j$) can be found and verified as such in time $(2^{-j-1}/(\ell+1))^{-1} (2^j\e)^{-2} = O(\ell)\e^{-2}/2^j$. [Proof: Otherwise, $E_S[\e_S]$ is upperbounded by $$\prob_S[\e_S \leq\e/2]\cdot(\e/2) + \sum_j \prob_S[\e_S \in I_j]\cdot 2^j\e < (\e/2) + \sum_j (2^{-j-1}/(\ell+1))\cdot 2^j\e = (\e/2) + (\ell+1) (\e/2(\ell+1)) = \e$$] Now, a more careful formulation of Prop 2.5.7 says that if you can find in tome $t$ a set $S$ such that you can predict the XOR wrt $S$ in time $t'$ and advatage $\e'$ then you can predict the GL-bit in time $t+t'$ with advantage $\e'$. Furthermore, you can find in time $t$ an advice (string) that allows to predict the GL-bit in time $t'$ with advantage $\e'$. Recall the latter implies inverting in work related to $(t+t')/(\e')^2$. Using the furthermore-claus, gives $t+(t'/(\e')^2)$, becuase you have to find $S$ only once... Recalling that $\e'=2^j\e$ and $t=\tildeO(\e^{-2})/2^j$, we get $t+(t'/(\e')^2) \approx (\e^{-2}/2^j)+(t'\e^{-2}/2^{2j}$, which is indeed maximized at $j=0$.