Cryptology ePrint Archive: Report 2016/860

Efficient IBE with Tight Reduction to Standard Assumption in the Multi-challenge Setting

Junqing Gong and Xiaolei Dong and Jie Chen and Zhenfu Cao

Abstract: 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].

Category / Keywords: Identity based encryption, Tight security, Nested dual system group, Prime-order bilinear group, Groth-Sahai proof

Original Publication (in the same form): IACR-ASIACRYPT-2016

Date: received 6 Sep 2016, last revised 10 Sep 2016

Contact author: gongjunqing at 126 com, S080001 at e ntu edu sg

Available format(s): PDF | BibTeX Citation

Version: 20160910:152224 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]