Sage Journals: Discover world-class research

Abstract

The concept of public key encryption with equality test was introduced at CT-RSA 2010. It has been used in many fields, especially in cloud storage. However, the previous schemes do not provide an effective authorization mechanism. To fill this gap, Ma et al. presented a public key encryption with equality test supporting flexible authorization based on the bilinear pairings. Recently, Lin et al. presented a pairing-free scheme that employs quadratic curve to perform the equality tests, which can achieve a trade-off between computational cost and storage space. In this article, we show that the equality test can be better performed by using a straight line, rather than a quadratic curve. Moreover, we simplify the encryption algorithm, as well as reduce the ciphertext storage space.

Keywords

Public key encryption with equality test cloud storage flexible authorization

Introduction

Searchable encryption (SE) scheme, presented in 2004 by Boneh et al.,¹ allows the server to check whether some messages contain specific keyword without retrieving entire messages. Subsequently, scholastic community presented many improved schemes.^2–8 In 2007, Bellare and ONeill⁹ conceptualized deterministic encryption (DE) for public-key encryption schemes, in which the encryption algorithm is executed in a deterministic manner. Later, DE was uplifted by Bellare et al.¹⁰ and Boldyreva and ONeill¹¹ But, DE could not gain immense appreciations due to its deterministic approach.

With the development of cloud computing and outsourcing, traditional encryption schemes cannot provide the solutions for many applications such as splitting of database. To handle the prescribed issue, Yang et al.¹² proposed the notion of public key encryption with equality test (PKEwET) at CT-RSA 2010. This effective mechanism allows anyone to check whether two ciphertexts contain the same message without decryption. Tang¹³ intensified PKEwET with finegrained authorization (FG-PKEwET), which authorizes two users to a semi-trusted proxy, who can perform the equality test on their ciphertexts. Later, an extension of FG-PKEwET was also put forward by Tang.¹⁴ Besides, in the same year, Tang¹⁵ presented a new primitive called all-or-nothing PKEwET (AoN-PKEwET), which authorizes the specific users to perform a plaintext equality test from their ciphertexts. Another perspective in the form of identity-based encryption with equality test (IBEwET) was proposed by Ma¹⁶ that combines the concepts of PKEwET and identity-based encryption.

The privacy of users is an essential context that necessitates to be considered while designing an applied protocol. Therefore, Ma et al.¹⁷ strengthened the concept of PKEwET by introducing flexible authorization, which is termed as PKEwET-FA. In his scheme, the author implemented different authorization policies along with a corresponding trapdoor for each authorization to perform the test algorithm. For instance, as described in Ma et al.,¹⁷ suppose Alice is a ciphertext receiver, then four types of authorization with different granularity can be described as follows:

Type 1. User-level authorization: All ciphertexts of Alice can be compared with all ciphertexts of any other receiver.

Type 2. Ciphertext-level authorization: A specific ciphertext of Alice can be compared with a specific ciphertext of any other receiver.

Type 3. User-specific ciphertext-level authorization: A specific ciphertext of Alice can be only compared with a specific ciphertext of a specific receiver, for example, Bob, but could not be compared with any ciphertext of any receiver other than Bob.

Type 4. Ciphertext-to-user (or user-to-ciphertext) level authorization: A specific ciphertext of Alice can be compared with all ciphertexts of any other receiver (or vice versa).

Recently, Lin et al.¹⁸ proposed a new PKEwET-FA scheme, in which the equality tests are performed without bilinear pairing. More precisely, the author utilized the message for generating a quadratic curve and then used Shamir’s secret sharing scheme to perform the equality test. Although it gets rid of the dependence on bilinear pairings, however, the computational cost of this scheme is high due to the involvement of quadratic curve.

Motivation and contribution

In this article, we improve the scheme presented in Lin et al.¹⁸ by replacing the quadratic curve with the straight line to reduce the computational cost. Moreover, we improve the scheme by simplifying the encryption algorithm while reducing the computation of the modular exponentiation. Comparing with Lin et al.,¹⁸ our proposed scheme is more efficient in terms of the equality test as well as with respect to encryption and decryption. Furthermore, the storage space of ciphertexts is also smaller than that of Lin et al.¹⁸ We compare the presented scheme with the previous work and the result shows that our scheme is more efficient and robust.

Organization

The rest of this article is organized as follows. In section “Preliminaries,” Shamir’s secret sharing scheme and the related security model are discussed. In section “The proposed scheme,” we present our scheme and four types of authorization and prove the validity of the proposed scheme. In section “Security,” we provide the security proof of presented scheme. In section “Performances analysis,” a detailed analysis of the presented scheme and comparisons with other schemes are presented. Finally, concluding remarks are given in section “Conclusion.”

Preliminaries

Definitions

Definition 1

Decision Diffie-Hellman (DDH) Problem: Let $G$ be a group of large prime order q, given two 4-tuples $(g, g^{a}, g^{b}, g^{ab})$ and $(g, g^{a}, g^{b}, g^{c}) \in G$ with $g \neq 1$ , where $a, b, c \in Z_{q}$ . A DDH algorithm $A$ for a group $G$ is a probabilistic polynomial time algorithm satisfying

