# 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$
-
I don't see how $\mathcal{A}$ could ever succeed in this case as it can only recover $k$ of the shares of $x$. Are you asking if it is known that with IBE, $\mathcal{A}$ cannot use private keys that correspond to some IDs to generate a private key that corresponds to a different ID? –  mikeazo Jul 31 '13 at 13:26
Minor typo: Challenger gives pub (not msk) to adversary. –  minar Jul 31 '13 at 19:39
@minar: fixed </embarrased> –  Ricky Demer Jul 31 '13 at 21:57
@mikeazo: $\;\;$ I'm asking if it can be important that $\mathcal{A}$ gets to choose which private keys to see after seeing the ciphertexts. $\:$ I can see the reduction for the modification where the adversary must choose which private keys it will get before seeing the ciphertexts. $\;\;\;\;$ –  Ricky Demer Jul 31 '13 at 22:00
I've not read it, but judging by the title this paper seems to address this exact situation: Bellare, Waters, Yilek: Identity-Based Encryption Secure against Selective Opening Attack. –  Mikero Aug 1 '13 at 4:39

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$.

1. 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.
2. 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>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<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.

-
I don't see a reason it should be unlikely for $y$ to be consistent with $x_0$ when $\hspace{2 in}$ the Challenger returned an encryption of $x_0'$. $\:$ –  Ricky Demer Jul 31 '13 at 22:12
I just noticed a problem with your argument: in the asymptotic case, it's not clear that one can choose a smallest $\ell$ since whether or not there is an adversary with a non-negligible success probability depends on all values of the function $\ell$, and in the concrete case, the reduction from $\:(2\cdot k)+1\:$ to $\:k+1\:$ changes $\epsilon$ by an exponential (in $k$) factor. $\;\;\;$ –  Ricky Demer Aug 17 '13 at 1:47
The more precise analysis does seem to work, since it uses the difference between the $\epsilon\hspace{.015 in}$s, $\hspace{.7 in}$ rather that just each $\epsilon$ individually. $\:$ –  Ricky Demer Aug 18 '13 at 0:33