<<

. 14
( 19)



>>

tends to for negligible when goes to infinity; however, because of the
underlying assumption for E0, is restricted to no larger than 26, i.e.
To conclude, we show that the modified distinguisher (Algorithm 1) needs data
complexity


Observe that Section 4 actually deals with the special case of Table 7
shows the best improvement achieved with We see that the minimum
drops from previous to




6 A Maximum Likelihood Decoding Algorithm
We restate the MLD problem for a general linear code (see [19] for details)
of length and dimension L with generator matrix G (let denote the
TEAM LinG
Faster Correlation Attack on Bluetooth Keystream Generator E0 417




column vector of G): find the closest codeword to the received vector
and decode the message such that i.e.
find such r that minimizes

6.1 The Time-Domain Analysis
Obviously, the trivial approach (yet common in most correlation attacks) to
find r is an exhaustive search in time-domain: for every message we compute
the distance and keep the smallest. The final record leads to r. The time
complexity is with memory

6.2 The Frequency-Domain Analysis
We introduce an integer-valued function,




for all where denotes the matrix transpose. We compute the
Walsh transform of as follows:




We thereby reach the theorem below.
Theorem 9.


for all where is defined by Eq.(8).
This generalizes the result [19, p. 414] of a special case when and
corresponds to the binary representation of So we just compute the table
of perform FWT [30], and find the maximal The time and memory
complexities of FWT are respectively. Since the precomputation
of takes time with memory we conclude that our improved MLD
algorithm runs in with memory (additionally, using linear
transformation allows to compute FWT over with memory where
Note that when the time complexity corresponds to
which is optimal in the sense that it stands on the same order of magnitude
TEAM LinG
418 Yi Lu and Serge Vaudenay

as the data complexity does. Table 8 compares the original exhaustive search
algorithm with the improved frequency transformation algorithm. Note that the
technique of FWT was used in another context [7] to speed up other kinds of
fast correlation attacks. In the next section we will see how it helps to speed up
the attack [10] by a factor of We estimate similar correlation attacks like [6]
can be speeded up by a factor of 10; undoubtedly, some other attacks can be
significantly improved by our algorithm as well.




6.3 A More Generalized MLD Algorithm
We further generalize the preceding problem by finding the L-bit vector r such
that given a sequence of vectors and together
with matrices of size L by the sequence of vectors
defined by minimizes Note that previous
subsections are merely a special case of and for
Define a real function by:




for all We compute the Walsh transform of as follows:




Algorithm 2 directly follows above computation. The total running time of our
algorithm is with memory To speed up the computation
of we could precompute the inner products of all pairs of vectors in
time with memory Thus, the total running time of the algorithm
is with memory
TEAM LinG
Faster Correlation Attack on Bluetooth Keystream Generator E0 419




In the special case that is applicable to E0 (as is done in the next section):
for we precompute another table to map any L-
bit vector to It takes time with memory The total time of the
algorithm is thus , with memory

7 The Key-Recovery Attack Against E0
We approach similarly as in [10] to transform our distinguisher of Subsection 4.3
into a key-recovery attack. Our main contribution, however, is to decrease the
time complexity by applying the preceding algorithm.
Let be the multiple polynomial of with
degree and weight Using techniques in Subsection 4.2 to find with
(precomputation) complexity PC, we list the corresponding triplets
for small in Table 9.




Let be a guess for the initial state of which generates the keystream
together with the other three fixed LFSRs. Denote the output bit of
with the initial state at time We define


TEAM LinG
420 Yi Lu and Serge Vaudenay

It can be shown that the second addend in Eq.(9) is also an generated
by the same LFSR. For brevity, we set




for (it corresponds to the data complexity We rewrite Eq. (9)
as


we count the occurrences5
Given sequence of of ones, i.e.
Using the analysis of [28], we estimate is the
smallest of all with



Note that this estimated figure is actually comparable to the conventional esti-
mation [6,16] on critical data complexity in correlation attacks, where




and is the binary entropy function6. According to [6] simulations showed the
probability of success is close to 1 for which is
consistent with our analysis. Table 10 shows our estimated minimal for
to achieve a top rank corresponding to Now define
where Clearly our current problem
to recover right fits into the MLD problem in Subsection 6.2. So we use
the preceding MLD algorithm to recover r first, then apply linear transform to
solve Finally we conduct the same analysis as in Section 5 to decrease data
complexity down to and we apply the technique introduced
in Subsection 6.3 to obtain the reduced time complexity
So, choosing we can halve the time and data complexities. The attack
complexities to recover for E0 are listed in Table 11. Once we recover we
target next based on multiple of Last, we use the technique of
guess and determine in [11] to solve and with knowledge of the shortest
two LFSRs. The detailed complexities of each step are shown in Table 12. A
comparison of our attacks with the similar attack7 [10] and the best two algebraic
attacks [1,8] is shown in Table 13.
5
is fixed in the attack, so we omit it in the notation
6
for
7
The estimate of data complexity in [10] uses a different heuristic formula than ours.
However we believe that their estimate and ours in Attack B are essentially the
same.

TEAM LinG
Faster Correlation Attack on Bluetooth Keystream Generator E0 421




8 Conclusions

This paper formulates a systematic computation method of correlations by a
recursive expression, which makes it easier to calculate correlations of the FSM
output sequences up to 26 bits for E0 (and allows us to prove for the first time
that the two known biases are the only largest). Then we successfully apply the
concept of convolution to the analysis of the distinguisher based on all corre-
lations, which allows us to build an efficient distinguisher that halves the data
complexity of the basic uni-bias-based distinguisher due to the linear dependency
of the two largest biases. Finally, by means of FWT, we propose a novel MLD
algorithm to recover the closest codeword for any linear code. Our proposed
algorithm can be easily adapted to speed up a class of fast correlation attacks.
Furthermore the algorithm is optimal when the length of the code and the
dimension L satisfy the relation which is the case when we apply it to
recover for E0. This results in the best known key-recovery attack against
E0. Considering a maximal keystream length of 2745 bits for practical E0 in
TEAM LinG
422 Yi Lu and Serge Vaudenay

Bluetooth, our results still remain the academic interest. Meanwhile, our attack
successfully illustrates the attack methodology of Baignères et al.8


Acknowledgment
Words fail the first author when she would like to express her heartfelt thanks to
her forever faithful bosom friend Aoife Hegarty, who, in the face of a rough time
in her own life, has been generously offering continuous one-way help through
all those years ...


References
1. F. Armknecht, M. Krause, Algebraic Attacks on Combiners with Memory, Advances
on Cryptography - CRYPTO 2003, Lecture Notes in Computer Science, vol.2729,
D. Boneh ed., Springer-Verlag, pp. 162-175, 2003
2. T. Baignères, A Generalization of Linear Cryptanalysis, Diploma Thesis, EPFL,
2003
3. Bluetooth„, Bluetooth Specification, version 1.2, pp. 903-948, November, 2003,
available athttp://www.bluetooth.org
4. A. Canteaut, F. Chabaud, A New Algorithm for Finding Minimum-weight Words
in a Linear Code: Application to Primitive Narrow-sense BCH Codes of Length
511, INRIA, technical report, No. 2685, 1995
5. A. Canteaut, M. Trabbia, Improved Fast Correlation Attacks Using Parity-check
Equations of Weight 4 and 5, Advances in Cryptology - EUROCRYPT 2000, Lec-
ture Notes in Computer Science, vol.1807, B. Preneel ed., Springer-Verlag, pp.
573-588, 2000
6. V. Chepyzhov, T. Johansson, B. Smeets, A Simple Algorithm for Fast Correla-
tion Attacks on Stream Ciphers, Fast Software Encryption 2000, Lecture Notes in
Computer Science, vol.1978, B. Schneier ed., Springer-Verlag, pp. 181-195, 2000
7. P. Chose, A. Joux, M. Mitton, Fast Correlation Attacks: An Algorithmic Point of
View, Advances in Cryptology - EUROCRYPT 2002, Lecture Notes in Computer
Science, vol.2332, L. R. Knudsen ed., Springer-Verlag, pp. 209-221, 2002
8. N. T. Courtois, Fast Algebraic Attacks on Stream Ciphers with Linear Feedback,
Advances on Cryptography - CRYPTO 2003, Lecture Notes in Computer Science,
vol.2729, D. Boneh ed., Springer-Verlag, pp. 176-194, 2003
9. P. Ekdahl, T. Johansson, Some Results on Correlations in the Bluetooth Stream
Cipher, Proceedings of the 10th Joint Conference on Communications and Coding,
Austria, 2000
10. P. Ekdahl, On LFSR Based Stream Ciphers (Analysis and Design), Ph.D. Thesis,
Lund Univ., Nov. 2003
11. S. Fluhrer, S. Lucks, Analysis of the E0 Encryption System, Selected Areas in
Cryptography- SAC 2001, Lecture Notes in Computer Science, vol. 2259, S. Vau-
denay and A. Youssef eds., Springer-Verlag, pp. 38-38, 2001
Correlation Properties of a General Binary Combiner with Memory,
12.
Journal of Cryptology, vol. 9, pp. 111-126, Nov. 1996
8
Personal communication. Prior work available in [2].

TEAM LinG
Faster Correlation Attack on Bluetooth Keystream Generator E0 423

13. V. Bagini, G. Morgari, Linear Cryptanalysis of Bluetooth Stream Ci-
pher, Advances in Cryptology - EUROCRYPT 2002, Lecture Notes in Computer
Science, vol. 2332, L. R. Knudsen ed., Springer-Verlag, pp. 238-255, 2002
M. Hermelin, K. Nyberg, Correlation Properties of the Bluetooth Combiner, Infor-
14.
mation Security and Cryptology- ICISC™99, Lecture Notes in Computer Science,
vol. 1787, JooSeok. Song ed., Springer-Verlag, pp. 17-29, 2000
15. M. Jakobsson, S. Wetzel, Security Weakness in Bluetooth, Topics in Cryptology
- CT-RSA 2001, Lecture Notes in Computer Science, vol. 2020, D. Naccache ed.,
Springer-Verlag, pp. 176-191, 2001
16. T. Johansson, F. Jonsson, Improved Fast Correlation Attacks on Stream Ciphers
via Convolutional Codes, Advances on Cryptography - CRYPTO™99, Lecture Notes
in Computer Science, vol.1666, M. Wiener ed., Springer-Verlag, pp. 181-197, 1999
17. M. Krause, BDD-Based Cryptanalysis of Keystream Generators, Advances in Cryp-
tology - EUROCRYPT 2002, Lecture Notes in Computer Science, vol. 2332, L. R.
Knudsen ed., Springer-Verlag, pp. 222-237, 2002
18. R. Lidl, H. Niederreiter, Introduction to Finite Fields and Their Applications, Cam-
bridge, 1986
F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-correcting Codes, North-
19.
Holland, 1996
M. Matsui, Linear Cryptanalysis Method for DES Cipher, Advances in Cryptology
20.
- EUROCRYPT™93, Lecture Notes in Computer Science, vol.765, Springer-Verlag,
pp. 386-397, 1993
21. W. Meier, O. Staffelbach, Fast Correlation Attacks on Certain Stream Ciphers,
Journal of Cryptology, vol. 1, pp. 159-176, Nov. 1989
W. Meier, O. Staffelbach, Correlation Properties of Combiners with Memory in
22.
Stream Ciphers, Journal of Cryptology, vol. 5, pp. 67-86, Nov. 1992
23. A. J. Menezes, P. C. van. Oorschot, S. A. Vanstone, Handbook of Applied Cryptog-
raphy, CRC, 1996
W. Penzhorn, Correlation Attacks on Stream Ciphers: Computing Low Weight Par-
24.
ity Checks based on Error Correcting Codes, Fast Software Encryption 96, Lecture
Notes in Computer Science, vol.1039, D. Gollmann ed., Springer-Verlag, pp. 159-
172, 1996
25. R. A. Rueppel, Correlation Immunity and the Summation Generator, Advances in
Cryptology - CRYPTO™85, Lecture Notes in Computer Science, Springer-Verlag,
pp. 260-272, 1986
26. M. Saarinen, Re: Bluetooth and E0, Posted at sci.crypt.research, 02/09/00
27. T. Siegenthaler, Correlation-Immunity of Nonlinear Combining Functions for
Cryptographic Applications, IEEE Transactions on Information Theory, vol. 30,
pp. 776-780, 1984
S. Vaudenay, An Experiment on DES - Statistical Cryptanalysis, Proceedings of
28.
the 3rd ACM Conferences on Computer Security, pp. 139-147, 1996
29. D. Wagner, A Generalized Birthday Problem, Advances in Cryptology - CRYPTO
2002, Lecture Notes in Computer Science, vol.2442, Springer-Verlag, pp. 288-304,
2002
30. R. K. Yarlagadda, J. E. Hershey, Hadamard Matrix Analysis and Synthesis with
Applications to Communications and Signal/Image Processing, Kluwer Academic,
pp. 17-22, 1997

TEAM LinG
424 Yi Lu and Serge Vaudenay

Appendix
A. Proof of Lemma 5
Let be a random variable independent of X with uniform distribu-
tion. We have




which is

B. Examples of Multiple Polynomials
Example of with Low Degree. Here is a multiple polynomial of degree
less than 855 with weight 31:



Observe that is not optimal as from Table 3.

Examples of with Weight Four. Recall that is the
order of for By definition, On the other hand,
for hence we deduce the
following three multiple polynomials of with weight 4 with ease:




where




The degrees of are approximately respectively.
Note that we may also expect optimal multiples with degree in the same order
of magnitude and weight 3.
TEAM LinG
Faster Correlation Attack on Bluetooth Keystream Generator E0 425

C. Table of for




TEAM LinG
A New Paradigm of Hybrid Encryption Scheme

Kaoru Kurosawa1 and Yvo Desmedt2,3
1
Ibaraki University, Japan
kurosawa@cis.ibaraki.ac.jp
2
Dept. of Computer Science, University College London, UK
3
Florida State University, USA



Abstract. In this paper, we show that a key encapsulation mechanism
(KEM) does not have to be IND-CCA secure in the construction of hy-
brid encryption schemes, as was previously believed. That is, we present a
more efficient hybrid encryption scheme than Shoup [12] by using a KEM
which is not necessarily IND-CCA secure. Nevertheless, our scheme is
secure in the sense of IND-CCA under the DDH assumption in the stan-
dard model. This result is further generalized to projective
hash families.
Keywords: hybrid encryption, KEM, standard model


1 Introduction
1.1 Background
Cramer and Shoup showed the first provably secure practical public-key encryp-
tion scheme in the standard model [3,6]. It is secure against adaptive chosen
ciphertext attack (IND-CCA) under the Decisional Diffie-Hellman (DDH) as-
sumption. They further generalized their scheme to projective hash families [4].
(In the random oracle model [1], many practical schemes have been proven to
be IND-CCA, for example, OAEP+ [13], SAEP [2] , RSA-OAEP [8], etc. [7].
However, while the random oracle model is a useful tool, it does not rule out all
possible attacks.)
On the other hand, a hybrid encryption scheme uses public-key encryption
techniques to derive a shared key that is then used to encrypt the actual messages
using symmetric-key techniques.
For hybrid encryption schemes, Shoup formalized the notion of a key en-
capsulation mechanism (KEM), and an appropriate notion of security against
adaptive chosen ciphertext attack [12,6]. A KEM works just like a public key
encryption scheme, except that the encryption algorithm takes no input other
than the recipient™s public key. The encryption algorithm can only be used to
generate and encrypt a key for a symmetric-key encryption scheme. (One can
always use a public-key encryption scheme for this purpose. However, one can
construct a KEM in other ways as well.) A secure KEM, combined with an ap-
propriately secure symmetric-key encryption scheme, yields a hybrid encryption
scheme which is secure in the sense of IND-CCA [12].

M. Franklin (Ed.): CRYPTO 2004, LNCS 3152, pp. 426“442, 2004.
© International Association for Cryptologic Research 2004
TEAM LinG
A New Paradigm of Hybrid Encryption Scheme 427

Shoup presented a secure KEM under the DDH assumption [12]. As a result,
his hybrid encryption scheme is secure in the sense of IND-CCA under the DDH
assumption in the standard model [12].

1.2 Our Contribution
In order to prove the security of hybrid encryption schemes, one has believed
that it is essential for KEM to be secure in the sense of IND-CCA, as stated in
[6, Remark 7.2, page 207].
In this paper, however, we disprove this belief. That is, it is shown that
KEM does not have to be CCA secure, as was previously believed. On a more
concrete level, we present a more efficient hybrid encryption scheme than Shoup
[12] by using a KEM which is not necessarily secure in the sense of IND-CCA.
Nevertheless, we prove that the proposed scheme is secure in the sense of IND-
CCA under the DDH assumption in the standard model.
In a typical implementation, the underlying Abelian group may be a subgroup
of where is a large prime. In this case, the size of our ciphertexts is bits
shorter than that of Shoup [12]. The number of exponentiations per encryption
and that of per decryption are also smaller. (Further, our scheme is more efficient
than the basic Cramer-Shoup scheme [3,6].)
This shows that one can start with a weak KEM and repair it with a hy-
brid construction. Eventually, more efficient hybrid encryption schemes could be
obtained.
Our KEM is essentially a projective hash family [4]. We present a
generalization of our scheme to projective hash families also.
The only (conceptual) cost one pays is that one needs to assume a simple
condition on the symmetric encryption scheme. Namely, any fixed ciphertext is
rejected with overwhelming probability, where the probability is taken over keys
K. This property is already satisfied by the symmetric encryption scheme SKE
which is used in the hybrid construction of Shoup [12]. Hence the SKE can be
used in our hybrid construction too.
Our result gives new light to Cramer-Shoup encryption schemes [3,4,6] and
opens a door to design more efficient hybrid encryption schemes.

2 Preliminaries
We denote by a security parameter. PPT denotes probabilistic polynomial
time.

2.1 Notation and Definitions
denotes the cardinality of S if S is a set. denotes the bit length of
,·, · · ·) is a probabilistic algorithm, then
if is a string or a number. If A(·
denotes the experiment of running A on input and
letting be the outcome. If S is a set, denotes the experiment of choosing
at random.
TEAM LinG
428 Kaoru Kurosawa and Yvo Desmedt

2.2 Public-Key Encryption Scheme (PKE)
A public-key encryption scheme is a three tuple of algorithms
The key generation algorithm generates a pair where pk
is a public key and sk is a secret key. The encryption algorithm takes a public
key pk and a plaintext and returns a ciphertext The decryp-
tion algorithm takes a secret key sk and a ciphertext and returns or
reject.
The chosen plaintext attack (IND-CPA) game is defined as follows. We imag-
ine a PPT adversary A that runs in two stages. In the “find” stage, A takes a
public key pk and queries a pair of equal length messages and to an
encryption oracle. The encryption oracle chooses and computes a
challenge ciphertext of randomly. In the “guess” stage, given A out-
puts a bit and halts.
The adaptive chosen ciphertext attack (IND-CCA) game is defined similarly.
The difference is that the adversary A is given access to a decryption oracle,
where A cannot query the challenge ciphertext itself in the guess stage.
Definition 1. We say that PKE is secure in the sense of IND-CCA if
is negligible in the IND-CCA game for any PPT adversary A.
In particular, we define the IND-CCA advantage of A as follows:


For any and define where the maxi-
mum is taken over all A which runs in time and makes at most queries to
the decryption oracle.

2.3 Diffie-Hellman Assumptions
Let G be an Abelian group of order Q, where Q is a large prime. Let be a
generator of G. Let



The decisional Diffie-Hellman (DDH) assumption claims that DH and Random
are indistinguishable.
For a distinguisher D, consider the following two experiments. In experiment
0, let In experiment 1, let
Define

where


For any define where the maximum is taken
over all D which runs in time
TEAM LinG
A New Paradigm of Hybrid Encryption Scheme 429

2.4 Target Collision Resistant Hash Function
The notion of target collision resistant TCR family of hash functions was shown
by Cramer and Shoup [6]. It is a special case of universal one-way hash function
UOWH family introduced by Naor and Yung [10], where a UOWH family can be
built from arbitrary one-way functions [10,11].
In a TCR family, given a randomly chosen tuple of group elements for
some and a randomly chosen hash function H, it is infeasible for an adversary
(In a UOWH family, is chosen by the
A to find such that
adversary.) In practice, one can use a dedicated cryptographic hash function,
like SHA-1. Define


For any define where the maximum is taken
over all A which runs in time

3 Previous Results on KEM
It is known that by combining a KEM and a one-time symmetric encryption
scheme which are both secure in the sense of IND-CCA, we can obtain a hybrid
encryption scheme which is secure in the sense of IND-CCA.

3.1 KEM [12] [6, Sec.7.1]
A key encapsulation mechanism KEM consists of the following algorithms.
A key generation algorithm KEM.Gen that on input outputs a pub-
lic/secret key pair (pk,sk).
An encryption algorithm KEM.Enc that on input and a public key pk,
outputs a pair where K is a key and is a ciphertext.
A key K is a bit string of length where is another
parameter of KEM.
A decryption algorithm KEM.Dec that on input a secret key sk, a string
(in particular a ciphertext) outputs either a key K or the special symbol
reject.
KEM.Gen and KEM.Enc are PPT algorithms and KEM.Dec is a deterministic
polynomial time algorithm.
In the chosen ciphertext attack (IND-CCA) game, we imagine a PPT adver-
sary A that runs in two stages. In the find stage, A takes a public key pk and
queries an encryption oracle. The encryption oracle computes:




where and responds with the pair In the guess stage,
given the adversary A outputs a bit and halts.
TEAM LinG
430 Kaoru Kurosawa and Yvo Desmedt

The adversary A is also given access to a decryption oracle. For each decryp-
tion oracle query, the adversary A submits a ciphertext and the decryption
oracle responds with where A cannot query the challenge
ciphertext itself in the guess stage.

Definition 2. We say that KEM is secure in the sense of IND-CCA if
is negligible in the above game for any PPT adversary A.

3.2 One-Time Symmetric-Key Encryption [6, Sec.7.2]
A one-time symmetric-key encryption scheme SKE consists of two algorithms:
A deterministic polynomial time encryption algorithm SKE.Enc that takes
as input a key K and a message and outputs a ciphertext
A deterministic polynomial time decryption algorithm SKE.Dec that takes
as input a key K and a ciphertext and outputs a message or the
special symbol reject.
The key K is a bit string of length where is a parameter
of the encryption scheme.
In the passive attack game, we imagine a PPT adversary A that runs in two
stages. In the “find” stage, A takes and queries a pair of equal length messages
and to an encryption oracle. The encryption oracle generates a random
key K of length along with random and encrypts
using the key K. In the “guess” stage, given the resulting ciphertext A
outputs a bit and halts.
In the chosen ciphertext attack (IND-CCA) model, the adversary A is also
given access to a decryption oracle in the guess stage. In each decryption oracle
query, A submits a ciphertext and obtains the decryption of under
the key K.
Definition 3. We say that SKE is secure in the sense of IND-CCA if
is negligible in the IND-CCA game for any PPT adversary A.
In particular, we define the IND-CCA advantage of A as follows.



For any and define where the maximum
is taken over all A which runs in time and makes at most queries to the
decryption oracle.

Construction of SKE
3.3
Shoup showed a construction of a one-time symmetric-key encryption scheme
as follows [12, page 281]. Let PRBG be a pseudo-random bit generator which
stretches strings to strings of arbitrary (polynomial) length. We assume
TEAM LinG
A New Paradigm of Hybrid Encryption Scheme 431

that is a negligible quantity. In a practical implementation, it is perfectly
reasonable to stretch the key by using it as the key to a dedicated block
cipher, and then evaluate the block cipher at successive points (so called “counter
mode”) to obtain a sequence of pseudo-random bits [6, Sec.7.2.2].
Let AXUH be a hash function which is suitable for message authentication,
i.e., an almost XOR-universal hash function [9]. We assume that AXUH is keyed
by an string and hashes arbitrary bit string to strings. Many efficient
constructions for AXUH exist that do not require any intractability assumptions.
we apply PRBG
To encrypt a message by using a key
to to obtain an string Then we compute




The ciphertext is where is called a tag. (We can generate K by
applying PRBG to a shorter key.)
To decrypt using a key we first test if eq.(4)
holds. If it does not hold, then we reject. Otherwise, we output

3.4 A Hybrid Construction
Let KEM be a key encapsulation mechanism and let SKE be a one-time symmetric
for all Let HPKE
key encryption scheme such that
be the hybrid public-key encryption scheme obtained from KEM and SKE.

Proposition 1. [6, Theorem 7.2] If KEM and SKE are secure in the sense of
IND-CCA, then so is HPKE.


4 Proposed Hybrid Encryption Scheme
In this section, we show a more efficient hybrid encryption scheme than before
[12,6] by using a KEM which is not necessarily secure in the sense of IND-
CCA. Nevertheless, we prove that the proposed scheme is secure in the sense of
IND-CCA under the DDH assumption in the standard model.

4.1 Overview
A KEM works just like a public key encryption scheme, except that the encryp-
tion algorithm takes no input other than the recipient™s public key. Instead, the
where K is a key of SKE and
encryption algorithm generates a pair
is an encryption of K. The decryption algorithm applied to yields K. In our
hybrid encryption scheme,
The notion of IND-CCA is adapted to KEM as follows. The adversary does
not give two messages to the encryption oracle. Rather, the encryption oracle
runs the KEM encryption algorithm to obtain a pair The encryption
TEAM LinG
432 Kaoru Kurosawa and Yvo Desmedt

oracle then gives the adversary either or where is an inde-
pendent random bit string; the choice of K versus depends on the value of
the random bit chosen by the encryption oracle.
Up to now, in order to prove the security of the hybrid encryption scheme, it
has been believed to be essential for KEM to be secure in the sense of IND-CCA,
as stated in [6, Remark 7.2, page 207].
However, we know of no way to prove that our KEM is secure in the sense of
IND-CCA. Nevertheless, we prove that the proposed hybrid encryption scheme
is secure in the sense of IND-CCA. This shows that one can start with a weak
KEM and repair it with a hybrid construction. Eventually, more efficient hybrid
encryption schemes could be obtained.
A generalization of our scheme to projective hash families [4] will
be given in Sec.8.

4.2 Secure
We require that a one-time symmetric-key encryption scheme SKE satisfies the
following property: any bit string is rejected by the decryption algorithm with
overwhelming probability. Formally, we say that SKE is secure if for
any bit string



where the probability is taken over K.
This property is already satisfied by the one-time symmetric-key encryption
scheme shown in Sec.3.3. Indeed, for any fixed eq.(4) holds with
probability because is random. Therefore, this encryption scheme is
secure for

4.3 Proposed Scheme
The proposed hybrid encryption scheme is based on the basic Cramer-Shoup
scheme [3,6]. However, it does not use as the validity check as in [3,6], but
rather it is used to derive the encapsulated key K. This saves the value which
was previously used to encapsulate the key, and one exponentiation encryp-
tion/decryption. It also makes the public key and the secret key one element
shorter.
Let G be an Abelian group of order Q, where Q is a large prime. Let SKE
be a one-time symmetric-key encryption scheme.
Let be a hash function, where We assume
that is uniformly distributed over if is uniformly distributed over
G. This is a very weak requirement on H, and we can use SHA-1, for example.
Key Generation. Generate two distinct generators of G at random.
Choose at random. Compute


TEAM LinG
A New Paradigm of Hybrid Encryption Scheme 433

Finally, a random indexing a target collision resistant hash function TCR (see
Sec.2.4) is chosen. The public-key is and the secret key is

Encryption. To encrypt a message choose at random and compute




(In the ciphertext, the KEM part is
The ciphertext is
Decryption. For a ciphertext compute


Then decrypt under K using SKE.Dec, and output the resulting decryption
may be reject.)

4.4 Security
Theorem 1. The proposed hybrid encryption scheme Hybrid is secure in the
sense of IND-CCA under the DDH assumption if SKE is secure in the sense of
IND-CCA and it is secure for negligible In particular,



where are essentially the same as
A proof will be given in the next section.

4.5 Efficiency Comparison
In the hybrid encryption scheme of Shoup [12] and in the Cramer-Shoup scheme
[3],
is included in the ciphertext C to check the validity of C.
is included in a public-key to generate a key K of SKE.
In our scheme, on the other hand,
is not included in the ciphertext, but it is used to derive a key K of SKE.
is not necessary at all.
In a typical implementation, the underlying Abelian group G may be a sub-
group of where is a large prime. Table 1 shows an efficiency comparison
among the proposed hybrid encryption scheme, the hybrid encryption scheme of
Shoup [12] and the basic Cramer-Shoup scheme [3]. (In the table, denotes the
tag of SKE as shown in Sec.3.3.)
We can see that
TEAM LinG
434 Kaoru Kurosawa and Yvo Desmedt

We can see that
the size of our ciphertext is bits shorter than that of Shoup [12].
the size of our public-key is bits shorter than that of Shoup [12].
The number of exponentiations per encryption and that of per decryption
of our scheme are also smaller.
Further, our scheme is more efficient than the Cramer-Shoup scheme [3] for
Moreover, in Cramer-Shoup [3] must belong to G (so
while in ours and Shoup™s [12] (polynomial length).




5 Proof of Theorem 1
5.1 Outline
The following lemma is simple but useful.
Lemma 1. [6, Lemma 6.2] Let and F be events defined on some proba-
bility space. Suppose that the event occurs if and only if occurs.
Then

Let A be an adversary who breaks the proposed scheme in the sense of
IND-CCA. The attack game is as described in Sec.2.2. Suppose that the public
key is and the secret key is The target ciphertext
is denoted by We also denote by the values
corresponding with K related to
Suppose that A queries at most times to the decryption oracle in the find
stage, and at most times to the decryption oracle in the guess stage, where
We say that a ciphertext is valid if and
for some Otherwise, we say that C is invalid.
Let log(·) denote and let Then



Let be the original attack game, let denote the output of A,
and let be the event that in Therefore,




TEAM LinG
A New Paradigm of Hybrid Encryption Scheme 435

We shall define a sequence of modified attack games. For any
we let be the event that in game
In game we modify the encryption oracle as follows: is
replaced by

This change is purely conceptual, and
In game we modify the encryption oracle again, so that is re-
placed by a random pair with Under the DDH assumption,
A will hardly notice, and is negligible. More precisely, we have
Lemma 2. There exists a PPT algorithm whose running time is essentially
the same as that of A, such that


The proof is the same as that of [6, Lemma 6.3].
In game we modify the decryption oracle, so that it applies the following
special rejection rule: In the guess stage, if the adversary submits a ciphertext
but then the decryption oracle immediately outputs
reject and halts. Let be the event that the decryption oracle in game
rejects a ciphertext using the special rejection rule. It is clear that games
and proceed identically until the event occurs. In particular, the event
and are identical. So by Lemma 1, we have


Lemma 3. There exists a PPT algorithm whose running time is essentially
the same as that of A, such that


The proof is the same as that of [6, Lemma 6.5].
In game we modify the decryption oracle, so that it rejects all invalid
ciphertexts C in the find stage. Let be the event that a ciphertext is rejected
in that would not have been rejected under the rules of game It is
clear that games and proceed identically until the event occurs. In
particular, the event and are identical. So by Lemma 1, we
have

Lemma 4. (For the proof, see Section 5.2.)
In game we modify the encryption oracle as follows.
is randomly chosen in such a way that an event does not occur, where is
the event that for some invalid ciphertext which A
queries in the find stage. It is clear that the event and are
identical. So by Lemma 1, we have


TEAM LinG
436 Kaoru Kurosawa and Yvo Desmedt

Lemma 5. (For the proof, see Section 5.3.)
In game we modify the decryption oracle, so that it rejects all invalid
ciphertexts C in the guess stage. Let be the event that a ciphertext is rejected
in that would not have been rejected under the rules of game It is
clear that games and proceed identically until the event occurs. In
particular, the event and are identical. So by Lemma 1, we
have

Lemma 6. (For the proof, see Section 5.4.)
In game we modify the encryption oracle and the decryption oracle, so
that is replaced by a random key
Lemma 7. (For the proof, see Section 5.5.)
Lemma 8. There exists a PPT algorithm whose running time is essentially
the same as that of A, such that


For the proof, see Section 5.6.
From the above results, we immediately obtain that




5.2 Proof of Lemma 4
From the A™s view, is a random point satisfying eq.(5) and eq.(6).
Suppose that A queries an invalid ciphertext to the decryption oracle,
where and with Let
where Then


It is clear that eq.(5),(6) and (7) are linearly independent. This means that
can take any value. In other words, is uniformly distributed over G. Hence
Now since SKE is
is uniformly distributed over
secure, the decryption oracle accepts with probability at most Con-
sequently, we obtain this lemma.

5.3 Proof of Lemma 5
For any fixed



because is randomly chosen in such a way that

TEAM LinG
A New Paradigm of Hybrid Encryption Scheme 437

5.4 Proof of Lemma 6
As the worst case, we assume that A knows Then from the A™s view,
is a random point satisfying eq.(5), (6) and


In the guess stage, suppose that A queries an invalid ciphertext
to the decryption oracle, where and with Let
where Then


Now




Therefore, eq.(5), (6), (8) and (9) are linearly independent. This means that
is uniformly distributed over G. Hence is uniformly distributed
Now since SKE is
over secure, the decryption oracle accepts
with probability at most
Consequently, we obtain this lemma.

5.5 Proof of Lemma 7
In game from the A™s view, is a random point satisfying eq.(5)
and eq.(6). Further, it is clear that eq.(5),(6) and (8) are linearly independent.
This means that can take any value. In other words, is uniformly distributed
over G. Hence is uniformly distributed over Consequently,
we obtain this lemma.

5.6 Proof of Lemma 8
We describe Algorithm Algorithm provides an environment for A as
runs the key generation algorithm of Hybrid to generate a
follows. First,
public-key and the secret-key In partic-
ular, chooses randomly and computes It then gives pk to
A.
In the find stage, whenever A submits a ciphertext C to the decryption oracle,
applies the decryption rule of game using the secret-key sk and
When A submits to the encryption oracle, submits to
her encryption oracle.
The encryption oracle of chooses a random key along with
a random bit and encrypts using the key It then returns the resulting
ciphertext to
TEAM LinG
438 Kaoru Kurosawa and Yvo Desmedt

generates according to the encryption rule of game It then
returns the target ciphertext to A.
In the guess stage, suppose that A submits a ciphertext to
the decryption oracle. If then applies the decryption rule
of game using the secret-key sk and Otherwise, queries to her
decryption oracle, where the decryption oracle decrypts by using then
returns the answer to A.
When A outputs outputs and halts. That completes the description
of
It is clear that perfectly simulates the environment of A. Therefore,



On the other hand,



Consequently, we obtain this lemma.


6 Discussion
We have argued that a KEM does not have to be CCA-secure in the construction
of hybrid encryption schemes, as was previously believed.
In the IND-CCA definition of hybrid encryption schemes, the decryption
oracle returns the message for a queried ciphertext where
is the KEM part and is the symmetric encryption ciphertext. On the other
hand, in the IND-CCA definition of KEM, the decryption oracle returns the
symmetric key K for a queried Hence, the IND-CCA definition of KEM is
too demanding because the decryption oracle reveals much more information
than the decryption oracle of the hybrid encryption scheme does.
Then one may consider to define a weaker condition on KEM such that
when coupled with CCA-secure symmetric encryption (with the extra condition
of Section 3.4), it would yield a CCA-secure hybrid encryption scheme. However,
it seems to be impossible because the security of KEM and that of the symmetric
encryption scheme are intertwined (as in our scheme).


7 Hash Proof System
Cramer and Shoup introduced a notion of Hash Proof System (HPS) [4,5] in or-
der to generalize their encryption scheme based on the DDH assumption [3]. By
using HPS, they showed new CCA-secure encryption schemes under Quadratic
Residuosity assumption and Paillier™s Decision Composite Residuosity assump-
tion, respectively.
In this section, we give the definition of a slight variant of HPS, where
is replaced by strongly

TEAM LinG
A New Paradigm of Hybrid Encryption Scheme 439

7.1 Subset Membership Problem [4, 5]
A subset membership problem Mem specifies a collection such
that for every is a probability distribution over problem instances
Each specifies the following:
Define, non-empty sets, X, L and W such that
A binary relation such that iff for some witness

We require that the following PPT algorithms exist.
1. Instance sampling: samples an instance according to on
2. Subset sampling: outputs a random together with a witness
for on input and
3. Element sampling: outputs a random
We say that Mem is hard if and are indistinguishable for a
random and a random

7.2 Projective Hash Family
Let X and be finite, non-empty sets. Let be a set of
functions indexed by I. We call (F, I, X, a universal hash family [4,5].
Let Let S be a finite, non-empty set, and let be a function.
Set
Definition 4. [4, 5] is called a projective hash
on L is determined3 by
family if for all the action of
In other words, the value is determined by if We next define
the notion of strongly projective hash, a variant of Cramer-Shoup™s
projective hash.
Definition 5. Let be a projective hash family.
Consider the probability space defined by choosing at random. We say
that Project is strongly if
for all and


and for all with and


Project is strongly means that for any the value of is
uniformly distributed over conditioned on a fixed value of and it is also
uniformly distributed over conditioned on fixed values of and for
with
3
For a further clarification, see Section 7.3.

TEAM LinG
440 Kaoru Kurosawa and Yvo Desmedt

7.3 Hash Proof System [4,5]
Let Mem be a subset membership problem. A hash proof system (HPS) P for
Mem associates with each instance of Mem a projective hash family

P provides several algorithms to carry out basic operations: and com-
puting given The private evaluation algorithm for P computes
given and The public evaluation algorithm for P com-
putes given and where is a witness for



8 Proposed Hybrid Construction Based on HPS
In this section, we generalize our hybrid encryption scheme of Sec.4.3 by using
the variant of HPS shown above. Then efficient hybrid encryption schemes are
obtained which are secure in the sense of IND-CCA under Quadratic Resid-
uosity assumption and Paillier™s Decision Composite Residuosity assumption,
respectively, in the standard model.

8.1 Hybrid Construction
Let Mem be a subset membership problem and P be a hash proof system for
Mem. Let SKE be a one-time symmetric-key encryption scheme.
Key Generation. Generate an instance using the instance sampling
algorithm of Mem. Suppose that P associates with a projective
hash family Choose at random and compute

The public key is and the secret key is Let be a hash
function, where We assume that is uniformly distributed
over if is uniformly distributed over This is a very weak requirement
on H, and we can use SHA-1, for example.
Encryption. To encrypt a message generate at random together with
for using the subset sampling algorithm of Mem. Compute
a witness
using the public evaluation algorithm for P on inputs and
Compute and The ciphertext is
Decryption. To decrypt a ciphertext compute using the private
evaluation algorithm for P on inputs and Then decrypt under K using
SKE.Dec, and outputs the resulting decryption may be reject.)

8.2 Security
Theorem 2. In the above construction, suppose that Mem is hard, and the asso-
ciated projective hash family is strongly
of Mem. Moreover, suppose that the one-time
for each instance

TEAM LinG
A New Paradigm of Hybrid Encryption Scheme 441

symmetric-key encryption scheme SKE is secure in the sense of IND-CCA and it
is secure for negligible Then the proposed hybrid encryption scheme
is secure in the sense of IND-CCA.

A proof is a generalization of that of Theorem 1. Roughly speaking, in the
proof, if the challenge ciphertext is based upon application of the projective
universal hash function to an element then the attack works as in the
real case.
If then the following happens: At the beginning of the CCA attack,
(which is used as the symmetric key by is totally
uniform and secret from the point of view of the adversary. This is due to the
property of the projective hash family Project. This informa-
strongly
tion theoretic property of the symmetric key K* remains as the attack progresses
due to the fact that invalid queries are not decrypted due to the prop-
erty of the SKE, where a ciphertext is invalid if


8.3 Examples

From [4,5]. Let G be an Abelian group of order Q, where Q is a large prime.
Let where are two distinct
generators of G. Then it is clear that the related membership problem Mem is
hard if and only if the DDH assumption holds.
Let be an injective function for some Let and
Define



where for For let
and define



(1) is a projective hash family because if
then



(2) Consider the probability space defined by choosing
at random. For the example of [4,5] we now have:

For any is uniformly distributed
over G conditioned on fixed values of
For any with we easily see that:
is uniformly distributed over G conditioned on fixed
values of and
TEAM LinG
Kaoru Kurosawa and Yvo Desmedt
442

Hence Project is strongly
Now from Sec.8.1, a concrete hybrid encryption scheme is obtained such that
the ciphertext is where and is given by
eq.(10). From Theorem 2, it is secure in the sense of IND-CCA if SKE satisfies
the condition of the theorem. (This scheme is a TCR-free variant of Sec.4.3.)
Similarly, we can obtain efficient hybrid encryption schemes which are secure
in the sense of IND-CCA under Quadratic Residuosity assumption and Paillier™s
Decision Composite Residuosity assumption, respectively.

Acknowledgment
We would like to thank Ronald Cramer and the anonymous reviewers for their
helpful comments. The second author was supported by JPSP fellowship for
research in Japan.

References
1. M. Bellare and P. Rogaway: Random Oracles are Practical: A Paradigm for De-
signing Efficient Protocols. ACM Conference on Computer and Communications
Security 1993: 62-73
2. D.Boneh, Simplified OAEP for the RSA and Rabin Functions. CRYPTO 2001,
pp.275-291 (2001)
3. R. Cramer and V. Shoup, “A practical public key cryptosystem provably
secure against adaptive chosen ciphertext attack,” Advances in Cryptology -
CRYPTO™98, Lecture Notes in Computer Science Vol. 1462, H. Krawczyk ed.,
Springer-Verlag, 1998.
4. R. Cramer and V. Shoup, “Universal hash proofs and a paradigm for chosen
ciphertext secure public key encryption, against adaptive chosen ciphertext at-
tack,” Advances in Cryptology - Eurocrypt™02, Lecture Notes in Computer Science
Vol. 2332, Springer-Verlag, 2002.
5. Full length version of [4]. http://shoup.net/papers/uhp.pdf
6. R. Cramer and V. Shoup, Design and analysis of practical public-key encryp-
tion schemes secure against adaptive chosen ciphertext attack, SIAM Journal on
Computing, Volume 33, Number 1, pp. 167-226 (2003)
7. E. Fujisaki and T. Okamoto, Secure Integration of Asymmetric and Symmetric
Encryption Schemes, Advances in Cryptology - CRYPTO ™99, Lecture Notes in
Computer Science Vol. 1666, M. Wiener ed., Springer-Verlag, 1999.
8. E.Fujisaki, T.Okamoto, D.Pointcheval, J.Stern, RSA-OAEP Is Secure under the
RSA Assumption. CRYPTO 2001, pp.260-274 (2001)
9. H.Krawczyk, LFSR-based Hashing and Authentication, CRYPTO 1994, pp.129-
139 (1994)
10. M.Naor and M.Yung, Universal One-Way Hash Functions and their Crypto-
graphic Applications, STOC 1989, pp.33-43 (1989)
11. J.Rompel: One-Way Functions are Necessary and Sufficient for Secure Signatures,
STOC 1990, pp.387-394 (1990)
12. V. Shoup, Using Hash Functions as a Hedge against Chosen Ciphertext Attack,
EUROCRYPT 2000, pp.275-288 (2000)
13. V. Shoup, OAEP Reconsidered, CRYPTO 2001, pp.239-259 (2001)


TEAM LinG
Secure Identity Based Encryption
Without Random Oracles

Dan Boneh1,* and Xavier Boyen2
1
Computer Science Department, Stanford University, Stanford CA 94305-9045
dabo@cs.stanford.edu
2
Voltage Security, Palo Alto, California
xb@boyen.org




Abstract. We present a fully secure Identity Based Encryption scheme
whose proof of security does not rely on the random oracle heuristic.
Security is based on the Decision Bilinear Diffie-Hellman assumption.
This solves an open problem posed by Boneh and Franklin in 2001.


1 Introduction

Identity Based Encryption (IBE) provides a public key encryption mechanism
where a public key is an arbitrary string such as an email address or a telephone
number. The corresponding private key can only be generated by a Private Key
Generator (PKG) who has knowledge of a master secret. In an IBE system, users
authenticate themselves to the PKG and obtain private keys corresponding to
their identities. Although Identity based encryption was proposed two decades
ago [Sha84], and a few early precursors suggested over the years [Tan87,MY96],
it is only recently that the first working implementations were proposed. Boneh
and Franklin [BF01,BF03] defined a security model for Identity Based Encryp-
tion and gave a construction based on the bilinear Diffie-Hellman problem.
Cocks [Coc01] describes another construction using quadratic residues modulo
a composite. The security of these systems requires cryptographic hash func-
tions that are modeled as random oracles, i.e., these systems are proven secure
in the random oracle model [BR93]. The same holds for several other identity
based systems featuring signatures [CC03], key exchange [SOK00], hierarchical
identities [GS02], and signcryption [Boy03].
It is natural to ask whether secure IBE systems can exist in the standard
model, i.e., without resorting to the random oracle heuristic. This question is
especially relevant in light of several uninstantiable random oracle cryptosys-
tems [CGH98,BBP04], which are secure in the random oracle model, but are
trivially insecure under any instantiation of the oracle. Towards this goal, sev-
eral recent results [CHK03,BB04,HK04] construct IBE systems secure without
random oracles in weaker versions of the Boneh-Franklin model. However, until
now, building a fully secure IBE remained open.
* Supported by NSF and the Packard Foundation.

M. Franklin (Ed.): CRYPTO 2004, LNCS 3152, pp. 443“459, 2004.
© International Association for Cryptologic Research 2004
TEAM LinG
444 Dan Boneh and Xavier Boyen

In this paper we construct an IBE system that is secure in the Boneh-Franklin
model without using random oracles. Security is based on the decisional version
of the bilinear Dime-Hellman assumption. Our system demonstrates that fully
secure IBE systems can exist without random oracles. The main shortcoming of
the proposed system is that it is inefficient; consequently, we mostly view our
construction as an existence proof.


2 Preliminaries
Before presenting our results we briefly review a definition of security for an IBE
system. We also review the definition for groups with a bilinear map. First, we
introduce some notation.

2.1 Notation
For a finite set S we use to define a random variable that picks
an element of S uniformly at random. For a randomized algorithm we use
to define a random variable that is the output of algorithm on
input We let denote the probability that the predicate
is true where is the random variable defined by For a vector
we use to denote the component of

2.2 Secure IBE Systems
Recall that an Identity Based Encryption system (IBE) consists of four algo-
rithms [Sha84,BF01]: Setup, KeyGen, Encrypt, Decrypt. The Setup algorithm
generates system parameters, denoted by params, and a master key master-key.
The KeyGen algorithm uses the master key to generate the private key corre-
sponding to a given identity. The encryption algorithm encrypts messages for
a given identity (using the system parameters) and the decryption algorithm
decrypts ciphertexts using the private key.
Boneh and Franklin [BF01] define chosen ciphertext security for IBE systems
under a chosen identity attack. In their model the adversary is allowed to adap-
tively chose the public key it wishes to attack (the public key on which it will
be challenged). More precisely, security for an IBE system is defined using the
following two probabilistic experiments and
Experiment for an algorithm and a bit define the
following game between a challenger and
Setup: A challenger runs the Setup algorithm. It gives the resulting system
parameters params. It keeps the corresponding master-key to itself.
Phase 1: Algorithm issues queries where each query is one of:
Private key query for an identity The challenger responds by running
algorithm KeyGen to generate the private key corresponding to the
public key It sends to
TEAM LinG
Secure Identity Based Encryption Without Random Oracles 445

Decryption query for a ciphertext and an identity The challenger
responds by running algorithm KeyGen to generate the private key
corresponding to It then runs algorithm Decrypt to decrypt the
ciphertext using the private key It gives the resulting plaintext.
These queries may be asked adaptively, that is, each query may depend
on the replies to
Challenge: Once decides that Phase 1 is over it outputs an identity
and two equal length plaintexts that it wishes to be chal-
lenged on, under the constraint that it had not previously asked for the
private key of The challenger sets the challenge ciphertext to
It sends as the challenge to
Phase 2: Algorithm issues more queries where is one of:
Private key query for any identity where The challenger
responds as in Phase 1.
Decryption query for identity where The challenger
responds as in Phase 1.
These queries may be asked adaptively as in Phase 1.
Guess: Finally, outputs a guess

We call the output of the game and define the random variable
as The probability is over the random bits used by the
challenger and the adversary. We define adversary advantage in attacking
the IBE system as:



Definition 1. We say that an WE system is chosen
IND-ID-CCA
ciphertext secure under a chosen identity attack if for any
adversary that makes at most chosen private key queries and at most
chosen decryption queries we have that As shorthand, we say that
is secure.

Semantic Security. As usual, we define chosen plaintext security for an IBE
system as in the game above, except that the adversary is not allowed to issue any
decryption queries. The adversary may still issue adaptive private key queries.
The resulting system is semantically secure under an adaptive chosen identity
attack.

Definition 2. We say that an IBE system is chosen plaintext se-
cure under a chosen identity attack if is ciphertext secure
under a chosen identity attack. As shorthand, we say that is
secure.

For we use to denote the experiment where
cannot make any decryption queries.
TEAM LinG
446 Dan Boneh and Xavier Boyen

2.3 Bilinear Groups
We briefly review the necessary facts about bilinear maps and bilinear map
groups.
1. and are two (multiplicative) cyclic groups of prime order
2. is a generator of
3. is a bilinear map
Let and be two groups as above. A bilinear map is a map
with the following properties:
1. Bilinear: for all and
2. Non-degenerate:
We say that is a bilinear group if the group action in can be computed
efficiently and there exists a group and an efficiently computable bilinear
map as above. Note that is symmetric since


3 Complexity Assumptions
Let be a bilinear group of prime order and be a generator of We
review the standard Bilinear Diffie-Hellman (BDH) assumption as well as the
definition for binary biased Pseudo Random Functions (PRF™s) and collision
resistant functions.

3.1 Bilinear Diffie-Hellman Assumption
The BDH problem [Jou00,BF01] in is as follows: given a tuple
as input, output An algorithm has advantage in solving
BDH in if

where the probability is over the random choice of in and the random
bits of
Similarly, we say that an algorithm that outputs has advantage
in solving the decision BDH problem in if


where the probability is over the random choice of in the random choice
of and the random bits of We use the following notation:
We denote the distribution over 5-tuples in the left term of (1) by
We denote the distribution over 5-tuples in the right term of (1) by
Definition 3. We say that the BDH assumption holds in
if no algorithm has advantage at least in solving the (decision) BDH
problem in
Occasionally we drop the and and refer to the BDH and Decision BDH
assumptions in
TEAM LinG
Secure Identity Based Encryption Without Random Oracles 447

3.2 Biased Binary Pseudo-random Functions
Next we review the definition of a Pseudo Random Function (PRF) with bias
Let F be a function We say that F has bias if the
expectation of F over all inputs in is i.e.,
We let denote the set of all functions with bias
We also let denote a set of keys. For an algorithm we define the following
value:

Here denotes the output of algorithm when it is given oracle access
to the function F and input The input is a dummy input needed only so
that takes the same input as the below.
The biased Pseudo Random Functions that we will be using are parameter-
ized by two random values, say and The parameter is kept
secret while is public. To capture this concept we consider a set of functions
For such a family of functions
and an algorithm we define the following value:


Note that is given but is not given
Definition 4. Let be a set of func-
tions. We say that is a if for any oracle algo-
rithm making at most queries to its oracle we have:


We say that the parameter is kept secret while is public.

3.3 Collision Resistance
We briefly review the definition of collision resistant hash functions.
Definition 5. Let be an alphabet of size and let be some positive inte-
ger. We say that a family of functions is
resistant if for any algorithm we have


It is well known that collision resistant hash functions can be constructed
from a finite cyclic group for which the discrete log problem is intractable. Since
the Decision BDH assumption in implies that discrete-log in is intractable
it follows that the existence of collision resistant hash functions is implied by the
Decision BDH assumption. Consequently, rather than saying that our construc-
tion depends on both Decision BDH and collision-resistance we can say that our
construction depends on Decision BDH alone for security. Nevertheless, in our
security theorems we state collision resistance as an explicit assumption so that
one can use any cryptographic hash function such as SHA-1, if so desired.
TEAM LinG
448 Dan Boneh and Xavier Boyen

4 Secure IBE Construction
Before presenting our secure IBE system we first introduce a specific construction
for a biased binary PRF from any collision resistant hash function. Later, in
Section 5, we prove that it is indeed a PRF with overwhelming probability.

4.1 A Special Biased Binary PRF
Let be an alphabet of size and let For denote
by the set of vectors in that have exactly components in For
any vector with and any function
with we define the bias map as




Observe that when H is a random function, the bias map has an expecta-
tion of over the inputs
Definition 6. Let be positive integers with Let be an al-
phabet of size and set We say that a hash function fam-
ily is if the function family
is a PRF. Here is public and K is
secret.
In Section 5 we show how an admissible hash function family can be con-
structed given a collision resistant hash function family. In the rest of this section,
we show how to use admissible hash functions to construct a secure IBE in the
standard model.

4.2 Secure IBE Using Admissible Hash Functions
We are now ready to present our secure IBE system. It is based on a recent
HIBE construction without random oracles by Boneh and Boyen [BB04] (secure
in a selective identity attack model), itself inspired from a random oracle HIBE
construction due to Gentry and Silverberg [GS02].
The system makes use of a collision resistant hash function and security is
based on the Decision BDH assumption. Let be a bilinear group of prime
order and be a generator of Let be the bilinear map. We
assume that the messages to be encrypted are elements of
Throughout the section we let be an alphabet of size
although later we restrict our attention to the binary case We also let
be a family of hash functions. For now, we assume
that public keys (ID) are elements in We later extend the construction
by first hashing ID using a collision resistant hash
to public keys over
The IBE system works as follows:
TEAM LinG
Secure Identity Based Encryption Without Random Oracles 449

Setup: To generate system parameters the algorithm picks a random
and sets Next, it picks a random and a random
matrix where each is random in Finally, the algorithm
picks a random as a hash function key. The system parameters are
the master key is
KeyGen(params, ID, master-key): To generate the private key for an identity
the algorithm lets and picks
random The private key is:




Encrypt(params, ID, M): To encrypt a message under the public
key first set then pick a random
and output




Note that can be precomputed so that encryptiondoes not require
any pairing computations.
: To decrypt a ciphertext using
the private key output:




Let Then, indeed, for a valid ciphertext we
have:




This completes the description of the system.

4.3 Security
We now turn to proving security of the IBE above. The system makes use of
an admissible hash function family and security is based on the Decision BDH
assumption. We prove security in the standard model, i.e., without random or-
acles.
Theorem 1. Let Suppose the BDH assumption holds
in Furthermore, suppose is a
family of hash functions. Set and
Assume that Then the IBE system above is plaintext
(IND-ID-CPA) secure for any
TEAM LinG
450 Dan Boneh and Xavier Boyen

We note that taking leads to Then, ignoring
we have that Hence, in groups where BDH
holds we obtain a secure IBE system without random oracles.
To prove the theorem we need to show that for any algorithm that
makes at most private key queries we have


To do so we first define two additional experiments.

Experiment 1: Let be an algorithm, be a bit
in {0,1}, and a 5-tuple where and Define
the following game between a simulator and
Setup: To start, the simulator generates system parameters by first picking a
random vector It then generates an matrix
as follows. For each and it picks a random
and sets



Next, the simulator picks a random as a hash function key. It gives
the system parameters Note that the correspond-
ing (unknown) master key is where
Phase 1. issues up to private key queries. Consider a query for the private
key Let If for all
then the simulator terminates the experiment and outputs abort.
Otherwise, there exists an such that The simulator derives

<<

. 14
( 19)



>>