Further observation on proxy re-encryption with keyword search

Abstract

Recently Shao et al. proposed an interesting cryptographic primitive called proxy re-encryption with keyword search (PRES). The main novelty is simultaneously realizing the functionality of proxy re-encryption and keyword search in one primitive. In this paper, we further extend their research by introducing a new primitive: constrained single-hop unidirectional proxy re-encryption supporting conjunctive keywords search (CPRE-CKS). Our results are as following: (1) In Shao's PRES scheme, the proxy can re-encrypt all the second level ciphertext. While in our CPRE-CKS proposal, the proxy can only re-encrypt those second level ciphertexts which contain the corresponding keywords. (2) We give the definition and security model for CPRE-CKS, and propose a concrete scheme and prove its security. (3) On the way to construct a secure CPRE-CKS scheme, we found a flaw in the security proof of Hwang et al.'s public key encryption with conjunctive keyword search (PECK) scheme proposed in Pairing’07.

Introduction

Proxy re-encryption (hereafter referred to as “PRE”) allows a semi-trusted third party, called “proxy”, to convert ciphertexts computed under Alice's public key into those can be decrypted using Bob's private key. The proxy in PRE is given a re-encryption key with which he/she can perform the conversion without knowing the corresponding plaintexts. A PRE scheme is bidirectional if the proxy can use the re-encryption key to divert ciphertexts from Alice to Bob and vice versa. Otherwise, it is called unidirectional. According to how the conversion is performed, PRE can be classified as multi-hop and single-hop. A multi-hop PRE scheme supports “re-encryption chain”, namely any ciphertexts converted by the proxy during the re-encryption phase can be re-encrypted to the ciphertexts of someone else. In other words, the re-encryption phase in multi-hop PRE can be conducted as many times as needed. This differs from a single-hop PRE scheme, where ciphertexts converted by the proxy cannot be re-encrypted again.

The notion of PRE was introduced by Blaze et al. (1998) and recently investigated by Ateniese et al. (2005). They proposed the first construction of unidirectional PRE and demonstrated several applications of PRE (Ateniese et al., 2005), including e-mail forwarding, law enforcement, cryptographic operations on storage-limited devices, distributed secure file systems and outsourced filtering of encrypted spam. To date, many variants of PRE have been proposed, and in this paper we focus on two of them: conditional proxy re-encryption and proxy re-encryption supporting keyword search.

Conditional proxy re-encryption (hereafter referred to as “CPRE”) is motivated by a practical issue, namely how to selectively delegate the decryption right. In normal PRE, the proxy can use the re-encryption key to re-encrypt all ciphertexts, and thus once giving the re-encryption key to the proxy, the delegator can no longer control which ciphertexts will be decrypted by the delegatee. It is certainly desirable if the delegator can choose the ciphertexts that can be correctly re-encrypted by the proxy and then can be decrypted by the delegatee. For this purpose, Tang (2008) proposed the notion of type-based proxy re-encryption (TPRE). In the new notion, ciphertexts and re-encryption keys are classified into different types, and the re-encryption can be performed correctly only if the proxy has a valid re-encryption key matching the type of ciphertexts. Similarly and independently, Weng et al. (2009) proposed the concept of conditional proxy re-encryption (CPRE), whose purpose is to achieve a fine-grained delegation. The essential idea of CPRE is almost the same as TPRE, with the difference that the “type” in TPRE (Tang, 2008) is replaced by a more generic notion called “condition information” in CPRE (Weng et al., 2009).

Proxy re-encryption with keyword search (hereafter referred to as “PRES”) (Libert and Vergnaud, 2011, Shao et al., 2010) incorporates the property of keyword search in proxy re-encryption, namely the proxy is given a search-key with which it can test whether or not a ciphertext contains a keyword (e.g., “urgent”) or a set of keywords (e.g., { “ urgent ” , “ family ” }) without knowing anything else about the corresponding plaintext. Very recently, Shao et al. (2010) proposed a concrete construction of PRES, and demonstrated the potential applications of PRES in cloud computing and sensor networks.

PRES in Shao et al. (2010) allows the proxy to test the keyword that a ciphertext has. While it is a significant improvement of the original PRE, PRES might not be a satisfactory solution to the following issue.

Suppose Alice wants to delegate the decryption right to Bob such that Bob can decrypt her ciphertexts with the keyword “research” but cannot retrieve any messages from other ciphertexts (e.g., those with the keyword “family”). By employing the PRES proposed in Shao et al. (2010), Alice can generate a search-key with which the proxy can check if a ciphertext contains the keyword “research”. If it does, the proxy can use the re-encryption key to convert that ciphertext into Bob's ciphertext. Notice that with the re-encryption key the proxy is actually able to re-encrypt any ciphertexts of Alice, no matter which keyword the ciphertexts have. In this case, once colluding with the proxy, Bob can read the messages of any ciphertexts sent to Alice. Therefore, an assumption must be made if we use the PRES scheme (Shao et al., 2010) in the above situation, namely the proxy is trusted to re-encrypt ciphertexts only with the keyword specified by Alice. This however may not hold in practice since the proxy in PRE is generally untrusted and may collude with the delegatee for their common interests. Another limitation of Shao et al. (2010) is that each search-trapdoor only allows the proxy to search one keyword but a document always contains two or more keywords. Thus, it would be desirable if a search-key provides conjunctive keywords searching.

