Paper 2016/860

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

Junqing Gong, Xiaolei Dong, Jie Chen, and Zhenfu Cao


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

Available format(s)
Publication info
Published by the IACR in ASIACRYPT 2016
Identity based encryptionTight securityNested dual system groupPrime-order bilinear groupGroth-Sahai proof
Contact author(s)
gongjunqing @ 126 com
S080001 @ e ntu edu sg
2016-09-10: received
Short URL
Creative Commons Attribution


      author = {Junqing Gong and Xiaolei Dong and Jie Chen and Zhenfu Cao},
      title = {Efficient IBE with Tight Reduction to Standard Assumption in the Multi-challenge Setting},
      howpublished = {Cryptology ePrint Archive, Paper 2016/860},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.