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