Elsevier

Information Sciences

Volume 328, 20 January 2016, Pages 389-402
Information Sciences

Identity-based encryption with outsourced equality test in cloud computing

https://doi.org/10.1016/j.ins.2015.08.053Get rights and content

Highlights

  • It is the first time to integrate identity-based encryption into public key encryption with equality test.

  • It extends identity-based encryption with keyword search to yield a general function: equality test.

  • It is proven to be one-way chosen-ciphertext security against a chosen identity attack as a desirable security.

  • Unlike PEKS or IBEKS, it can be used alone since it contains decryption algorithm besides encryption algorithm.

Abstract

We firstly combine the concepts of public key encryption with equality test (PKEET) and identity-based encryption (IBE) to obtain identity-based encryption with equality test (IBEET). Inheriting the advantage of IBE, IBEET can simplify the certificate management of PKEET with all messages encrypted with the receiver’s public identity. In the IBEET scheme, the receiver computes a trapdoor using the secret value for the identity and then sends it to a cloud server for equality test on its ciphertexts with others’ ciphertexts. Using this primitive someone with the trapdoor for its identity can delegate out the capability of equality test on its ciphertexts without requiring a central authority to act as a delegator. So it is very suitable for the client with minimal computation resource, e.g, mobile phone. Furthermore, compared with PKEET, it has security improvement since not anyone can perform the test. Therefore, IBEET may have interesting applications in cloud computing, e.g., partition of encrypted emails. We define one-way chosen-ciphertext security against a chosen identity attack (OW-ID-CCA) and propose a construction in bilinear pairing. Finally, extensive security analysis and comparison with related works show that the proposed scheme is proven secure and useful.

Introduction

There has recently been interest in “searchable encryption” due to interesting applications in cloud computing era. A searchable encryption scheme allows a third party to search over a client’s encrypted data on its behalf without the need of recovering the plaintexts. It enables organizations and individuals to outsource their data in encrypted form and securely delegate search functionalities to the cloud service provider. Mainly, existing works concentrate on keywords search [2], [3], [7], [9], [10], [11], [12], [15], [16], [19], [23], [24], [26], [29], [30], [34], [35], [37], [39], [40], where a match is determined by whether the keyword encoded in the trapdoor is equal to the plaintext underneath the ciphertext. Additionally, other works study search queries with more complex comparison structures [5], [8], [14], [17], allowing conjunctive, disjunctive, subset and inner product. Recently, as a special type of searchable encryption, public key encryption with equality test (PKEET) [36] has been proposed to check whether two ciphertexts are encryptions of the same message, which can be used to support keywords search on encrypted data trivially. In order to simplify certificate management of PKEET, we firstly combine the concepts of public key encryption with equality test (PKEET) and identity-based encryption (IBE) to obtain identity-based encryption with equality test (IBEET).

IBEET has interesting applications in cloud computing, e.g., partition of encrypted emails. In the following scenario (see Fig. 1), Alice and Bob work in the same company with a cloud email system. For security reasons, all senders produce encrypted emails to Alice (Bob) using Alice’s (Bob’s) public identity: “alice@company.com” (“bob@company.com”) appended with a small number of encrypted keywords, for example, tags about the email’s confidentiality including “Ordinary”, “Secret” and “Top-secret” could be used as keywords. Suppose that this company expects to utilize the storage partition service of the email system [1] to divide the email storage into different regions according to the customer’s requirements depending on whether the emails have the same keywords. In this case, the email server needs to classify all receivers’ encrypted emails based on the emails’ keywords. Since both the contents of the email and the keywords are encrypted, the email server cannot see the keywords and hence, cannot make the classification of Alice’s and Bob’s encrypted emails. Thus, our goal is to enable Alice and Bob to authorize the server to perform an equality test on the encrypted keywords in their emails but the server should learn nothing about the emails’ contents. Previous works have solved the problem of keywords search on single receiver’s encrypted emails, but have not studied a general comparison: equality test on multiple receivers’ keywords in their encrypted emails.

To do so, the sender encrypts his (her) email using a standard public key system with the receiver’s identity (IDA or IDB), and then appends to the resulting ciphertext an identity-based encryption with outsouced equality test (IBEET) of each keyword. For simplicity, there is only one keyword for each email. To send a message M with keyword W to Alice, the following data are sent to the server: E(IDA,M)IBEET(IDA,W)

The key point of the IBEET scheme is that Alice can give the server a trapdoor tdA to enable it testing whether W is equal to the keyword in others’ emails. Given IBEET(IDA,W), tdA, IBEET(IDB,W) and tdB, the server can test whether W=W. If WW′, the server learns nothing more about W and W′. Note that although we only refer to two receivers (Alice and Bob) in the example, we hope that the keywords in multiple receivers’ emails could be compared as long as their trapdoors are given to the server. Besides, we also expect that the IBEET scheme can support keyword search on single receiver’s encrypted emails trivially, which would help the system upgrade in single user setting.

