# «CCA-Secure Proxy Re-Encryption without Pairings Jun Shao1,2 and Zhenfu Cao1 Department of Computer Science and Engineering Shanghai Jiao Tong ...»

CCA-Secure Proxy Re-Encryption without

Pairings

Jun Shao1,2 and Zhenfu Cao1

Department of Computer Science and Engineering

Shanghai Jiao Tong University

College of Information Sciences and Technology

Pennsylvania State University

chn.junshao@gmail.com; zfcao@cs.sjtu.edu.cn.

Abstract. In a proxy re-encryption scheme, a semi-trusted proxy can

transform a ciphertext under Alice’s public key into another ciphertext

that Bob can decrypt. However, the proxy cannot access the plaintext.

Due to its transformation property, proxy re-encryption can be used in many applications, such as encrypted email forwarding. In this paper, by using signature of knowledge and Fijisaki-Okamoto conversion, we propose a proxy re-encryption scheme without pairings, in which the proxy can only transform the ciphertext in one direction. The proposal is secure against chosen ciphertext attack (CCA) and collusion attack in the random oracle model based on Decisional Diﬃe-Hellman (DDH) assumption over Z∗ 2 and integer factorization assumption, respectively.

N To the best of our knowledge, it is the ﬁrst unidirectional PRE scheme with CCA security and collusion-resistance.

Keywords: Unidirectional PRE, DDH, random oracle, CCA security, collusionresistance 1 Introduction In 1998, Blaze, Bleumer, and Strauss [6] proposed the concept of proxy reencryption (PRE), where a semi-trusted proxy can transform a ciphertext for Alice into another ciphertext that Bob can decrypt.3 However, the proxy cannot get the plaintext. According to the direction of transformation, PRE schemes Supported by Research Fund for the Doctoral Program of Higher Education No.

20060248008, National Natural Science Foundation of China No. 60673079, Special Foundation of Huawei No. YZCB2006001, and National 973 Program No.

2007CB311201.

Corresponding author.

In almost all related papers, the concept of PRE is introduced as “PRE allows a semitrusted proxy to convert a ciphertext under Alice’s public key to another ciphertext under Bob’s public key”. However, all existing unidirectional PRE schemes (including ours) do not exactly follow the deﬁnition. In particular, in these unidirectional PRE schemes, there are two kinds of ciphertexts, one is the original ciphertext, and can be classiﬁed into two types, one is bidirectional, i.e., the proxy can transform from Alice to Bob and vice versa; the other is unidirectional, i.e., the proxy can only convert in one direction. Blaze et al. [6] also gave another method to classify PRE schemes: multi-use, i.e., the ciphertext can be transformed from Alice to Bob to Charlie and so on; and single-use, i.e., the ciphertext can be transformed only once.

Due to its transformation property, PRE can be used in many applications, including simpliﬁcation of key distribution [6], key escrow [21], distributed ﬁle systems [2, 3], security in publish/subscribe systems [23], multicast [10], secure certiﬁed email mailing lists [24, 22], the DRM of Apple’s iTunes [36], interoperable architecture of DRM [34], access control [35], and privacy for public transportation [19]. Recently, Hohenberger et al. got a result of securely obfuscating re-encryption [20], which is the ﬁrst positive result for obfuscating an encryption functionality and against a series of impossibility results [18, 16, 4].

Since the introduction of PRE by Blaze, Bleumer, and Strauss [6], there have been many papers [6, 21, 2, 3, 17, 9, 11, 25] that have proposed diﬀerent PRE schemes with diﬀerent security properties. Some of them are related to chosen ciphertext attack (CCA) security. Ivan and Dodis [21] proposed a CCA security model for PRE and a generic construction of single-use PRE in the security model. Nevertheless, their security model allows the delegatee (Bob) to make use of the proxy as an oracle. As a result, the schemes only secure in their security model are not enough for some applications. For example, in encrypted email forwarding, an adversary (Bob) might hope to gain access to the original encrypted email by re-forming it, sending it to the proxy, and then hoping that the proxy responds with, “Can you forward the following to me again? [Encrypted attachment.]” To ﬁx the problem, Green and Ateniese [17], Canetti and Hohenberger [9] proposed new CCA security models for ID-based PRE and PRE, respectively. In these two new security models, it requires that the proxy checks the validity of the ciphertext before transformation, which is called public veriﬁability. Following this intuition, the ﬁrst CCA secure, single-use, unidirectional ID-based PRE scheme in the random oracle model and the ﬁrst CCA secure, multi-use, bidirectional PRE scheme in the standard model are proposed in [17, 9], respectively.