A feasible method to solve the above issue is CPRE, where the re-encryption key is linked with the type of ciphertexts and the delegatee (i.e., Bob in our example) can only retrieve messages of ciphertexts satisfying certain requirements. This however is not a practical solution. Suppose the proxy in CPRE is given a re-encryption key associated with the keyword “research”. As the proxy cannot test if a ciphertext contains the keyword “research”, the proxy will re-encrypt all ciphertexts and send them to the delegatee. Similarly, the delegatee will decrypt all ciphertexts but only those with the keyword “research” can be correctly decrypted. In this case, both the proxy and the delegatee must perform a large number of (unnecessary) computations: the proxy must re-encrypt all ciphertexts and the delegatee must decrypt all ciphertexts which are re-encrypted by the proxy. Therefore, CPRE alone is not a satisfactory solution of the situation we are concerned about.

As one can see, the optimal solution is that the proxy only re-encrypts ciphertexts with the specified keywords and sends the results to the delegatee. To achieve this, the proxy must be given a search-key with which it can test if a ciphertext contains a certain set of keywords. The motivation of this paper is to investigate proxy re-encryption with those properties.

The purpose of this paper is find a practical solution to address the issue we described previously, namely a proxy re-encryption scheme simultaneously accommodates conjunctive keywords search and selective delegation. The contribution of this paper is threefold:

• We first introduce the notion of constrained single-hop unidirectional proxy re-encryption supporting conjunctive keywords search, where the proxy can first test if a ciphertext contains a certain set of keywords, after which it can re-encrypt the ciphertext with the corresponding re-encryption key.

• We formalize the security requirements of constrained single-hop unidirectional proxy re-encryption supporting conjunctive keywords search. The first concrete scheme is also proposed. Our construction is built on bilinear maps and its security is proved in the random oracle model.

• Our construction can be viewed as a significant improvement of the proxy re-encryption scheme with keyword search in Shao and Cao (2009) (where the proxy can search only one keyword and the delegatee can have unlimited decryption right), the type based or conditional proxy re-encryption scheme in Tang, 2008, Weng et al., 2009 (which does not support keyword search) and the public key encryption scheme with conjunctive keyword search in Hwang and Lee (2007).¹

Blaze et al. first introduced the concept of PRE and presented a concrete scheme based on ElGamal encryption (Blaze et al., 1998). But their scheme is only bidirectional. The first unidirectional PRE scheme was proposed by Ateniese et al. (2005). However, their scheme can only achieve IND-CPA security. Canetti and Hohenberger (2007) demonstrated the first IND-CCA2 secure bidirectional PRE. Following their work, Libert and Vergnaud (2008) constructed the first replayable IND-CCA secure unidirectional PRE scheme in the standard model. Recently Weng et al. showed how to construct IND-CCA secure unidirectional PRE scheme without random oracles in the adaptive corruption model (Weng et al., 2010a, Weng et al., 2010b). PRE schemes without pairing also investigated by researchers (Deng et al., 2008, Shao and Cao, 2009).

However, the proxy in all these schemes has the ability of transforming all the delegator's original ciphertext. Aiming at enabling the delegator to selectively delegate his decryption right to the delegatee, Tang and Weng independently introduced the concept of type-based PRE (Tang, 2008) and conditional PRE (Weng et al., 2009). Later, Fang et al. (2009) gave a construction of a conditional PRE satisfy anonymous conditions, which was left as an open problem in Weng et al. (2009). Recently Weng et al. revised their concept on conditional PRE and constructed a more efficient scheme (Weng et al., 2008).

Public key encryption with keyword search (PKES) follows another line of research. This concept and its construction were first established by Boneh et al. (2004). Abdalla et al. further formalized their construction and proposed the consistency notion (Abdalla et al., 2005). However, all these schemes handled with the one keyword search problem. It does not say anything about the conjunctive keywords search. The first public key encryption with conjunctive keywords search (PECK) was proposed by Park et al. (2004). Later they introduced the concept of keyword based searchable encryption (SKBE), which is almost same as PECK except there is an additional algorithm DTrapdoor for decrypting the searched ciphertext (Park et al., 2005). They demonstrated such a construction. Their work was later improved by Byun et al. (1998). Oblivious conjunctive keyword search was proposed by Rhee et al. (2005). In Pairing’07, Hwang and Lee (2007) pointed out flaws in the security proof of Park et al.'s PECK scheme and gave a new construction. But unfortunately, in this paper we will also see a flaw in their security proof. According to comments from Huang et al., Park et al. revised their security model to a weaker one (we refer it as wIND-CCA security in our paper) and proved their SKBE scheme is secure in this weaker model (Park et al., 2005).

Combining proxy re-encryption with public key encryption with keyword search, Shao et al. proposed a new cryptographic primitive called proxy re-encryption with keyword search (PRES) (Shao et al., 2010) recently. Besides its traditional use in e-mail forwarding, law enforcement, cryptographic operations on storage-limited devices and distributed secure file systems, they also discussed its potential application in cloud computing and sensor networks. We note that Libert and Vergnaud also mentioned this concept in their paper (Libert and Vergnaud, 2008), although with no formal definition and security model. We also note recently Yau et al. (2010) proposed a new definition of PRES and even PEKS. Their definition extends the original PEKS definition (Boneh et al., 2004) by including the algorithms of re-encryption key generation and re-encryption of keyword ciphertext. Furthermore, their approach keeps the encryption of message and encryption of keyword separate. While their approach has its particular applications, we remark this approach is not consistent with the normal view on PEKS. In that view, the encryption of message and encryption of keyword should be integrated.

We organize our paper as follows. Section 2 reviews some preliminaries. Formal definitions of constrained single-hop proxy re-encryption scheme supporting conjunctive keywords search is given in Section 3. In Section 4, we give our concrete construction and its security proof. Then in Section 5, we evaluate our scheme's performance. Section 6 describes an application in cloud computation. In the last Section 7, we conclude our paper. In Appendix A, we show a flaw in the security proof of public key encryption with conjunctive keywords search proposed by Hwang's et al. in Pairing’07.