Two related cryptographic primitives have been proposed: public key encryption with equality test [36] and identity-based encryption with keyword search [2].

Public key encryption with equality test. Public key encryption with equality test (PKEET), firstly introduced in [36], is used to check whether two users’ ciphertexts contain the same message. To impose authorization on PKEET [36], Tang [31] proposes an enhanced PKEET (FG-PKEET) to realize a fine-grained authorization mechanism, where only the authorized two users can do the test with the help of a trusted party. Also, Tang [33] presents an all-or-nothing PKEET (AoN-PKEET) to achieve a coarse-grained authorization, which specifies who can perform an equality test on ciphertexts. Furthermore, Tang [32] extends FG-PKEET to a two-proxy setting, where two proxies collaborate to execute equality test. Recently, Ma et al. [22] propose a public key encryption with delegated equality test (PKE-DET) to only allow a delegated party to perform the work. Huang et al. [13] present a public key encryption with authorized equality test (PKE-AET), where a receiver authorizes a receiver’s warrant on all of its ciphertexts or a receiver authorizes a cipher-warrant on a specific ciphertext. Also, Ma et al. [21] design a flexible PKEET scheme supporting four types of authorization at the same time.

Identity-based encryption with keyword search.Identity-based encryption with keyword search (IBEKS), firstly introduced in [2], is an interesting extension of public key encryption with keyword search (PEKS) [4], which is a combination of the concepts of PEKS and identity-based encryption (IBE) and allows any string as a receiver’s public key for the PEKS scheme. In IBEKS, someone with query trapdoor for an identity can delegate out the capability of keyword search without requiring a central authority to act as a delegator. They also propose a generic transformation to convert an anonymous hierarchical identity-based encryption (HIBE) with two levels to IBEKS, where the first level is an identity and the second level is a keyword.

Analysis. Next we will show the conceptual analysis on IBEET, PKEET and IBEKS. The differences between IBEET and PKEET are:

  • 1.

    IBEET uses the receiver’s identity as a public key, whereas PKEET uses the public key certificate distributed by a certificate authority (CA).

  • 2.

    IBEET has security improvement compared with PKEET because for the former the server should be authorized by the receiver before performing the equality test on the ciphertexts, but for the latter anyone can check whether two ciphertexts are encryptions of the same message. Therefore, IBEET can provide more control on search capabilities of the delegated party.

The differences between IBEET and IBEKS are:

  • 1.

    In IBEKS, the identity whose ciphertexts are compared is the same as the identity used to generate the trapdoor for a keyword, which means that as input of Text algorithm, tw and C refer to the same identity. However, in IBEET, Test algorithm is performed between two ciphertexts which may belong to two receivers with different identities.

  • 2.

    IBEET supports keyword search trivially provided by IBEKS scheme. For the implementation of keyword search in IBEET, given a ciphertext C of keyword w for identity id, to check whether w is equal to a keyword w′, the trapdoor consists of both the ciphertext C′ of the keyword w′ for the identity id and the equality test trapdoor td associated with the identity id. Then the server computes whether Test(C,td,C,td) is equal to 1 denoting w=w.

  • 3.

    The definition of IBEKS does not contain decryption algorithm, hence IBEKS cannot be used alone but has to be paired with another encryption of message. However, since the definition of IBEET includes decryption algorithm, IBEET can be used independently in applications.