However, the scheme in [17] suﬀers from the attack in Remark 2. Furthermore, the generic construction of PRE in [21] cannot be proved secure in the CCA security model in [9]. (See Appendix A for details. Hereafter, we refer CCA security to the deﬁnition in [9] or Section 2 of this paper.) Chu and Tzeng [11] proposed a multi-use, unidirectional ID-based PRE scheme, and claimed that it was CCA secure in the standard model. However, we showed that it was not true [31], since its transformed ciphertext (Cv1, R, d1, d2, d2 ) can be modiﬁed to another well-formed transformed ciphertext (Cv1, R, d1 F2 (vk)r, d2, d2 g r ) by the other is the transformed ciphertext. The transformed ciphertext is not exactly as the ciphertext under Bob’s public key, but Bob can decrypt the transformed ciphertext only by his secret key. To the best of our knowledge, only the bidirectional schemes in [6, 9] satisfy the deﬁnition.

anyone, where r is random number. Recently, Libert and Vergnaud [25] proposed a new unidirectional PRE scheme, which is replayable chosen ciphertext attack (RCCA) secure but not CCA-secure. It is fair to say that there is no CCA-secure unidirectional PRE scheme.4 Furthermore, according to the results in [5, 29], the timing of a pairing computation is more than twice of that of a modular exponentiation computation. Hence, the CCA-secure unidirectional PRE schemes without pairings are desired.

Another important security notion on unidirectional PRE is collusion-resistance, which disallows Bob and the proxy to collude to reveal Alice’s (long term) secret key, but allows the recovery of Alice’s “weak” secret key only. In this case, Alice can delegate decryption rights, while keeping signing rights for the same public key. Till now, there are only a few PRE schemes [2, 3, 25] holding this security.5 Though many PRE schemes have been proposed, we ﬁnd that no unidirectional PRE scheme without pairings but satisfying CCA security and collusionresistance simultaneously, even in the random oracle model. In this paper, we attempt to propose such a unidirectional PRE scheme.

**1.1 Our Contribution**

We present a proxy re-encryption scheme without pairings, named scheme U, which is unidirectional and single-use, and proven CCA-secure and collusion resistant in the random oracle model based on Decisional Diﬃe-Hellman (DDH) assumption over Z∗ 2 and integer factorization assumption, respectively. Here, N N is a safe-prime modulus.

The diﬃculty in constructing a CCA secure PRE scheme is to add the public veriﬁability to original ciphertexts. This public veriﬁability can prevent malicious Bob from gaining some advantage by using the proxy as an oracle. In pairing setting, such as [9], we can use the gap Diﬃe-Hellman problem (decisional DiﬃeHellman problem is easy, but computational Diﬃe-Hellman problem is hard) to achieve this. In particular, the gap Diﬃe-Hellman problem allows us to check whether logg A = logh B. In this paper, we use signature of knowledge [8, 1] to provide logg A = logh B, hence obtaining public veriﬁability for original ciphertexts. In fact, using the signature of knowledge to provide public veriﬁability is due to Shoup and Gennaro [33]. Furthermore, we use Fujisaki-Okamoto conversion [14, 15] to provide the validity check of both original ciphertexts and re-encrypted ciphertexts for the decryptor (Alice or Bob).

When we prepared the camera-ready version, we found another paper [13] dealing the similar problems, and getting the similar results with us. In [13], the authors use Schnorr signature [28] to make the original ciphertext be publicly veriﬁable, while we use signature of knowledge [8, 1]. In our submission version, we have a CCA-secure bidirectional PRE scheme, however, the bidirectional one in [13] beats ours in every aspects. Hence, in the current version, we removed our bidirectional one, which can be found in [30]. Furthermore, the unidirectional scheme in [13] suﬀers from the attack in Remark 2.

The unidirectional PRE scheme in [13] suﬀers from the collusion attack.

Following the construction of the public key encryption scheme with double trapdoors in [7], scheme U holds collusion-resistance. In particular, the factors of N are the long term secret key, and an exponent is the “week” secret key, and revealing the exponent does not hurt the secrecy of the factors of N. To the best of our knowledge, scheme U is the ﬁrst unidirectional PRE scheme holding CCA security and collusion-resistance simultaneously.

Finally, we extend scheme U to scheme UT, where the delegator can revoke the proxy’s transformation ability. In particular, the proxy can only transform the ciphertext during a restricted time interval.

1.2 Organization The remaining paper is organized as follows. In Section 2, we review the deﬁnitions related to our proposals. In what follows, we present scheme U and its security analysis, and scheme UT and its security analysis, in Section 3 and Section 4, respectively. In Section 5 we compare scheme U with previous unidirectional PRE schemes. Finally, we conclude the paper in Section 6.

