International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Efficient Identity-Based Encryption with Tight Security Reduction

Nuttapong Attrapadung
Benoit Chevallier-Mames
Jun Furukawa
Takeshi Gomi
Goichiro Hanaoka
Hideki Imai
Rui Zhang
Search ePrint
Search Google
Abstract: 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.
  title={Efficient Identity-Based Encryption with Tight Security Reduction},
  booktitle={IACR Eprint archive},
  keywords={ID-based encryption, tight security},
  note={ 13111 received 9 Sep 2005, last revised 24 Nov 2005},
  author={Nuttapong Attrapadung and Benoit Chevallier-Mames and Jun Furukawa and Takeshi Gomi and Goichiro Hanaoka and Hideki Imai and Rui Zhang},