\begin{array}{l} | \Pr [A (g, G, g^{a}, g^{b}, g^{a b}) \\ = ″ True ″] - \Pr [A (g, G, g^{a}, g^{b}, g^{c}) = ″ True ″ | > ε \end{array}

We say that the group $G$ satisfies the DDH assumption if there is no DDH algorithm for $G$ .

Definition 2 (Correctness)

If a $PKEwET - FA$ scheme is correct, for any $sp \leftarrow Setup (k)$ , and $(p k_{j}, s k_{j}) \leftarrow KeyGen (sp, i)$ , the following conditions must be satisfied.¹⁷

For any $M \in M$ , $Decrypt (Encrypt (M, p k_{i}), s k_{i}) = M$ always holds.

For any ciphertexts $c_{i}$ and $c_{j}$ , if $Decrypt (c_{i}, s k_{i}) = Decrypt (c_{j}, s k_{j}) \neq ⊥$ .

Type 1 Authorization. Given $Au t_{1} (s k_{i}) = t d_{1, i}$ and $Au t_{1} (s k_{j}) = t d_{1, j}$ , it holds that

Tes t_{1} (c_{i}, t d_{1, i}, c_{j}, t d_{1, j}) = 1

Type 2 Authorization. Given $Au t_{2} (s k_{i}, c_{i}) = t d_{2, i, c_{i}}$ and $Au t_{2} (s k_{j}, c_{j}) = t d_{2, j, c_{j}}$ , it holds that

Tes t_{2} (c_{i}, t d_{2, i, c_{i}}, c_{j}, t d_{2, j, c_{j}}) = 1

Type-3 Authorization. Given $Au t_{3} (s k_{i}, c_{i}, c_{j}) = t d_{3, i, c_{i}, j, c_{j}}$ and $Au t_{3} (s k_{j}, c_{j}, c_{i}) = t d_{3, j, c_{j}, i, c_{i}}$ , it holds that

Tes t_{3} (c_{i}, t d_{3, i, c_{i}, j, c_{j}}, c_{j}, t d_{3, j, c_{j}, i, c_{i}}) = 1

Type 4 Authorization. Given $Au t_{4} (s k_{i}, c_{i}) = t d_{4, i, c_{i}}$ and $Au t_{4} (s k_{j}) = t d_{4, j}$ , it holds that

Tes t_{4} (c_{i}, t d_{4, i, c_{i}}, c_{j}, t d_{4, j}) = 1

For any ciphertexts $c_{i}$ and $c_{j}$ , if $Decrypt (c_{i}, s k_{i}) \neq Decrypt (c_{j}, s k_{j})$

Type 1 Authorization. Given $Au t_{1} (s k_{i}) = t d_{1, i}$ and $Au t_{1} (s k_{j}) = t d_{1, j}$ , it holds that

\Pr [Tes t_{1} (c_{i}, t d_{1, i}, c_{j}, t d_{1, j}) = 1]

is negligible

Type 2 Authorization. Given $Au t_{2} (s k_{i}, c_{i}) = t d_{2, i, c_{i}}$ and $Au t_{2} (s k_{j}, c_{j}) = t d_{2, j, c_{j}}$ , it holds that

\Pr [Tes t_{2} (c_{i}, t d_{2, i, c_{i}}, c_{j}, t d_{2, j, c_{j}}) = 1]

is negligible

Type 3 Authorization. Given $Au t_{3} (s k_{i}, c_{i}, p k_{j}, c_{j}) = t d_{3, i, c_{i}, j, c_{j}}$ and $Au t_{3} (s k_{j}, c_{j}, p k_{i}, c_{i}) = t d_{3, j, c_{j}, i, c_{i}}$ , it holds that

\Pr [Tes t_{3} (c_{i}, t d_{3, i, c_{i}, j, c_{j}}, c_{j}, t d_{3, j, c_{j}, i, c_{i}}) = 1]

is negligible

Type 4 Authorization. Given $Au t_{4} (s k_{i}, c_{i}) = t d_{4, i, c_{i}}$ and $Au t_{4} (s k_{j}) = t d_{4, j}$ , it holds that

\Pr [Tes t_{4} (c_{i}, t d_{4, i, c_{i}}, c_{j}, t d_{4, j}) = 1]

is negligible.

Shamir’s secret sharing scheme

Shamir’s $(t, n)$ -threshold secret sharing scheme is based on Lagrange interpolation polynomial. A detailed introduction is described as follows.

Given t distinct points $(x_{i}, f (x_{i}))$ , where $f (x)$ is a polynomial of degree less than t, then $f (x)$ is determined as follows

f (x) = \sum_{i = 1}^{t} Π_{j = 1, j \neq i}^{t} \frac{(x - x_{j})}{(x_{i} - x_{j})}

Shamir’s scheme is defined for a secret $s \in Z_{p}$ , by setting $a_{0} = s$ , and choosing $a_{1}, a_{2}, \dots, a_{t - 1} \in Z_{q}$ . For all $1 \leq x_{i} \leq q, 1 \leq i \leq n$ , the trusted party computes $f (x_{i})$ , where $f (x) = \sum_{k = 0}^{t - 1} a_{k} x^{k}$ . The shares $(x_{i}, f (x_{i}))$ are distributed to n distinct parties. Since the secret is a constant term $s = a_{0} = f (0)$ , hence, the secret can be recovered from any t shares $(x_{i}, f (x_{i}))$ as follows

s = f (0) = \sum_{i = 1}^{t} f (x_{i}) Π_{j = 1, j \neq i}^{t} \frac{x_{i}}{(x_{j} - x_{i})}

Security models

We recall the security models of PKEwET-FA defined in Ma et al.¹⁷ It consists of six algorithms: Setup, KeyGen, Encrypt, Decrypt, ${Authorization}_{α}$ and Test-α $(α = 1, 2, 3, 4)$ . Suppose that the system has a label i for user $u_{i}$ . The setup algorithm takes the security parameter as input and outputs system parameters sp. The KeyGen algorithm takes as inputs the system parameters, a user i, and outputs the public key and private key of user i. The encryption algorithm takes the given public key, a message M, and outputs ciphertext $c_{i}$ . The decryption algorithm takes the private key $s k_{i}$ , a ciphertext $c_{i}$ , and outputs a message M $or ⊥$ . The authorization algorithm takes as inputs the private key $s k_{i}$ and other required information and outputs the trapdoor. The test algorithm takes as inputs two ciphertexts, the trapdoors, and outputs 1 for the same message or 0 for otherwise. Because the Type 4 authorization is a combination of Type 1 and Type 2 authorization, we leave out Type 4 authorization queries for simplicity and only allow Type-α (α = 1, 2, 3) authorization queries to the adversary in the security games.

Two types of adversaries for the security of PKEwET-FA are described as follows:

Type I adversary. For Type-α (α = 1, 2, 3) authorization, with Type-α trapdoor information, the attacker cannot recover the plaintext from the challenge ciphertext.

Type II adversary. For Type-α (α = 1, 2, 3) authorization, without Type-α trapdoor information, the adversary cannot decide $c_{t}^{*}$ is the encryption of which message.

First, we define one-way against chosen-ciphertext attack (OW-CCA) security for Type-α (α = 1, 2, 3) authorization against Type I adversary in PKEwET-FA as follows.

Game 1

Suppose that $A_{1}$ is a Type I adversary and $S$ is the challenger. The target receiver has label $t (1 \leq t \leq n)$ . The game between $A_{1}$ and $S$ is presented in Figure 1.

Figure 1.

The game between $A_{1}$ and $S$ .

Here, $O_{1} (i) \overset{Δ}{=} KeyGen (sp, i)$ , $O_{2} (i, c_{i}) \overset{Δ}{=} dec (s k_{i}, c_{i})$ , $O_{3} (i, \cdot) \overset{Δ}{=} ET - Auth (s k_{i}, \cdot)$ , $O_{6} = O_{3}$ , but

O_{4} (i) = {\begin{matrix} O_{1} (i) & i \neq t \\ ⊥ & otherwise \end{matrix}

and

O_{5} (i, c_{i}) = {\begin{matrix} O_{2} (i, c_{i}) & c_{i} \neq c^{*} \\ ⊥ & otherwise \end{matrix}

The advantage of $A_{1}$ in the aforementioned game is defined as follows

{Adv}_{PKEwET - FA, A_{1}}^{OW - CCA, Type - α} (k) = \Pr [M_{t} = M_{t}^{*}] (α = 1, 2, 3)

Definition 3

For $Type - α (α = 1, 2, 3)$ authorization, a PKEwET-FA scheme is OW-CCA secure if for all OW-CCA adversaries, ${Adv}_{PKEwET - FA, A_{1}}^{OW - CCA, Type - α} (k)$ is negligible in the security parameter k.

Next, we define the indistinguishable against chosen-ciphertext attacks (IND-CCA) security for Type-α (α = 1, 2, 3) authorization against Type II adversary in PKEwET-FA as follows.

Game 2

Suppose that $A_{2}$ is a Type II adversary and $S$ is the challenger. The target receiver has label $t (1 \leq t \leq n)$ . The game between $A_{2}$ and $S$ is presented in Figure 2.

Figure 2.

The game between $A_{2}$ and $S$ .

Here, $O_{1} (i) \overset{Δ}{=} KeyGen (i)$ , $O_{2} (i, c_{i}) \overset{Δ}{=} dec (s k_{i}, c_{i})$ , $O_{3} (i, \cdot) \overset{Δ}{=} ET - Auth (s k_{i}, \cdot)$ , $O_{6} = O_{3}$ ( $α = 1, i \neq t$ ) and ( $α = 2$ or $3, c_{i} \neq c^{*})$ , but

O_{4} (i) = {\begin{matrix} O_{1} (i) & i \neq t \\ ⊥ & otherwise \end{matrix}

and

O_{5} (i, c_{i}) = {\begin{matrix} O_{2} (i, c_{i}) & c \neq c^{*} \\ ⊥ & otherwise \end{matrix}

The advantage of $A_{2}$ in the aforementioned game is defined as follows

{Adv}_{PKEwET - FA, A_{2}}^{IND - CCA, Type - α} (k) = | \Pr [b = b^{*}] - 1 / 2 | (α = 1, 2, 3)

Definition 4

For $Type - α (α = 1, 2, 3)$ authorization, a PKEwET-FA scheme is IND-CCA secure if for all IND-CCA adversaries, ${Adv}_{PKEwET - FA, A_{2}}^{OW - CCA, Type - α} (k)$ is negligible in the security parameter k.

Notice

The aim of our scheme is to perform equality test for the messages corresponding to the ciphertexts of different users, which can be used in multi-user settings in a public key encryption.

The proposed scheme

Here, we describe our scheme in detail.

Setup(k): Let k be a security parameter, $M \in {0, 1}^{k}$ , the algorithm outputs system parameters sp as follows:

Let $G$ be a group of prime order q, g be a random generator of $G$ .

Select hash functions: $H_{1} : G \to {0, 1}^{k}, H_{2} : G^{4} \to Z_{q}^{4}$ , and $H_{3}, H_{4}, H_{5}, H_{6} : {0, 1}^{k} \to Z_{q}$ .

KeyGen( $sp, i$ ): This algorithm allocates a label for each user and keeps a list of the users with ( $key, i$ ). With the system parameters sp, it chooses $x_{i}, y_{i} \in Z_{q}$ randomly and computes $X_{i} = g^{x_{i}}, Y_{i} = g^{y_{i}}$

The user’s key pair: $(p k_{i}, s k_{i}) = ((X_{i}, Y_{i}), (x_{i}, y_{i}))$

Encrypt( $M, p k_{i}$ ): It takes public key $p k_{i}$ and the message $M \in {0, 1}^{k}$ as input and outputs the ciphertext $c_{i} = (c_{i, 1}, c_{i, 2}, c_{i, 3})$ as follows:

Use $H_{3}, H_{4}, H_{5}, H_{6}$ to create two points $p_{1} = (H_{3} (M), H_{4} (M)), p_{2} = (H_{5} (M), H_{6} (M))$ ;

Use two points $p_{1}, p_{2}$ to construct a straight line $f (x)$ ;

Choose $x_{i, 1}, x_{i, 2} \in {0, 1}^{l}$ randomly and let $f (x_{i, 1}) = y_{i, 1}, f (x_{i, 2}) = y_{i, 2}$ . If $x_{i, 1} = 0$ or $x_{i, 2} = 0$ , then takes $x_{i, 1}, x_{i, 2} \in {0, 1}^{l}$ randomly again.

Choose a random number $r \in Z_{q}^{*}$ , and let

c_{i, 1} = g^{r}

c_{i, 2} = M \oplus H_{1} (Y_{i}^{r})

c_{i, 3} = (x_{i, 1} | | x_{i, 2} | | y_{i, 1} | | y_{i, 2}) \oplus H_{2} (X_{i}^{r}, c_{i, 1}, c_{i, 2})

Decrypt( $c, sk$ ): Given $s k_{i}$ and a ciphertext $c_{i} = (c_{i, 1}, c_{i, 2}, c_{i, 3})$ , the algorithm decrypts as follows

M \leftarrow c_{i, 2} \oplus H_{1} (c_{i, 1}^{y_{i}})

x_{i, 1} | | x_{i, 2} | | y_{i, 1} | | y_{i, 2} \leftarrow c_{i, 3} \oplus H_{2} (c_{i, 1}^{x_{i}}, c_{i, 1}, c_{i, 2})

Then, it uses M to create $f (x)$ by employing the same process as step (1) and (2) of Encryption process. If both $f (x_{i, 1}) = y_{i, 1}$ and $f (x_{i, 2}) = y_{i, 2}$ hold, the algorithm outputs M; otherwise, it $outputs ⊥$ .

Suppose $u_{i}$ and $u_{j}$ are two users in the system and $c_{i} = (c_{i, 1}, c_{i, 2}, c_{i, 3})$ (resp., $c_{j} = (c_{j, 1}, c_{j, 2}, c_{j, 3})$ ) is a ciphertext of $u_{i}$ (resp., $u_{j}$ ). $r_{i}$ (resp., $r_{j}$ ) denotes a randomness used in the generation of $c_{i}$ (resp. $c_{j}$ ).

1. Type 1 Authorization

• Auth₁ $(s k_{i})$ : The algorithm outputs a trapdoor $t d_{(1, i)} = x_{i}$ .

• Test₁ $(c_{i}, t d_{1, i}, c_{j}, t d_{1, j})$ : This algorithm performs as follows

x_{i, 1} | | x_{i, 2} | | y_{i, 1} | | y_{i, 2} \leftarrow c_{i, 3} \oplus H_{2} (c_{i, 1}^{t d_{1, i}}, c_{i, 1}, c_{i, 2})

x_{j, 1} | | x_{j, 2} | | y_{j, 1} | | y_{j, 2} \leftarrow c_{j, 3} \oplus H_{2} (c_{j, 1}^{t d_{1, j}}, c_{j, 1}, c_{j, 2})

f_{i} (x) \leftarrow (q, (x_{i, 1}, y_{i, 1}), (x_{j, 1}, y_{j, 1}))

f_{j} (x) \leftarrow (q, (x_{i, 2}, y_{i, 2}), (x_{j, 2}, y_{j, 2})) .

Then, it outputs 1 if $f_{i} (x) = f_{j} (x)$ holds, and 0 otherwise.

2. Type 2 Authorization

• Auth₂ $(s k_{i}, c_{i})$ : The algorithm computes a trapdoor $t d_{(2, i, c_{i})} = H_{2} (c_{i, 1}^{x_{i}}, c_{i, 1}, c_{i, 2})$ .

• Test₂ $(c_{i}, t d_{2, i}, c_{j}, t d_{2, j})$ : This algorithm performs as follows

x_{i, 1} | | x_{i, 2} | | y_{i, 1} | | y_{i, 2} \leftarrow c_{i, 3} \oplus t d_{(2, i, c_{i})}

x_{j, 1} | | x_{i, 2} | | y_{i, 1} | | y_{j, 2} \leftarrow c_{j, 3} \oplus t d_{(2, j, c_{j})}

f_{i} (x) \leftarrow (q, (x_{i, 1}, y_{i, 1}), (x_{j, 1}, y_{j, 1}))

f_{j} (x) \leftarrow (q, (x_{i, 2}, y_{i, 2}), (x_{j, 2}, y_{j, 2})) .

Then, it outputs 1 if $f_{i} (x) = f_{j} (x)$ holds, and 0 otherwise.

3. Type 3 Authorization

• Auth₃ $(s k_{i}, c_{i}, c_{j})$ : The algorithm computes a trapdoor as follows

\begin{array}{l} t d_{(3, i, c_{i}, j, c_{j})} = (z_{i}, V_{i, 1}, V_{i, 2}) \\ = ({[H_{2} (c_{i, 1}^{x_{i}}, c_{i, 1}, c_{i, 2})]}_{0}^{2 l - 1}, Z_{i}^{y_{i, 1}}, Z_{i}^{y_{i, 2}}) \end{array}

where $Z_{i} = c_{j, 1} c_{i, 1}$ .

• Test₃ $(c_{i}, t d_{3, i}, c_{j}, t d_{3, j})$ : It is performed as follows

x_{i, 1} | | x_{i, 2} \leftarrow [c_{i, 3}]_{0}^{2 l - 1} \oplus z_{i}

x_{j, 1} | | x_{j, 2} \leftarrow [c_{j, 3}]_{0}^{2 l - 1} \oplus z_{j} .

Then, it employs the Lagrange interpolation coefficients to compute $Δ_{i, 1} = (x_{i, 2}) / (x_{i, 2} - x_{i, 1})$ (mod q), $Δ_{i, 2} = (x_{i, 1}) / (x_{i, 1} - x_{i, 2})$ (mod q), $Δ_{j, 1} = (x_{j, 2}) / (x_{j, 2} - x_{j, 1})$ (mod q), and $Δ_{j, 2} = (x_{j, 1}) / (x_{j, 1} - x_{j, 2})$ (mod q).

Finally, it tests whether or not $V_{i, 1}^{Δ_{i, 1}} V_{j, 1}^{Δ_{j, 1}} = V_{j, 2}^{Δ_{j, 2}} V_{i, 2}^{Δ_{i, 2}}$ holds. If it is, it returns 1, and 0 otherwise.

4. Type 4 Authorization

• Auth₄ $(s k_{i}, c_{i})$ : The algorithm computes a trapdoor $t d_{(4, i, c_{i})} = Au t_{2} (s k_{i}, c_{i}) = H_{2} (c_{i, 1}^{x_{i}}, c_{i, 1}, c_{i, 2})$ .

Aut₄ $(s k_{j})$ : The algorithm outputs a trapdoor $t d_{(4, j)} = Au t_{1} (s k_{j}) = x_{j}$

• Test₄ $(c_{i}, t d_{4, i}, c_{j}, t d_{4, j})$ : This algorithm performs as follows

x_{i, 1} | | x_{i, 2} | | y_{i, 1} | | y_{i, 2} \leftarrow c_{i, 3} \oplus t d_{(4, i, c_{i})}

x_{j, 1} | | x_{i, 2} | | y_{i, 1} | | y_{j, 2} \leftarrow c_{j, 3} \oplus H_{2} (c_{j, 1}^{t d_{4, j}}, c_{j, 1}, c_{j, 2})

f_{i} (x) \leftarrow (q, (x_{i, 1}, y_{i, 1}), (x_{j, 1}, y_{j, 1}))

f_{j} (x) \leftarrow (q, (x_{i, 2}, y_{i, 2}), (x_{j, 2}, y_{j, 2}))

Then, it outputs 1 if $f_{i} (x) = f_{j} (x)$ holds, and 0 otherwise.

Theorem 1

According to Definition 2, our proposed $PKEwET - FA$ scheme is correct.

Proof

Here, we prove that our scheme satisfies the three conditions, as defined in Definition 2:

1. It is not difficult to check that the first condition is satisfied.

2. Considering the second condition, for any $sp \leftarrow Setup (k), (p k_{i}, s k_{i}) \leftarrow KeyGen (sp, i), c_{i} = (c_{i, 1}, c_{i, 2}, c_{i, 3}) = Encrypt (M_{i}, p k_{i})$ and $c_{j} = (c_{j, 1}, c_{j, 2}, c_{j, 3}) = Encrypt (M_{j}, p k_{j})$ , the following equalities hold.

For any message $M_{i} (resp . M_{j})$ , the straight line $f_{i} (x) (resp ., f_{j} (x))$ is constructed by passing through two points $(x_{i, 1}, y_{i, 1})$ , $(x_{j, 1}, y_{j, 1})$ or $(x_{i, 2}, y_{i, 2})$ , $(x_{j, 2}, y_{j, 2})$ .

If $f_{i} (x) = f_{j} (x)$ (or $f_{i} (0) = f_{j} (0)$ , in Type 3 Authorization), we have $M_{i} = M_{j}$ .

Type 1 Authorization: With $t d_{(1, i)} = x_{i}$ and $t d_{(1, j)} = x_{j}$ , we compute

x_{i, 1} | | x_{i, 2} | | y_{i, 1} | | y_{i, 2} \leftarrow c_{i, 3} \oplus H_{2} (c_{i, 1}^{t d_{1, i}}, c_{i, 1}, c_{i, 2})

x_{j, 1} | | x_{j, 2} | | y_{j, 1} | | y_{j, 2} \leftarrow c_{j, 3} \oplus H_{2} (c_{j, 1}^{t d_{1, j}}, c_{j, 1}, c_{j, 2})

Therefore, $f_{i} (x) = f_{j} (x)$ holds for $M_{i} = M_{j}$ .

Type 2 Authorization: With $t d_{(2, i, c_{i})} = H_{2} (c_{i, 1}^{x_{i}}, c_{i, 1}, c_{i, 2})$ and $t d_{(2, j, c_{j})} = H_{2} (c_{j, 1}^{x_{j}}, c_{j, 1}, c_{j, 2})$ , we compute

x_{i, 1} | | x_{i, 2} | | y_{i, 1} | | y_{i, 2} \leftarrow c_{i, 3} \oplus t d_{(2, i, c_{i})}

x_{j, 1} | | x_{i, 2} | | y_{i, 1} | | y_{j, 2} \leftarrow c_{j, 3} \oplus t d_{(2, j, c_{j})}

Therefore, $f_{i} (x) = f_{j} (x)$ holds for $M_{i} = M_{j}$ .

Type 3 Authorization: With

\begin{array}{l} t d_{(3, i, c_{i}, j, c_{j})} = (z_{i}, V_{i, 1}, V_{i, 2}) \\ = ({[H_{2} (c_{i, 1}^{x_{i}}, c_{i, 1}, c_{i, 2})]}_{0}^{2 l - 1}, Z_{i}^{y_{i, 1}}, Z_{i}^{y_{i, 2}}) \end{array}

and

\begin{matrix} t d_{(3, j, c_{j}, i, c_{i})} = (z_{j}, V_{j, 1}, V_{j, 2}) \\ = ([H_{2} (c_{j, 1}^{x_{j}}, c_{j, 1}, c_{j, 2})]_{0}^{2 l - 1}, Z_{j}^{y_{j, 1}}, Z_{j}^{y_{j, 2}}) \end{matrix}

where $Z_{i} = c_{j, 1} c_{i, 1}$ , $Z_{j} = c_{i, 1} c_{j, 1}$ , then $Z_{i} = Z_{j} = g^{r_{i, 1} + r_{j, 1}}$

\begin{array}{l} t d_{(3, j, c_{j}, i, c_{i})} = (z_{j}, V_{j, 1}, V_{j, 2}) \\ = ({[H_{2} (c_{j, 1}^{x_{j}}, c_{j, 1}, c_{j, 2})]}_{0}^{2 l - 1}, Z_{i}^{y_{j, 1}}, Z_{i}^{y_{j, 2}}) \end{array}

with $t d_{(3, i, c_{i}, j, c_{j})}$ and $t d_{(3, j, c_{j}, i, c_{i})}$ , we compute

x_{i, 1} | | x_{i, 2} \leftarrow [c_{i, 3}]_{0}^{2 l - 1} \oplus z_{i}

x_{j, 1} | | x_{j, 2} \leftarrow [c_{j, 3}]_{0}^{2 l - 1} \oplus z_{j}

V_{i, 1}^{Δ_{i, 1}} V_{j, 1}^{Δ_{j, 1}} = Z_{i}^{y_{i, 1} Δ_{i, 1}} Z_{i}^{y_{j, 1} Δ_{j, 1}} = Z_{i}^{y_{i, 1} Δ_{i, 1} + y_{j, 1} Δ_{j, 1}} = Z_{i}^{f_{i} (0)}

V_{j, 2}^{Δ_{j, 2}} V_{i, 2}^{Δ_{i, 2}} = Z_{i}^{y_{j, 2} Δ_{j, 2}} Z_{i}^{y_{i, 2} Δ_{i, 2}} = Z_{i}^{y_{j, 2} Δ_{j, 2} + y_{i, 2} Δ_{i, 2}} = Z_{i}^{f_{j} (0)}

Therefore, $f_{i} (0) = f_{j} (0)$ holds for $M_{i} = M_{j}$ .

Type 4 Authorization: With $t d_{(4, i, c_{i})} = H_{2} (c_{i, 1}^{x_{i}}, c_{i, 1}, c_{i, 2})$ and $t d_{(4, j, c_{j})} = x_{j}$ , we compute

x_{i, 1} | | x_{i, 2} | | y_{i, 1} | | y_{i, 2} \leftarrow c_{i, 3} \oplus t d_{(4, i, c_{i})}

x_{j, 1} | | x_{i, 2} | | y_{i, 1} | | y_{j, 2} \leftarrow c_{j, 3} \oplus H_{2} (c_{j, 1}^{t d_{4, j}}, c_{j, 1}, c_{j, 2})

Therefore, $f_{i} (x) = f_{j} (x)$ holds for $M_{i} = M_{j}$ .

3. For the third condition, the following scenarios hold:

Type 1 Authorization: If $Tes t_{1} (c_{i}, t d_{1, i}, c_{j}, t d_{1, j}) = 1$ , implies that $f_{i} (x) = f_{j} (x)$ . Since $\Pr [f_{i} (x) = f_{j} (x)]$ is negligible for $M_{i} \neq M_{j}$ , we have $\Pr [Tes t_{1} (c_{i}, t d_{1, i}, c_{j}, t d_{1, j}) = 1]$ is negligible.

Type 2 Authorization: If $Tes t_{2} (c_{i}, t d_{2, i, c_{i}}, c_{j}, t d_{2, j, c_{j}}) = 1$ , implies that $f_{i} (x) = f_{j} (x)$ . Since $\Pr [f_{i} (x) = f_{j} (x)]$ is negligible for $M_{i} \neq M_{j}$ , we have $\Pr [Tes t_{2} (c_{i}, t d_{2, i, c_{i}}, c_{j}, t d_{2, j, c_{j}}) = 1]$ is negligible.

Type 3 Authorization: If $Tes t_{3} (c_{i}, t d_{3, i, c_{i}, j, c_{j}}, c_{j}, t d_{3, j, c_{j}, i, c_{i}}) = 1$ , implies that $V_{i, 1}^{Δ_{1}} V_{j, 1}^{Δ_{1}^{'}} = V_{j, 2}^{Δ_{2}^{'}} V_{i, 2}^{Δ_{2}}$ means $f_{i} (0) = f_{j} (0)$ . Since $\Pr [f_{i} (0) = f_{j} (0)]$ is negligible for $M_{i} \neq M_{j}$ , we have $\Pr [Tes t_{3} (c_{i}, t d_{3, i, c_{i}, j, c_{j}}, c_{j}, t d_{3, j, c_{j}, i, c_{i}}) = 1]$ is negligible.

Type 4 Authorization: If $Tes t_{4} (c_{i}, t d_{4, i, c_{i}}, c_{j}, t d_{1, j}) = 1$ , implies that $f_{i} (x) = f_{j} (x)$ . Since $\Pr [f_{i} (x) = f_{j} (x)]$ is negligible for $M_{i} \neq M_{j}$ , it concludes that $\Pr [Tes t_{4} (c_{i}, t d_{4, i, c_{i}}, c_{j}, t d_{1, j}) = 1]$ is negligible.

Security

Scheme security

In this section, we prove the security of our proposed scheme.

Theorem 2

Our proposed scheme is OW-CCA secure based on DDH assumption in the random oracle model for $Type - α (α = 1, 2, 3)$ authorization against Type I adversary.

Proof

Suppose $A_{1}$ is the Type I adversary breaking the cryptosystem. We build an algorithm $B$ that solves the DDH problem in $G$ by simulating an attack environment to such an adversary. Algorithm $B$ is given with four-tuple $(g, g^{a}, g^{b}, g^{c}) \in G^{4}$ , its target is to test whether or not $g^{ab} = g^{c}$ holds. During the course of the interaction, $B$ records answers that adversary makes in response to all queries, and additionally maintains a separate watch lists for $H_{1}$ .

Let $A_{1}$ chooses t as his target at the beginning of the game.

Setup. $B$ creates system parameter $sp = (G, g, H_{1}, H_{2}, H_{3}, H_{4}, H_{5}, H_{6})$ by employing a security parameter k as in Setup and provides sp to $A_{1}$ , where $H_{1}$ is random oracle controlled by $B$ . Then, $B$ generates n public/private key pairs $(p k_{i}, s k_{i}) (1 \leq i \leq n)$ by algorithm KeyGen and provides all $p k_{i} = (X_{i} = g^{x_{i}}, Y_{i} = g^{y_{i}})$ to $A_{1}$ (if $i = t$ , $p k_{t} = (X_{t} = g^{x_{t}}, Y_{t} = g^{a})$ ) and keeps the $s k_{i} = (x_{i}, y_{i})$ (if $i = t$ , then $s k_{t} = (x_{t})$ and he doesn’t know the $s k_{t}$ corresponding to $Y_{t}$ ) as secret, where $x_{i}, y_{i}, x_{t} \in Z_{q}^{*}$ .

Phase 1. $A_{1}$ may issue queries to all random oracles for polynomial number of times. The constraint is that t does not appear in the decryption key to retrieve the queries:

$H_{1}$ query: Responding to $A_{1}$ queries, $B$ keeps a list of tuples- $H_{1}$ , a tuple of the form $(α_{i}, θ_{i})$ . $B$ does the following:

If $α_{i}$ already appears in the $H_{1}$ list in the form $(α_{i}, θ_{i})$ , then $B$ responds with $H_{1} (α_{i}) = θ_{i}$

Otherwise, $B$ picks $θ_{i}$ $\in {0, 1}^{k}$ randomly, adds a new tuple $(α_{i}, θ_{i})$ into $H_{1}$ -list and responds with $H_{1} (α_{i}) = θ_{i}$

Decryption key queries retrieval (i): $B$ responds $A_{1}$ with $s k_{i}$ created in the Setup ( $i \neq t$ ).

Decryption queries ( $i, c_{i}$ ): Suppose $c_{i} = (c_{i, 1}, c_{i, 2}, c_{i, 3})$ .

If $i \neq t$ , $B$ runs algorithm Decrypt with a valid $c_{i}$ and $s k_{i}$ as inputs and responds $A_{1}$ with the output

Else $B$ proceeds as follows:

If each tuple $(α_{i}, θ_{i})$ in $H_{1}$ -list, $B$ computes:

$M_{i} = c_{i, 2} \oplus θ_{i}$ and $x_{i, 1} | | x_{i, 2} | | y_{i, 1} | | y_{i, 2} = c_{i, 3} \oplus H_{2} (c_{i, 1}^{x_{i}}, c_{i, 1}, c_{i, 2})$

Using $M_{i}$ to generate $P_{1}, P_{2}$ as done in the algorithm Encrypt

Using the two points: $P_{1}, P_{2}$ to construct a straight line $f_{i} (x)$

Test whether $f_{i} (x_{i, 1}) = y_{i, 1}$ and $f_{i} (x_{i, 2}) = y_{i, 2}$ hold, if yes, then $B$ returns $M_{i}$ to $A_{1}$

Else, it $responds ⊥$ to $A_{1}$ .

Authorization queries ( $i, \cdot$ ): For a $Type - α (α = 1, 2, 3)$ authorization:

For $α = 1$ with given i, $B$ runs Auth₁ $(s k_{i})$ ) by $s k_{i}$ and responds $A_{1}$ with $t d_{i, 1} = x_{i}$ $(x_{i} = s k_{i})$ ;

For $α = 2$ with given $(i, c_{i})$ , $B$ runs Auth₂ $(s k_{i}, c_{i})$ by $s k_{i}$ and responds $A_{1}$ with $t d_{i, 2} = H_{2} (c_{i, 1}^{x_{i}}, c_{i, 1}, c_{i, 2})$ $(x_{i} = s k_{i})$ ;

For $α = 3$ with given $(i, c_{i}, j, c_{j})$ , $B$ runs Auth₃ $(s k_{i}, c_{i}, c_{j})$ by $s k_{i}$ , and responds with the following

\begin{array}{l} t d_{(3, i, c_{i}, j, c_{j})} = (z_{i}, V_{i, 1}, V_{i, 2}) \\ = ({[H_{2} (c_{i, 1}^{x_{i}}, c_{i, 1}, c_{i, 2})]}_{0}^{2 l - 1}, Z_{i}^{y_{i, 1}}, Z_{i}^{y_{i, 2}}) \end{array}

where $Z_{i} = c_{i, 1} c_{j, 1}$ , $c_{i} = (c_{i, 1}, c_{i, 2}, c_{i, 3}), c_{j} = (c_{j, 1}, c_{j, 2}, c_{j, 3})$

Challenge. Once $A_{1}$ decides that Phase 1 is over, $B$ takes a message $M_{t}$ randomly, which will be challenged, encrypts it to generate two points ( $x_{t, 1}, y_{t, 1}$ ), ( $x_{t, 2}, y_{t, 2}$ ), and computes the challenge ciphertext $c_{t}^{*} = (c_{t, 1}^{*}, c_{t, 2}^{*}, c_{t, 3}^{*})$ as follows

c_{t, 1}^{*} = g^{b}

c_{t, 2}^{*} = M \oplus H_{1} (g^{c})

c_{t, 3}^{*} = (x_{t, 1} | | x_{t, 2} | | y_{t, 1} | | y_{t, 2}) \oplus H_{2} (c_{t, 1}^{* x_{t}}, c_{t, 1}^{*}, c_{t, 2}^{*})

Finally, it provides $c_{t}^{*}$ to $A_{1}$ as the challenge ciphertext.

4. Phase 2. $A_{1}$ issues more queries as in Phase 1. But there are two conditions as follows:

During decryption key queries retrieval, $i \neq t$ holds;

During decryption queries process, $(t, c_{t}^{*})$ is not allowed.

5. Guess. $A_{1}$ outputs a guess $M_{t}^{*} \in M$ . If $M_{t}^{*} = M_{t}$ holds, $B$ outputs 1 meaning $g^{ab} = g^{c}$ , and 0 otherwise.

$c^{*}$ is a valid ciphertext for challenging information, when $g^{ab} = g^{c}$ .

Theorem 3

Our proposed scheme is IND-CCA secure based on DDH assumption in the random oracle model for $Type - α (α = 1, 2, 3)$ authorization against Type II adversary.

Proof

Suppose that $A_{2}$ is the Type II adversary breaking the encryption scheme. We build an algorithm $B$ that solves the DDH problem in $G$ by simulating an attack environment against such an adversary. Algorithm $B$ is given a four-tuple $(g, g^{a}, g^{b}, g^{c}) \in G^{4}$ , his target is to test whether or not $g^{ab} = g^{c}$ holds. During the course of the interaction, $B$ records answers it makes in response to all queries, and additionally maintains a separate watch lists for $H_{1}$ .

Let $A_{2}$ chooses t as his target at the beginning of the game.

Setup. $B$ generates system parameter $sp = (G, g, H_{1}, H_{2}, H_{3}, H_{4}, H_{5}, H_{6})$ while considering a security parameter k as in the Setup and provides sp to $A_{2}$ , where $H_{1}$ is random oracles controlled by $B$ . Subsequently, $B$ generates n public/private key pairs $(p k_{i}, s k_{i}) (1 \leq i \leq n)$ by invoking algorithm KeyGen and provides all $p k_{i} = (X_{i} = g^{x_{i}}, Y_{i} = g^{y_{i}})$ to $A_{1}$ (if $i = t$ , $p k_{t} = (X_{t} = g^{x_{t}}, Y_{t} = g^{a})$ ) and keeps the $s k_{i} = (x_{i}, y_{i})$ (if $i = t$ then $s k_{t} = (x_{t})$ , and it does not know $s k_{t}$ corresponding to $Y_{t}$ ) as secret, where $x_{i}, y_{i}, x_{t} \in Z_{q}^{*}$ .

Phase 1. $A_{2}$ may issue queries to all random oracles for polynomial number of times. The constraint is that t does not appear in the decryption key to retrieve queries:

$H_{i}$ -query: Responding to $A_{2}$ queries, $B$ keeps a list of tuples- $H_{1}$ , a tuple of the form $(α_{i}, θ_{i})$ . Responding to query $α_{i}$ , $B$ does the following:

If $α_{i}$ already appears in the $H_{1}$ list in the form $(α_{i}, θ_{i})$ , then $B$ responds with $H_{1} (α_{i}) = θ_{i}$

Otherwise, $B$ picks $θ_{i}$ $\in {0, 1}^{k}$ randomly, adds a new tuple $(α_{i}, θ_{i})$ into $H_{1}$ -list and responds with $H_{1} (α_{i}) = θ_{i}$

Decryption key queries retrieval (i): $B$ responds $A_{2}$ with $s k_{i}$ created in the Setup $(i \neq t)$ .

Decryption queries $(i, c_{i})$ : Suppose $c_{i} = (c_{i, 1}, c_{i, 2}, c_{i, 3})$ .

If $i \neq t$ , $B$ runs algorithm Decrypt with a valid $c_{i}$ and $s k_{i}$ as inputs, and responds $A_{1}$ with the output.

Else $B$ proceeds as follows.

If each tuple $(α_{i}, θ_{i})$ in $H_{1}$ -list, $B$ computes:

$M_{i} = c_{i, 2} \oplus θ_{i}$ and $x_{i, 1} | | x_{i, 2} | | y_{i, 1} | | y_{i, 2} | | = c_{i, 3} \oplus H_{2} (c_{i, 1}^{x_{i}}, c_{i, 1}, c_{i, 2})$ ;

Uses $M_{i}$ to generate $P_{1,} P_{2}$ as done in the algorithm Encrypt;

Constructs $f_{i} (x)$ with two points $P_{1,} P_{2}$ ;

Tests whether $f_{i} (x_{i, 1}) = y_{i, 1}$ and $f_{i} (x_{i, 2}) = y_{i, 2}$ hold, if yes, then $β$ returns $M_{i}$ to $A_{2}$ .

Else, it $responds ⊥$ to $A_{2}$ .

Authorization queries ( $i, \cdot$ ): For a $Type - α (α = 1, 2, 3)$ authorization:

In Type 1 authorization, with given i, $B$ runs Auth₁ $(s k_{i})$ by $s k_{i}$ and responds $A_{2}$ with $t d_{i, 1} = x_{i}$ $(x_{i} = s k_{i})$ ;

In Type 2 authorization, given $(i, c_{i})$ , $B$ runs Auth₂ $(s k_{i}, c_{i})$ with $s k_{i}$ and responds $A_{2}$ with $t d_{i, 2} = H_{2} (c_{i, 1}^{x_{i}}, c_{i, 1}, c_{i, 2})$ $(x_{i} = s k_{i})$ ;

In Type 3 authorization, given $(i, c_{i}, j, c_{j})$ , $B$ runs Auth₃ $(s k_{i}, c_{i}, c_{j})$ with $s k_{i}$ and responds as follows

\begin{array}{l} t d_{(3, i, c_{i}, j, c_{j})} = (z_{i}, V_{i, 1}, V_{i, 2}) \\ = ({[H_{2} (c_{i, 1}^{x_{i}}, c_{i, 1}, c_{i, 2})]}_{0}^{2 l - 1}, Z_{i}^{y_{i, 1}}, Z_{i}^{y_{i, 2}}) \end{array}

where $Z_{i} = c_{i, 1} c_{j, 1}$ , $c_{i} = (c_{i, 1}, c_{i, 2}, c_{i, 3}), c_{j} = . 3 (c_{j, 1}, c_{j, 2}, c_{j, 3})$ .

Challenge. Once $A_{2}$ decides that Phase 1 is over, it provides two messages $M_{0}, M_{1} \in {0, 1}^{k}$ randomly to $B$ . $B$ chooses a random bit $b \in {0, 1}$ , then runs Encrypt to generate two points ( $x_{b, 1}, y_{b, 1}$ ), ( $x_{b, 2}, y_{b, 2}$ ) and outputs the challenge ciphertext $c_{t}^{*} = (c_{t, 1}^{*}, c_{t, 2}^{*}, c_{t, 3}^{*})$ as follows

c_{t, 1}^{*} = g^{b}

c_{t, 2}^{*} = M_{b} \oplus H_{1} (g^{c})

c_{t, 3}^{*} = (x_{b, 1} | | x_{b, 2} | | y_{b, 1} | | y_{b, 2}) \oplus H_{2} (c_{t, 1}^{* x_{t}}, c_{t, 1}^{*}, c_{t, 2}^{*})

Finally, it provides $c_{t}^{*}$ to $A_{1}$ as the challenge ciphertext.

4. Phase 2. $A_{2}$ issues more queries as in Phase 1. However, it requires the following:

During decryption key queries retrieval, $i \neq t$ holds;

During decryption queries phase, $(t, c_{t}^{*})$ is not allowed.

For a $Type - α (α = 1, 2, 3)$ authorization queries:

In Type 1 authorization queries, $i = t$ is not allowed;

In Type 2 authorization queries, $(t, c_{t}^{*})$ is not allowed;

In Type 3 authorization queries, $(t, c_{t}^{*},)$ is not allowed;

5. Guess. $A_{2}$ outputs a guess $b^{*}$ . If $b^{*} = b$ , $B$ outputs 1 meaning $g^{ab} = g^{c}$ , otherwise it outputs 0.

When $g^{ab} = g^{c}$ , $c^{*}$ is a valid ciphertext for challenging information.

Authorization security

In this section, we analyze the security of authorization.

In Type 4 authorization, the authorized party has $t d_{(4, i, c_{i})} = Au t_{2} (s k_{i}, c_{i}) = H_{2} (c_{i, 1}^{x_{i}}, c_{i, 1}, c_{i, 2})$ and $t d_{(4, j)} = Au t_{1} (s k_{j}) = x_{j}$ . He cannot get the $s k_{i} = x_{i}$ , which is used by the user. Therefore, adversary cannot get Type 1 authorization.

In Type 3 authorization, the authorized party has the followings

t d_{(3, i, c_{i}, j, c_{j})} = (z_{i}, V_{i, 1}, V_{i, 2}) = ([H_{2} {(c_{i, 1}^{x_{i}}, c_{i, 1}, c_{i, 2}]}_{0}^{2 l - 1}, Z_{i}^{y_{i, 1}}, Z_{i}^{y_{i, 2}})

and

\begin{matrix} t d_{(3, j, c_{j}, i, c_{i})} = (z_{j}, V_{j, 1}, V_{j, 2}) \\ = ([H_{2} (c_{j, 1}^{x_{j}}, c_{j, 1}, c_{j, 2}]_{0}^{2 l - 1}, Z_{j}^{y_{j, 1}}, Z_{j}^{y_{j, 2}}) \end{matrix}

where $Z_{i} = c_{j, 1} c_{i, 1}$ , $Z_{j} = c_{i, 1} c_{j, 1}$ , adversary cannot get ( $y_{i, 1}, y_{i, 2}, y_{j, 1}, y_{j, 2}, x_{i}, x_{j}$ ) without M. Thus, adversary cannot get Type 4 authorization, Type 2 authorization, and Type 1 authorization.

In Type 2 authorization, the authorized party has $t d_{(2, i, c_{i})} = H_{2} (c_{i, 1}^{x_{i}}, c_{i, 1}, c_{i, 2})$ . Adversary cannot get ( $x_{i}, x_{j}$ ). Therefore, it cannot get Type 4 authorization and Type 1 authorization.

Performances analysis

In this section, we discuss the efficiency of our scheme. According to the experimental results in previous studies,^19–21 a bilinear pairing costs about five times than an exponentiation. Computational complexity in modular exponentiation is higher than in modular inverse. We provide an efficiency comparison with the papers by Ma et al.¹⁷ and Lin et al.¹⁸ in Table 1, the storage space comparison with Lin et al.¹⁸ in Table 2, and a brief comparison with others in Table 3.

Table 1.

The comparison of computational complexity.

	$C_{Enc}$	$C_{Dec}$	Auth				Test
	$C_{Enc}$	$C_{Dec}$	Type 1	Type 2	Type 3	Type 4	Type 1	Type 2	Type 3	Type 4
Ma et al.¹⁷	6E	5E	0	2E	2E+2P	1E	2E+2P	2E+2P	2E+2P+2I	2E+2P
Lin et al.¹⁸	4E+3I	3E+3I	0	1E	4E	1E	2E+6I	6I	6E+6I	1E+6I
Our scheme	3E+1I	2E+1I	0	1E	3E	1E	2E+2I	2I	4E+4I	1E+2I

$C_{Enc}$ , $C_{Dec}$ , Auth and Test: the computation complexity of algorithms for encryption, decryption, Type-α of authorization, and Type-α of test; E, P and I: the exponentiation operation, the pairing operation, and the inversion operation in the group $G$ .

Table 2.

The comparison of storage space.

	pk	sk	$C_{len}$
Lin et al.¹⁸	2logq(Bit)	2logq(Bit)	8logq(Bit)
Our scheme	2logq(Bit)	2logq(Bit)	6logq(Bit)

pk, sk, and $C_{len}$ : the bit size of public key, secret key, and ciphertext; logq: the bit length of the public key, the secret key, and the ciphertext.

Table 3.

The comparison of computational complexity with others.

	$C_{Enc}$	$C_{Dec}$
Tang^13,14	4E	2E
Tang¹⁵	5E	2E
Ma¹⁶	6E+2P	2E+2P+1I
Our scheme	3E+1I	2E+1I

$C_{Enc}$ and $C_{Dec}$ : the computation complexity of algorithms for encryption and decryption; E, P and I: the exponentiation operation, the pairing operation, and the inversion operation in the group $G$ .

In Table 1, we compare the presented scheme with the scheme in Ma et al.¹⁷ and Lin et al.¹⁸ with respect to the computation complexity of Encrypt (C_Enc), Decrypt (C_Dec) (from the second to the third columns), four types of Authorization (Auth) (from the fourth to the seventh columns) and four types of Test (from the 8th to the 11th columns). In Table 2, we compare the storage space with Lin et al.,¹⁸ in terms of the sizes of pk, sk, $C_{len}$ (from the second to the forth columns). In Table 3, we present a comparison with the earlier PKEwET schemes while considering the computation complexity in encryption, decryption (from the second to the third columns).

It is quite clear from the tables that our scheme requires smaller ciphertext storage compared to the previous study by Lin et al.¹⁸ Computational cost is less when compared to the previous studies by Ma et al.¹⁷ and Lin et al.¹⁸ in case of Encrypt, Decrypt, four types of Authorizations, and four types of Tests. Thus, our presented scheme is more efficient. From Table 3, it can be observed that our scheme is more efficient than that of Tang^13–15 in encryption.

As a whole, our scheme supports much more flexible authorization and is more efficient, compared to previous studies.^{12–14,17,18} Thus, we remark that our scheme is more practical for the age of big data.

Conclusion

In this article, we present an improved PKEwET-FA scheme. We prove that our scheme is more flexible and more practical comparing with previous works. For the Encrypt, Decrypt, and Test algorithms, we use a straight line instead of the quadratic curve. Finally, we conclude that the presented scheme achieves lower computational complexity and smaller storage space under the same level of security.

Footnotes

Academic editor: Shancang Li

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Foundation of China (NSFC) (Nos. 61370194, 61502048).

References

Boneh

Crescenzo

Ostrovsky

. Public key encryption with keyword search In: Cachin C and Camenisch JL (eds) Advances in cryptology—EUROCRYPT 2004, vol. 3027. Heidelberg: Springer, 2004, p.506C522.

Abdalla

Bellare

Catalano

. Searchable encryption revisited: consistency properties, relation to anonymous IBE, and extensions. In: Shoup

(ed.) Annual international cryptology conference—CRYPTO 2005 (Lecture notes in computer science), vol. 3621. Berlin, Heidelberg: Springer, 2005, pp.205–222.

Liu

Zhu

Wang

. Search pattern leakage in searchable encryption: attacks and new construction. Inform Sciences 2014; 265: 76C188.

Byun

Rhee

Park

. Off-line keyword guessing attacks on recent keyword search schemes over encrypted data. In: Jonker

Petković

(eds) Secure data management. Berlin, Heidelberg: Springer, 2006, pp.75–83.

Cao

Wang

. Privacy-preserving multi-keyword ranked search over encrypted cloud data. IEEE T Parall Distr 2014; 25(1): 222–233.

Fang

Susilo

. Public key encryption with keyword search secure against keyword guessing attacks without random oracle. Inform Sciences 2013; 238: 221–241.

Hofheinz

Weinreb

Searchable encryption with decryption in the standard model cryptology ePrint archive (Report 2008/423), 2008, http://eprint.iacr.org/

Nishioka

Perfect keyword privacy in PEKS systems. In: Nishioka

(ed.) Provable security. Berlin, Heidelberg: Springer, 2012, pp.175–192.

Bellare

ONeill

Deterministic and efficiently searchable encryption. In: Menezes

(ed.) Advances in cryptology—CRYPTO 2007 (Lecture notes in computer science), vol. 4622. Heidelberg: Springer, 2007, p.535.

10.

Bellare

Fischlin

ONeill

. Deterministic encryption: definitional equivalences and constructions without random oracles. In: Wagner

(ed.) Advances in cryptology (Lecture notes in computer science), vol. 5157. Berlin: Springer, 2008, pp.360–378.

11.

Boldyreva

ONeill

. On notions of security for deterministic encryption, and efficient constructions without random oracles. In: Proceedings of the annual international cryptology conference, Santa Barbara, CA, 17–21 August 2008, pp.335–359. Berlin: Springer.

12.

Yang

Tan

Huang

. Probabilistic public key encryption with equality test. In: Pieprzyk

(ed.) Cryptographers track at the RSA conference. Berlin, Heidelberg: Springer, 2010, pp.119–131.

13.

Tang

Towards public key encryption scheme supporting equality test with fine-grained authorization. In: Proceedings of the 16th Australasian conference on information security and privacy, Melbourne, VIC, Australia, 11–13 July 2011, vol. 6812, p.389C406. New York: ACM.

14.

Tang

Public key encryption schemes supporting equality test with authorisation of different granularity. Int J Appl Cryptograp 2012; 2(4): 304C321.

15.

Tang

Public key encryption supporting plaintext equality test and user-specified authorization. Secure Commun Netw 2012; 5(12): 1351C1362.

16.

Identity-based encryption with outsourced equality test in cloud computing. Inform Sciences 2016; 328: 389–402.

17.

Huang

Zhang

. Efficient public key encryption with equality test supporting flexible authorization. IEEE T Inf Foren Sec 2015; 10(3): 458–470.

18.

Lin

Zhang

Public key encryption supporting equality test and flexible authorization without bilinear pairings IACR cryptology ePrint archive, 2016, http://eprint.iacr.org/2016/277.

19.

Lynn

Pairing based cryptography-benchmarks, http://crypto.stanford.edu/pbc/times.html, 2014.

20.

Lauter

The advantages of elliptic curve cryptography for wireless security. IEEE T Wirel Commun 2004; 11(1): 62–67.

21.

Yoshitomi

Takagi

Kiyomoto

. Efficient implementation of the pairing on mobile phones using BREW. IEICE T Inf Syst 2008; 6434: 1330–1337.

Pairing-free equality test over short ciphertexts

Abstract

Keywords

Introduction

Motivation and contribution

Organization

Preliminaries

Definitions

Definition 1

Definition 2 (Correctness)

Shamir’s secret sharing scheme

Security models

Game 1

Definition 3

Game 2

Definition 4

Notice

The proposed scheme

Theorem 1

Proof

Security

Scheme security

Theorem 2

Proof

Theorem 3

Proof

Authorization security

Performances analysis

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References