Cryptology ePrint Archive: Report 2005/320

Efficient Identity-Based Encryption with Tight Security Reduction

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

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.

Category / Keywords: ID-based encryption, tight security

Date: received 9 Sep 2005, last revised 24 Nov 2005

Contact author: takego at imailab iis u-tokyo ac jp

Available format(s): PDF | BibTeX Citation

Version: 20051124:072627 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]