International Association
for Cryptologic Research

The notion of extended nested dual system groups (ENDSG) was recently proposed by Hofheinz et al. [PKC 2015] for constructing almost-tight identity based encryptions (IBE) in the multi-instance, multi-ciphertext setting. However only the composite-order instantiation was provided and more efficient prime-order instantiations are absent. The paper fills the blank by presenting two constructions.

- We revisit the notion of ENDSG and realize it using asymmetric prime-order bilinear groups based on Chen and Wee\'s prime-order instantiation of nested dual system groups [CRYPTO 2013]. This yields the first almost-tight IBE in the prime-order setting achieving weak adaptive security in the multi-instance, multi-ciphertext scenario under the $d$-linear assumption (in the asymmetric setting). We further extended the ENDSG to capture stronger security notions, including $B$-weak adaptive security and full adaptive security, and show that our prime-order instantiation is $B$-weak adaptive secure without any additional assumption and full adaptive secure under the $d$-linear assumption.

- We also try to provide better solution by fine-tuning ENDSG again and realizing it following the work of Chen, Gay, and Wee [EUROCRYPT 2015]. This leads to an almost-tight fully adaptively secure IBE in the same setting with better performance than our first IBE scheme but requires a non-standard assumption, $d$-linear assumption with auxiliary input. However we note that, the $2$-linear assumption with auxiliary input is implied by the external decisional linear assumption. Or we can realize the second instantiation using \\emph{symmetric} bilinear pairings in which case the security relies on standard decisional linear assumption.