﻿Chosen-Ciphertext Secure Identity-Based Encryption in the Standard
Model with short Ciphertexts
Eike Kiltz
CWI Amsterdam
kiltz@cwi.nl
Abstract
We describe a practical identity-based encryption scheme that is secure in the standard model
against chosen-ciphertext (CCA2) attacks. Security is based on an assumption comparable to (but
slightly stronger than) Bilinear Decisonal Diffie-Hellman (BDDH). A comparison shows that our
construction outperforms all known identity-based encryption schemes in the standard model and
its performance is even comparable with the one from the random-oracle based Boneh/Franklin
IBE scheme. Our proposed IBE scheme has furthermore the property that it fulfills some notion of
“redundancy-freeness”, i.e. the encryption algorithm is not only a probabilistic injection but also a
surjection. As a consequence the ciphertext overhead is nearly optimal: to encrypt k bit messages
for k bit identities and with k bit randomness we get 3k bit ciphertexts to guarantee (roughly) k
bits of security.
Keywords: Chosen-ciphertext security, Identity-Based Encryption, Bilinear Maps.
1 Introduction
Identity-Based Encryption and Key Encapsulation. An Identity-Based Encryption (IBE)
scheme is a public-key encryption scheme where any string is a valid public key. In particular, email
addresses and dates can be public keys. The ability to use identities as public keys avoids the need to
distribute public key certificates.
After Shamir proposed the concept of IBE in 1984 [38] it remained an open problem for almost two
decades to come up with a satisfying construction for it. In 2001, Boneh and Franklin [8] proposed
formal security notions for IBE systems and designed a fully functional secure IBE scheme using
bilinear maps. This scheme and the tools developed in its design have been successfully applied in
numerous cryptographic settings, transcending by far the identity based cryptography framework. IBE
is currently in the process of getting standardized — from February 2006 on the new IEEE P1363.3
standard for “Identity-Based Cryptographic Techniques using Pairings” [25] accepts submissions.
An alternative but less efficient IBE construction was proposed by Cocks [16] based on quadratic
residues. Both IBE schemes (Cocks’ scheme only through Fujisaki-Okamoto [18]) provide security
against chosen-ciphertext attacks. In a chosen ciphertext attack, the adversary is given access to a
decryption oracle that allows him to obtain the decryptions of ciphertexts of his choosing. Intuitively,
security in this setting means that an adversary obtains (effectively) no information about encrypted
messages, provided the corresponding ciphertexts are never submitted to the decryption oracle. For
different reasons, the notion of chosen-ciphertext security has emerged as the “right” notion of security
for encryption schemes. We stress that, in general, chosen-ciphertext security is a much stronger
security requirement than chosen-plaintext attacks [1], where in the latter an attacker is not given
access to the decryption oracle.
The drawback of the IBE scheme from Boneh-Franklin and Cocks is that security can only be
guaranteed in the random oracle model [2], i.e. in an idealized world where all parties magically get
1
black-box access to a truly random function. Unfortunately a proof in the random oracle model can
only serve as a heuristic argument and has proved to possibly lead to insecure schemes when the
random oracles are implemented in the standard model (see, e.g., [11]).
Waters’ IBE. To fill this gap Waters [40] presents the first efficient Identity-Based Encryption scheme
that is chosen-plaintext secure without random oracles. The proof of his scheme makes use of an
algebraic method first used by Boneh and Boyen [5] and security of the scheme is based on the
Bilinear Decisional Diffie-Hellman (BDDH) assumption. However, Waters’ plain IBE scheme only
guarantees chosen-plaintext security.
From 2-level Hierarchical IBE to chosen-chipertext secure IBE. Hierarchical identitybased
encryption (HIBE) [24, 19] is a generalization of IBE allowing for hierarchical delegation of
decryption keys. Recent results from Canetti, Halevi, and Katz [12], further improved upon by Boneh
and Katz [9] show a generic and practical transformation from any chosen-plaintext secure 2-level
HIBE scheme to a chosen-ciphertext secure IBE scheme. Since Waters’ IBE scheme can naturally be
extended to a 2-level HIBE this implies the first efficient chosen-ciphertext secure IBE in the standard
model. Key size, as well as the security reduction of the resulting scheme are comparable to the ones
from Waters’ IBE. However, the transformation involves some symmetric overhead to the ciphertext
in form of a one-time signature or a MAC with their respective keys.
The first “direct” (non 2-level HIBE based) chosen-ciphertext IBE construction in the standard
model was given by Galindo and Kiltz [26]. Their construction is based on Waters’ IBE and adds one
additional element to the ciphertext that is used for a consistency check in the decryption algorithm.
However, in terms of ciphertext size and performance it did not introduce a dramatic improvement
over the generic 2-level HIBE based constructions.
Identity-based key encapsulation. Instead of providing the full functionality of an IBE scheme,
in many applications it is sufficient to let sender and receiver agree on a common random session
key. This can be accomplished with an identity-based key encapsulation mechanism (IB-KEM) as
formalized in [17, 4]. Any IB-KEM can be updated to a full IBE scheme by adding a symmetric
encryption scheme. The latter one is also called a data encapsulation scheme (DEM) and the resulting
identity-based encryption scheme the resulting hybrid IBE scheme. If both the IB-KEM and the DEM
are chosen-ciphertext secure, then the hybrid IBE scheme is also chosen-ciphertext secure. We note
that chosen-ciphertext secure DEMs can be created from relatively weak primitives such as a one-time
symmetric encryption scheme (e.g., a one-time pad) plus a message authentication code (MAC).
1.1 Our Contributions
A new chosen-ciphertext secure IB-KEM/IBE scheme. Based on Waters’ chosen-plaintext
secure IBE scheme we present a new and direct identity-based key encapsulation mechanism with short
ciphertexts and very efficient encapsulation/decapsulation algorithms. Chosen-ciphertext security is
obtained at sheer optimal cost. Compared to Waters’ raw chosen-plaintext secure IBE scheme (viewed
as an IB-KEM) our scheme comes with the same ciphertext overhead whereas computational overhead
is one more exponentiation for encapsulation and two more exponentiations for decapsulation. We
give a rigorous game-based proof reducing chosen-ciphertext security of our scheme to breaking the
modified Bilinear Decisional Diffie-Hellman assumption (mBDDH), an assumption closely related to
BDDH. By adding a one-time secure symmetric encryption scheme and a MAC we obtain a new hybrid
IBE scheme with short ciphertexts using the IB-KEM/DEM methodology [4].
An identity-preserving redundancy-free IBE scheme in the standard model. It is furthermore
possible to obtain a full IBE scheme with shorter ciphertexts by using the DEMs based
on the CMC [22] and EME [23] mode of operation that avoid the overhead due to the MAC. Then
2
ciphertexts of our IBE come with minimal overhead, i.e they are identity-preserving redundancy-free.
Following Phan and Pointcheval [34] this property means that the IBE encryption algorithm (viewed
as a mapping from randomness space, identity space, and message space into the ciphertext space) is a
bijection. Consequently all possible ciphertexts in the ciphertext space are reachable by the encryption
algorithm — shrinking the ciphertext any further is not possible. Our construction is the first weakly
redundancy-free IBE scheme in the standard model.
A (stronger) notion of redundancy-free IBE schemes further requires that even for any possible
identity from the identity-space the encryption algorithm (now viewed as a mapping from randomness
space and message space into the ciphertext space) is a bijection. Obtaining such strongly redundancyfree
IBE schemes is possible but they are only known to exist in the random oracle model and under
the highly non-standard “gap-BDDH” assumption [28].
We find even the existence of identity-preserving redundancy-free IBE schemes in the standard
model particularly remarkable since in the standard public-key encryption setting redundancy-free
schemes (in the sense of [34]) are not known to exist. We further remark that the ciphertexts of our
IBE scheme have the same message expansion as the most efficient standard public-key encryption
schemes (like Kurosawa/Desmedt [27] and BMW [10]), i.e. compared to standard PKE we obtain
identity-based encryption with no overhead.
The mBDDH assumption and its relation to known assumptions. As a by-product we
formalize and study our new mBDDH assumption and relate its hardness to well-known pairing-based
“standard assumptions”. In particular we show that “2-BDDHI is at least as strong as mBDDH is at
least as strong as BDDH”. The 2-BDDHI (2 Biliear Decisional Diffie-Hellman Inversion) assumption
was introduced by Boneh and Boyen [5] and its stronger variants (q-BDDHI for some polynomial q)
already found numerous applications in [5, 6, 7, 32].
1.2 Related Work and Comparison
As we already pointed out, chosen-ciphertext secure IBE scheme were known to exist using generic
reductions [12] based on Waters’ 2-level HIBE [40]. Recently the first direct chosen-ciphertext secure
IBE scheme was constructed in [26]. Compared to Waters’ chosen-plaintext secure IBE scheme, the
latter direct construction adds one additional redundant element to the ciphertext. This element is
used as a “check” to defend against invalid ciphertexts, where the check had to be carried out using
bilinear pairings. A similar technique is implicitly contained in the generic constructions based on 2level
HIBEs. The main idea of our new scheme is to encode the information necessary for the validity
check into Waters’ original ciphertext. This more efficient encoding also enables us to perform a more
efficient decryption.
A comparison with chosen-ciphertext secure IBE schemes in the standard model. We
will (in Section 7) carefully review all known chosen-ciphertext secure IBE constructions, including the
above proposals, and make an extensive comparison with our scheme. In terms of ciphertext expansion
our IBE scheme saves (at least) one group element compared to all so far known constructions. The
relative savings for encryption/decryption are (at least) one exponentiation and one pairing plus one
exponentiation, respectively. We conclude that, to the best of our knowledge, our IBE is the most
efficient chosen-ciphertext secure IBE scheme in the standard model.
A comparison with the Boneh/Franklin random oracle IBE scheme. Using recent experimental
data for atomic primitives (such as exponentiations and pairings) from Granger, Page, and
Smart [21] we estimate the efficiency of a possible implementation of our scheme using asymmetric
pairings over non-singular elliptic curves. We make a careful comparison with the well known IBE
scheme from Boneh and Franklin [8] (which is only known to be secure in the random oracle model).
3
In turns out that the efficiency of our scheme is comparable to the one from Boneh and Franklin —
ciphertext expansion is more or less the same and encryption is a factor of 3 − 10 faster (depending on
the chosen security parameter), whereas decryption is about 1.5 − 3 times slower. We conclude that
our scheme has ciphertext size and efficiency comparable to the random oracle based Boneh/Franklin
IBE scheme.
2 Definitions
2.1 Notation
If x is a string, then |x| denotes its length, while if S is a set then |S| denotes its size. If k ∈ N then 1k denotes the string of k ones. If S is a set then s $
← S denotes the operation of picking an element s of
S uniformly at random. We write A(x, y, . . .) to indicate that A is an algorithm with inputs x, y, . . .
and by z $
← A(x, y, . . .) we denote the operation of running A with inputs (x, y, . . .) and letting z be
the output. We write AO1,O2,... (x, y, . . .) to indicate that A is an algorithm with inputs x, y, . . . and
access to oracles O1, O2, . . . and by z $
← AO1,O2,... (x, y, . . .) we denote the operation of running A with
inputs (x, y, . . .) and access to oracles O1, O2, . . ., and letting z be the output.
2.2 Identity Based Key Encapsulation
An identity-based key-encapsulation mechanism (IB-KEM) scheme [38, 8] IBKEM = (IBKEMkg,
IBKEMkeyder, IBKEMenc, IBKEMdec) consists of four polynomial-time algorithms. Via (pk, msk) $
←
IBKEMkg(1k ) the randomized key-generation algorithm produces master keys for security parameter
$
k ∈ N; via usk[id] ← IBKEMkeyder(msk, id) the master computes the secret key for identity id; via
(C , K) $
← IBKEMenc(pk, id) a sender creates a random session key K and a corresponding ciphertext
C with respect to identity id; via K ← IBKEMdec(usk, C ) the possessor of secret key usk decapsulates
ciphertext C to get back a session key K. Associated to the scheme is a key space KeySp. For consistency,
we require that for all k ∈ N, all identities id, and all (C , K) $
← IBKEMenc(pk, id), we have
Pr[IBKEMdec(IBKEMkeyder(msk, id), C ) = K] = 1, where the probability is taken over the choice of
(pk, msk) $
← IBKEMkg(1k ), and the coins of all the algorithms in the expression above.
Let IBKEM = (IBKEMkg, IBKEMkeyder, IBKEMenc, IBKEMdec) be an IB-KEM with associated
key space KeySp. To an adversary A we associate the following experiment:
Experiment Exp ibkem-cca
IBKEM ,A (k)
(pk, msk) $
← IBKEMkg(1k )
(id ∗ , state) $
← AKeyDer(·),Dec(·,·) (find, pk)
K∗ $
0 ← KeySp ; (C ∗ , K∗ $
1 ) ← IBKEMenc(pk, id ∗ )
γ $
← {0, 1} ; K ∗ ← K ∗ γ
γ ′ $
← AKeyDer,Dec (guess, K∗ , C ∗ , state)
If γ �= γ ′ then return 0 else return 1
The oracle KeyDer(id) returns sk[id] $
← KeyDer(msk, id) with the restriction that A is not allowed
to query oracle KeyDer(·) for the target identity id ∗ . The oracle Dec(id, C ) first computes sk[id] $
←
KeyDer(msk, id) as above and then returns K ← IBKEMdec(sk[id], id, C ) with the restriction that
in the guess stage A is not allowed to query oracle Dec(·, ·) for the tuple (id ∗ , C ∗ ). state is some
internal state information of adversary A and can be any (polynomially bounded) string. We define
4
the advantage of A in the chosen-ciphertext experiment as
Adv ibkem-cca
�
�
IBKEM ,A (k) = �
�Pr �
Exp ibkem-cca
�
IBKEM ,A (k) = 1 − 1
�
�
�
2�
.
An IB-KEM IBKEM is said to be secure against chosen-ciphertext attacks (CCA secure) if the advantage
functions Adv ibkem-cca
IBKEM ,A (k) is a negligible function in k for all polynomial-time adversaries A.
We remark that our security definition is given with respect to “full-identity” attacks, as opposed
to the much weaker variant of “selective-identity” attacks where the adversary has to commit to its
target identity id ∗ in advance, even before seeing the public key.
2.3 Target Collision Resistant Hash Functions
Let F = (TCRs)s∈S be a family of hash functions for security parameter k and with seed s ∈ S = S(k).
F is said to be collision resistant if, for a hash function TCR = TCRs (where the seed is chosen at
random from S), it is infeasible for an efficient adversary to find two distinct values x �= y such that
TCR(x) = TCR(y).
A weaker notion is that of target collision resistant hash functions. Here it should be infeasible for
an efficient adversary to find, given a randomly chosen element x and a randomly drawn hash function
TCR = TCRs, a distinct element y �= x such that TCR(x) = TCR(y). (In collision resistant hash
functions the value x may be chosen by the adversary.) Such hash functions are also called universal
one-way hash functions [31] and can be built from arbitrary one-way functions [31, 35]. We define
(slightly informal)
Adv hash-tcr
TCR,H (k) = Pr[H finds a collision in TCR].
Hash function family is said to be a target collision resistant if the advantage function Adv hash-tcr
TCR,H is
a negligible function in k for all polynomial-time adversaries H.
In practice, to build a target collision resistant hash function TCR, one can use a dedicated cryptographic
hash function, like SHA-1 [37]. For that reason and to simplify our presentation, in what
follows we will consider the hash function TCR to be a fixed function.
3 Assumptions
3.1 Parameter generation algorithms for Bilinear Groups.
All pairing based schemes will be parameterized by a pairing parameter generator. This is a PTA G
that on input 1 k returns the description of an multiplicative cyclic group G of prime order p, where
2 k < p < 2 k+1 , the description of a multiplicative cyclic group GT of the same order, and a nondegenerate
bilinear pairing ê: G×G → GT . See [8] for a description of the properties of such pairings.
We use G ∗ to denote G\{0}, i.e. the set of all group elements except the neutral element. Throughout
the paper we use PG = (G, GT , p, ê, g) as shorthand for the description of bilinear groups, where g is
a generator of G.
3.2 The modified BDDH assumption
Let PG be the description of pairing groups. Consider the following problem: Given (g, g a , g b , g (b2 ) , g c , W ) ∈
G 5 × GT as input, output yes if W = ê(g, g) abc and no otherwise. The mBDDH assumption states
that, roughly, this problem is computational infeasible. Note that this is nearly the standard BDDH
assumption (see Appendix C for a formal definition) with the only difference that with mBDDH a
distinguisher is additionally provided with the element g (b2 ) (which is hard to compute from g b ).
5
More formally, to a parameter generation algorithm for pairing-groups G and an adversary B we
assotiate the following experiment.
Experiment Expmbddh G,B (1k )
PG $
← G(1k )
a, b, c, w $
← Z∗ p
β $
← {0, 1}. If β = 1 then W ← ê(g, g) abc else W ← ê(g, g) w
β ′ $
← B(1k , PG, g, ga , gb , gb2, gc , W )
If β �= β ′ then return 0 else return 1
We define the advantage of B in the above experiment as
Adv mbddh
G,B (k) =
�
�
�
�Pr �
Exp mbddh
G,B (1 k �
) = 1 − 1
�
�
�
2�
.
We say that the modified Bilinear Decision Diffie-Hellman (mBDDH) assumption relative to generator
is a negligible function in k for all PTAs B.
G holds if Adv mbddh
G,B
3.3 Relation to BDDH and q-BDDHI
The next lemma classifies the strength of the modified BDDH assumption we introduced between the
well known standard pairing-based assumptions BDDH and 2-BDDHI (see Appendix C for definitions).
Here ”A ≤ B” means that assumption B implies assumption A (in a black-box sense), i.e. assumption
B is a stronger assumption than A.
Lemma 3.1 BDDH ≤ mBDDH ≤ 2-BDDHI ≤ 3-BDDHI ≤ . . .
The simple proof is postponed until Appendix C.3. Since 2-BDDHI is known to hold in the genericgroup
model [6] this in particular implies correctness of the mBDDH assumption in generic-groups.
4 A chosen-ciphertext secure IB-KEM based on mBDDH
In this section we present our new chosen-ciphertext secure IB-KEM. Let PG = (G, GT , p, ê, g) be
public system parameters obtained by running the group parameter algorithm G(1 k ).
4.1 Waters’ Hash
We review the hash function H : {0, 1} n → G used in Waters’ identity based encryption schemes [40].
On input of an integer n, the randomized hash key generator HGen(G) chooses n + 1 random group
elements h0, . . . , hn ∈ G and returns h = (h0, h1, . . . , hn) ∈ Gn+1 as the public description of the hash
function. The hash function H : {0, 1} n → G∗ is evaluated on a string id = (id 1, . . . , id n) ∈ {0, 1} n as
the product
H(id) = h0
In Appendix D.1 we remind the reader of Water’s original chosen-plaintext secure IBE scheme.
n�
i=1
6
h id i
i
∈ G.
IBKEMkg(1k )
α, u $
← G∗ ; z ← ê(g, α)
H $
← HGen(G)
mpk ← (H, u, z) ∈ Gn+2 × GT ; msk ← α ∈ G
Return (mpk, msk)
IBKEMenc(mpk, id)
r $
← Z ∗ p
c1 ← g r ; t ← TCR(c1)
c2 ← (H(id) · u t ) r
K ← z r ∈ GT
C ← (c1, c2) ∈ G 2
Return (C , K)
IBKEMkeyder(msk, id)
s $
← Zp
sk[id] ← (α · H(id) s , gs , us ) ∈ G3 Return sk[id]
IBKEMdec(mpk, id, sk[id], C )
Parse C as (c1, c2)
Parse sk[id] as (d1, d2, d3)
t ← TCR(c1)
v $
← Z ∗ p
Return K ← ê(d1 · d t 3 · (H(id)ut ) v , c1)
ê(g v · d2, c2)
Figure 1: Our chosen-ciphertext secure identity-based key encapsulation.
4.2 The IB-KEM Construction
Let TCR : G → Zp be a target collision-resistant hash function (whose definition can be looked up in
Appendix 2.3). Our IB-KEM with identity space IDSp = {0, 1} n (n = n(k)) and key space KeySp = GT
is depicted in Figure 1.
We call a (possibly malformed) ciphertext C = (c1, c2) ∈ G 2 consistent (w.r.t identity id and
public key pk) if (g, c1, H(id) · u t , c2) is a Diffie-Hellman tuple 1 , where t = TCR(c1). A correctly
generated ciphertext for identity id has the form C = (c1, c2) = (g r , (H(id) · u t ) r ) and therefore
(g, c1, H(id) · u t , c2) = (g, c1, H(id) · u t , (H(id) · u t ) r ) is always a DH tuple and consequently C is
consistent. Testing for a DH-tuple is equivalent to checking if if ê(g, c2) = ê(H(id) · u t , c1) and
therefore consistency of C can be implemented by evaluating the bilinear map twice. Note that
this consistency test can be performed by anybody knowing the public-key only. This property is
called “public verification” of the ciphertext.
4.3 Alternative Decapsulation
We now describe an alternative deterministic decapsulation algorithm which is more intuitive but less
efficient. We claim that the decapsulation algorithm from Figure 1 is equivalent to
1. Compute t = TCR(c1) and check if (g, c1, H(id) · u t , c2) is a DH tuple. If not, a random session key
K is returned (or the ciphertext gets rejected).
2. Otherwise return K ← ê(c1, d1 · d t 3 )/ê(c2, d2)
To prove this claim we define the function ∆(C ) = ê(c1, H(id)u t )/ê(g, c2). Then ∆(C ) = 1 if and
only if C is consistent. Consequently, for a random v ∈ Z ∗ p, K = ê(d1 · d t 3 , c1)/ê(d2, c2) · (∆(C )) v ∈ G ∗ T
evaluates to ê(d1 · d t 3 , c1)/ê(d2, c2) if C is consistent and to a random group element otherwise. The
claim then follows by
K = ê(c1, d1 · d t 3)/ê(c2, d2) · (∆(C )) v
= ê(c1, d1 · d t 3)/ê(c2, d2) · (ê(c1, H(id)u t )/ê(g, c2)) v
= ê(c1, d1 · d t 3 · (H(id)ut ) v )
ê(c2, g v · d2)
1 A tuple (g, g a , g b , g c ) ∈ G 4 is said to be a Diffie-Hellman tuple (DH tuple)i f ab = c mod p.
7
.
We remark that the original decapsulation algorithm roughly saves two pairing operations.
We now show correctness of the scheme, i.e. that the K computed in the encapsulation algorithm
matches the key K computed in the alternative decapsulation algorithm. We already showed that a
correctly generated ciphertext is always consistent. A correctly generated secret key for identity id has
the form sk[id] = (d1, d2, d3) = (α · H(id) s , g s , u s ). Therefore the key decryption algorithm computes
the key K as
K = ê(c1, d1 · d t 3)/ê(c2, d2)
= ê(g r , αH(id) s · (u s ) t )/ê((H(id) · u t ) r , g s )
= ê(g r , α) · ê(g r , H(id) s · (u s ) t )/ê((H(id) · u t ) r , g s )
= z r · ê(g r , (H(id) · u t ) s )/ê((H(id) · u t ) s , g r )
= z r ,
as the key computed in the encryption algorithm. This shows correctness.
4.4 Security
Theorem 4.1 Assume TCR is a target collision resistant hash function. Under the modified Bilinear
Decisional Diffie-Hellman (mBDDH) assumption relative to generator G, the IB-KEM from Section 4.2
is secure against chosen-ciphertext attacks. In particular, we have
Adv ibkem-cca
IBKEM ,A
= O(nq · (ɛ + q/p) + Advhash-tcr
TCR,H (k)) ,
for any adversary A running for time TimeA(k) = TimeB−Ω(ɛ−2 ·ln(ɛ−1 )+q), where ɛ = Adv mbddh
G,B (k)
and q is an upper bound on the number of key derivation/decryption queries made by adversary A.
The proof of Theorem 4.1 uses ideas from Waters [40] and will be given in Appendix B.
5 (Redundancy-free) Identity-Based Encryption
Given an IB-KEM and a symmetric encryption scheme, a hybrid identity-based encryption scheme
can be obtained by using the IB-KEM to securely transport a random session key that is fed into
the symmetric encryption scheme (also called data encapsulation mechanism — DEM) to encrypt the
plaintext message. It was recently shown in [4] that if both the IB-KEM and the DEM are chosenciphertext
secure, then the resulting hybrid encryption is also chosen-ciphertext secure. The security
reduction is tight.
A DEM secure against chosen-ciphertext attacks can be built from relatively weak primitives, i.e.
from any one-time symmetric encryption scheme by essentially adding a MAC. For concreteness we
mention that a chosen-ciphertext secure IBE scheme can be built from our IB-KEM construction with
an additional overhead of a DEM which consists of a (one-time secure) symmetric encryption plus
additional 128 bits for the MAC.
The modes of operation CMC [22] and EME [23] both give chosen-ciphertext secure DEMs provided
that the underlying block-cipher is a strong pseudorandom permutation and avoid the usual overhead
due to the MAC.
We note that for the natural task of securely generating a joint random session key, a IB-KEM is
sufficient and a fully-fledged identity-based encryption scheme is not needed.
8
At an abstract level, for each identity id from identity space IDSp, an IBE encryption algorithm
IBEencid can be viewed as an injective mapping
IBEencid : RandSp × MsgSp ↩→ CipherSp,
where RandSp is the randomness space, MsgSp is the message space, and CipherSp is the ciphertext
space. For each identity id ∈ IDSp this mapping must be injective since otherwise reconstruction
of the message M ∈ MsgSp (decryption) is not unique. That also implies that decrypting a fixed
ciphertext with respect to different identities must consequently lead to distinct plaintexts. By our
security definition we need a sufficiently large randomness space since otherwise the IBE scheme is
not even indistinguishable against chosen-plaintext attacks [20]. Following Phan and Pointcheval [34]
we say that an IBE scheme is redundancy-free if for any possible identity id the above encryption
mapping IBEencid is a bijection, i.e. if all elements from the ciphertext space are “reachable”. This
redundancy-free property means that in some sense the ciphertexts are minimal and can’t be further
shrunk.
Our scheme only satisfies redundancy-freeness with respect to a different (weaker) notion, it is
identity-preserving redundancy-free in the sense that the mapping
IBEenc : RandSp × IDSp × MsgSp → CipherSp
is a bijection, i.e. information about the identity id is absorbed by the ciphertext CipherSp. This
relaxation is useful if an IBE ciphertext is needed to be verifiable, i.e. if one can (publicly) verify if
an IBE ciphertext was indeed encrypted with some given identity. Applications of this property can
be found in threshold IBE scheme [26].
Using the IB-KEM/DEM paradigm with our IB-KEM constriction and one of the DEMs based on
the CMC/EME mode of operation we get an identity-preserving redundancy-free chosen-ciphertext
secure IBE scheme that is publicly verifiable.
As a consequence the ciphertext overhead of our IBE scheme is nearly optimal with respect to the
verifiability property. Suppose an adversary attacking the IBE scheme makes at most q decryption/key
derivation queries. A common estimate used here is q = 2 30 (suggested by Bellare and Rogaway [3]).
According to Theorem 4.1, to encrypt k bit messages for n = k bit identities and with k bit randomness
we get 3k bit ciphertexts to guarantee ≈ k − 30 bits of security. The 30 = log(q) bits of loss in the
security stems from the fact that the security reduction in Theorem 4.1 is not optimal (and depends
multiplicatively on q). We remark that the ciphertext size of our IBE scheme is about the same as
the one of the most efficient (standard) public-key encryption schemes in the standard model [27, 10].
We mention that there exists a redundancy-free IBE scheme [28] (in the sense of the first definition)
in the random oracle model but it’s security proof depends on a highly non-standard assumption. 2
6 Extensions
6.1 A Tradeoff between Public Key Size and Security Reduction
As independently discovered in [13, 30], there exists an interesting trade-off between key-size of Waters’
hash H and the security reduction of the IBE scheme.
The construction modifies Waters hash H as follows: Let the integer l = l(k) be a new parameter
of the scheme. In particular, we represent an identity id ∈ {0, 1} n as an n/l-dimensional vector
id = (id 1, . . . , id n/l), where each id i is an l bit string. Waters hash is then redefined to H : {0, 1} n → G,
2 The scheme in [28] is secure under the “gap-BDDH assumption” which is same as the BDDH assumption but it
additionally assumes the existence of an efficient DDH algorithm in the target group GT which is not known to exist.
9
�n/l with H(id) = h0
i=1 hid i
i for random public elements h0, h1, . . . , hn/l ∈ G. Waters’ original hash
function is obtained as the special case l = 1. It is easy to see that using this modification in our IBE
scheme (i) reduces the size of the public key from n + 3 to n/l + 3 group elements, whereas (ii) it adds
another multiplicative factor of 2l to the security reduction of the IBE scheme (Theorem 4.1). 3
6.2 Chosen-ciphertext secure Hierarchical Identity-Based Encryption
Hierarchical identity-based encryption is a generalization of IBE to identities supporting hierarchical
structures [24, 19]. By the relation to Waters IBE scheme it is easy to see that our technique can
also be used to obtain a chosen-ciphertext secure HIBE. Using a technique from [7] it is furthermore
possible to reduce the HIBE ciphertext size to three elements, i.e. it is independent of the hierarchy’s
depth. As in [19, 40] the security reduction is only exponential in the depth d of the hierarchy, i.e. it
introduces, roughly, a multiplicative factor of (nq) d . The keysize of the HIBE scheme is O(nd), whereas
the same tradeoff between public-key size and security reduction mentioned in the last subsection is
possible.
6.3 IB-KEM with Non-Interactive Threshold Decryption
Exploiting the public verifiability property of the ciphertext and using the same ideas as in [26] we
are able to make key derivation and decapsulation of our IB-KEM construction “threshold”. The
ciphertexts of the resulting threshold IB-KEM are shorter in comparison with [26].
6.4 Selective-Identity Chosen-Ciphertext Secure IB-KEM
For the definition of a selective-identity chosen-ciphertext secure IB-KEM we change the security
experiment such that the adversary has to commit to the target identity id ∗ before seeing the public
key. Clearly, this is a weaker security requirement. We quickly note that (using an algebraic technique
from [5]) by replacing Waters’ hash H with H(id) = h0 · hid 1 (for id ∈ Zp) we get a selective-id chosenciphertext
secure IB-KEM. Note that the size of the public-key of this scheme drops to 3 elements.
6.5 Chosen-Ciphertext Secure IB-KEM in the random oracle model
Replacing Water’s hash H with H(id) = h0 · h R(id)
1 (where R : {0, 1} ∗ → Zp is a random oracle) we
get (using the slective-identity secure scheme from the last subsection and a general result from [5])
a chosen-ciphertext secure IB-KEM in the random oracle model. By adding another random oracle
to the symmetric key the scheme can then be proved chosen-ciphertext secure with respect to the
computation variant of the mBDDH assumption. Again the size of the public-key of this scheme
drops to 3 elements.
6.6 Implementing the Target Collision Resistant Hash Function TCR
In practice, to build a target collision resistant hash function, one can use a dedicated cryptographic
hash function, like SHA-1 [37]. Every injective function TCR : G → Zp trivially also is (target) collision
resistant (with zero advantage). Boyen, Mei and Waters [10] note that for bilinear maps defined on
elliptic curves there exists a very efficient way to implement such injective mappings. We refer to [10]
for more details.
3 On the technical side our proof basically stays the same, only the bound from Lemma B.2 needs to be adapted to
take the modified Waters’ hash into account.
10
7 Comparison
In this section we compare our scheme with the known IBE schemes from the literature. For a uniform
treatment we do all comparisons in terms of the respective IBE schemes. The previously most efficient
CCA-secure IBE scheme is the one from Kiltz and Galindo [26]. We also compare our scheme with
the generic construction [12] obtained from a 2-level HIBE [40, 5] and with the original (only chosenplaintext
secure) IBE scheme from Waters. Furthermore we compare or scheme with the reference
random-oracle IBE scheme from Boneh and Franklin [8].
In pairing based cryptography efficiency depends on the chosen curve and how well the scheme
can be adapted to it. Usually [12, 10] a comparison is done by taking the pairing as a black-box and
under the simplified assumption that all exponentiations carried out in different groups have about
the same running time. We will follow this approach in Section 7.1. Then, in Section 7.2 we will
discuss how our scheme can possibly be instantiated in non-supersingular asymmetric pairing groups.
A carefull implementation-based comparison in the asymmetric setting with the Boneh/Franklin IBE
scheme will then be done in Section 7.3.
7.1 Comparison in the symmetric setting
We will consider the following IBE schemes:
Ours+DEM: Our construction from Section 4 updated with a DEM to get a full IBE scheme.
Kiltz/Galindo+DEM: The IB-KEM from [26] updated with a DEM to get a full IBE scheme.
Hybrid Waters/BB+CHK: The IBE scheme obtained by the generic transformation [12, 9] applied
to the 2-level hybrid HIBE consisting of Waters’ IBE scheme [40] at the first level and the
Boneh/Boyen IBE scheme [5] at the second level (as proposed in [40]).
Waters: Waters’ plain chosen-plaintext secure IBE scheme [40].
Boneh/Franklin: The random-oracle “fullident” chosen-ciphertext secure IBE scheme [8].
Since evaluating Waters’ hash H requires computing n/2 products in G on the average, where n ≤
log 2 p, it can be seen as a single exponentiation. Therefore we count computing H(id) r for random r
as two exponentiations in G. For decryption the value H(id) can be precomputed (and assumed to be
contained in sk[id]).
Comparison. An efficiency comparison is done in Table 1. We conclude that our scheme is the
most efficient chosen-ciphertext secure IBE scheme in the standard model. Furthermore its performance
and ciphertext expansion seems comparable to the random-oracle based reference scheme from
Boneh/Franklin.
7.2 Our IBE scheme in asymmetric pairing groups
Our definition of the bilinear groups assumed a symmetric pairing ê : G × G → GT . However, there
is a large class of admissible bilinear groups which have an asymmetric pairing ê : G1 × G2 → GT , i.e.
G1 �= G2. Such asymmetric bilinear groups have the advantage of being less special than symmetric
ones — and consequently have better security properties since their greater generality makes it harder
to design tailor-made attacks. Furthermore, as we will sketch below, they can lead to considerably
shorter ciphertexts than symmetric pairings.
In this setting we have to allocate the various group elements appearing in our IBE scheme to
the two groups G1 and G2. Depending on how this is done we can give different trade-offs between
computational efficiency for encryption/decryption and ciphertext size. To this end we will use the
following conventions [21]: (i) For general curves an element in G2 takes about α times as much space
11
Scheme CCA Standard Size Encrypt Decrypt Key Der.
Ours+DEM
Kiltz/Galindo+DEM
Hybrid Waters/BB+CHK
(Waters)
(Boneh/Franklin)
secure?
√
√
√
—
√
Model?
√
√
√
√
—
|C |
2|G|+128
3|G|+128
3|G|+768
2|G|
1|G|+256
pk
n + 3
n + 4
n + 4
n + 2
1
#pairings + #[multi,reg]-exp
0 + [1, 2] 2 + [1, 1] 0 + [0, 3]
0 + [1, 3] 3 + [1, 3] 0 + [0, 2]
0 + [1, 3] 3 + [1, 2] 0 + [0, 2]
0 + [0, 3] 2 + [0, 0] 0 + [0, 2]
1 + [0, 2] 1 + [0, 1] 0 + [0, 1]
Table 1: Efficiency comparison for chosen-ciphertext secure IBE schemes. Ciphertext overhead represents the
difference (in bits) between the ciphertext length and the message length. The additional bits account for the
necessary symmetric overhead for 128 bits security. The keysize of the public key is measured in terms of the
number of group elements. The size of the secret key sk is the same for all three schemes (a single element
in G). For computational efficiency we neglect all symmetric operations (like symmetric encryption, random
oracle hashes, and MACs). For comparison we mention that relative timings for the various operations are as
follows: regular pairing ≈ 3 − 5 [33], multi-exponentiation ≈ 1.5, regular exponentiation = 1.
Variant Element ... in group key decapsulation Encryption Decryption
c1 c2 d1 d2 d3 #pairings + #exp in (G1, G2, GT )
V1 G2 G2 G1 G1 G1
V2 G1 G1 G2 G2 G2
V3 G2 G1 G1 G2 G1
ê(d1d t
3 (H(id)ut ) v ,c1)
ê(g v d2,c2) 0 + (0, 3.5, 1) 1.5 + (2.5, 0, 0)
ê(c1,d1d t
3 (H(id)ut ) v )
ê(c2,g v d2) 0 + (3.5, 0, 1) 1.5 + (0, 2.5, 0)
ê(d1d t
3 (H(id)ut ) v ,c1)
ê(c2g v ,d2) 0 + (2.5, 1, 1) 1.5 + (2.5, 0, 0)
Table 2: Different asymmetric variants of our IBE scheme.
to represent as one in G1 , where α is the embedding degree (typical values for α are α = 6, 12, 24).
(ii) An exponentiation in G2 takes about α as much time as an exponentiation in G1. We adapt the
convention to count one multi-exponentiation as 1.5 exponentiations [12] and the ratio of two pairings
as 1.5 pairings [10]. 4 Based on those assumptions in Table 2 we give three variants of our IBE scheme
with different tradeoffs between ciphertext size and encryption/decryption efficiency. The relative
advantages are summarized in Table 3.
7.3 A comparison with the Boneh/Franklin scheme in the asymmetric setting
In this section we demonstrate the practicability of our IBE scheme by comparing it with the one
from Boneh/Franklin. We remark that the latter scheme is intensively used in practice (see, e.g.,
http://www.voltage.com). We aim to compare the schemes for fixed security parameters k =
80, 128, 192, 256. We denote the size of the message space by m.
4 Actually [10] mentions in Section 5.1 that “computation of a ratio of two pairings [...] can be done almost as efficiently
as a single pairing, by modifying Miller’s algorithm in a manner akin to multi-exponentiation [29]”. We think that a
factor of 1.5 is more realistic.
Variant Ciphertext space Ciphertext size Encryption Decryption
V1 G2 × G2 big slow fast
V2 G1 × G1 small fast slow
V3 G2 × G1 big medium fast
Table 3: Tradeoff between ciphertext size and efficiency for our IBE variants.
12
k Curve (log 2 p, α) Our IBE (Variant 2) Our IBE (Variant 3) Boneh/Franklin Boneh/Franklin2
Enc Dec |C| Enc Dec |C| Enc Dec |C| Enc Dec |C|
80 A (160,6) 4 20 400 8 10 720 16 6 320 11 10 640
128 B (512,6) 60 325 1152 115 187 2176 458 115 768 196 170 1792
128 C (256,12) 18 220 640 64 103 1920 314 66 512 118 113 1792
192 D (1365,6) 611 3687 2922 1170 2286 5652 7970 1431 1749 2472 1991 4479
192 E (683,12) 174 2405 1558 632 1259 4973 5472 815 1067 1350 1273 4482
256 F (2560,6) 2808 19074 5376 5386 12629 10496 51256 7989 3072 13613 10567 8192
256 G (1280,12) 788 11920 2816 2877 6697 9216 34950 4355 1792 6904 6445 8192
256 H (640,24) 262 7627 1536 1602 4276 8576 21418 2822 1152 4289 4163 8192
Table 4: Number of estimated 32 bit multiplications needed to perform Encryption/Decryption (scaled
by 10 5 ) and ciphertext overhead in bits. The column |C| gives the ciphertext overhead in bits.
Boneh/Franklin. We consider the fullident chosen-ciphertext secure Boneh/Franklin IBE scheme
(which for completeness can be looked up in Appendix D.2). For encryption it performs one exponentiation
in G1, one exponentiation in GT , one pairing, and one call a “hash-to-point” hash function
, modeled as a random oracle. The latter one was already identified in [33, 15, 21]
H1 : {0, 1} n → G∗ 2
to be problematic to implement since it needs one “cofactor” exponentiation in G2. For decryption it
needs one exponentiation in G1 and one pairing. The ciphertext space is G1 × {0, 1} 2k × {0, 1} m , the
{0, 1} 2k stems from the output of a hash function H2 (due to the birthday attack a domain of 2k is
needed to guarantee security of k bits).
Boneh/Franklin2. We denote by Boneh/Franklin2 the above scheme with switched roles of G1 and
G2. In variant the expensive “hash-to-point” hash function maps into the group G1 but on the other
hand we all exponentiations have to be carried out in G2 and furthermore the ciphertext lies in G2.
Our Scheme. We consider variants two and three of our IBE scheme from Table 2. Since we consider
full IBE schemes ciphertexts consist of the IB-KEM ciphertext plus a summetric one-time encryption
and a MAC. More precisely, the ciphertext space of our IBE scheme is G1 × G1 × {0, 1} k × {0, 1} m ,
where the {0, 1} k stands for the tag of the MAC (k bits are sufficient to guarantee security of k bits).
We estimate the cost of encryption and decryption using the timings for each atomic primitive
(exponentiations/hashes in G1, G2, GT and pairings) calculated in [21], where we used the timings for
the “pairing friendly curves” and the Tate pairing. Here we counted one hash-into-curve operation
used in the Boneh/Franklin scheme (the random oracle H2) as one co-factor exponentiation [21]. For
completeness all used timing data for the atomic primitives is given in Table 5 of Appendix A. The
comparison is done with respect to the different curves A-H considered in [21], the names correspond
the ones given therein. Important parameters for the curves are the estimated bits of security they
provide, the embedding degree α = 6, 12, 24, and the field size of the underlying finite field. We assume
that one element in G1 can be represented using log 2 p bits. We furthermore assume that one element
in G2 needs a factor of α as much space to represent as one element in G1, i.e. α log 2 p bits.
Comparison. The extensive comparison matrix for the different curves A-H is given in Table 4. We
conclude that efficiency of our scheme is comparable to the one from Boneh and Franklin — ciphertext
sizes are more or less the same and encryption is a factor of 3 − 10 faster (depending on the chosen
security parameter), whereas decryption of our scheme is about 1.5 − 3 times slower (depending on
the variant). One disadvantage of our scheme seems to be the relatively large public-key (n + 3 group
elements for n bit identities). We stress that with the techniques from Section 6.1 the public-key size
can easily be shrunk to n/l group elements with losing only l bits of security.
The IBE scheme from Sakai and Kasahara [36]. We remark that in the random oracle model
there also exists a more efficient IBE scheme that was recently proved secure by Chen and Cheng [14],
and further analyzed and implemented by Chen et al. [15]. Its encryption speed it roughly 1.5 times
13
faster than ours (and therefore 6-30 times faster than the one from Boneh/Franklin), and decryption
speed is 2 − 3 times as fast (and therefore comparable to the one from Boneh/Franklin). Therefore
it outperforms our IBE construction as well as the Boneh/Franklin IBE scheme. The drawback is,
however, that it relies on a seemingly much stronger security assumption, the qhash-BDDHI assumption
(as defined in Appendix C), where qhash ≈ 2 60 is the number of total random oracle queries an adversary
can do in attacking the scheme. 5 In contrast our scheme can be proved secure under the mBDDH
assumption which is according to Lemma 3.1 not stronger than the 2-BDDHI assumption.
Acknowledgment. We thank Alex Dent, Javier Herranz, Dennis Hofheinz, John Malone-Lee, and
Nigel Smart for their comments and suggestions.
References
[1] Mihir Bellare, Anand Desai, David Pointcheval, and Phillip Rogaway. Relations among notions of
security for public-key encryption schemes. In Hugo Krawczyk, editor, CRYPTO’98, volume 1462
of LNCS, pages 26–45, Santa Barbara, CA, USA, August 23–27, 1998. Springer-Verlag, Berlin,
Germany.
[2] Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing
efficient protocols. In ACM CCS 93, pages 62–73, Fairfax, Virginia, USA, November 3–5, 1993.
ACM Press.
[3] Mihir Bellare and Phillip Rogaway. The exact security of digital signatures: How to sign with
RSA and Rabin. In Ueli M. Maurer, editor, EUROCRYPT’96, volume 1070 of LNCS, Saragossa,
Spain, May 12–16, 1996. Springer-Verlag, Berlin, Germany.
[4] K. Bentahar, P. Farshim, J. Malone-Lee, and N.P. Smart. Generic constructions of
identity-based and certificateless KEMs. Cryptology ePrint Archive, Report 2005/058, 2005.
http://eprint.iacr.org/.
[5] Dan Boneh and Xavier Boyen. Efficient selective-id secure identity based encryption without
random oracles. In Christian Cachin and Jan Camenisch, editors, EUROCRYPT 2004, volume
3027 of LNCS, pages 223–238, Interlaken, Switzerland, May 2–6, 2004. Springer-Verlag, Berlin,
Germany.
[6] Dan Boneh and Xavier Boyen. Short signatures without random oracles. In Christian Cachin
and Jan Camenisch, editors, EUROCRYPT 2004, volume 3027 of LNCS, pages 56–73, Interlaken,
Switzerland, May 2–6, 2004. Springer-Verlag, Berlin, Germany.
[7] Dan Boneh, Xavier Boyen, and Eu-Jin Goh. Hierarchical identity based encryption with constant
size ciphertext. In Ronald Cramer, editor, EUROCRYPT 2005, volume 3494 of LNCS, pages
440–456, Aarhus, Denmark, May 22–26, 2005. Springer-Verlag, Berlin, Germany.
[8] Dan Boneh and Matthew K. Franklin. Identity based encryption from the Weil pairing. SIAM
Journal on Computing, 32(3):586–615, 2003.
[9] Dan Boneh and Jonathan Katz. Improved efficiency for CCA-secure cryptosystems built using
identity-based encryption. In Alfred Menezes, editor, CT-RSA 2005, volume 3376 of LNCS, pages
87–103, San Francisco, CA, USA, February 14–18, 2005. Springer-Verlag, Berlin, Germany.
5 Bellare and Rogaway suggest to use qhash = 2 60 for exact security reductions [3].
14
[10] Xavier Boyen, Qixiang Mei, and Brent Waters. Simple and efficient CCA2 security from IBE
techniques. In ACM Conference on Computer and Communications Security—CCS 2005, pages
320–329. New-York: ACM Press, 2005.
[11] Ran Canetti, Oded Goldreich, and Shai Halevi. The random oracle methodology, revisited. In
30th ACM STOC, pages 209–218, Dallas, Texas, USA, May 23–26, 1998. ACM Press.
[12] Ran Canetti, Shai Halevi, and Jonathan Katz. Chosen-ciphertext security from identity-based
encryption. In Christian Cachin and Jan Camenisch, editors, EUROCRYPT 2004, volume 3027 of
LNCS, pages 207–222, Interlaken, Switzerland, May 2–6, 2004. Springer-Verlag, Berlin, Germany.
[13] Sanjit Chatterjee and Palash Sarkar. Trading time for space: Towards an efficient ibe scheme
with short(er) public parameters in the standard model. Proceedings of ICISC, to appear, 2005.
[14] L. Chen and Z. Cheng. Security proof of sakai-kasahara’s identity-based encryption scheme. In
Proceedings of Cryptography and Coding 2005, volume 2796 of LNCS, pages 442–459. Berlin:
Springer-Verlag, 2005.
[15] L. Chen, Z. Cheng, J. Malone-Lee, and N.P. Smart. An efficient ID-KEM based on
the sakai-kasahara key construction. Cryptology ePrint Archive, Report 2005/224, 2005.
http://eprint.iacr.org/.
[16] Clifford Cocks. An identity based encryption scheme based on quadratic residues. In Bahram
Honary, editor, Cryptography and Coding, 8th IMA International Conference, volume 2260 of
LNCS, pages 360–363, Cirencester, UK, December 17–19, 2001. Springer-Verlag, Berlin, Germany.
[17] Ronald Cramer and Victor Shoup. Design and analysis of practical public-key encryption schemes
secure against adaptive chosen ciphertext attack. SIAM Journal on Computing, 33(1):167–226,
2003.
[18] Eiichiro Fujisaki and Tatsuaki Okamoto. Secure integration of asymmetric and symmetric encryption
schemes. In Michael J. Wiener, editor, CRYPTO’99, volume 1666 of LNCS, pages 537–554,
Santa Barbara, CA, USA, August 15–19, 1999. Springer-Verlag, Berlin, Germany.
[19] Craig Gentry and Alice Silverberg. Hierarchical ID-based cryptography. In Yuliang Zheng, editor,
ASIACRYPT 2002, volume 2501 of LNCS, pages 548–566, Queenstown, New Zealand, December
1–5, 2002. Springer-Verlag, Berlin, Germany.
[20] Shafi Goldwasser and Silvio Micali. Probabilistic encryption. Journal of Computer and System
Sciences, 28:270–299, 1984.
[21] R. Granger, D. Page, and N. P. Smart. High security pairing-based cryptography revisited.
Cryptology ePrint Archive, Report 2006/059, 2006. http://eprint.iacr.org/.
[22] Shai Halevi and Phillip Rogaway. A tweakable enciphering mode. In Dan Boneh, editor,
CRYPTO 2003, volume 2729 of LNCS, pages 482–499, Santa Barbara, CA, USA, August 17–
21, 2003. Springer-Verlag, Berlin, Germany.
[23] Shai Halevi and Phillip Rogaway. A parallelizable enciphering mode. In Tatsuaki Okamoto, editor,
CT-RSA 2004, volume 2964 of LNCS, pages 292–304, San Francisco, CA, USA, February 23–27,
2004. Springer-Verlag, Berlin, Germany.
15
[24] Jeremy Horwitz and Ben Lynn. Toward hierarchical identity-based encryption. In Lars R. Knudsen,
editor, EUROCRYPT 2002, volume 2332 of LNCS, pages 466–481, Amsterdam, The Netherlands,
April 28 – May 2, 2002. Springer-Verlag, Berlin, Germany.
[25] IEEE P1363.3 Committee. IEEE 1363.3 / CfS — standard for identity-based cryptographic techniques
using pairings. http://grouper.ieee.org/groups/1363/index.html/, February 2006.
Call for submissions.
[26] Eike Kiltz and David Galindo. Direct chosen-ciphertext secure identity-based encryption without
random oracles. Cryptology ePrint Archive, Report 2006/034, 2006. http://eprint.iacr.org/.
[27] Kaoru Kurosawa and Yvo Desmedt. A new paradigm of hybrid encryption scheme. In Matthew
Franklin, editor, CRYPTO 2004, volume 3152 of LNCS, pages 426–442, Santa Barbara, CA, USA,
August 15–19, 2004. Springer-Verlag, Berlin, Germany.
[28] B. Libert and J. Quisquater. Identity based encryption without redundancy. In ACNS’05, pages
285–300, 2005.
[29] Victor Miller. The Weil pairing, and its efficient calculation. Journal of Cryptology, 17(4), 2004.
[30] David Naccache. Secure and practical identity-based encryption. Cryptology ePrint Archive,
Report 2005/369, 2005. http://eprint.iacr.org/.
[31] Moni Naor and Moti Yung. Universal one-way hash functions and their cryptographic applications.
In 21st ACM STOC, pages 33–43, Seattle, Washington, USA, May 15–17, 1989. ACM Press.
[32] Tatsuaki Okamoto. Efficient blind and partially blind signatures without random oracles. In Shai
Halevi and Tal Rabin, editors, TCC 2006, LNCS, pages ???–???, New York, USA, February 5–7,
2006. Springer-Verlag, Berlin, Germany.
[33] D. Page, N.P. Smart, and F. Vercauteren. A comparison of MNT curves and supersingular curves.
Cryptology ePrint Archive, Report 2004/165, 2004. http://eprint.iacr.org/.
[34] Duong Hieu Phan and David Pointcheval. Chosen-ciphertext security without redundancy. In
Chi-Sung Laih, editor, ASIACRYPT 2003, volume 2894 of LNCS, pages 1–18, Taipei, Taiwan,
November 30 – December 4, 2003. Springer-Verlag, Berlin, Germany.
[35] John Rompel. One-way functions are necessary and sufficient for secure signatures. In 22nd ACM
STOC, pages 387–394, Baltimore, Maryland, USA, May 14–16, 1990. ACM Press.
[36] R. Sakai and M. Kasahara. ID based cryptosystems with pairing on elliptic curve. Cryptology
ePrint Archive, Report 2003/054, 2003. http://eprint.iacr.org/.
[37] Secure hash standard. National Institute of Standards and Technology, NIST FIPS PUB 180-1,
U.S. Department of Commerce, April 1995.
[38] Adi Shamir. Identity-based cryptosystems and signature schemes. In G. R. Blakley and David
Chaum, editors, CRYPTO’84, volume 196 of LNCS, pages 47–53, Santa Barbara, CA, USA,
August 19–23, 1985. Springer-Verlag, Berlin, Germany.
[39] Victor Shoup. OAEP reconsidered. In Joe Kilian, editor, CRYPTO 2001, volume 2139 of LNCS,
pages 239–259, Santa Barbara, CA, USA, August 19–23, 2001. Springer-Verlag, Berlin, Germany.
[40] Brent R. Waters. Efficient identity-based encryption without random oracles. In Ronald Cramer,
editor, EUROCRYPT 2005, volume 3494 of LNCS, pages 114–127, Aarhus, Denmark, May 22–26,
2005. Springer-Verlag, Berlin, Germany.
16
k Curve (log 2 p, α) exp G1 hash G1 exp G2 hash G2 exp GT pairing |G1| |G2|(|GT |)
80 A (160,6) 0.9 0 4.8 9.4 0.8 5.4 160 480
128 B (512,6) 14 14 69 330 11 101 512 1536
128 C (256,12) 3.6 0 50 243 5 63 256 1536
192 D (1365,6) 140 361 700 6419 120 1291 1365 4095
192 E (683,12) 36 28 494 4608 49 780 683 4098
256 F (2560,6) 644 2493 3223 42714 552 7345 2560 7680
256 G (1280,12) 163 241 2252 30377 217 4192 1280 7680
256 H (640,24) 42 10 1382 18480 115 2781 640 7680
Table 5: Timings in terms of estimated 32 bit multiplications needed to perform atomic primitives
(scaled by 10 5 ) and representation of group elements in bits. Hashing into the groups G1 and G2 is
dominated by a cofactor exponentiation which in case of hashing into G1 for curves A and C (nearly)
for free due to the small cofactor. All data is taken from Section 5 of [21].
A Timing data from [21].
The timing data used in our comparison in Section 7.3 is given in Table 5.
B Proof of Theorem 4.1
In this section we provide a game-based proof of Theorem 4.1. In fact in our proof some games could
be absorbed nearly verbatim from [26], i.e. Games 1-4 are the nearyl same as Games 1-4 in [26]. The
rest of the games are similar but due to the short ciphertexts and the different security assumption in
our construction important and non-trivial changes had to be made to the respective games.
We will make use of the following simple “Difference Lemma” [39].
Lemma B.1 Let X1,X2, B be events defined in some probability distribution, and suppose that
X1 ∧ ¬B ⇔ X2 ∧ ¬B. Then |Pr [ X1 ] − Pr [ X2 ]| ≤ Pr [ B ].
We assume modified BDDH is hard, i.e. for any adversary B running for polynomial time TimeB(k)
we have Adv mbddh
G,B (k) = ɛ(k), for a non-negligible function ɛ = ɛ(k). We will show that for any
adversary A against the chosen-ciphertext security of the IBE scheme running for time
TimeA(k) = TimeB(k) − Ω(ɛ −2 · ln(ɛ −1 ) + q)
and making a maximum of q = q(k) key-derivation/decapsulation queries, we have
Adv ibkem-cca
IBKEM ,A (k) = O(nq · (ɛ + q/p) + Advhash-tcr
TCR,H (k)) .
Game 0. Fix an efficient adversary A. We now define a game, Game 0, an interactive game between
adversary A and a simulator. Game 0 is simply the same game as the IBE security experiment
of Section 2.2 in which the simulator provides adversary A’s environment. While describing the
experiment we wll make a couple of conventions on how the simulator chooses the values appearing in
its simulation. These conventions will be purely conceptual and, compared to the original experiment,
do not change the distribution of any value appearing during the experiment. We will also make a
couple of definitions of values appearing during the experiments.
We assume that in the beginning the simulator chooses some values a, b, and c, uniformly distributed
from Zp. The whole simulation will depend on these values (i.e., the key generation will
depend on a, b, where the challenge ciphertext will depend on c). In sequel games the simulator will
”forget” the values a, b, and c and instead only use the values ga , gb , gb2, and gc .
17
Key Generation. Initially the simulator runs the IBE key generation algorithm IBKEMkg(1k ) and
obtains the public key mpk = (u, z, H) and secret key msk = α. We make the convention that the
keys are generated as
u $
← g b ; z ← ê(g a , g b ) ; H $
← HGen(G) (1)
depending on the element g a , g b chosen by the simulator in advance. Note that the way the value
z = ê(g a , g b ) = ê(g, g ab ) from the public key is generated implies α = g ab = u a . Note that α can be
computed by the simulator since a is still known in this game. The public key is given to the adversary
to start its find phase.
Find Phase. During its execution adversary A makes a number of key derivation and decapsulation
requests. If the adversary makes a key derivation query IBKeyDer(id) then (using its secret key α)
the simulator computes the secret key sk[id] and returns it to the adversary. If the adversary makes a
decapsulation query Dec(id, C ) the simulator (using α) decapsulates the ciphertext and returns the
session key to the adversary.
Eventually, the adversary returns a target identity id ∗ . The simulator chosen a random key K∗ 0
and run the encapsulation algorithm to create a key K∗ 1 together with the the challenge ciphertext
C ∗ = (c∗ 1 , c∗2 ). We make the convention that the challenge ciphertext C ∗ = (c∗ 1 , c∗2 ) is computed as
c ∗ 1 ← g c , t ∗ ← TCR(g c ), c ∗ 2 ← H(id ∗ ) c u ct∗
, (2)
depending on the random value c chosen by the simulator in advance, and the key K ∗ 1 = zc . Then the
simulator chooses a random bit γ and the challenge ciphertext C ∗ together with the key K ∗ = K ∗ γ is
returned to the adversary.
Guess Phase. The adversary continues to make its oracle queries, subsequent key derivation requests
must be different from the target identity id ∗ and decapsulation requests must be different from
(id ∗ , C ∗ ). Finally, adversary A returns a bit γ ′ ∈ {0, 1}. If γ �= γ ′ the simulator returns β ′ = 0, else
it returns β ′ = 1. This completes the description of the simulator. Note that the simulator behaves
exactly as in the original IBE security experiment.
Now a few important definitions are in place. During its execution A may query the key derivation
oracle for some identity id or the decapsulation oracle for the identity/ciphertext pair (id, C ). We
collect all those identities used to make queries to the key derivation and decapsulation oracle in the
set � ID. Note that � ID may contain the target identity id ∗ or one identity more than once. Let ID be
the subset of queried identities obtained by removing from � ID all multiples and the target identity. We
write ID = {id (1) , . . . , id (q0) } (without any particular order) for some q0 ≤ q such that id (i) �= id (j) for
each 1 ≤ i �= j ≤ q0 and id ∗ �∈ ID. Furthermore, we define ID ∗ = ID ∪ {id ∗ } = {id (1) , . . . , id (q0) , id ∗ }.
The proof of the theorem is obtained by considering subsequent games, Game 1, Game 2, ..., These
games will be quite similar to Game 0. In every game the simulators’ output bit β ′ will be well-defined.
For each i we define the event
Xi : The simulator outputs β ′ = 1 in Game i.
Then, since in Game 0 the simulator exactly plays the IBE security experiment with adversary A, we
have
| Pr[X0] − 1/2| = Adv ibkem-cca
IBKEM ,A .
Game 1. (Eliminate hash collisions) Note that the values c ∗ 1 = gc and t ∗ = TCR(g c ) from the
challenge ciphertext Equation (2) are completely independent of the view of adversary A until A’s
guess phase (since c is simply not touched by the simulator before generating the challenge ciphertext).
Therefore we may assume that the value c ∗ 1 and t∗ are already generated by the simulator before the
key generation.
18
In this game the simulator changes its answers to all decapsulation queries Dec(id, C ) made by A
as follows: Let C = (c1, c2) and t = TCR(c1). If t = t ∗ and c1 �= c∗ 1 , the simulator aborts. Otherwise
it continues as in the last game. Let HashAbort be the event that this new abortion rule applies.
Until HashAbort happens Game 0 and Game 1 are identical. Therefore by Lemma B.1 we have
Furthermore,
| Pr[X1] − Pr[X0]| ≤ Pr[HashAbort] .
Pr[HashAbort] ≤ Adv hash-tcr
TCR,H (k) ,
i.e. there exists an adversary H against the target collision resistence of TCR (note that c ∗ 1 = gc is a
random element coming from outside H’s view) running in time TimeH(k) = TimeA(k) + O(1) that
succeeds with probability at least Pr[HashAbort].
Game 2. (Change of the hash keys) This is the same as Game 1 except that the simulator changes
the generation of the hash keys h = (h0, h1, . . . , hn) as follows.
Set m = 2q (the choice of m will become clear later). Instead of generating the hash keys with the
hash key-generation algorithm HGen(G) as in the last game the simulator chooses
x0, x1, . . . , xn
y ′ 0, y1, . . . , yn
k
and sets
$
← {0, . . . , p − 1}
$
← {0, . . . , m − 1}
$
← {0, . . . , n} (3)
y0 ← p − km + y ′ 0 .
The public keys h = (h0, . . . , hn) of the hash function H are then defined as h0 = (ga ) y0 · (gb ) −t∗ · gx0 and hi = gxi �
(ga yi n
) , for 1 ≤ i ≤ n. The public hash function is H(id) = h0 i=1 hid i
i . From the
simulator’s point of view, the hash function evaluated in identity id ∈ {0, 1} n is
H(id) = g x(id)+y(id)a−t∗ b , (4)
with x(id) = x0 + �n i=1 id ixi and y(id) = y0 + �n i=1 id iyi only known to the simulator. On the other
hand note that this does not change the distribution of the hash keys h = (h0, h1, . . . , hn). Therefore
we have
Pr[X1] = Pr[X2] .
Game 3. (Abort at the end of the game) Fix all the random variables adversary A gets to see during
its execution, including its random coin tosses: fix mpk, the challenge bit γ, and the randomness used
in answering the key derivation and decapsulation queries. Now the adversary can be seen as a deterministic
algorithm, in particular the set of all queried (distinct) identities ID ∗ = {id (1) , . . . , id (q0) , id ∗ }
can be seen as fixed. By view A we denote all these fixed variables.
Define Y = (y ′ 0 , y1, . . . , yn, k), where the random variables (y ′ 0 , y1, . . . , yn, k) are distributed as
in Equation (3). It is clear that once view A is fixed, the random variable Y still has its original
distribution. Define the event
ForcedAbort :
q0�
i=1
�
y(id (i) �
) = 0 mod p ∨ y(id ∗ ) �= 0 mod p .
We call this abort forced since in sequel games the simulator is modified such that it always has to
abort once this event happens. For fixed view A we define
η := Pr
Y [¬ForcedAbort] (5)
19
and let λ be a lower bound on η (that holds for every view A). The following lemma provides a lower
bound on η.
Lemma B.2 For each possible choice of identities ID ∗ = {id (1) , . . . , id (q0) , id ∗ } we have η ≥ λ =
1
4(n+1)q .
The proof of the lemma is given in [26].
Compared to Game 2 we will make two modifications to the simulator in Game 3. The simulation
is exactly the same as in Game 2 until adversary A outputs his guess bit γ ′ . Since adversary A already
terminated we can assume view A to be fixed from now on.
First modification: add forced abort. After adversary A outputs his guess bit γ ′ , the simulator
checks if the event ForcedAbort occurs. If yes, it aborts the game and returns a random bit as its
output bit β ′ . If not the simulation is continued as before.
Let’s first make an unsuccessful attempt to relate the two events X3 and X2. Clearly we have
Pr [ X3 ] = Pr [ X2 ∧ ¬ForcedAbort ] + 1/2 · Pr [ ForcedAbort ]. Now we would like to continue
with Pr [ X2 ∧ ¬ForcedAbort ] ≥ Pr [ X2 ] · Pr [ ¬ForcedAbort ]. However, this is not correct since
the simulator may aborts with a probability that is a function in the choices of the identities ID ∗ =
{id (1) , . . . , id (q0) , id ∗ } queried by adversary A and hence the two events X2 and ¬ForcedAbort
cannot be considered as independent.
To get rid of this unwanted dependence the simulator adds some artificial abort such that it always
aborts with probability nearly λ (recall that λ was is upper bound on the abortion probability),
independent of the choices of the identities ID ∗ = {id (1) , . . . , id (q0) , id ∗ }. This way it will be possible
to decorrelate the event X2 with the abortion.
Second modification: add artificial abort. After the simulator has checked for the event
ForcedAbort (and decided not to abort), it continues as follows: First it samples (using sufficiently
many samples) an estimate η ′ of the probability η (over Y) that the ForcedAbort happens (cf.
Eqn. (5)). 6 We want to stress that view A is fixed at this point so sampling does not involve running
adversary A again. This estimate η ′ is a function in id (1) , . . . , id (q0) , id ∗ .
Depending on the estimate η ′ the simulator distinguishes two cases:
Case η ′ ≤ λ: the simulator continues as before.
Case η ′ > λ: With probability 1 − λ/η ′ the simulator aborts and outputs a random bit β ′ . With
probability λ/η ′ the simulator does not abort and continues as before.
This concludes the description of Game 3.
Lemma B.3 Let 0 < ρ ≤ 1 be a function in k. If the simulator takes O(ρ −2 ln(ρ −1 ) · λ −1 ln(λ −1 ))
samples when computing the estimate η ′ , then
�
�
�
�Pr[X2] − 1
2 − Pr[X3]
�
− 1/2�
�
λ
�
The parameter ρ will be determined at the end of the proof.
≤ ρ
2 .
Game 4. (Forced abort during the game I) Compared to the last game we make the following
changes to the simulator: When identity id ∈ ID is queried to the key derivation oracle, the simulator
immediately aborts if y(id) = 0 mod p. When receiving the challenge identity id ∗ , the simulator
immediately aborts if y(id ∗ ) �= 0 mod p. On abort the simulator returns a random bit β ′ . The
artificial abort at the end of the simulation is the same as in the last game.
6 Unfortunately, there seems not to be an efficient way to compute the exact value η. If there was one we could greatly
simplify our analysis.
20
Clearly, this modification does not affect the adversary if there is no forced abort. In case there is
a new forced abort the simulator outputs a random bit β ′ as in Game 3. Therefore we have
Pr [ X4 ] = Pr [ X3 ] .
Game 5. (Change key derivation oracle) The simulator changes its answers to all key derivation
queries IBKeyDer(id) made by the adversary A as follows: By Eqn. (4) we have H(id) =
g x(id)+y(id)a−t∗ b , for some values x(id) and y(id) known to the simulator.
Case y(id) = 0 mod p: The simulator aborts (as in the last game).
Case y(id) �= 0 mod p: The derived key sk[id] = (d1, d2, d3) is computed as follows:
For a random r ′ ∈ Zp, the simulator implicitly defines r = −b/y(id) + r ′ mod p and computes
d1 ← (g a ) y(id)r′
d2 ← (g b ) −1/y(id) · g r′
· (g b ) −x(id)/y(id)−r′ t ∗
d3 ← (g b2
) −1/y(id) · (g b ) r′
.
· (g b2
) t∗ /y(id) x(id)r
· g ′
Note that the randomness r is not known to the simulator and that the generation of the derived keys
sk[id] does not involve the knowledge of the secret key α = g ab anymore.
Lemma B.4 Pr[X4] = Pr[X5].
Proof: We have to verify that each derived key sk[id] = (d1, d2, d3) is identically distributed as in the
last game. Let us abbreviate x = x(id), and y = y(id) �= 0 mod p. Clearly, if r ′ is uniform in Zp then
so is r. Then
and
d1 = (g a ) yr′
d2 = (g b ) −1/y · g r′
= g −b/y g r−b/y
= g r ,
· (g b ) −x/y−r′ t ∗
= g ayr′ −bx/y−br ′ t ∗ +b 2 t ∗ /y+xr ′
· (g b2
) t∗ /y xr
· g ′
= g ay(r+b/y)−bx/y−bt∗ (r+b/y) ∗ +b 2 t/y+x(r+b/y)
= g ayr+ab−bx/y−bt∗ r−b 2 t ∗ /y+b 2 t ∗ /y+xr+xb/y
= g ayr+ab−bt∗ r+xr
= α · (g ay−bt∗ +x ) r
= α · (H(id)) r ,
d3 = (g b2
) −1/y · (g b ) r′
= u −b/y u r−b/y
= u r .
Game 6. (Forced abort during the game II) Compared to the last game we make the following changes
to the simulator: When the tuple (id, C ) is queried to the decapsulation oracle for id ∈ ID ∪ {id ∗ }
and C = (c1, c2) the simulator computes t = TCR(c1) and immediately aborts if y(id) = 0 mod p, C
is consistent, and t = t ∗ . In case of abort the simulator returns a random bit β ′ .
Lemma B.5 | Pr[X5] − Pr[X6]| ≤ 2q2
p , where q2 is an upper bound on the number of decapsulation
queries an adversary makes.
21
Proof: Clearly, this modification does not affect the adversary if there is no new forced abort. Note
that a new forced abort implies c1 = c ∗ 1 since otherwise by t = t∗ the simulator already aborted in the
last game and found a collision in the hash function TCR. If there is a new forced abort we distinguish
between two cases:
Case 1: the new forced abort happens in the guess stage. Recall that we call a ciphertext C = (c1, c2)
consistent if (g, c1, H(id) · u t , c2) is a Diffie-Hellman tuple (where t = TCR(c1)), i.e. if (g, c1, H(id) ·
u t , c2) = (g, g r , H(id) · u t , (H(id) · u t ) r ) for some value r ∈ Zp.
Note that the way the public-key is generated by Eqn. (4) and since y(id) = 0 and t = t ∗ , for any
consistent ciphertext C we have
c2 = (H(id) · u t ) r = g r(x(id)+b(t−t)∗ ) = (c b 1) t−t∗
· c x(id)
1
= c x(id)
1 . (6)
If id = id ∗ (i.e., if A queries the decapsulation oracle with the target identity) then Equation (6)
implies c2 = c x(id)
= (c∗ 1 )x(id ∗ ) = c∗ 2 . Consequently C = C ∗ and so the simulator rejects as in the
1
original IBE security experiment. If id �= id ∗ then, by definition, id ∈ ID and the simulator outputs
a random bit β ′ as in Game 5 where the abort was still done at the end of the experiment. Therefore,
conditioned on case 1 we have Pr[X5] = Pr[X6].
Case 2: the new forced abort happens in the find stage. Since in the find stage the adversary has
no information (in a statistical sense) about c ∗ 1 from the challenge ciphertext C ∗ , and the adversary
makes at most q2 decapsulation queries in its find stage, this implies
as claimed.
| Pr[X5] − Pr[X6]| ≤ 1 1
1
q2
+ + . . . +
≤
p p − 1 p − q2 + 1 p − q2
≤ 2q2
p ,
Game 7. (Change the answers to the decapsulation queries.) The simulator changes its answers to all
decapsulation queries Dec(id, C) made by A as follows: By Eqn. (4) we have H(id) = g x(id)+y(id)a−t∗ b
for some values x(id) and y(id) known to the simulator.
Case y(id) �= 0 mod p: the query is answered using the key derivation oracle.
Case y(id) = 0 mod p: the simulator simulates the decapsulation queries as follows: Let C =
(c1, c2, E) be the queried ciphertext and let t = TCR(c1).
If the ciphertext is not consistent then return a random session key K
If t = t ∗ then the simulator aborts (as in the last game)
If t �= t ∗ then return K ← ê(c2/c x(id)
1 , ga ) (t−t∗ ) −1
We claim that these changes do not affect the view of A:
Lemma B.6 Pr[X6] = Pr[X7].
Proof of Lemma B.6: Let C = (c1, c2) be an arbitrary ciphertext submitted to the decapsulation
oracle with respect to identity id. In case y(id) �= 0 mod p decapsulation will be done using the
simulation of the key derivation oracle which we already showed to be correct so we may now assume
y(id) = 0 mod p. Every inconsistent ciphertext leads to a random key K as in the original description
of the scheme so in what follows we may also assume a consistent ciphertext.
We distinguish the following three cases: Case 1a: t = t ∗ and c1 �= c∗ 1 . In this case the simulator has
found a collision in the hash function TCR and aborts as in the last game.
Case 1b: t = t ∗ and c1 = c∗ 1 . In the case the simulator aborts as in forced abort introduced in the last
game.
22
Case 2: t �= t ∗ . Similar to Eqn. (6) consistency of C implies
and we obtain
c2 = (H(id) · u t ) r = g r(x(id)+b(t−t)∗ ) = (c b 1) t−t∗
(c2/c x(id)
1 ) (t−t∗ ) −1
= ((c b 1) t−t∗
· c x(id)
1
/c x(id)
) (t−t∗ ) −1
1
· c x(id)
1
,
= c b 1 . (7)
In the original IBE decapsulation algorithm first the user secret key for identity id is computed as
sk[id] = (d1, d2, d3) = (α · H(id) s , g s , u s ) for random s, and then the session key K is reconstructed as
K = ê(c1, d1 · d t 3)/ê(c2, d2) = ê(c1, α · H(id) s · (u s ) t )/ê(c2, g s )
= ê(c b 1, g a ) · ê(c1, H(id) s · (u s ) t )/ê(c2, g s )
(7)
= ê((c2/c x(id)
) (t−t∗ ) −1
, g a ) · (ê(c1, H(id) · u t )/ê(c2, g)) s
1
= ê(c2/c x(id)
1 , g a ) (t−t∗ ) −1
· (∆(C)) s ,
with ∆(C) = ê(c1, H(id) · u t )/ê(c2, g). Since (∆(C)) s = 1 if ê(c1, H(id)u t ) = ê(g, c2) and (∆(C)) s is a
random element in GT otherwise, the decapsulated session key in the original scheme is distributed as
in the simulation.
Game 8. (Modify the challenge) After A’s find stage the simulator inputs the target identity id ∗
from A. The simulator modifies the computation of the challenge ciphertext C ∗ follows:
Case y(id ∗ ) �= 0 mod p: The simulator aborts (as in the last game).
Case y(id ∗ ) = 0 mod p: The simulator chooses a random bit γ and creates the challenge ciphertext
C ∗ = (c ∗ 1 , c∗ 2 ) and key K∗ 1 as
c ∗ 1 ← g c , c ∗ 2 ← c ∗ 2 ← (g c ) x(id ∗ ) , K ∗ 1 ← ê(g, g) abc . (8)
By virtue of Eqns. (4), (6), and since TCR(c∗ 1 ) = t∗ and y(id ∗ ) = 0 mod p, C ∗ is a correctly distributed
ciphertext of K∗ 1 . Clearly,
Pr[X9] = Pr[X8] .
Game 9. (Replace the Challenge) The simulator replaces the value K∗ 1 from the challenge C ∗ with
a random element from GT . Since K∗ 1 is now completely independent of the challenge bit γ, we have
Pr[X10] = 1/2 .
Observe that Game 10 does not use the secret key anymore and that the whole simulation only depends
on the values ga , gb , gb2, gc (i.e., the simulator “forgot the values a, b, and c). Game 8 and Game 9
are equal unless adversary A can distinguish ê(g, g) abc (the value of K∗ 1 in Game 8) from a random
in Game 9). Therefore we have
element in GT (the value of K ∗ 1
| Pr[X9] − Pr[X8]| ≤ Adv mbddh
G,B (k),
for any adversary B against the hardness of mBDDH running in the same time as the simulator, i.e.
TimeB = TimeA + O(ρ −2 ln(ρ −1 ) · λ −1 · ln(λ −1 ) + q).
23
Analysis. We collect the probabilities relating the different games as follows:
Using λ =
with
1
4(n+1)q
Adv ibkem-cca
IBKEM ,A = | Pr[X0] − 1
2 |
≤ | Pr[X1] + Adv hash-tcr
1
TCR,H (k) −
2 |
≤ | Pr[X2] − 1/2 + Adv hash-tcr
TCR,H (k)|
≤ | Pr [ X3 ] − 1
2
λ
≤ |Pr [ X6 ] + 2q2
p
λ
≤ |Pr [ X9 ] + 2q2
p
λ
+ ρ
+ Advhash-tcr
TCR,H
2 (k)|
− 1
2 |
− 1
2 |
≤ Advmbddh
G,B (k) + 2q2
p
λ
+ ρ
+ Advhash-tcr
TCR,H
2 (k)
+ ρ
+ Advhash-tcr
TCR,H
2 (k)
+ ρ
2
Advmbddh
G,B
(by Lemma B.2) and defining ρ = min{1, λ
+ Advhash-tcr
TCR,H (k) .
(k)
} ≤ 1 we conclude the proof
Adv ibkem-cca
IBKEM ,A (k) ≤ 6(n + 1)q · (Advmbddh
G,B (k) + 2q2/p) + Adv hash-tcr
TCR,H (k)
�
�
= O
,
nq · (Adv mbddh
G,B
(k) + q/p) + Adv hash-tcr
TCR,H (k)
where q is an upper bound on all (derivation plus decapsulation) queries made by A,
where ɛ = ɛ(k) = Adv mbddh
G,B (k), and
TimeB(k) = TimeA(k) + O(ρ −2 ln(ρ −1 ) · λ −1 · ln(λ −1 ) + q)
= TimeA(k) + O(ɛ −2 ln(ɛ −1 ) + q) ,
TimeH(k) = TimeA(k) + O(1) .
C Relations between the Assumptions
C.1 The BDDH assumption
Let PG be the description of bilinear groups and let g ∈ G be a random element from group G
of prime order p. Consider the following problem formalized by Boneh and Franklin [8]: Given
(g, g a , g b , g c , W ) ∈ G 4 ×G2 as input, output yes if W = ê(g, g) abc and no otherwise. The corresponding
BDDH assumption can be formalized the same way as the modified BDDH assumption.
C.2 The q-BDDHI assumptions
Let PG as above and let z ∈ G be a random element from group G. Let q = q(k) be a function
polynomial in the security parameter. Associated to q the following problem introduced by Boneh and
Boyen [5]: Given (h, h a , h (a2 ) , . . . , h (a q ) , W ) ∈ G q+1 × G2 as input, output yes if W = ê(h, h) 1/a and
no otherwise.
24
IBEkg(1k )
α $
← G∗ ; z ← ê(g, α)
H $
← HGen(m)
mpk ← (H, z) ; msk ← α
Return (mpk, msk)
IBEenc(mpk, id, M)
r $
← Z∗ p ; c1 ← gr ; c2 ← H(id) r
e ← M · zr C ← (c1, c2, e) ∈ G2 × GT
Return C
C.3 Proof of Lemma 3.1
IBEkeyder(msk, id)
s $
← Zp
sk[id] ← (α · H(id) s , gs )
Return sk[id]
IBKEMdec(sk[id], C )
Parse C as (c1, c2, e)
Parse sk[id] as (d1, d2)
Return M ← e · ê(c2, d2)/ê(c1, d1)
Figure 2: CPA-secure IBE from Waters.
Proof: The implications BDDH ≤ mBDDH and 1-BDDHI ≤ 2-BDDHI ≤ 3-BDDHI ≤ . . . are easy
to show. To prove “modified BDDH assumption ≤ 2-BDDHI assumption”, assume there exists a
polynomial-time adversary A that breaks the modified BDDH assumption. We show that then there
exists a polynomial-time adversary B with oracle access to A that breaks the 2-BDDHI assumption.
Let (h, ha , ha2, W ) be an input instance of the 2-BDDHI problem given to B. B’s goal is to find out
if W = ê(h, h) 1/a or W is random. B picks two random values y0, z0 and defines its output bit as
γ := γ ′ , where γ ′ is input from A as
γ ′ ← A(h a2
, h a , h, h y0 z0 ′ y0z0 , h , W = W ).
We now show correctness. Defining g := ha2 gx and h = g1/a2 = gx2. Consequently, (ha2, ha , h, hy0 z0 , h ) = (g, gx , gx2 then
, x = 1/a, y = y0/a2 , and z = z0/a2 , we have ha = g1/a =
, gy , gz ). If W = ê(h, h) 1/a ,
W ′ = W y0z0 = ê(h, h) 1/a·y0·z0 = ê(g, g) 1/a 5 ·y0z0 = ê(g, g) 1/a·y0/a 2 ·z0/a 2
If W is a random element, so is W ′ . This proves the lemma.
D Known IBE constructions
D.1 The IBE scheme from Waters [40]
= ê(g, g) xyz .
Waters IBE scheme with identity space IDSp = {0, 1} n and message space MsgSp = GT is depicted in
Figure 2.
D.2 The IBE scheme from Boneh/Franklin [8]
The Boneh/Franklin fullident IBE scheme with identity space IDSp = {0, 1} n and MsgSp = {0, 1} m
is depicted in Figure 3. It needs four random oracles H1 : {0, 1} n → G2, H2 : GT → {0, 1} 2k , H3 :
{0, 1} k × MsgSp → Z ∗ p, and H4 : {0, 1} k → {0, 1} m .
25
IBEkg(1 k )
α $
← G ∗
Pick random oracles H1, H2, H3, H4
mpk ← (H1, H2, H3, H4) ; msk ← α
Return (mpk, msk)
IBEenc(mpk, id, M)
σ $
← {0, 1} k ; r ← H3(σ, M)
c1 ← g r ; c2 ← σ⊕H2(ê(g, H1(id)) r )
e ← H4(σ)⊕M
C ← (c1, c2, e) ∈ G × {0, 1} 2k × {0, 1} m
Return C
IBEkeyder(msk, id)
sk[id] ← H1(id) α ∈ G2
Return sk[id]
IBEdec(sk[id], C )
Parse C as (c1, c2, e)
c2 ← c2⊕H2(ê(c1, sk[id]))
M ← e⊕H(σ)
r ← H3(σ, M) ; if g r �= c1 then reject
Else return M
Figure 3: CCA-secure fullident IBE scheme from Boneh/Franklin.
26