2 Preliminaries In this section, we brieﬂy review the deﬁnitions related to our proposals, some similar content can be found in [8, 1, 17, 9].

2.1 Public Key Encryption Deﬁnition 1 (Public Key Encryption (PKE)). A public key encryption scheme

**PKE is a triple of PPT algorithms (KeyGen, Enc, Dec):**

– KeyGen(1k ) → (pk, sk). On input the security parameter 1k, the key generation algorithm KeyGen outputs a public key pk and a secret key sk.

– Enc(pk, m) → C. On input a public key pk and a message m in the message space, the encryption algorithm Enc outputs a ciphertext C.

– Dec(sk, C) → m. On input a secret key sk and a ciphertext C, the decryption algorithm Dec outputs a message m in the message space or ⊥.

Correctness. The correctness property is that for any message m in the message space and any key pair (pk, sk) ← KeyGen(1k ). Then the following condition must hold: Dec(sk, Enc(pk, m)) = m.

2.2 Unidirectional Proxy Re-Encryption Deﬁnition 2 (Unidirectional PRE). A unidirectional proxy re-encryption scheme

**UniPRE is a tuple of PPT algorithms (KeyGen, ReKeyGen, Enc, ReEnc, Dec):**

– KeyGen, Enc, Dec: Identical to those in public key encryption.

– ReKeyGen(sk1, pk2 ) → rk1→2. On input a secret key sk1 and a public key pk2, the re-encryption key generation algorithm ReKeyGen outputs a unidirectional re-encryption key rk1→2.

– ReEnc(rk1→2, C1 ) → C2. On input a re-encryption key rk1→2 and a ciphertext C1, the re-encryption algorithm ReEnc outputs a re-encrypted ciphertext C2 or ⊥.

**Correctness. A correct proxy re-encryption scheme should satisfy two requirements:**

Dec(sk, Enc(pk, m)) = m, and Dec(sk, ReEnc(ReKeyGen(sk, pk ), C)) = m, where (pk, sk), (pk, sk ) ← KeyGen(1k ), and C is the ciphertext of message m for pk from algorithm Enc or algorithm ReEnc.

Chosen Ciphertext Security for Unidirectional Proxy Re-Encryption.

This security note is a modiﬁcation of replayable chosen ciphertext security in [25], where the corrupted public keys are not decided before start of the UniPRE-CCA game, and the adversary is allowed adaptive corruption of users6, and proxies between corrupted and uncorrupted users. But unlike [25], we require that one well-formed ciphertext cannot be modiﬁed (but can be transformed) to be another well-formed ciphertext. In [25], anyone can modify the transformed cit−1 t t phertext, such that (C1, C2, C2, C2, C3, C4, σ) → (C1, C2, C2, C2, C3, C4, σ), where t is a random number from Zp.

Note that this security model is only for single-use scheme.

**Phase 1: The adversary A issues queries q1, · · ·, qn1 where query qi is one of:**

– Public key generation oracle Opk : On input an index i,7 the Challenger takes a security parameter k, and responds by running algorithm KeyGen(1k ) to generate a key pair (pki, ski ), gives pki to A and records (pki, ski ) in table TK.

– Secret key generation oracle Osk : On input pk by A, where pk is from Opk, the Challenger searches pk in table TK and returns sk.

– Re-encryption key generation oracle Ork : On input (pk, pk ) by A, where pk, pk are from Opk, the Challenger returns the re-encryption key rkpk→pk = ReKeyGen(sk, pk ), where sk is the secret key corresponding to pk.

– Re-encryption oracle Ore : On input (pk, pk, C) by A, where pk, pk are from Opk, the re-encrypted ciphertext C = ReEnc(ReKeyGen(sk, pk ), C) is returned by the Challenger, where sk is the secret key corresponding to pk.

– Decryption oracle Odec : On input (pk, C), where pk is from Opk, the Challenger returns Dec(sk, C), where sk is the secret key corresponding to pk.

The security model in[13] does not allow such adaptive corruption.

This index is just used to distinguish diﬀerent public keys.

These queries may be asked adaptively, that is, each query qi may depend on the replies to q1, · · ·, qi−1.

Challenge: Once the adversary A decides that Phase 1 is over, it outputs two equal length plaintexts m0, m1 from the message space, and a public key pk ∗ on which it wishes to be challenged. There are three constraints on the public key pk ∗, (i) it is from Opk ; (ii) it did not appear in any query to Osk in Phase 1; (iii) if (pk ∗, ) did appear in any query to Ork, then did not appear in any query to Osk. The Challenger picks a random bit b ∈ {0, 1} and sets C ∗ = Enc(pk ∗, mb ).

It sends C ∗ as the challenge to A.