The Twin Bilinear Diffie-Hellman Inversion Problem and Applications - Information Security and Cryptology-ICISC 2010 - page 130

18. Dodis, Y., Yampolskiy, A.: A Verifiable Random Function with Short Proofs and
Keys. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 416-431. Springer,
Heidelberg (2005)
19. Gentry, C.: Practical Identity-Based Encryption Without Random Oracles. In:
Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 445-464. Springer,
Heidelberg (2006)
20. Libert, B., Quisquater, J.J.: Identity based encryption without redundancy. In:
Ioannidis, J., Keromytis, A.D., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531,
pp. 285-300. Springer, Heidelberg (2005)
21. McCullagh, N., Barreto, P.S.L.M.: A New Two-Party Identity-Based Authenti-
cated Key Agreement. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp.
262-274. Springer, Heidelberg (2005)
22. Sakai, R., Kasahara, M.: ID based Cryptosystems with Pairing on Elliptic Curve.
Cryptology ePrint Archive, Report 2003/054 (2003), http://eprint.iacr.org/

A Security Notions

In this section, we briefly review the security notions for IBE and ID-KEM.

A.1 Chosen Ciphertext Security for IBE

Recall that an IBE system consists of four algorithms [7]: Setup , KeyGen , Encrypt ,
Decrypt .Via( mpk, msk )= Setup (1 κ ) the PKG generate the master key pair
( mpk, msk ). Via sk

← KeyGen ( msk, ID ) the PKG uses the master secret key msk
to generate the private key sk corresponding to ID .Via C

← Enc ( mpk, M, ID )
the encryption algorithm encrypts messages for a given identity and the decryp-
tion algorithm decrypts ciphertexts using the private key via M ← Dec ( sk, C ).

The definition of adaptive chosen ciphertext security for IBE was first formalized
by Boneh and Franlkin in [7, 8]. An IBE scheme is said to be secure against an

adaptively chosen ciphertext attack ( IND - ID - CCA ) if no probabilistic polynomial
time (PPT) algorithm

E

A has a non-negligible advantage against the challenger

in the following game:

Setup. The challenger run the Setup on security parameter κ to generate the
public parameters mpk and the master secret msk , gives the adversary the public
parameters, and keeps the master secret to itself.
Phase 1. The adversary issues queries q 1 ,...,q m where query q i is one of:
- Extraction query . The challenger responds by running algorithm Extract

to generate the private key d i corresponding to ID i . It sends d i to the adversary
A

ID i

.
- Decryption query . The challenger responds by running algorithm

Extract to generate the private key d i corresponding to ID i . It then runs
algorithm Decrypt to decrypt the ciphertext C i

ID i ,C i

using the private key d i .It

.
These queries may be asked adaptively, that is, each query q i may depend on
the replies to q 1 ,...,q i− 1 .

sends the resulting plaintext to the adversary A