Printer Friendly

Novel multi-user conjunctive keyword search against keyword guessing attacks under simple assumptions.

Abstract

Conjunctive keyword search encryption is an important technique for protecting sensitive personal health records that are outsourced to cloud servers. It has been extensively employed for cloud storage, which is a convenient storage option that saves bandwidth and economizes computing resources. However, the process of searching outsourced data may facilitate the leakage of sensitive personal information. Thus, an efficient data search approach with high security is critical. The multi-user search function is critical for personal health records (PHRs). To solve these problems, this paper proposes a novel multi-user conjunctive keyword search scheme (mNCKS) without a secure channel against keyword guessing attacks for personal health records, which is referred to as a secure channel-free mNCKS (SCF-mNCKS). The security of this scheme is demonstrated using the Decisional Bilinear Diffie-Hellman (DBDH) and Decision Linear (D-Linear) assumptions in the standard model. Comparisons are performed to demonstrate the security advantages of the SCF-mNCKS scheme and show that it has more functions than other schemes in the case of analogous efficiency.

Keywords: Personal health records, Conjunctive keyword search, Search policy, Channel free, Keyword guessing attacks, Multi-user

1. Introduction

Cloud computing has the advantages of dynamic expansion, on-demand service and billing quantity; this computing resource represents one of the most important information technology revolutions since the invention of the Internet [1]. With the development of cloud computing, personal health records (PHRs) have emerged as a patient-centric model of health information exchange, and architectures for storing PHRs in the cloud have been proposed [2]. However, numerous issues regarding PHR services must be investigated: 1. How can communication be secured between different PHR clouds? To resolve this problem, Amjad Mehmood et al. [3] proposed a secure multi-agent-based framework for communication among open clouds. In their framework, each cloud has a secure mobile agent that is responsible for secure communication among the cloud servers. 2. How can authentication technology be integrated into the cloud environment to protect PHRs? To resolve this problem, Ismail Butun et al. [4] proposed cloud-centric, multi-level authentication as a service approach that addresses scalability and time constraints and demonstrated its effectiveness. 3. How can the problem of information wireless transmission among a large number of users be resolved? To resolve this problem, Mohammad Shojafar et al. [5] applied learning automata for channel assignment in multi-radio wireless mesh networks (WMNs).

A PHR service enables a patient to create, manage, and control his or her personal health data in one location accessed via the web; this approach has facilitated the efficient storage, retrieval, and sharing of medical information. However, due to the high cost of building and maintaining specialized data centres, many PHR services are outsourced or provided by third-party service providers. To guarantee the security of their sensitive personal health information (PHI), patients should adopt encryption for their PHI before storing it in the cloud.

However, encryption may severely hinder several functionalities that users are accustomed to receiving from cloud solutions. For instance, searches for a data owner's outsourced encrypted data would not be possible with encryption. Therefore, to retrieve specific data from the stored data, the cloud provider must be able to search encrypted documents. One solution for this problem is the use of searchable encryption schemes, which enable users to securely execute the search operation on remote data stored on a third party's server. In a cloud computing service, PHI is shared among public users. Thus, searchable encryption should enable multi-users to search for PHI. Therefore, the construction of efficient multi-user searchable encryption is important and challenging.

In the literature, two categories of searchable encryption schemes can be considered: the symmetric key and the public key. Song et al. [6] proposed the first scheme, which enables searchability in symmetric encryption, whereas Boneh et al. [7] introduced the second scheme, which enables public key encryption with keyword search (PEKS). For a network with too many users, the PEKS option is more adaptive than symmetric key searchable encryption.

For example, assume that Bob is a patient who wishes to send his PHI to his doctor, Alice. Bob can establish keywords for his PHI and use Alice's public key to encrypt his PHI and keywords; the encrypted data are sent in the following form:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

where [A.sub.pub] is Alice's public key and [kw.sub.1],[kw.sub.2],[??],[kw.sub.n] are the keywords that Bob establishes. When Alice wants to search the encrypted documents with the keyword W, she generates a trapdoor containing W and sends it to the server. The server locates the corresponding encrypted documents by comparing the trapdoor and the keyword ciphertexts and returns them to Alice. Although the initial security model of PEKS cannot achieve this result because the user can only use one keyword to search the encrypted documents, the ability to use more than one keyword to search a large amount of data can reduce the search scope and improve the query performance. Therefore, Golle et al. [8] proposed secret key encryption with a conjunctive field keyword search scheme in 2004. These authors assumed that m documents and n keyword fields are associated with each document. In 2005, Park et al. [9] presented a conjunctive keyword search scheme based on bilinear paring in the public key cryptosystem; it is named the public key encryption with conjunctive field keyword search (PKCKS). Zhang et al. [10] constructed a public key encryption with conjunctive-subset keywords search algorithm that enables users to list keywords in any order. Sun et al. [11, 12] presented the first verifiable conjunctive keyword search schemes for static and dynamic databases. The verifiable mechanism ensures that the search results are correct and complete.

The limitation in the schemes presented above is that they may require a secure channel between the receiver and the server. Heavy computational and communication loads, such as a Secure Sockets Layer (SSL) between the server and the receiver, are typically required to establish a secure channel. To address this problem, Baek et al. [13] considered removing the secure channel and proposed public key encryption with a keyword search scheme, which is a secure channel-free PEKS (SCF-PEKS). The basic concept of a SCF-PEKS scheme is that the server maintains its public and private key pairs. Whenever the data owner generates the keyword ciphertexts, he inputs the server's public key in the algorithm, and only the corresponding private key can execute the Test algorithm in the SCF-PEKS scheme. Rhee et al. [14] strengthened the security model [13] of Baek. However, these schemes can only achieve security in the random oracle model. In another study [15], the secure channel was removed, and the heavy computational and communication loads required to establish a secure channel were resolved.

Without the protection of a secure channel, Byun et al. [16] indicated that the scheme proposed by Baek may be attacked by off-line keyword guessing attacks. Because keywords are chosen from a substantially smaller space than passwords, users usually include well-known keywords for searching documents. Even if the keywords have been encrypted, the attackers can learn the embedded keywords by performing off-line keyword guessing attacks. Inspired by the work of Byun et al. [16], Yau et al. [17] presented an off-line keyword guessing attack on the SCF-PEKS [13] and PKE/PEKS [18] schemes. Rhee et al. [19] constructed a new secure SCF-PEKS scheme against keyword guessing attacks in the random oracle model. Unfortunately, a proof in the random oracle model can only serve as a heuristic argument, and because of the use of contrived constructions, it may generate unsecure schemes when the random oracles are implemented in the standard model [20]. Hwang et al. [21] proposed an efficient secure channel-free public key encryption with a conjunctive field keyword search scheme that can secure against off-line keyword-guessing attacks. Guo et al. [22] proposed an efficient secure channel-free public key encryption with a keyword search scheme that has been shown to be secure in the standard model. We demonstrate that our SCF-PEKS scheme is secure not only against chosen keyword and ciphertext attacks but also against keyword-guessing attacks. Yang et al. [23] proposed a scheme that supports the conjunctive keyword search and resists keyword-guessing attacks. However, this SCF-PECKS scheme uses a significantly complex assumption called the Decisional q-Augmented Bilinear Diffie-Hellman Exponent (q-ABDHE). Miao et al. [24] proposed a significantly more effective and secure cryptographic primitive, called a verifiable conjunctive keyword search over encrypted data without secure channel scheme, to secure against an outside keyword-guessing attack. The combination of artificial intelligence algorithms and file search algorithms can also improve the efficiency of the search algorithm [25] and represents a key research direction.

These scenarios specified a search user; thus, only a single user can search the ciphertext. In the PHR system, the patient Bob uses surgeon Alice's public key to encrypt his PHI and keywords, which enables Alice to search Bob's PHI. However, when pharmacist Lucy must fill a prescription for Bob, she cannot search Bob's PHI. A familiar approach is that Bob encrypts his PHI and keywords again with Lucy' s public key; however, this method is inefficient and consumes a significant amount of system storage resources. Therefore, a multi-user search is critical for PHR systems. To solve this problem, Hwang et al. [26] designed a PECKS based on a bilinear map and extended their scheme to a multi-user system, which is the first security model for multi-user public key encryption with a conjunctive keyword search (mPECKS) scheme that requires a secure channel.

