Paper 2005/320

Efficient Identity-Based Encryption with Tight Security Reduction

Nuttapong Attrapadung, Benoit Chevallier-Mames, Jun Furukawa, Takeshi Gomi, Goichiro Hanaoka, Hideki Imai, and Rui Zhang


In a famous paper of Crypto'01, Boneh and Franklin proposed the first identity-based encryption scheme (IBE), around fifteen years after the concept was introduced by Shamir. Their scheme security (more precisely, the notion of resistance against an IND-ID-CCA attacker) relies in the random oracle model. However, the reduction is far from being tight, and notably depends on the number of extractions queries. In this paper, we present an efficient modification to the Boneh-Franklin scheme that provides a tight reduction. Our scheme is basically an IBE under two keys, one of which is (randomly) detained by the recipient. It can be viewed as a continuation of an idea introduced by Katz and Wang; we will however show how our construction improves this last scheme. Our scheme features a tight reduction to the list bilinear Diffie-Hellman (LBDH) problem, which can be itself reduced tightly either to the gap bilinear Diffie-Hellman (GBDH) or the decisional bilinear Diffie-Hellman (DBDH) problems. Furthermore, for a relaxed notion of tightness (called weak-tightness) that we introduce and discuss in our paper, we show that there is a weakly tight reduction from our scheme to the computational bilinear Diffie-Hellman (CBDH) problem. Our scheme is very efficient, as one can precompute most of the quantity involved in the encryption process. Furthermore, the ciphertext size is very short: for proposed parameters, they are |M|+330 bits long.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
ID-based encryptiontight security
Contact author(s)
takego @ imailab iis u-tokyo ac jp
2005-11-24: last of 3 revisions
2005-09-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nuttapong Attrapadung and Benoit Chevallier-Mames and Jun Furukawa and Takeshi Gomi and Goichiro Hanaoka and Hideki Imai and Rui Zhang},
      title = {Efficient Identity-Based Encryption with Tight Security Reduction},
      howpublished = {Cryptology ePrint Archive, Paper 2005/320},
      year = {2005},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.