Generic group model: use of polynomials in the proof of the master theorem

Question

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

$$L_i(x_1,\ldots,x_n)=L_j(x_1,\ldots,x_n)$$

can be replaced by an equality check

$$L_i(X_1,\ldots,X_n)=L_j(X_1,\ldots,X_n),$$

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.

Answer 1

The problem can be simplified to the following problem, since the standard argument doesn't really take into account that you can't generate all the polynomials of the given maximum degree :

Assume that we have sampled a random point $\vec{x}\in \mathbb{F}_p^n$. We let an adversary adaptively choose polynomials of degree at most $d$ and after each choice we tell whether $\vec{x}$ is a root of the chosen polynomial. Then after $q$ queries, the probability that the attacker has found a polynomial for which $\vec{x}$ is a root is bounded above by

$$\frac{qd}{p}.$$

What we know is that the probability that a random element in $\mathbb{F}_p^n$ is a root of some polynomial of degree $d$ is bounded above by $d/p$. Therefore, the attacker is essentially choosing subsets of size at most $d/p\cdot p^n$, since we only care about roots, not the actual polynomials. Thus, the problem is equivalent to the following:

Assume that we have chosen a random point $x$ in a set $S$ of size $p$. We let an an attacker adaptively choose $d$ points at each round and then tell the attacker whether or not $x$ is among the $d$ points. Then the probability that after $q$ queries we have chosen a set of points containing $x$ is bounded above by $qd/p$.

We prove by induction that the upper bound is given by $qd/p$. This clearly holds for one query, since on the first attempt we're just picking a set of size $d$ and the probability of $x$ being in this set is $d/p$. Now assume by induction that the winning probability on $q$ queries is $qd/p$. Now with $q+1$ queries, we either win during the first $q$ queries or we don't and win on the $q+1$st. It follows that we get

$$\frac{qd}{p}+\frac{d}{p-dq}\left(1-\frac{qd}{p}\right)=\frac{(q+1)d}{p}$$

It's correct, however, that none of the existing proofs in the literature discuss the point that the adversary chooses polynomials adaptively. All the proofs just say that at the end we have $(s+q)^2$ possible polynomials and the chance of a random element being a root of one is $(s+q)^2d/p$, which is not really a valid argument in this case, although you get the same bound.