Based on this analysis, the conjunctive keyword search scheme for PHRs should achieve the following objectives: remove the secure channel, secure against keyword-guessing attacks, and employ simple assumptions without a random oracle and multi-user conjunctive keyword search. According to these objectives, we propose a novel multi-user conjunctive keyword search scheme (mNCKS) without a secure channel for PHRs, which is referred to as a secure channel-free mNCKS (SCF-mNCKS). This scheme can secure against keyword-guessing attacks. By referencing the access structure [27] of ciphertext policy attribute-based encryption (CP-ABE) [28], the patient constructs the search policy using the keywords of the data files to encrypt the data files and then uploads the ciphertext to the servers. The keyword set L is used to search the data files, and an attribute authority then generates a trapdoor for the users. Users send the trapdoor to the server. If the ciphertext can be successfully tested, the users should obtain the desired data; otherwise, the search fails. A detailed description of this process is provided in Section 3.1.

We propose an efficient mechanism for removing the secure channel. A patient's smart phone is connected to the cloud server provider (CSP) via an unsecure communication channel, such as a GPRS network. The basic concept is for the server to maintain its private and public key pairs. To create a ciphertext, the data owner uses the public keys of the server and the receiver. The receiver can then send a trapdoor to retrieve data associated with the keyword list and send it via a public channel. After receiving the trapdoor, the server can test whether the provided ciphertexts match the trapdoor using its private key. The security of this scheme is verified based on the Decisional Bilinear Diffie-Hellman (DBDH) and Decision Linear (D-Linear) assumptions in the standard model. The scheme comparison shows that the SCF-mNCKS scheme has advantages with respect to security and other functions.

The remainder of this paper is organized as follows: In Section 2, definitions are provided, and we describe the system and security model. In Section 3, we propose the concrete SCF-mNCKS scheme and analyse the security of the proposed generic construction. In Section 4, we describe the performance comparison. In Section 5, we present the conclusions and describe future work.

2. Definitions

In this section, we review the bilinear maps and the computational hardness assumptions and provide the definitions of the proposed construction and selective game model.

2.1 Bilinear Maps

We present a few facts concerning groups with efficiently computable bilinear maps. Assume the efficient algorithm [product] for generating bilinear groups. Through input of a security parameter k, the algorithm [product] outputs a tuple: G = [p,G,[G.sub.T],g [member of] G, e], where G and [G.sub.T] are multiplicative groups of prime order p ; g is a generator of G ; and e is the bilinear map e: G x G [right arrow] [G.sub.T]. The parameter e(g, g) is the generator of [G.sub.T], and [Z.sub.p] represents a group of large prime order p. The bilinear map e has the following properties:

* Bilinearity: For all x, y [member of] G and a, b [member of] [Z.sub.p], e([x.sup.a], [y..sup.b]) = e[(x, y).sup.ab];

* Non-degeneracy: e(g, g) [not equal to] 1, where 1 is the identity element of [G.sub.T].

We state that G is a bilinear group if the group operation in G and the bilinear map e: Gx G [right arrow] [G.sub.T] are efficiently computable.

2.2 Complexity Assumptions

Definition 1: DBDH Assumption. Let a,b, c, z [member of] [Z*.sub.p] be chosen at random, and let g be a generator of G. The DBDH problem in G and [G.sub.T] is a problem, and the tuple {g, [g.sup.a], [g.sup.b], [g.sup.c], Z} should be input to determine whether Z = e[(g,g).sup.abc]. The algorithm H has the advantage [epsilon] in solving the DBDH problem in G and [G.sub.T] if