In this paper, we propose the notion of identity-based encryption with equality test (IBEET) and its construction. Our main technique is to use an identity-based encryption [4] to mask the output of public key encryption with equality test [36]. After the disclosure by an identity-related trapdoor, the test function provided by Yang et al. [36] works just as before. In brief, our contributions are summarized as follows.

  • 1.

    Our construction is the first time to integrate identity-based cryptosystem into public key encryption with equality test, thus it inherits the advantages of both primitives. Specifically, it supports to authorize the cloud server to perform an equality test on ciphertexts via a trapdoor, which is computed using the secret value for the identity. In this sense, it would be viewed as a variant of public key encryption with equality test supporting user-level authorization {CITEHuang2015doi:10.1093/comjnl/bxv025,Ma2015,Tang-415.

  • 2.
  • 3.
  • 4.

The rest of this paper is organized as follows. In Section 2 we introduce some preliminaries. In Section 3 we give the definition of IBEET scheme and its security notion. Then we present a concrete IBEET construction in Section 4 and its security proof in Section 5. In Section 6, we compare it with related works. Finally, Section 7 concludes the paper.

Section snippets

Preliminaries

Bilinear map. Let G1 and G2 be two multiplicative cyclic groups of prime order p. Suppose that g is a generator of G1. A bilinear map e:G1×G1G2 satisfies the following properties:

  • 1.

    Bilinear: For any gG1 and a,bZp,e(ga,gb)=e(g,g)ab.

  • 2.

    Non-degenerate: e(g, g) ≠ 1.

  • 3.

    Computable: There is an efficient algorithm to compute e(g, g) for any gG1.

Bilinear Diffie–Hellman (BDH) problem. Let G1,G2 be two groups of prime order p. Let e:G1×G1G2 be an admissible bilinear map and let g be a generator of G1. The

Identity-based encryption with equality test.

In identity-based encryption with equality test (IBEET), there are three roles: the users (including the sender and the receiver), the private key generator (PKG) and the cloud server (see Fig. 2). Any sender firstly encrypts sensitive data using the receiver’s public identity and stores it in the cloud server. At any time, the receiver can decrypt its ciphertexts using the decryption key according to its identity issued by the PKG. Some day, if the receiver wants to delegate the test

Constructions

In this section, we will provide a detailed construction for the IBEET scheme as follows:

  • 1.

    Setup: Given a security parameter kZ+, the algorithm works as follows:

    • (a)

      Generate the pairing parameters: two groups G1,G2 of prime order p, and an admissible bilinear map e:G1×G1G2. Choose a random generator gG1.

    • (b)

      Choose cryptographic hash functions: H1:{0,1}*G1,H2:GTG1,H3:GT{0,1}l1+l2 where l1 and l2 are security parameters such that elements of G1 are represented in l1 bits and elements of Zp are

Security

In this section, we prove that the above IBEET scheme is OW-ID-CCA secure (Fig. 3).

Theorem 2

LetA be an OW-ID-CCA adversary that has advantage ϵ(k) against IBEET. SupposeA makes at most qdk > 0 private decryption key queries, qtd > 0 trapdoor queries, qD > 0 decryption queries andqH1>0,qH2>0,qH3>0 queries to the hash functions H1, H2, H3, respectively. Then there is an algorithm that solves the BDH problem with advantage at leastϵ(k)/e(qdk+qtd+qD+1)(2qH2+qH3)((12l1+l2+12l1+12l1·12l1+l2)·(qH2+qH3)·qD+qD·

Comparison

In this section, we compare our construction with the following works for the reasons shown in Section 1.1:

  • 1.

    Yang et al. [36] proposed the first PKEET scheme.

  • 2.

    Abdalla et al. [2] firstly presented the notion of IBEKS and its generic transformation. Further, we use an anonymous HIBE [25] to instantiate this generic construction and then yield a concrete IBEKS scheme. (In reality, any other anonymous HIBE scheme [6], [27], [28] can be used for the instantiation.)

  • 3.

    Tang [33] and Ma et al. [21] provided

Conclusion

In this paper, we present a new cryptography tool: an identity-based encryption with equality test, which can be used for the outsourced computation on encrypted data in cloud computing. We define one-way chosen-ciphertext security against a chosen identity attack (OW-ID-CCA) and then propose a concrete construction in bilinear pairing. Finally we prove its security in the random oracle model under the BDH assumption.

Acknowledgment

This work is supported by the National Natural Science Foundation of China (no. 61402184)

References (40)

  • J. Byun et al.

    Off-line keyword guessing attacks on recent keyword search schemes over encrypted data

    Secure Data Management (SDM) 2006, Seoul, Korea

    (2006)
  • N. Cao et al.

    Privacy-preserving multi-keyword ranked search over encrypted cloud data

    IEEE Trans. Parallel Distrib. Syst.

    (2014)
  • R. Chen et al.

    A new general framework for secure public key encryption with keyword search

    20th Australasian Conference on Information Security and Privacy (ACISP 2015), Brisbane, QLD, Austrlia

    (2015)
  • T. Fuhr et al.

    Decryptable searchable encryption

    Provable Security 2007, Wollongong, Australia

    (2007)
  • K. Huang et al.

    PKE-AET: Public key encryption with authorized equality test

    Comput. J.

    (2015)
  • Y. Hwang et al.

    Public key encryption with conjunctive keyword search and its extension to a multi-user system

    Pairing-Based Cryptography (Pairing) 2007, Tokyo, Japan

    (2007)
  • L. Ibraimi et al.

    Public-key encryption with delegated search

    Applied Cryptography and Network Security(ACNS) 2011, Nerja, Spain

    (2011)
  • J. Katz et al.

    Predicate encryption supporting disjunctions, polynomial equations, and inner products

    J. Cryptol.

    (2013)
  • K. Lauter

    The advantages of elliptic curve cryptography for wireless security

    IEEE Trans. Wirel. Commun.

    (2004)
  • B. Lynn, Pairing based cryptography-benchmarks. http://crypto.stanford.edu/pbc/times.html (accessed...
  • Cited by (158)

    View all citing articles on Scopus
    View full text