I've been looking at the paper of Boneh, Boyen, Goh Hierarchical Identity Based Encryption with Constant Size Ciphertext which contains a general theorem (Theorem A.2) about the advantage of an attacker in the generic group model. It seems to be based on the idea that in the generic bilinear group model, we can only compute things that are linear combinations of the given inputs as well as multiply linear polynomials once when computing a pairing. What they argue is that if the randomly sampled inputs are $x_1,\ldots,x_n$ and we have computed two (at most quadratic) polynomials $L_i(x_1,\ldots,x_n)$ and $L_j(x_1,\ldots,x_n)$, then the equality check for
can be replaced by an equality check
i.e. we check for equality as polynomials, not as evaluated polynomials.
The general idea of the proof is then that we may afterwards check what the probability is that the adversary could have seen a difference between these two cases. This seems to be based on the idea that for random polynomials, we have an upper bound for the probability that a randomly sampled point is a root.
My issue with this proof is that since the polynomials that show up in the computation depend on information the adversary has gained from previous oracle queries, the list of polynomials $L_1,\ldots,L_q$ has been adaptively constructed. Therefore, the list is not independent of the sampled values $x_1,\ldots,x_n$. I don't see how this is taken into account in the proof? Anyone care to explain this in more detail, since all later papers with similar theorems seem to sidestep this issue too.