[Adv.sup.DBDH.sub.H]([lambda]) :=| Pr|[H(g, [g.sup.a],[g.sup.b], [g.sup.c],e[(g,g).sup.abc]) = 1] -Pr[H(g, [g.sup.a], [g.sup.b], [g.sup.c], e[(g, g).sup.z] = 1] |[greater than or equal to] [epsilon]([lambda]) (2)

where e[(g, g).sup.z] [member of] [G.sub.T] \{e[(g, g).sup.abc]} and [lambda] is the security parameter. We state that the DBDH assumption holds in G if no probabilistic polynomial time (PPT) algorithm has an advantage of at least [epsilon] in solving the DBDH problem in G.

Definition 2: D-Linear Assumption. Let [z.sub.1], [z.sub.2], [z.sub.3], [z.sub.4], z [member of] [Z*.sub.p] be chosen at random, and let g [member of] G be a generator. The D-Linear problem in G is a problem, and the tuple [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] should be input to determine whether [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The algorithm H has the advantage [epsilon] in solving the D-Linear problem in G if

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [lambda] is the security parameter. We state that the D-Linear assumption holds in G, if no PPT algorithm has an advantage of at least [epsilon] in solving the D-Linear problem in G.

2.3 Definition of SCF-mNCKS

SCF-mNCKS contains six polynomial time algorithms: GlobalSetup, AASetup, [KeyGen.sub.CSP], EncIndex, Trapdoor and Test. These algorithms are presented as follows:

GlobalSetup([1.sup.[lambda]]): The algorithm is executed by the trusted authority centre (AC) and it takes the security parameter [lambda] as input. The AC generates the global parameter GP. Specifically, GP [left arrow] GlobalSetup([1.sup.[lambda]]).

AASetup(GP, U): The algorithm takes the global parameter GP and keyword set U as inputs. The algorithm returns PK and MSK as the attribute authority's (AA) public key and master private key, respectively. Specifically, < PK,MSK >[left arrow] AASetup(GP, U).

[KeyGen.sub.csp](GP): The algorithm takes the global parameter GP as input and returns [pk.sub.CSP] and [sk.sub.CSP] as the cloud service provider's (CSP) public key and private key, respectively. Specifically, <[pk.sub.CSP], [sk.sub.CSP] >[left arrow] [KeyGen.sub.CSP](GP).

EncIndex(GP,PK, [pk.sub.CSP], W): The algorithm takes the global parameter GP, AA's public key PK, a CSP's public key [pk.sub.CSP] and the search policy W based on keywords as inputs. The algorithm returns the ciphertext CT. Specifically, CT [left arrow] EncIndex(GP,PK,[pk.sub.CSP],W).

Trapdoor (GP,[pk.sub.CSP], MSK, L). The algorithm takes the global parameter GP, a CSP's public key [pk.sub.CSP], AA's master private key MSK and the keyword list L as inputs and outputs a trapdoor [TD.sub.L]. Specifically, [TD.sub.L] [left arrow] Trapdoor(GP,[pk.sub.CSP],MSK,L).

Test(GP,[sk.sub.CSP],CT,[TD.sub.L]): The algorithm takes the global parameter GP, the CSP's private key [sk.sub.CSP], the ciphertext CT and the trapdoor [TD.sub.L] as inputs and determines whether L satisfies W If L satisfies W, then "Correct" [left arrow]Test(GP,[sk.sub.CSP],CT,[TD.sub.L]).

2.4 Game-Based Security Model

Computational consistency was introduced in [29] and represents a crucial security requirement. To discuss the definitions, we describe the following experiment with the adversary A.

Definition 3: Consistency. Assume that adversary A wants to cause a failure in consistency. Consistency is formally defined as follows:

Setup: The simulator B executes GlobalSetup([1.sup.[lambda]]), AASetup(GP,U) and [KeyGen.sub.CSP](GP).

Phase 1: A submits a keyword list L and a search policy W based on keywords, where L|[not equal to]W. Then, EncIndex(GP,PK,[pk.sub.CSP],W) and Trapdoor(GP,[pk.sub.CSP],MSK,L) are executed.

Challenge: Test(GP,[sk.sub.CSP],CT,[TD.sub.L])is executed, where L|[not equal to]W.

Guess: If "Correct" [left arrow] Test(GP, [sk.sub.CSP],CT,[TD.sub.L]), then A wins the game.

The advantage of A is defined as [Adv.sup.cons.sub.A]([lambda]):=Pr["Correct" [left arrow] Test(GP,[sk.sub.CSP],CT,[TD.sub.L])]. The SCF-mNCKS scheme is computationally consistent if the advantage for all polynomial time adversaries A to win in this experiment is negligible.

Compared with traditional conjunctive keyword searches, our scheme is based on CP-ABE; therefore, the security model must be redefined. According to the definition of the CP-ABE security model and the characteristics of our scheme, this paper presents a new security game model for our conjunctive keyword search. We formally define the game-based security of SCF-mNCKS, which we refer to as "indistinguishability of secure channel free against chosen keyword attack (IND-CF-CKA)". Informally, IND-CF-CKA guarantees that the CSP, which has not obtained the trapdoors for given keywords, cannot distinguish the correspondence of the ciphertext and keywords. The outside attacker that has not obtained the CSP's private key cannot make any decisions concerning the ciphertexts even if they obtain all trapdoors for the keywords that it holds. Note that the attack models for these two types of attackers are described as [Game.sub.CSP] and [Game.sub.OA]. In the SCF-mNCKS security game, the following scenario will occur; this definition is formalized according to a security game between any PPT adversary and a simulator.

Definition 4: IND-CF-CKA. Let [lambda] be the security parameter and A be the adversary. We consider the following two games between A and the simulator B :

[Game.sub.CSP] : A is assumed to be a CSP.

Init: The adversary A sends the challenge search policies [W.sub.0] and [W.sub.1] based on the keywords to the simulator.

Setup: The simulator executes GP [left arrow]GlobalSetup([1.sup.[lambda]]), <PK,MSK >[left arrow] AASetup(GP,U) and <[pk.sub.CSP],[sk.sub.CSP] >[left arrow] [KeyGen.sub.CSP](GP) to obtain the global parameter GP. The public key and master private key pairs (PK,MSK) of AA are calculated. The public and private key pairs ([pk.sub.CSP],[sk.sub.CSP]) of CSP are set. Then, B provides ([pk.sub.CSP],[sk.sub.CSP]) and PK to A.

Phase 1: A submits a keyword list L in a trapdoor query [TD.sub.L] = Trapdoor (GP,[pk.sub.CSP],MSK,L), where L |[not equal to] [W.sub.0] [??] L |[not equal to] [W.sub.1]. The simulator answers with a trapdoor for the keyword list L. Note that these queries can be adaptively repeated.

Challenge: The simulator chooses w[member of]{0,1} and executes CT[left arrow]EncIndex(GP,PK,[pk.sub.CSP],[W.sub.w]). The simulator provides the ciphertext CT to A.

Phase 2: Same as Phase 1. A sends L' to the simulator for a query. The simulator answers with a trapdoor for the keyword list. Notice that L' | [not equal to] [W.sub.0] [??] L' | [not equal to] [W.sub.1].

Guess: A outputs guess w' [member of] {0,1}. A wins if w' = w.

The advantage of A is defined as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

[Game.sub.OA]: A is assumed to be an outside attacker (including the receiver).

Setup: The simulator executes GP [left arrow]GlobalSetup([1.sup.[lambda]]), <PK,MSK >[left arrow] AASetup(GP,U) and <[pk.sub.CSP],[sk.sub.CSP] >[left arrow][KeyGen.sub.CSP](GP) to obtain the global parameter GP. The public key and master private key pairs (PK, MSK) of AA are calculated. The public and private key pairs ([pk.sub.CSP], [sk.sub.CSP]) of CSP are set. Then, B provides PK and [pk.sub.CSP] to A.

Phase 1: A submits a keyword list L in a trapdoor query [TD.sub.L] = Trapdoor(GP,[pk.sub.CSP],MSK,L). The simulator answers with a trapdoor for the keyword list L. Note that these queries can be adaptively repeated.

Challenge: A sends the two challenge search policies [W.sub.0] and [W.sub.1] based on the keywords to the simulator. The simulator chooses w [member of]{0,1} and executes CT [left arrow] EncIndex(GP,PK, [pk.sub.CSP],[W.sub.w]). The simulator provides the ciphertext CT to A.

Phase 2: Same as Phase 1. A sends L' to the simulator for a query. The simulator answers with a trapdoor for the keyword list. In contrast to [Game.sub.CSP], L' | = [W.sub.0] [??] L' | = [W.sub.1] is allowed to be queried as a trapdoor query.

Guess: A outputs guess w' [member of] {0,1}. A wins if w' = w.

The advantage of A is defined as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Our SCF-mNCKS scheme is said to be IND-CF-CKA secure if [Adv.sup.Game.sub.A] ([lambda]) is negligible, where i is either CSP or OA.

In the following section, we define the notion of indistinguishability of SCF-mNCKS against a keyword-guessing attack (IND-KGA). Specifically, IND-KGA ensures that an outside adversary (neither the server nor the receiver) that has obtained the trapdoor for a challenge keyword cannot observe the relationship between the trapdoor and any keywords.

Definition 5: Off-Line Keyword-Guessing Attacks on SCF-mNCKS.

Because a trapdoor is sent without a secure channel, an outside adversary is capable of capturing the trapdoor and performing off-line keyword-guessing attacks. The attacker may reveal the encrypted keyword list L that is used by the receiver to search for a document. Similarly, an inside adversary (malicious server) can perform the attack to reveal the keyword in the trapdoor and execute the Test algorithm to determine the ciphertext that contains the keyword list. However, the outside adversary is unable to distinguish ciphertexts from encrypting a specific keyword list because the Test phase requires the server's private key.

A SCF-PEKS scheme that is secure against keyword-guessing attacks, where the attacker is the server, cannot be constructed [30]. Therefore, in this work, we do not consider the keyword-guessing attacks of an inside adversary.

3. SCF-mNCKS Scheme

3.1 Search Policy for Ciphertext

In the CP-ABE scheme, an encryptor specifies an access structure for a ciphertext, which is referred to as an access structure. If a decryptor has the secret key whose associated set of attributes satisfies the access structure, he or she can decrypt the ciphertext.

The access structure and the attribute set that are associated with the secret key in [27] are as follows: Let us assume that the set of attributes in universe U = {[att.sub.1],[att.sub.2],***,[att.sub.n]} contains n attributes. Each attribute [att.sub.i] can take two values: 1 and 0. Assume that L = [[L.sub.1],[L.sub.2],***,[L.sub.n]] is a set of attributes for a user, and it is called the attribute list. AA generates a secret key for the user based on the user's attribute list. Assume that W = [W.sub.1],[W.sub.2],***,[W.sub.n] is an access policy to specify the access structure for a ciphertext. Formally, the attribute list L = [[L.sub.1],[L.sub.2],***,[L.sub.n]] for a user and the access policy W = [[W.sub.1],[W.sub.2],***,[W.sub.n]] for a ciphertext are given. For all i where 1 [less than or equal to] i [less than or equal to] n, if [L.sub.i] = [W.sub.i] or [W.sub.i] = *, L satisfies W, which is represented by the notation L |= W . Otherwise, L does not satisfy W, which is represented by the notation L |[not equal to] W. The wildcard * can be used in the ciphertext policies and represents the function of a "do not care" value, which can be considered as an AND-gate on all the attributes. For instance, we can let W = [[W.sub.1],[W.sub.2],***,[W.sub.n]] = [0,*,1,*,1,0], where n = 6. If a user has the attribute list L = [0,1,1,0,1,0], he can obtain a secret key associated with [0,1,1, 0,1, 0] and decrypt the ciphertext encrypted with [0,*,1,*,1,0] but not if the secret key is associated with [0,1,1,0,1,1] .

Compared with the access structure of [27], we let U = {[kw.sub.1],[kw.sub.2],***,[kw.sub.n]} represent the set of keywords of data files that replace the attributes. W is the search policy based on the keywords. For all i where 1 [less than or equal to]i[less than or equal to]n, each keyword [kw.sub.t] can take two or more values. More formally, assume that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the set of all possible values for [kw.sub.i], where [n.sub.i], is the number of the possible values for [kw.sub.i], specifically [n.sub.i] =|[S.sub.i]|. When the encryptor specifies a wildcard * for [W.sub.i], this action corresponds to specifying [W.sub.i] =[S.sub.i]. We achieve keyword privacy by hiding the subset [W.sub.i] for each keyword [kw.sub.i] that is specified in the access structure of the AND-gate of all keywords.

For a PHR system, assume U = {[kw.sub.1],[kw.sub.2],[kw.sub.3],[kw.sub.4],[kw.sub.5]}={name,sex,medicalhistory,examination, sensitiveinfo}, n = 5 ; [S.sub.1] = {[[nu].sub.11],[[nu].sub.12],[v.sub.13]}={Zhang,Wang,Li}, [n.sub.1] = 3 ; [S.sub.2] = {[[nu].sub.2,1], [[nu].sub.2,2]} = {male, female}, [n.sub.2] = 2; [S.sub.3] = {[[nu].sub.3,1],[[nu].sub.3,2],[v.sub.3,3]}={conditions, allergies, prescriptions}, [n.sub.3] = 3; [S..sub.4] = {[[nu].sub.4,1], [[nu].sub.4,2], [[nu].sub.4,3], [[nu].sub.4,4]}= {pulse,heart, blood test, X-ray images}, [n.sub.4] = 4 ; and [S.sub.5] = {[[nu].sub.5,1], [[nu].sub.5,2]} = {HIV, none}, [n.sub.5] = 2. We assume that the search policy W is Zhang [??] (male [??] female) [??] allergies [??] (pulse [??] heart) [??] none and use W to generate the index. When receivers use L=[Zhang, male, allergies, heart, none] to the search data file M, they can obtain the correct result. Receivers cannot obtain the correct result when they use L=[Li, male, allergies, heart, HIV] to search the data file.

3.2 Concrete Scheme

The six algorithms are as follows:

GlobalSetup([1.sup.[lambda]]): The algorithm is executed by a trusted authority centre and based on the security parameter [lambda]. The authority centre generates the tuple G = [p,G,[G.sub.T],g [member of] G,e] where g is the generator of G. The global parameter is GP = (p,G,[G.sub.T],g,e).

AASetup(GP, U) : Uniformly and randomly choose y[member of][Z*.sub.p] and compute Y = e[(g, g).sup.y]. For each keyword [kw.sub.i] [member of]U, where 1 [less than or equal to]i [less than or equal to]n, AA chooses random values [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and random points [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Return [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and MSK = (y, [a.sub.i,t],[b.sub.i,t]) as the AA's public key and master private key, respectively, where 1 [less than or equal to] i [less than or equal to] n and 1 [less than or equal to] t [less than or equal to] [n.sub.i].

[KeyGen.sub.CSP](GP) : Uniformly and randomly choose [beta] [member of] [Z*.sub.p] and compute B = [g.sup.[beta]]. Return [pk.sub.CSP] = (GP,B) and [sk.sub.CSP] = (GP,[beta]) as the CSP's public key and private key, respectively.

EncIndex(GP,PK,[pk.sub.CSP],W): Choose a search policy based on the keywords W = [[W.sub.1],***,[W.sub.n]]. The data owner selects the random value s [member of] [Z*.sub.p] and computes C = [Y.sup.s] = e[(g, g).sup.ys] and [C.sub.0] = [B.sup.s] = [g.sup.[beta]s]. For 1 [less than or equal to] i [less than or equal to] n, the data owner selects random values [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as follows: if [v.sub.i,t], [member of] [W.sub.t], the data owner sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (well-formed); if [v.sub.i,t] [??] W and [[C.sub.i,t,1],[C.sub.i,t,2]] are random (malformed), then the keyword ciphertext is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Trapdoor(GP,[pk.sub.CSP],MSK,L): The user that uses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for searching can obtain the corresponding secret key, which is regarded as the searching trapdoor. For 1 [less than or equal to]i[less than or equal to]n, AA selects random values [r.sub.i], [[lambda].sub.i] [member of] [Z*.sub.p], sets r = [n.summation over (i=1)] [r.sub.i], and computes [D.sub.0] = [g.sup.(y-r)]. Then, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are computed by AA. The searching trapdoor is [[TD.sub.L]=([D.sub.0],[{[D.sub.i,0],[D.sub.i,1],[D.sub.i,2]}].sub.1[less than or equal to]i[less than or equal to]n]).

Test(GP,[sk.sub.CSP],CT,[TD.sub.L]): The data user sends the searching trapdoor [TD.sub.L] to the CSP to implement the search request. The CSP executes the algorithm to verify whether the data user that corresponds to the keyword list L satisfies the search policy W. If L satisfies W, then CSP computes [C'.sub.0] =[C.sup.1/[beta].sub.0]. For 1[less than or equal to]i[less than or equal to]n, we let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If equation (4) holds, then return "Correct"; otherwise, return "Incorrect".

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

Correctness. In the following, we show that a correctly generated ciphertext can be correctly tested by the CSP who has the correct trapdoor. Let the ciphertext [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which is associated with search policy W = [[W.sub.1],[W.sub.2],***,[W.sub.n]], be based on keywords. The trapdoor is [[TD.sub.L] = ([D.sub.0], [{[D.sub.i,0], [D.sub.i,1], [D.sub.i,2]}].sub.1[less than or equal to]i[less than or equal to]n]). This process produces the following equation:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

3.3 Security Analysis

Theorem 1. Our SCF-mNCKS scheme is computationally consistent.

Proof: Assume that a polynomial-time adversary A can attack the computational consistency of our scheme. Let (W, L) denote the search policy based on keywords and the keyword list for a user, which A returns in the consistency experiment. Without a loss of generality, assume that L does not satisfy W.

Select a random value s [member of] [Z*.sub.p]. Let C = [Y.sup.s] = e[(g, g).sup.ys] and [C.sub.0] = [B.sup.s] = [g.sup.[beta]s]. For 1 [less than or equal to] i [less than or equal to] n, the data owner picks random values [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as follows: if [v.sub.i,t] [member of] [W.sub.i], then the data owner sets are [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (well-formed); if [v.sub.i,t] [??] [W.sub.i], then [[C.sub.i,t,1], [C.sub.i,t,2]] are random (malformed). Let [TD.sub.L] = ([D.sub.0],[{[D.sub.i,0], [D.sub.i,1], [D.sub.i,2]}.sub.1[less than or equal to]i[less than or equal to]n]) where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For 1 [less than or equal to]i[less than or equal to]n, AA selects random values [r.sub.i],[[lambda].sub.i],[member of] [Z*.sub.p] and sets r = [n.summation over (i=1)] [r.sub.i]. Note that A wins exactly when L does not satisfy W if formula (7) is established.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Assume that [L.sub.k][??] [W.sub.k], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

Because [Z.sub.1] and [z.sub.1] are random, [z.sub.k] and s are kept secret from the receiver. Therefore, Pr[[Z.sub.1] [z.sub.1] = [z.sub.k]s] = 1/([p.sup.2] - p), where p -1 is the total element number in [Z*.sub.p]. As previously described, when L [??] W and "Correct" [left arrow] Test(GP, [sk.sub.CSP], CT, [TD.sub.L]), the following result is obtained:

[Adv.sup.cons.A]([lambda]) = Pr[[z.sub.1][z.sub.2] = [z.sub.k]s] [less than or equal to]1/([p.sup.2]-p) (9)

We previously discussed the security analysis of the SCF-mNCKS with a single authority approach and provided proof using the DBDH and D-Linear assumptions. The analysis of [Game.sub.CSP] and [Game.sub.OA] is as follows:

Theorem 2: SCF-mNCKS satisfies the indistinguishability of keywords using the DBDH and D-Linear assumptions in [Game.sub.CSP].

Assume that adversary A commits to the challenge search policies [W.sub.0] and [W.sub.1] at the beginning of the game. We employ the notation [W.sub.w] = [W.sub.w,1], [W.sub.w,2], ***,[W.sub.w,n]. The proof uses a sequence of hybrid games to argue that adversary A cannot win the original security game denoted by [G.sub.0] with non-negligible probability. We begin by slightly modifying game [G.sub.0] into game [G.sub.1]. Games [G.sub.0] and [G.sub.1] are identical, with the exception of how the challenge ciphertext is generated. In [G.sub.1], if adversary A did not obtain the [TD.SUB.L], whose associated keyword list L is such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then the challenge ciphertext component CT is a random element of [G.sub.T], regardless of the random coin u. The remainder of the ciphertext is generated as usual. If the adversary obtained the [TD.SUB.L] whose associated keyword list L is such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then the challenge ciphertext in [G.sub.1] is generated correctly ([G.sub.0] =[G.sub.1] in this case).

Next, we modify [G.sub.1] by changing the manner of generating the components [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and define a sequence of the games as follows: If [v.sub.i,t] exists such that ([v.sub.i,t] [member of] [W.sub.0,i] [and] [v.sub.j,t] [??] [W.sub.1,i]) or ([v.sub.i,t] [??] [W.sub.0,i] [and] [v.sub.j,t] [member of] [W.sub.1,i]), then the components {[C.sub.i,t,1], [C.sub.i,t,2]} that are properly generated in game [G.sub.l - 1] are replaced with the random values in the new modified game [G.sub.1] regardless of the random coin u. We define a new game when this replacement occurs. We repeat this replacement one by one until no components satisfy ([v.sub.i,t] [member of] [W.sub.0,i] [and] [v.sub.j,t] [??] [W.sub.1,i]) or ([v.sub.i,t] [??] [W.sub.0,i] [and] [v.sub.j,t] [member of] [W.sub.1,i]). In the last game of the sequence, the advantage of the adversary is zero because the adversary is given a ciphertext that is chosen from the same distribution regardless of the random coin u. Thus, we obtain the indistinguishability of ciphertext by constantly modifying the games.

Lemma 1: The advantage of distinguishing game [G.sub.0] and game [G.sub.1] is negligible for any PPT adversary A using the DBDH assumption.

Proof: Given the DBDH challenge tuple [g, [g.sup.a], [g.sup.b], [g.sup.c], Z] by the simulator, where Z is either [(g,g).sup.abc] or random with equal probability. We let v [member of]{0,l}. If v = 0, then Z = e[(g,g).sup.abc]; if v = 1, then Z = e[(g,g).sup.z]. Assume that the PPT adversary A exists who distinguishes game [G.sub.0] and game [G.sub.1] with the non-negligible advantage [epsilon]. Thus, we can construct the simulator B that will break the DBDH assumption with the advantage [epsilon] / 2. Then, the simulator B creates the following simulation:

Init: A gives B the two challenge search policies [W.sub.0] = [[W.sub.0,1], ***, [W.sub.0,n]] and [W.sub.1] = [W.sub.1,1], ***, [W.sub.1,n] based on the keywords.

Setup: Let [lambda] be the security parameter and GP = (p,G,[G.sub.T], g, e) be the global parameter. B selects w [member of] {0,1} and sets [W.sub.w] = [W.sub.w,1], [W.sub.w,2], ***, [W.sub.w,n]. B selects [delta] [member of] [Z*.sub.p] and computes B = [g.sup.[delta]]. Establish [pk.sub.CSP]=(GP,B) and [sk.sub.CSP] = (GP,[delta]) as the CSP's public key and private key, respectively. Compute Y = e([g.sup.a], [g.sup.b]) = e[(g, g).sub.ab], which implies y = ab. For each keyword k[w.sub.i] where 1[less than or equal to]i[less than or equal to]n, B randomly chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If [v.sub.i,t] [??] [W.sub.w,i], then B generates [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], if [v.sub.i,t] [??] [W.sub.w,i], then B generates [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] selects [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] at random for each keyword k[w.sub.i]. Let PK = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and MSK = (y, [a.sub.i,t] [??] [b.sub.i,t]) represent AA's public key and master private key, respectively, where 1[less than or equal to]i[less than or equal to]n and 1[less than or equal to]t[less than or equal to][n.sub.i]. Then, B provides (PK,p[k.sub.CSP],s[k.sub.CSP]) to A.

Phase 1: A submits the keyword list [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in a trapdoor query. We only consider the case where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. When [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], B simply aborts and takes a random guess.

When [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] must exist such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For 1[less than or equal to]i[less than or equal to]n, B selects [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] at random. B then sets [r.sub.k]=ab + [r.sup'.sub.i]. For every i [not equal to] k, B sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. B sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [D.sub.0] can be computed as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For k, [[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]] is computed as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

where [[lambda].sub.k] is chosen at random such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and random [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is known by B. B can easily compute the components [[D.sub.k,1],[D.sub.k,2]]. For i [not equal to] k, B can also easily compute [[D.sub.i,0], [D.sub.i,1], [D.sub.i,2]]. Therefore, all valid components of TDL have been constructed.

Challenge: The simulator B calculates C = Z and C0=[B.sup.c] = [g.sup.[delta]c]. When [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], B can correctly generate {[C.sub.i,t,1], [C.sub.i,t,2]} because [A.sub.i,t] does not contain an unknown a. When [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], {[C.sub.i,t,1], [C.sub.i,t,2]} can be chosen at random, and then B sends [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to A.

Phase 2: A continues issuing queries to oracle Trapdoor to receive the trapdoor of keyword list L such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where w [??] {0,1}.

Guess: A outputs the guess w' [??] {0,1}. B outputs 0 if w' = w or 1 if w' [not equal to] w. Two cases are observed as follows:

* If Z = e[(g, g).sup.abc], v = 0. Then, A is in the original game G0. The advantage of A is [epsilon] ; thus, Pr[w' = w| v = 0] = 1/2+[epsilon]. When w' = w, B outputs v'=O. We have Pr[v' = v| v = 0] = 1/2 + [epsilon].

* If Z = e[(g, g).sup.z], v = 1. Then, A is in the modified game [G.sub.1]. A has no advantage to distinguish bit w ; thus, Pr[w' [not equal to]w|v = 1] = 1/ 2. When w' [not equal to] w, B outputs v' = 1. We have Pr[v'= v| v = 1] = 1/2.

Therefore, we know that the advantage of B in this DBDH game is as follows: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

Lemma 2: The advantage of distinguishing game [G.sub.l-1] and game [G.sub.l] is negligible for any PPT adversary A using the D-Linear assumption.

Proof: Given a D-Linear challenge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by the simulator, where Z is either [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] or random with equal probability. Let v [??] e{0,1}. If v = 0, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; otherwise, Z is random. We assume that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] without a loss of generality. Assume that the PPT adversary A exists who distinguishes the game [G.sub.l-1] and game [G.sub.l] with the non-negligible advantage [epsilon]. We build an algorithm B that can simulate the game with the advantage [epsilon]/2. Then, the simulator B creates the following simulation.

Ink: The simulator B executes A. A provides B two challenge search policies based on the keywords [W.sub.0]=[[W.sub.0,1],[W.sub.0,2],[??],[W.sub.0,n]] and [W.sub.1]=[[W.sub.1,1],[W.sub.1,2],[??],[W.sub.1,n]]. Then, B flips a random coin w [??] {0,1}. If w = 0, we have [G.sub.l-1] = [G.sub.l], and the advantage of A between [G.sub.l-1] and [G.sub.l], is equivalent. Thus, we consider the case where w = 1.

Setup: Let [lambda] be the security parameter and GP = (p,G,[G.sub.T],g,e) be the global parameter. B selects w[??]{0,1} and sets [W.sub.w] = [W.sub.w,1],[W.sub.w,2], [??],[W.sub.w,n]. B selects [delta]e [Z*.sub.p] and computes B = g ([delta]) . Let p[k.sub.CSP]=(GP,B) and s[k.sub.CSP] =(GP,[delta]) represent the CSP's public key and private key, respectively. Compute Y = e[(g, g).sup.y] where y is known to B. For each keyword k[w.sub.i] where 1[less than or equal to]i[less than or equal to]n, B chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] at random. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then B generates [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] then B generates [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. B randomly selects [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for each keyword k[w.sub.i]. For [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], B sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then, B computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] without knowing [z.sub.1] and [z.sub.2]. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] represent AA's public key and master private key, respectively, where 1[less than or equal to]i[less than or equal to]n and 1[less than or equal to]t[less than or equal to][n.sub.t]. Then, B provides (PK,p[k.sub.csp],s[k.sub.csp]) to A .

Phase 1: A submits the keyword list [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in a trapdoor query. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then B can easily generate the corresponding trapdoor. Let us assume that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. B must compute the trapdoor components

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

B can compute [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as follows: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is randomly chosen such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and random [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is known by B. B can easily compute the components [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] without knowing [z.sub.1] and [z.sub.2].

Here, we can assume [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] because [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], that is, the result is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; therefore, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then, B generates [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as follows: B sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [r.sup.'.sub.k] is random and known by B, and computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [[lambda].sub.k] is randomly chosen such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Random [[lambda].sup.'.sub.k] is known by B. B can easily compute the components [[D.sub.k,1], [D.sub.k,2]] without knowing [z.sub.2]. For i [not equal to][i.sub.l], B can also easily compute [[D.sub.i,0],[D.sub.i,1],[D.sub.i,2]].

Finally, by calculating

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)

the component [D.sub.0] = [g.sup.y-r] of the trapdoor can be computed. Therefore, all valid components of T[D.sub.L] have been constructed.

Challenge: B sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which implies s = [z.sub.3]+[z.sub.4]. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for every queried L, then B sets C to be random; otherwise, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. B generates the components [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for [W.sub.w] as for [G.sub.l-1], with the exception that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are computed as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] without knowing [z.sub.2][z.sub.4] and [z.sub.1][z.sub.3], which implies that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then the components are well formed. Then, A is in game [G.sub.l-1]. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is sent to A.

Phase 2: A continues issuing queries to the oracle Trapdoor to receive the trapdoor of the keyword list L such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where w [??] {0,1} .

Guess: A outputs the guess w' [??] {0,1}. B outputs 0 if w' = w or 1 if w' [not equal to] w. Two cases are observed as follows:

* If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], v = 0. Then, A is in the modified game [G.sub.l-1]. The advantage of A is [epsilon] ; thus, Pr[w' = w| v = 0] = l/2+[epsilon]. When w' = w, B outputs v' = 0. We have Pr[v' = v| v = 0] = 1/2 + [epsilon] .

* If Z = e[(g, g).sup.z], v = 1. Then, .4 is in game [G.sub.l], and .A has no advantage to distinguish bit w ; thus, Pr[w' [not equal to]w| v = 1] = 1/2. When w' [not equal to] w, B outputs v' = 1. We have Pr[v'= v| v = 1] = 1/2.

Therefore, we know that the advantage of B in this D-Linear game is as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (13)

By considering the sequence of the games ([G.sub.0], [G.sub.1],[??]) starting with the original game [G.sub.0], no polynomial adversary can win [G.sub.0] with a non-negligible advantage based on these lemmas.

Theorem 3: SCF-mNCKS satisfies the indistinguishability of the keywords in the DBDH assumption in [Game.sub.OA].

Proof: Given a DBDH challenge tuple [g, [g.sup.a], [g.sup.b], [g.sup.c], Z] by the simulator, where Z is either e[(g,g).sup.abc] or random with equal probability. Let v [??]{0,1}. If v = O, then Z = e[(g,g).sup.abc] ; otherwise, Z = e[(g, g).sup.z]. Assume that the adversary A in [Game.sub.OA] wins the selective game with the advantage [epsilon]. Thus, we can construct the simulator B that will break the DBDH assumption with an advantage over [epsilon]. Then, the simulator B creates the following simulation.

Setup: Let [lambda] be the security parameter and GP = (p,G,[G.sub.T],g,e) be the global parameter. Let B = [g.sup.c] and the CSP's public key be [pk.sub.CSP] = (GP,B). Compute Y = e([g.sup.a],[g.sup.b]) = e[(g,g).sup.ab], which implies that y = ab. For each k[w.sub.i] [??] U where 1[less than or equal to]i[less than or equal to]n, B chooses random values [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and random points [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Return [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as the AA' s public key and master private key, respectively, where 1 [less than or equal to]i[less than or equal to]n and 1[less than or equal to]t[less than or equal to][n.sub.i]. Then, B provides ([pk.sub.CSP], PK) to A .

Phase 1: If A submits the keyword list [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in a trapdoor query, then B computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as usual and returns it as the answer.

Challenge: A submits the two challenge policies [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] based on the keywords. B chooses w[??]{0,1} and calculates C = Z. B selects the random value [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and calculates [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For 1[less than or equal to]i[less than or equal to]n, B randomly selects [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as follows: if [v.sub.i,t] [??] [W.sub.w,i], then the data owner sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (well-formed); if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [[C.sub.i,t,1],[C.sub.i,t,2]] are random (malformed). B sends [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to A .

Phase 2: A continues issuing queries to the oracle Trapdoor to receive the trapdoor of the keyword list L. Note that L |= [W.sub.w] is allowed.

Guess: A outputs the guess w' [??] {0,1}. B outputs 0 if w' = w or outputs 1 if w' [not equal to] w. Two cases are observed as follows:

* If Z = e[(g, g).sup.abc], then A must satisfy | Pr[w' = w] -1/2|[greater than or equal to] [epsilon];

* If Z = e[(g, g).sup.z], then A has no advantage to distinguish the bit w. Specifically, Pr[w' = w] = 1/2.

Therefore, we can obtain equation (14), which completes the proof of [Game.sub.OA].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (14)

Theorem 4: SCF-mNCKS is secure against outside keyword-guessing attacks.

Proof: Assume that the outside adversary A exists who can eavesdrop on the trapdoor [TD.sub.L]. A can obtain the global parameter GP = (p,G,[G.sub.T],g,e), AA's public key [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and CSP's public key [pk.sub.CSP] =(GP,B) from the public network. To obtain the encrypted keywords, A first guesses the keyword list L and then executes the keyword guessing attacks as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

In these derivations, AA's private key [beta] is unknown to A ; therefore, the adversary A cannot successfully attack our scheme by performing keyword-guessing attacks.

4. Performance Comparison

We analysed our scheme by comparing it with the schemes of [10, 21, 23] in terms of the features, storage overhead and computation efficiency. Let | p | be the size of the elements in [Z.sub.p], and let | g | and |[g.sub.T]| be the element size in G and [G.sub.T], respectively (|[g.sub.1]| and |[g.sub.2]| are denoted by |g|). Let n denote the total number of keywords in the system, let [n.sub.i] denote the number of the values of each keyword, and let [n.sub.c] denote the number of keywords that are associated with the ciphertext. [G.sub.e] denotes the operation of the exponentiation of an elliptic curve, and P denotes the bilinear pairing operations.

4.1 Feature Comparison

Table 1 shows a comparison of the features of certain aspects of the system. These schemes and our scheme are based on the prime order of bilinear groups. Yang's scheme [23] and our scheme are based on symmetric bilinear groups and have advantages over Zhang's scheme [10] and Hwang's scheme [21], which are based on asymmetric bilinear groups. Zhang's scheme [10] and Yang's scheme [23] are based on the strong assumption of q-BDHEA. Our scheme and Hwang's scheme [21] are based on a simple assumption. Zhang [10] did not provide any security proof; therefore, we do not know whether Zhang [10] requires a random oracle. Only our scheme supports a multi-user search, which is suitable for PHRs.

4.2 Storage Overhead

Table 2 shows the comparison of the storage overhead on each entity in the system. To achieve the multi-user search, our scheme requires the AA to generate a master private key, which generates a trapdoor for each receiver. The main storage overhead on the AA is generated by the master key. In our scheme, the AA must generate a master key for each keyword value. All public parameters contribute to the storage overhead on the owner. We do not consider the storage overhead caused by the encrypted data because the storage overhead is the same in our scheme and the other schemes. In our scheme and schemes [21, 23], the CSP is required to store the ciphertext and a private key. The storage overhead on each receiver in the four scenarios is associated with the number of keywords that they possess, whereas other schemes require each receiver to store an additional private key.

Table 2 shows that the storage overhead of our scheme is similar to the storage overhead of the other schemes. Only the owner's storage overhead is larger than that of the other schemes. However, the keyword space is generally small; therefore, the total gap is not significant. Our approach is verified using simple assumptions and supports multi-user searches.

4.3 Computation Efficiency

Table 3 shows a comparison of the execution time of Encryption, Trapdoor and Test. Our scheme can achieve a richer conjunctive keyword search, as demonstrated in Section 3.1. For convenience, we allow our conjunctive keyword search to be identical to other schemes, that is, [n.sub.i] = 1 and [n.sub.c] = n. The proposed scheme is similar to the other three scenarios in terms of the execution time of Encryption, Trapdoor and Test. The time complexity of the Trapdoor and Test in the Hwang [21] scheme is a constant order; although it requires the multiplication of an elliptic curve of N times in practice. Because the time required for the multiplication operation is significantly smaller than the exponential operation, the multiplication time is omitted in Table 3. In the actual simulation process, the execution time of Trapdoor and Test increases with an increase in the number of keywords.

Experiment Setup: We conducted the experiment on a 64-bit Ubuntu 14.04 operating system with an Intel CoreTM i5-6200U (2.3 GHz) processor and 8 G RAM. The experimental code uses the Pairing-based Cryptography Library (PBC-0.5.14) and cpabe-0.11 to implement the schemes. We employ 160-bit elliptic curve groups in the hyper-singular curves [y.sup.2] = [x.sup.3] + x based on 512-bit finite fields. The simulation experiment system is built, and the operation time is tested in the system. Specifically, the pairing operation time of the PBC library is approximately 5.5 ms, and the exponential operation times of G and [G.sub.T] are approximately 5.1 ms and 0.9 ms, respectively. In the simulation process, the relationship between the number of keywords and the execution time of Encryption, Trapdoor and Test is tested. We select a 1 MB file and encrypt the file with a different number of keywords. We test the execution time of the Encryption, Trapdoor and Test processes as the number of keywords changes (from 1 to 20). All simulation results are the mean of 30 trials. According to this method, the other three schemes are simulated. The relationships are shown in Fig. 1.

Fig. 1 shows a comparison of the computational efficiency of the four schemes with different values of n, which is the number of keywords. The horizontal axis represents the number of keywords in the search, and the vertical axis represents the execution time of Encryption, Trapdoor and Test.

[FIGURE 1(a) OMITTED]

[FIGURE 1(b) OMITTED]

[FIGURE 1(c) OMITTED]

Fig. 1(a) plots the encryption time of the algorithms executed by the data owner. The encryption time increases with the number of keywords. When the number of keywords changes from 1 to 20, the encryption time of each scheme increases approximately linearly. The encryption time of all schemes is equivalent, which is consistent with the theoretical analysis in Table 3.

Fig. 1(b) shows the execution time of Trapdoor, which is executed by the receiver (Trapdoor is executed by the AA in our scheme). The schemes of [10, 23] and our scheme have the same time complexity; therefore, the three curves in the graph are similar. The execution time of Trapdoor is [G.sub.e] + 2[G.sub.m] + nH in Hwang [21], where [G.sub.m] denotes the multiplication of an elliptic curve and H denotes the operation of a hash (in the theoretical analysis, the time for the hash operation and the multiplication operation is omitted for simplicity). Because the calculation of H is small, the slope of Hwang [21] is very small, that is, with an increase in the number of keywords, the execution time of Trapdoor in [21] changes slightly less than the other three schemes. This finding is consistent with the theoretical analysis in Table 3. Our scheme has the longest execution time, and Trapdoor is executed by the AA in our scenario.

Fig. 1(c) shows the execution time of Test, which is executed by the CSP. The execution time of Test is positively correlated with the number of keywords. In the actual simulation process, the execution time of Test is 5[G.sub.e] + n[G.sub.m] + 5P in Hwang [21]. Because the multiplication is much faster than the bilinear pairing operations, the execution time of the multiplication is omitted in the theoretical analysis. Thus, in the case of the same number of keywords, the scheme in [21] requires a shorter execution time, which is consistent with the theoretical analysis in Table 3. The execution time of our scheme is longer than that of the other schemes. However, Test is performed by the CSP, which possesses strong computing power. In practical applications, this gap can be ignored.

However, our scheme achieves a multi-user conjunctive keyword search that is suitable for PHRs. Other schemes are not suitable.

5. Conclusions and Future Work

In this paper, we propose the novel multi-user conjunctive keyword search scheme without secure channel against keyword-guessing attacks (SCF-mNCKS) for PHRs. In this scheme, the owner constructs the search policy W based on the data file keywords to encrypt the data files and then uploads the ciphertext to the servers. The keyword list L is employed to search the data files. The scheme achieves the search purpose by determining whether L satisfies W. Because sensitive PHI is highly valuable, the trapdoors that are associated with the PHI keywords are often the targets of malicious behaviour, which may expose the PHI. To ensure trapdoor security while reducing the computational and communication burden, we propose an efficient mechanism for removing the secure channel. Our scheme resists keyword-guessing attacks and achieves a multi-user conjunctive keyword search that is suitable for PHRs. The security of this scheme is verified using the DBDH and D-Linear assumptions in the standard model. The scheme comparison shows that the SCF-mNCKS scheme has advantages regarding security and functions under analogous efficiency.

In future research, we will consider enhancing this scheme to achieve adaptive security. The current security lacks a formal security definition to capture keyword-guessing attacks. Building the formal security definition is a problem that we will continue to study.

References

[1] A. Bhargav-Spantzel, J. Camenisch, T. Gross and D. Sommer, "User centricity: a taxonomy and open issues," Journal of Computer Security, vol. 15, no. 5, pp. 493-527, July, 2007. Article (CrossRef Link).

[2] H. Lohr, A. R. Sadeghi and M. Winandy, "Securing the e-health cloud," in Proc. of the 1st ACM International Health Informatics Symposium, pp. 220-229, November 11-12, 2010. Article (CrossRef Link).

[3] A. Mehmood, H. Song and J. Lloret, "Multi-agent based framework for secure and reliable communication among open clouds," Network Protocols and algorithms. Macrothink Institute, vol. 6, no. 4, pp. 60-76, December, 2014. Article (CrossRef Link).

[4] I. Butun, M. Erol-Kantarci, B. Kantarci and H. Song, "Cloud-centric multi-level authentication as a service for secure public safety device networks," IEEE Communications Magazine, vol. 54, no. 4, pp. 47-53, April, 2016. Article (CrossRef Link).

[5] M. Shojafar, S. Abolfazli, H. Mostafaei and M. Singhal, "Improving channel assignment in multi-radio wireless mesh networks with learning automata," Wireless Personal Communications, vol. 82, no. 1, pp. 61-80, May, 2015. Article (CrossRef Link).

[6] D. X. Song, D. Wagner and A. Perrig, "Practical techniques for searches on encrypted data," in Proc. of IEEE Symposium on Security and Privacy, pp. 44-55, May 14-17, 2000. Article (CrossRef Link).

[7] D. Boneh, G. Di Crescenzo, R. Ostrovsky and G. Persiano, "Public key encryption with keyword search," in Proc. of International Conference on the Theory and Applications of Cryptographic Techniques, pp. 506-522, May 2-6, 2004. Article (CrossRef Link).

[8] P. Golle, J. Staddon and B. Waters, "Secure conjunctive keyword search over encrypted data," in Proc. of International Conference on Applied Cryptography and Network Security, pp. 31-45, June 8-11, 2004. Article (CrossRef Link).

[9] D. J. Park, K. Kim and P. J. Lee, "Public key encryption with conjunctive field keyword search," in Proc. of International Workshop on Information Security Applications, pp. 73-86, August 23-25, 2004. Article (CrossRef Link).

[10] B. Zhang and F. Zhang, "An efficient public key encryption with conjunctive-subset keywords search," Journal of Network and Computer Application, vol. 34, no. 1, pp. 262-267, January, 2011. Article (CrossRef Link).

[11] W. Sun, B. Wang, N. Cao and et al, "Verifiable privacy-preserving multi-keyword text search in the cloud supporting similarity-based ranking," IEEE Transactions on Parallel and Distributed Systems, vol. 25, no. 11, pp. 3025-3035, November, 2014. Article (CrossRef Link).

[12] W. Sun, X. Liu, W. Lou and et al, "Catch you if you lie to me: Efficient verifiable conjunctive keyword search over large dynamic encrypted cloud data," in Proc. of IEEE conference on computer communications, pp. 2110-2118, April 26-May 1, 2015. Article (CrossRef Link).

[13] J. Baek, R. Safavinaini and W. Susilo, "Public Key Encryption with Keyword Search Revisited," in Proc. of International Conference on Computational Science and Its Applications, pp. 1249-1259, June 30-July 3, 2008. Article (CrossRef Link).

[14] H. S. Rhee, J. H. Park, W. Susilo and D. H. Lee, "Improved searchable public key encryption with designated tester," in Proc. of ACM Symposium on Information, Computer and Communications Security, pp. 376-379, March 10-12, 2009. Article (CrossRef Link).

[15] K. Emura, A. Miyaji, M. S. Rahman and K. Omote, "Generic constructions of secure-channel free searchable encryption with adaptive security," Security and Communication Networks, vol. 8, no. 8, pp. 1547-1560, May, 2015. Article (CrossRef Link).

[16] J. W. Byun, H. S. Rhee, H. A. Park and D. H. Lee, "Off-line keyword guessing attacks on recent keyword search schemes over encrypted data," in Proc. of Workshop on Secure Data Management, pp. 75-83, September 10-11, 2006. Article (CrossRef Link).

[17] W. C. Yau, S. H. Heng and B. M. Goi, "Off-line keyword guessing attacks on recent public key encryption with keyword search schemes," in Proc. of International Conference on Autonomic and Trusted Computing, pp. 100-105, June 23-25, 2008. Article (CrossRef Link).

[18] J. Baek, R. Safavi-Naini and W. Susilo, "On the integration of public key data encryption and public key encryption with keyword search," in Proc. of International Conference on Information Security, pp. 217-232, August 30-September 2, 2006. Article (CrossRef Link).

[19] H.S. Rhee, W. Susilo and H-J. Kim, "Secure searchable public key encryption scheme against keyword guessing attacks," IEICE Electron. Express, vol. 6, no. 5, pp. 237-243, June, 2009. Article (CrossRef Link).

[20] R. Canetti, O. Goldreich and S. Halevi, "The random oracle methodology, revisited," Journal of the ACM (JACM), vol. 51, no. 4, pp. 557-594, July, 2004. Article (CrossRef Link).

[21] M. S. Hwang, S. T. Hsu and C. C. Lee, "A new public key encryption with conjunctive field keyword search scheme," Information Technology And Control, vol. 43, no .3, pp. 277-288, February, 2014. Article (CrossRef Link).

[22] L. Guo and W. C. Yau, "Efficient secure-channel free public key encryption with keyword search for EMRs in cloud storage," Journal of medical systems, vol. 39, no. 2, pp. 1-11, February, 2015. Article (CrossRef Link).

[23] Y. Yang and M. Ma, "Conjunctive keyword search with designated tester and timing enabled proxy re-encryption function for e-health clouds," IEEE Transactions on Information Forensics and Security, vol. 11, no. 4, pp. 746-759, April, 2016. Article (CrossRef Link).

[24] Y. Miao, J. Ma, F. Wei and et al, "VCSE: Verifiable conjunctive keywords search over encrypted data without secure-channel," Peer-to-Peer Networking and Applications, pp. 1-13, May, 2016. Article (CrossRef Link).

[25] M. Shojafar, J. H. Abawajy, Z. Delkhah and et al, "An efficient and distributed file search in unstructured peer-to-peer networks," Peer-to-Peer Networking and Applications, vol. 8, no. 1, pp. 120-136, January, 2015. Article (CrossRef Link).

[26] Y. H. Hwang and P. J. Lee, "Public key encryption with conjunctive keyword search and its extension to a multi-user system," in Proc. of International Conference on Pairing-Based Cryptography, pp. 2-22, July 2-4, 2007. Article (CrossRef Link).

[27] L. Cheung and C. Newport, "Provably secure ciphertext policy ABE," in Proc. of the 14th ACM conference on Computer and communications security, pp. 456-465, October 29-November 02, 2007. Article (CrossRef Link).

[28] J. Bethencourt, A. Sahai and B. Waters, "Ciphertext-policy attribute-based encryption," in Proc. of IEEE symposium on security and privacy, pp. 321-334, May 20-23, 2007. Article (CrossRef Link).

[29] M. Abdalla, M. Bellare, D. Catalano and et al, "Searchable encryption revisited: Consistency properties, relation to anonymous IBE, and extensions," in Proc. of Annual International Cryptology Conference, pp. 205-222, August 14-18, 2005. Article (CrossRef Link).

[30] L. Fang, W. Susilo, C. Ge and J. Wang, "Public key encryption with keyword search secure against keyword guessing attacks without random oracle," Information Sciences, vol. 238, no. 7, pp. 221-241, July, 2013. Article (CrossRef Link).

[ILLUSTRATION OMITTED]

Zhiyuan Zhao received an M.S. degree from Zhengzhou Information Science and Technology Institute, Zhengzhou, China in 2015. He is currently pursuing a Ph.D. degree at Zhengzhou Information Science and Technology Institute, China. His research interests include cryptograph theory, especially attribute-based encryption.

[ILLUSTRATION OMITTED]

Jianhua Wang received a Ph.D. degree from Zhengzhou Information Science and Technology Institute, China in 2008 and became a Full Professor in 2006. His research interests primarily focus on information security. He has authored and co-authored more than 100 journal and conference papers.

Zhiyuan Zhao (1), Jianhua Wang (1)

(1) Zhengzhou Information Science and Technology Institute Zhengzhou 450001, Henan--P. R. China

[e-mail: zzy_taurus@foxmail.com]

(*)Corresponding author: Zhiyuan Zhao

Received December 11, 2016; revised March 2, 2017; accepted March 11, 2017; published July 31, 2017

This work was supported by the National Key Research Program of China, "Collaborative Precision Positioning Project"(No. 2016YFB0501900).
Table 1. Features Comparison

Features         Zhang [10]   Hwang [21]   Yang [23]       Ours

Bilinear Maps    Asymmetric   Asymmetric   Symmetric       Symmetric
Assumption       p-DDHI       DDH          q-ABDHE, DBDH   DBDH, DL
Random Oracle    -            Without      Without         Without
SCF              No           Yes          Yes             Yes
KGA              No           Yes          Yes             Yes
Multi-user CKS   No           No           No              Yes

Table 2. Comparison of Storage Overhead

             AA         Owner                     CSP
Schemes      (MSK)      (All PK)                  (CT)

Zhang [10]   -          O(n) |g|                  O(n) |g|+O(1)|p|
Hwang [21]   -          O(1)|g|+O(1)|[g.sub.T]|   O(n) |g|+O(1)|p|
Yang [23]    -          O(1) |g|                  O(n) |g|+O(1)
                                                  |[g.sub.T]|+O(1)|p|
Ours         O(n) |p|   O(n)|g|+O(1)|[g.sub.T]|   O(n) |g|+O(1)
                                                  |[g.sub.T]|+O(1)|p|

              Receiver
Schemes       (Trapdoor & SK)

Zhang [10]    O(n)|g|+O(1)|p|
Hwang [21]    O(n) |g|+O(1)|p|
Yang [23]     O(n) |g|+O(1)|p|

Ours          O(n) |g|

Table 3. Comparison of Computation Efficiency

Schemes      Encryption Time        Trapdoor Time   Test Time

Zhang [10]   O(n)[G.sub.e] + O(1)P  O(n)[G.sub.e]   O(n)P
Hwang [21]   O(n)[G.sub.e]          O(1)[G.sub.e]   O(1)[G.sub.e]+O(1)P
Yang [23]    O(n)[G.sub.e]          O(n)[G.sub.e]   O(n)P
Ours         O(n)[G.sub.e] + O(1)P  O(n)[G.sub.e]   O(n)P
COPYRIGHT 2017 KSII, the Korean Society for Internet Information
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2017 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Zhao, Zhiyuan; Wang, Jianhua
Publication:KSII Transactions on Internet and Information Systems
Article Type:Report
Date:Jul 1, 2017
Words:12041
Previous Article:A self-authentication and deniable efficient group key agreement protocol for VANET.
Next Article:Robust biometric-based anonymous user authenticated key agreement scheme for Telecare Medicine Information Systems.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters