Efficient IBE with tight reduction to standard assumption in the multi-challenge setting

In 2015, Hofheinz et al. [PKC, 2015] extended Chen and Wee’s almost-tight reduction technique for identity based encryptions (IBE) [CRYPTO, 2013] to the multi-instance, multi-ciphertext (MIMC, or multi-challenge) setting, where the adversary is allowed to obtain multiple challenge ciphertexts from multiple IBE instances, and gave the first almost-tightly secure IBE in this setting using composite-order bilinear groups. Several prime-order realizations were proposed lately. However there seems to be a dilemma of high system performance (involving ciphertext/key size and encryption/decryption cost) or weak/standard security assumptions. A natural question is: can we achieve high performance without relying on stronger/non-standard assumptions? In this paper, we answer the question in the affirmative by describing a prime-order IBE scheme with the same performance as the most efficient solutions so far but whose security still relies on the standard k-linear (k-Lin) assumption. Our technical start point is Blazy et al.’s almost-tightly secure IBE [CRYPTO, 2014]. We revisit their concrete IBE scheme and associate it with the framework of nested dual system group. This allows us to extend Blazy et al.’s almost-tightly secure IBE to the MIMC setting using Gong et al.’s method [PKC, 2016]. We emphasize that, when instantiating our construction by the Symmetric eXternal Diffie-Hellman assumption (SXDH = 1-Lin), we obtain the most efficient concrete IBE scheme with almost-tight reduction in the MIMC setting, whose performance is even comparable to the most efficient IBE in the classical model (i.e., the single-instance, single-ciphertext setting). Besides pursuing high performance, our IBE scheme also achieves a weaker form of anonymity pointed out by Attrapadung et al. [AsiaCrypt, 2015].