a possibly stronger type of attack on identity-based encryption What is known about the security of identity-based encryption schemes against attacks that involve seeing multiple ciphertexts and then receiving the private keys corresponding to some of those ciphertexts?

For example, is it known that feasible adversaries will have a negligible (in the security parameter $k$) probability of succeeding in the following, for IND-CCA2 IBE schemes?


Challenger generates $\:\langle$pub,msk$\rangle\:$ and then gives $\:$pub$\:$ to $\mathcal{A}$  
$\mathcal{A}$ outputs a list of $\:(2\hspace{-0.03 in}\cdot\hspace{-0.03 in}k)\hspace{-0.01 in}+\hspace{-0.02 in}1\:$ distinct IDs  
Challenger chooses $\:x\in \{0,\hspace{-0.04 in}1\}^k\:$ uniformly  
Challenger computes $\:(2\hspace{-0.03 in}\cdot\hspace{-0.03 in}k)\hspace{-0.01 in}+\hspace{-0.02 in}1\:$ Shamir shares of $x$ so that one needs $\:k\hspace{-0.03 in}+\hspace{-0.04 in}1\:$ of them to recover $x$  
Challenger encrypts those shares using $\:$pub$\:$ and the corresponding IDs from the list provided by $\mathcal{A}$  
Challenger gives the resulting list of ciphertexts to $\mathcal{A}$
$\mathcal{A}$ outputs a list of $k$ IDs  
Challenger uses $\:\langle$pub,msk$\rangle\:$ to extract the private decryption keys for those IDs  
Challenger gives the corresponding list of private decryption keys to $\mathcal{A}$ 
$\mathcal{A}$ outputs $y$
$\mathcal{A}$ succeeds if and only if $y = x$
You can probably prove the security against your game from the security in the IND-ID-CCA game of Boneh and Franklin (see http://courses.cs.vt.edu/cs6204/Privacy-Security/Papers/Crypto/IBE-Weil-Pairing.pdf). The idea is to create an adversary $\mathcal{B}$ against IND-ID-CCA from your adversary $\mathcal{A}$. Essentially $\mathcal{B}$ will play man-in-the-middle between the IND-ID-CCA challenger and $\mathcal{A}$.

When $\mathcal{B}$ receives the $2k+1$ identities from $\mathcal{A}$, he chooses one of those at random (let's call it $ID_0$) sends two random values $(x_0,x_0')$ together with $ID_0$ to the challenger and receives an encryption $C_0$ of either $x_0$ or $x'_0$. For each of the other identities $ID_i$, $\mathcal{B}$ encrypts values $x_i$ chosen in such a way that $(x_0,\cdots, x_{2k+1})$ are valid shares for the secret sharing, the ciphertexts are denoted by $C_i$. Then $\mathcal{B}$ returns the ciphertexts to $\mathcal{A}$. [Note that if the challenger has chosen $x_0$ your game is perfectly emulated, otherwise, the shares are invalid]

When $\mathcal{A}$ sends the $k$ identities, if $ID_0$ is in the set $\mathcal{B}$ aborts the communication with $\mathcal{A}$ and returns a random guess to the challenger. Otherwise, $\mathcal{B}$ asks the $k$ keys to the challenger and sends those to $\mathcal{A}$. When $\mathcal{A}$ returns $y$, $\mathcal{B}$ proceeds as follow:
If $y$ is consistent with the share $x_0$, then $\mathcal{B}$ guesses that the challenger returned an encryption of $x_0$, otherwise $\mathcal{B}$ guesses at random.

If $\mathcal{A}$ wins your game with probability $\epsilon$, the advantage of $\mathcal{B}$ is approximately $\epsilon/4$. 



Additional information:


The advantage is not $\epsilon/2$ as I wrote initially but $\epsilon/4$, this is due to the fact that there are two possible definitions for the advantage of a distinguisher. Some papers use the absolute value of the difference to $1/2$ and some papers use twice that. For technical reasons, twice the difference is preferable and I did not initialy noticed that Boneh-Franklin don't use this version.
How is the advantage computed ? This needs an additional hypothesis which I did not mention. Take your game with a variable number of shares, say $\ell$, keeping $k$ fixed and denote by $\ell_0$ the smallest value for which there exists an adversary with non-negligible advantage. Clearly, if there exists an adversary for $\ell=2k+1$ then $\ell_0\leq 2k+1$. And, of course, $\ell_0&gt;k$ because with $k$ shares you have no information about $x$.

If $\ell_0=2k+1$ use the above reasoning. in this case, $\mathcal{A}$ cannot return $y=x$ with non-negligible probability when one share contains $x'_0$ because you could then transform $\mathcal{A}$ into an adversary against $\ell_0-1$ shares by just adding a random valued share. If $\ell_0&lt;2k+1$, redo the reasoning with the new $\ell_0$. This changes the advantage to $\frac{(\ell_0-k)\epsilon}{2k}$. The only problem is that in the case $\ell_0=k+1$, the reduction is not tight.




Response to Ricky's comment on the tightness of the reduction:

I don't see how you get a degradation exponential in $k$. Here is a more precise analysis of the full game if you don't assume that the probability of success jumps from negligible for non-negligible but do a more precise analysis.

Let $\epsilon_\ell$ be the best possible advantage for an adversary that wins your game with $\ell$ queries. Note that $\epsilon_\ell$ form an increasing sequence.  

Moreover, the advantage in your original game is:
$$
\epsilon=\epsilon_{2k+1}=\sum_{i=k+1}^{2k+1}\epsilon_i-\epsilon_{i-1}.
$$
As a consequence, at least one of the differences is bigger than $\epsilon/(k+1)$.

Run $\mathcal{A}$ for an $\ell_0$ such that $\epsilon_{\ell_0}-\epsilon_{\ell_0-1}$ is not too small. The probability that $\mathcal{A}$ wins with $\ell_0$ genuine shares is higher than the probability with a fake share by at least  $\epsilon_{\ell_0}-\epsilon_{\ell_0-1}$, otherwise $\mathcal{A}$ could be used to improve $\epsilon_{\ell_0-1}$.

As a consequence, $\mathcal{B}$ wins with advantage at least $\frac{(\ell_0-k)(\epsilon_{\ell_0}-\epsilon_{\ell_0-1})}{2k}\geq \frac{(\ell_0-k)\epsilon}{2k^2}$.

So the degradation is polynomial in $k$ not exponential.