177

Space-Efficient Identity Based Encryption Without Pairings Dan Boneh∗ Craig Gentry† Michael Hamburg {dabo,cgentry,mhamburg}@cs.stanford.edu Stanford University Abstract Identity Based Encryption (IBE) systems are often constructed using bilinear maps (a.k.a. pairings) on elliptic curves. One exception is an elegant system due to Cocks which builds an IBE based on the quadratic residuosity problem modulo an RSA composite N . The Cocks system, however, produces long ciphertexts. Since the introduction of the Cocks system in 2001 it has been an open problem to construct a space efficient IBE system without pairings. In this paper we present an IBE system in which ciphertext size is short: an encryption of an `-bit message consists of a single element in Z/NZ plus ` + 1 additional bits. Security, as in the Cocks system, relies on the quadratic residuosity problem. The system is based on the theory of ternary quadratic forms and as a result, encryption and decryption are slower than in the Cocks system. 1 Introduction In an Identity Based Encryption (IBE) system any string can function as a public key [36]. IBE systems have found numerous applications in cryptography (see [12, 13, 7, 21, 41, 8, 10, 5] to name a few) and computer security [2, 40, 29, 30, 37]. There are currently two approaches for constructing IBE systems. The first approach builds IBE systems using bilinear pairings [9, 6, 39, 35]. The resulting systems are efficient both in performance and ciphertext size. The rich structure of bilinear maps enables various extensions such as Hierarchical IBE [27, 24], anonymous IBE [8, 1, 11, 23], and many others. The second approach, due to Cocks [16], builds an elegant IBE system based on the standard quadratic residuosity problem [31, p.99] modulo an RSA composite N (in the random oracle model). Ciphertexts in this system contain two elements in Z/NZ for every bit of plaintext. Hence, the encryption of an `-bit message key is of size 2` · log2N . For example, when encrypting a 128- bit message key using 1024-bit modulus, one ends up with a ciphertext of size 32678 bytes. For comparison, pairing based methods produce a 36 byte ciphertext for comparable security. A long standing open problem since [16] is the construction of a space efficient IBE system without pairings, namely a system with short ciphertexts. We construct such a system — an encryption of an ` bit message consists of a single element in Z/NZ plus (` + 1) additional bits. Hence, ciphertext size is about ` + log2N . When encrypting a 128-bit message key the result is a ciphertext of size 1024 + 129 = 1153 bits or 145 bytes. The system makes extensive use of the ∗Supported by NSF and the Packard Foundation. †Supported by the Herbert Kunzel Stanford Graduate Fellowship. 1 theory of quadratic forms [14]. In particular, encryption and decryption are based on an effective version of Legendre’s famous three squares theorem. Our main proposed IBE system is presented in Section 6. The system is related to the Cocks system and security is similarly based on the quadratic residuosity (QR) problem. As in the Cocks system, our IBE proof of security makes use of the random oracle model. However, the random oracle model is needed only for proving that the underlying Rabin signature scheme is existentially unforgeable. To make this precise we first prove security in the standard model under the Interactive QR assumption (IQR), namely under the assumption that the QR problem is difficult in the presence of a hash square root oracle. We then note that IQR is equivalent to QR in the random oracle model. We observe that the system is an anonymous IBE under the quadratic residuosity assumption. (the Cocks system is known to not be anonymous). In Appendix E, we describe a general framework for using hash proof systems (as defined in [18]) that have a trapdoor to construct IBE systems that are anonymous and secure against chosen-ciphertext attacks in the standard model under the Interactive Subset Membership (ISM) assumption, a generalization of the IQR assumption. We provide hash proof systems for quadratic residuosity, which induce a system based on IQR (in the standard model). We also provide a PKE system secure against chosen-ciphertext attacks under the QR assumption, which may be of independent interest. The computational performance of our system is far from ideal. Recall that encryption time in most practical public key systems such as RSA and existing IBE systems [9, 16] is cubic in the security parameter. Encryption time in our system is quartic in the security parameter per message bit. Decryption time, however, is cubic as in other systems. The bottleneck during encryption is the need to generate primes on the order of N . In Section 5.3 we show a time space tradeoff where the number of primes to generate can be significantly reduced at the cost of a modest increase in the ciphertext size. Encryption in the resulting system takes several seconds. 2 Definitions Recall from [36, 9] that an Identity Based Encryption system (IBE) consists of four algorithms: Setup, KeyGen, Encrypt, Decrypt. The Setup algorithm generates system parameters, denoted by PP, and a master key MSK. The KeyGen algorithm uses the master key to generate the private key dID corresponding to a given identity ID. The Encrypt algorithm encrypts messages for a given identity (using the system parameters) and the Decrypt algorithm decrypts ciphertexts using the private key. An IBE must remain secure against an attacker who can request private keys for identities of his choice. This is captured in the standard IBE security game [9], which also captures chosen ciphertext attacks. Beyond the basic semantic security requirements for IBE encryption one can also require that the IBE be anonymous, namely that a ciphertext reveal no information about the identity used to create the ciphertext. Anonymous IBE is useful for a variety of applications such as searching on encrypted data [8, 1, 11, 37]. Chosen ciphertext security, private key queries, and anonymity are captured in the following IBE security game: Setup: The challenger runs Setup(λ) and gives the adversaryA the resulting public parameters PP. It keeps MSK to itself. We set ID∗0, ID ∗ 1 ← ⊥ and C∗ ← ⊥. Queries: The adversary issues adaptive queries q1, q2, . . . where query qi is one of: 2 • Private key query 〈IDi〉 where IDi 6= ID∗0, ID∗1. The challenger responds by running algorithm KeyGen(MSK, IDi) and sends the resulting private key di to A. • Decryption query (IDi, Ci) where (IDi, Ci) is neither (ID∗0, C∗) nor (ID∗1, C∗). The chal- lenger responds by running algorithm KeyGen(MSK, IDi) to generate a private key di and then runs algorithm Decrypt(di, Ci). It sends the resulting plaintext to the adversary. • A single encryption query ((ID0,m0), (ID1,m1)) where ID0, ID1 are distinct from all previous private key queries and m0,m1 are two equal length plaintexts. The challenger picks a random bit b R← {0, 1} and sets C∗ ← Encrypt(PP, IDb,mb) , ID∗0 ← ID0, ID∗1 ← ID1 It sends C∗ to the adversary. Guess: Eventually, the adversary outputs a guess b′ ∈ {0, 1}. The adversary wins if b = b′. We define A’s advantage in attacking the scheme E as IBEAdvA,E(λ) = ∣∣∣∣Pr[b = b′]− 12 ∣∣∣∣ The probability is over the random bits used by the challenger and the adversary. An adversary A in this game is called an ANON-IND-ID-CCA adversary. We will also consider three types of weaker adversaries: • If A makes no decryption queries we say that A is an ANON-IND-ID-CPA adversary. This models an anonymous IBE under a chosen plaintext attack. • If in the single encryption query used to create the challenge ciphertext C∗, the adversary uses ID0 = ID1 then we say that the adversary is an IND-ID-CCA adversary. This models a chosen ciphertext secure IBE that is not necessary anonymous [9]. • An adversary that makes no decryption queries and sets ID0 = ID1 is said to be an IND-ID-CPA adversary. This is the standard IBE security model under a chosen plaintext attack. Definition 2.1. Let S be one of {IND-ID-CPA, IND-ID-CCA, ANON-IND-ID-CPA}. We say that an IBE system E is S secure if for all polynomial time S adversaries A we have that IBEAdvA,E(λ) is a negligible function. Notation: throughout the paper we let IDλ denote the set of all identities ID. The size of the set grows with λ. As shorthand, we will often write ID instead of IDλ. 2.1 Jacobi symbols and the QR assumption For a positive integer N , we use J(N) to denote the set {x ∈ Z/NZ : ( xN ) = 1}, where ( xN ) is the Jacobi symbol of x in Z/NZ. We use QR(N) to denote the set of quadratic residues in J(N). We base the security of our system on the following computational assumption. Definition 2.2 (Quadratic Residuosity Assumption (QR)). Let RSAgen(λ) be a algorithm that generates two equal size primes p, q. 3 • Let PQR(λ) be the distribution: (p, q) R← RSAgen(λ), N ← pq, V R← QR(N), output(N,V ) • Let PNQR(λ) be the distribution: (p, q) R← RSAgen(λ), N ← pq, V R← J(N) \QR(N), output(N,V ) We say that the QR assumption holds for RSAgen if for all PPT algorithms A, the function∣∣∣Pr[(N,V ) R← PQR(λ) : A(N,V ) = 1]− Pr[(N,V ) R← PNQR(λ) : A(N,V ) = 1]∣∣∣ is negligible. We call this the QR advantage QRAdvA,RSAgen(λ) of A against RSAgen. For completeness, we also prove our system secure without relying on random oracles. This, however, requires a stronger assumption we call the interactive QR assumption. Basically, the assumption says that the QR assumption holds relative to a square root oracle. Definition 2.3 (Interactive Quadratic Residuosity Assumption (IQR)). Let H be a hash function such that for every integerN the functionHN(·) maps {0, 1}∗ to J(N). LetO be a square root oracle — for every N which is a product of two odd primes it picks a quadratic non-residue uN ∈ J(N). It maps an input pair (N,x) to one of HN(x)1/2 or (uN HN(x))1/2 in Z/NZ, depending on which value is a quadratic residue. The oracle O is chosen uniformly from the set of all such functions. We say that the Interactive QR assumption (IQR) holds for the pair (RSAgen,H) if for all PPT algorithms A, the function∣∣∣Pr[(N,V ) R← PQR(λ) : AO(N,V ) = 1]− Pr[(N,V ) R← PNQR(λ) : AO(N,V ) = 1]∣∣∣ is negligible. We call this the IQR advantage IQRAdvA,(RSAgen,H)(λ) of A against RSAgen and H. Note that for IQR to hold, it must be difficult to find collisions in H, since each collision allows the adversary to factor N with probability 1/2. Note that the oracle O is a Rabin signature oracle. For a messages m ∈ {0, 1}∗ and public key (N,uN), the value O(N,m) is the Rabin signature on m. When H is a full-domain hash function modeled as a random oracle, the QR assumption implies the IQR assumption. Hence, our system will be secure in the standard model based on IQR and in the random oracle model based on the standard QR assumption. Our IBE system also uses a pseudorandom function (PRF) as defined in [25]. 3 An abstract IBE system with short ciphertexts We begin by describing an abstract IBE system that produces short ciphertexts. The system uses a deterministic algorithm Q with the following properties. Definition 3.1. Let Q be a deterministic algorithm that takes as input (N,R, S) where N ∈ Z+ and R,S ∈ Z/NZ. The algorithm outputs two polynomials f, g ∈ Z/NZ[x]. We say that Q is IBE compatible if the following two conditions hold: 4 • (Condition 1) If R and S are quadratic residues, then f(r)g(s) is a quadratic residue for all square roots r of R and s of S. • (Condition 2) If R is a quadratic residue, then f(r)f(−r)S is a quadratic residue for all square roots r of R. We construct an IBE compatible algorithm Q in Sections 4 and 5. Condition 1 implies that the Legendre symbol (f(r)/N) is equal to (g(s)/N), a fact that will be used during decryption. Condition 2 will be used to prove security. A single bit system. As a warm up to our IBE construction, consider briefly the following simple IBE for one bit messages. Setup(λ): generate (p, q) R← RSAgen(λ), N ← pq, and a random u R← J(N) \ QR(N). Output public parameters PP = (N,u,H) where H is a hash function H : ID → J(N). The master key MSK is the factorization of N . KeyGen(MSK, ID): generate a private key by first setting R← H(ID). If R ∈ QR(N) set r ← R1/2 and otherwise set r ← (uR)1/2. Output r as the private key for ID. Note that the private key is essentially a Rabin signature on ID, as in the Cocks system. Encrypt(PP, ID,m): to encrypt m ∈ {±1} with public key ID pick a random s ∈ Z/NZ and compute S ← s2. Let R← H(ID). Run Q twice: (f, g)← Q(N, R, S) and (f¯ , g¯)← Q(N, uR, S) and encrypt m using the two Jacobi symbols: c ← m · ( g(s) N ) and c¯ ← m · ( g¯(s) N ) . Output the ciphertext C ← (S, c, c¯). Decrypt(C, r): decrypt (S, c, c¯) using private key r. Let us first suppose that R = H(ID) is in QR(N) so that r2 = R. The decryptor runs Q(N, R, S) to obtain (f, g). By condition (1) of Definition 3.1 we know that ( g(s) N ) = ( f(r) N ) Hence the plaintext is obtained by setting m ← c · ( f(r) N ) . If R is a non-residue then uR is a quadratic residue and r2 = uR. We decrypt by running Q(N, uR, S) and recovering m from c¯. Since Q is deterministic, both sender and receiver always obtain the same pairs (f, g) and (f¯ , g¯). This completes the description of the one bit abstract system. Condition (1) implies soundness. As we will see, condition (2) enables us to prove semantic security under the QR assumption. We note that the Cocks system, reviewed in Appendix A, is not an instance of this system. Remark: Throughout the paper we let S, s be values chosen by the Sender (encryptor). We let R, r be values chosen by the Receiver (decryptor). 5 3.1 The Multi-Bit Abstract IBE System Observe that a single value S chosen by the encryptor can be used to encrypt multiple bits. To encrypt an `-bit message we hash ID multiple times by computing Ri ← H(ID, i) for i = 1, . . . , `. Now each pair (S,Ri) can be used to encrypt one message bit. The ciphertext only grows by two bits (ci, c¯i) per message bit. Hence, when encrypting an ` bit message, the complete ciphertext is C = (S, (c1, c¯1), . . . , (c`, c¯`)) whose length is dlog2(N)e + 2` bits. In Section 6 we show how to shrink the ciphertext length to dlog2(N)e+ (`+ 1) bits. We describe the complete system, called “BasicIBE” in more detail. Setup(λ): Generate (p, q) R← RSAgen(λ), N ← pq, and a random u R← J(N) \ QR(N). Output public parameters PP = (N,u,H) where H is a hash function H : ID × [1, `]→ J(N). The master key MSK is the factorization of N and a random key K for a pseudorandom function FK : ID × [1, `]→ {0, 1, 2, 3}. KeyGen(MSK, ID, `): Takes as input MSK, ID, and a message length parameter `. It generates a private key for decrypting encryptions of `-bit messages. For j = 1, . . . , ` do: Rj ← H(ID, j) ∈ J(N) and w ← FK(ID, j) ∈ {0, 1, 2, 3} let a ∈ {0, 1} be such that uaRj ∈ QR(N) let {z0, z1, z2, z3} be the four square roots of uaRj in Z/NZ Set rj ← zw Output the decryption key dID ← (PP, r1, . . . , r`). The PRF ensures that the key generator always outputs the same square roots for a given ID, but an adversary cannot tell ahead of time which of the four square roots will be output. Encrypt(PP, ID,m): Takes as input PP, a user ID, and a message m = m1 . . .m` ∈ {−1, 1}`. It generates random s ∈ Z/NZ and sets S ← s2. For j = 1, . . . , ` do: (1) Rj ← H(ID, j) , (f, g)← Q(N,Rj , S), and (f¯ , g¯)← Q(N,uRj , S) (2) cj ← mj · ( gj(s) N ) and c¯j ← mj · ( g¯j(s) N ) . Set c← c1 · · · c` and c¯← c¯1 · · · c¯` and output the ciphertext C ← (S, c, c¯). Decrypt(C, dID): Let dID = (PP, r1, . . . , r`). For j = 1, . . . , ` let Rj ← H(ID, j) and do: if r2j = Rj run (fj , gj)← Q(N,Rj , S) and set mj ← cj · ( fj(rj) N ) if r2j = uRj run (f¯j , g¯j)← Q(N,uRj , S) and set mj ← c¯j · ( f¯j(rj) N ) Output m← m1 . . .m`. The completes the description of BasicIBE. Soundness of decryption follows from Condition 1. Remark: The functionH outputs elements in J(N). This function can be easily implemented using a hash function H ′ that outputs elements in Z/NZ. Simply include in PP some element z ∈ Z/NZ whose Jacobi symbol (z/N) is −1. Then, to compute H(ID, j) first compute x ← H ′(ID, j). If x ∈ J(N) output H(ID, j) = x, otherwise output H(ID, j) = xz. Either way, H(ID, j) ∈ J(N) as required. 6 3.2 Security We prove security of the IBE system BasicIBE in the random oracle based on the QR assumption. Theorem 3.2. Suppose the QR assumption holds for RSAgen and F is a secure PRF. Then the IBE system BasicIBE is IND-ID-CPA secure when H is modeled as a random oracle. In particular, suppose A is an efficient IND-ID-CPA adversary. Then there exist efficient algorithms B1,B2 (whose running time is about the same as that of A) such that IBEAdvA,BasicIBE(λ) ≤ 2 ·QRAdvB1,RSAgen(λ) + PRFAdvB2,F (λ). The proof is given in Appendix B as a sequence of games. We also describe the underlying public key encryption system and prove its semantic security with a simple reduction style proof to the QR assumption. We note that the bounds in Theorem 3.2 are tight, and do not depend on the number of private key queries from the adversary. Since the theorem is set in the random oracle model, we could avoid the additional PRF assumption by implementing the PRF using the random oracle H. However, the proof is simpler and the result more concrete using a PRF. The proof of Theorem 3.2 depends on Condition (2) of Definition 3.1. Condition (2) is only used to satisfy the conditions of the following simple lemma, which is used to prove semantic security — it enables the challenger to create a challenge ciphertext that is well formed when S is in QR(N) but is random when S is not (see Appendix B). Lemma 3.3. Let N = pq be an RSA modulus, X ∈ QR(N), and S ∈ J(N) \ QR(N). Let x be a random variable uniformly chosen from among the four square roots of X. Let f be a polynomial such that f(x)f(−x)S is a quadratic residue for all four values of x. Then the Jacobi symbol (f(x)/N) is uniformly distributed in {±1}. Proof. Let x, x′ be two square roots of X such that x′ = x mod p, but x′ = −x mod q. Then the four square roots of X are {±x,±x′}. Since S 6∈ QR(N), we have ( f(x) p ) = − ( f(−x) p ) , and the same on q. By the Chinese Remainder Theorem, ( f(x′) p ) = ( f(x) p ) but ( f(x′) q ) = −1 · ( f(x) q ) , so that ( f(x′) N ) = −1 · ( f(x) N ) . So of the four values f(x), f(x′), f(−x), f(−x′), the first two must have different Jacobi symbols, as must the last two. Hence, among the four symbols, two are +1 and two are −1. Remark: The system BasicIBE is CPA secure, but is not anonymous — there are instances of Q for which anyone can test which identity created a given ciphertext. In Section 6 we make the system anonymous. Moreover, we shrink the ciphertext length to dlog2(N)e + (` + 1) bits. The resulting system can be proven secure in the standard model under the IQR assumption. The construction, however, cannot be based on a general IBE compatible algorithm Q. Instead, Q must satisfy additional properties. We view the construction in Section 6 as our main proposed construction. 7 4 Concrete instantiation: an IBE compatible algorithm To make our abstract system concrete, we need to give an IBE compatible algorithm Q. Recall that Q must generate polynomials f and g that meet Conditions 1 and 2 of Definition 3.1. The algorithm works as follows. Algorithm Q(N,R, S): 1. Construct a solution (x, y) ∈ (Z/NZ)2 to the equation Rx2 + Sy2 = 1 (∗) In Section 5 we describe algorithms and optimizations for solving this equation. Solving this equation is the main bottleneck in our system. 2. Output the polynomials f(r)← xr + 1 and g(s)← 2ys+ 2. We show that Q is IBE compatible. Let R,S ∈ Z/NZ. Let r be a square root of R and s a square root of S, if one exists. Condition 1 is met, since f(r) ·