# Noninteractive Verifiable Outsourcing Algorithm for Bilinear Pairing with Improved Checkability

Authors: Yanli Ren; Min Dong; Zhihua Niu; Xiaoni Du
Journal: Security and Communication Networks
 (2017)

---

## Abstract

It is well known that the computation of bilinear pairing is the most expensive operation in pairing-based cryptography. In this paper, we propose a noninteractive verifiable outsourcing algorithm of bilinear pairing based on two servers in the one-malicious model. The outsourcer need not execute any expensive operation, such as scalar multiplication and modular exponentiation. Moreover, the outsourcer could detect any failure with a probability close to 1 if one of the servers misbehaves. Therefore, the proposed algorithm improves checkability and decreases communication cost compared with the previous ones. Finally, we utilize the proposed algorithm as a subroutine to achieve an anonymous identity-based encryption (AIBE) scheme with outsourced decryption and an identity-based signature (IBS) scheme with outsourced verification.


---

## Body

## 1. Introduction

Outsourcing computation has received widespread attention with the development of cloud computing and the proliferation of mobile devices [1]. Despite of the huge benefits, it also encounters some security concerns and challenges. Firstly, the computation tasks often include some private information that should not be disclosed to the cloud servers, since the servers are not fully trusted. Secondly, the cloud servers may return an invalid result, but the outsourcer fails to detect the error [1]. Therefore, two main security challenges of the outsourcing computation are privacy and checkability: (1) the cloud servers cannot learn anything about the private inputs and the outputs of the computation outsourced to them; (2) the outsourcer can detect any failure if the cloud servers return a wrong computation result.Verifiable computation (VC) allows a client with limited computation capability to outsource evaluation of a function on some inputs to a powerful but semitrusted server [2, 3]. The client in this model first executes a lot of off-line computation and encrypts the function which will be evaluated and then sends the encrypted function to the server. The server then performs the computation on the encoded function and responds with a result and a proof that the result is correct. Finally, the client verifies whether the computation has been carried out honestly based on the server’s proof. During the whole process, the computation cost of the client is less than computing the function directly itself.Our Contributions. In this paper, we propose a noninteractive verifiable outsourcing algorithm of bilinear pairing in the one-malicious model of two untrusted servers, which improves the checkability of the outsourcer without any interactive operation between the outsourcer and the server. In the proposed algorithm, the outsourcer could detect any failure with a probability close to 1 if one of the servers returns the false result. The proposed algorithm improves the checkability at the expense of only a little efficiency when compared with previous algorithms. Finally, we utilize the proposed algorithm as a subroutine to achieve an AIBE scheme with outsourced decryption and an IBS scheme with outsourced verification.


### 1.1. Related Works

In the cryptographic community, outsourcing expensive operations to a semitrusted device is widely studied. Chaum and Pedersen [4] introduced the concept of “wallets with observers” that allows installing a piece of hardware on the client’s device to execute some operations for each transaction. Hohenberger and Lysyanskaya formalized this model [5] and presented algorithms for the computation of modular exponentiations (MExps) based on two noncolluding servers. Further, Chen et al. [1] proposed a new outsourcing algorithm for MExps with improved efficiency and checkability based on the same model as [5]. However, it is still possible for the outsourcer to be cheated by the server. Ren et al. then constructed a verifiable outsourcing scheme of MExps, where the outsourcer can detect the error with a probability of 1 if the server misbehaves [6]. Lai et al. [7] proposed an attribute-based encryption (ABE) scheme with verifiable outsourcing decryption, which guaranteed that an outsourcer can efficiently detect the wrong results. Qin et al. [8] then proposed new ABE scheme with outsourced decryption, where the outsourcer could verify the outsourcing results with a high efficiency at the expense of minimal overhead. Chen et al. first considered the problem of outsourcing computation in attribute-based signature (ABS) schemes and delegated the verification of signature to an untrusted server [9]. Yu et al. [10] proposed a secure and efficient cloud storage auditing scheme with verifiable outsourcing of key updates. The process of key updates is outsourced to the third party auditor (TPA), and the TPA only knows the encrypted secret key. Meanwhile, the outsourcer could verify the effectiveness of encrypted secret keys when uploading new files to the cloud server. Also, Wang et al. [11] proposed a privacy-preserving public auditing system for data storage security and extended it to handle the problem of multiple auditing, where the TPA could learn nothing about data and the integrity of data could be verified publicly. Other works target specific classes of functions, such as revocable identity-based encryption [12], solution of linear equations [13], and image features extraction [14].In recent years, bilinear pairings have various applications in constructing new cryptographic primitive, for example, identity-based encryption [15], short signature [16], and key agreement protocol [17]. In pairing-based cryptography, the computation of bilinear pairing is the most expensive operation and it has important effects on efficiency of these schemes or protocols. Thus, a lot of research work has been done to compute bilinear pairing efficiently [18, 19].Chevallier-Mames et al. [20] presented the first algorithm for secure outsourcing of bilinear pairings based on an untrusted server, where the outsourcer could detect any failure with probability of 1 if the server returns an incorrect result. However, the outsourcer must execute some other expensive operations such as scalar multiplications and modular exponentiations, where these computations are even comparable to those of bilinear pairings in some scenarios [19, 21]. Subsequently, other works on delegation of bilinear pairings [22, 23] also suffer from the same problems. Chen et al. proposed the first efficient outsourcing algorithm of bilinear pairing in the one-malicious version of two untrusted program models [24], where the outsourcer only carried out 5 point additions and 4 multiplications without any expensive operations, which is suitable for the computation-limited client. However, the checkability of the algorithm in [24] is only 1/2, and the outsourcer may accept a false result returned by a malicious server with probability of 1/2. Tian et al. presented two outsourcing algorithms of bilinear pairing based on two servers [25]. One is more efficient than the algorithm of [24], and the outsourcer needs to execute 4 point additions and 3 multiplications with the same checkability. The other algorithm is more flexible based on two untrusted servers with improved checkability. As we know, it is also possible for the outsourcer to be cheated by the server and the error cannot be detected successfully. Recently, Ren et al. presented a new outsourcing algorithm of bilinear pairing, which improves the checkability of the outsourcer to 1, and it is impossible for the server to cheat the outsourcer to accept a false outsourcing result [26]. However, it needs two interactive rounds between the outsourcer and the server and increases the communication cost, though the checkability is improved to 1.


### 1.2. Organization

The rest of this paper is organized as follows. In Section2, we introduce the definition of bilinear pairing and security model of the outsourcing scheme. A noninteractive verifiable outsourcing algorithm of bilinear pairing is presented and its security analysis is given in Section 3. In Section 4, we introduce two applications of the proposed outsourcing scheme: an AIBE scheme with outsourced decryption and an IBS scheme with outsourced verification. The performance evaluation of the proposed scheme is presented in Section 5. In Section 6, we conclude the paper.


## 1.1. Related Works

In the cryptographic community, outsourcing expensive operations to a semitrusted device is widely studied. Chaum and Pedersen [4] introduced the concept of “wallets with observers” that allows installing a piece of hardware on the client’s device to execute some operations for each transaction. Hohenberger and Lysyanskaya formalized this model [5] and presented algorithms for the computation of modular exponentiations (MExps) based on two noncolluding servers. Further, Chen et al. [1] proposed a new outsourcing algorithm for MExps with improved efficiency and checkability based on the same model as [5]. However, it is still possible for the outsourcer to be cheated by the server. Ren et al. then constructed a verifiable outsourcing scheme of MExps, where the outsourcer can detect the error with a probability of 1 if the server misbehaves [6]. Lai et al. [7] proposed an attribute-based encryption (ABE) scheme with verifiable outsourcing decryption, which guaranteed that an outsourcer can efficiently detect the wrong results. Qin et al. [8] then proposed new ABE scheme with outsourced decryption, where the outsourcer could verify the outsourcing results with a high efficiency at the expense of minimal overhead. Chen et al. first considered the problem of outsourcing computation in attribute-based signature (ABS) schemes and delegated the verification of signature to an untrusted server [9]. Yu et al. [10] proposed a secure and efficient cloud storage auditing scheme with verifiable outsourcing of key updates. The process of key updates is outsourced to the third party auditor (TPA), and the TPA only knows the encrypted secret key. Meanwhile, the outsourcer could verify the effectiveness of encrypted secret keys when uploading new files to the cloud server. Also, Wang et al. [11] proposed a privacy-preserving public auditing system for data storage security and extended it to handle the problem of multiple auditing, where the TPA could learn nothing about data and the integrity of data could be verified publicly. Other works target specific classes of functions, such as revocable identity-based encryption [12], solution of linear equations [13], and image features extraction [14].In recent years, bilinear pairings have various applications in constructing new cryptographic primitive, for example, identity-based encryption [15], short signature [16], and key agreement protocol [17]. In pairing-based cryptography, the computation of bilinear pairing is the most expensive operation and it has important effects on efficiency of these schemes or protocols. Thus, a lot of research work has been done to compute bilinear pairing efficiently [18, 19].Chevallier-Mames et al. [20] presented the first algorithm for secure outsourcing of bilinear pairings based on an untrusted server, where the outsourcer could detect any failure with probability of 1 if the server returns an incorrect result. However, the outsourcer must execute some other expensive operations such as scalar multiplications and modular exponentiations, where these computations are even comparable to those of bilinear pairings in some scenarios [19, 21]. Subsequently, other works on delegation of bilinear pairings [22, 23] also suffer from the same problems. Chen et al. proposed the first efficient outsourcing algorithm of bilinear pairing in the one-malicious version of two untrusted program models [24], where the outsourcer only carried out 5 point additions and 4 multiplications without any expensive operations, which is suitable for the computation-limited client. However, the checkability of the algorithm in [24] is only 1/2, and the outsourcer may accept a false result returned by a malicious server with probability of 1/2. Tian et al. presented two outsourcing algorithms of bilinear pairing based on two servers [25]. One is more efficient than the algorithm of [24], and the outsourcer needs to execute 4 point additions and 3 multiplications with the same checkability. The other algorithm is more flexible based on two untrusted servers with improved checkability. As we know, it is also possible for the outsourcer to be cheated by the server and the error cannot be detected successfully. Recently, Ren et al. presented a new outsourcing algorithm of bilinear pairing, which improves the checkability of the outsourcer to 1, and it is impossible for the server to cheat the outsourcer to accept a false outsourcing result [26]. However, it needs two interactive rounds between the outsourcer and the server and increases the communication cost, though the checkability is improved to 1.


## 1.2. Organization

The rest of this paper is organized as follows. In Section2, we introduce the definition of bilinear pairing and security model of the outsourcing scheme. A noninteractive verifiable outsourcing algorithm of bilinear pairing is presented and its security analysis is given in Section 3. In Section 4, we introduce two applications of the proposed outsourcing scheme: an AIBE scheme with outsourced decryption and an IBS scheme with outsourced verification. The performance evaluation of the proposed scheme is presented in Section 5. In Section 6, we conclude the paper.


## 2. Definitions

In this section, we introduce the properties of bilinear pairings, security definition, and model of the proposed outsourcing algorithms.


### 2.1. Bilinear Pairings

Letq be a large prime, G,G^ are two cyclic addition groups of order q, and GT is a cyclic multiplicative group of order q. P,Q are generators of G,G^, respectively. e:G×G^→GT is a bilinear map with the following properties [15, 16, 21]:1.
Bilinear:ea0R,b0V=eR,Va0b0 for any R∈G,V∈G^, and a0,b0∈Zq∗2.
Nondegenerate: there existR0∈G,V0∈G^ such that eR0,V0≠13.
Computable: there is an efficient algorithm to computeeR,V for any R∈G,V∈G^The bilinear map and the bilinear pairing can be realized by supersingular elliptic curves or hyperelliptic curves over finite groups and Weil or Tate pairings, respectively [15, 16, 21].


### 2.2. Security Definition and Model

Now we review the formal security definition of an outsourcing algorithm introduced by [5]. An algorithmAlg includes a trusted part T and an untrusted program U, and TU denotes the works carried out by T invoking U. An adversary A is simulated by a pair of algorithms E,U′, where E denotes the adversarial environment that submits adversarial inputs forAlg and U′ represents adversarial software written by E. As described in [5], we assume that the two adversaries E,U′ can only make direct communication before the execution of TU, and, in other cases, they can only communicate with each other by passing messages through the outsourcer T.Definition 1 (algorithm with outsourceI/O).
An algorithmAlg takes five inputs and generates three outputs. The first three inputs are chosen by an honest party, and the last two inputs are generated by the environment E. The first input is honest and secret, which is unknown for both E and U′; the second is honest and protected, which may be public for E but is private for U′; the third is honest and unprotected, which may be public for both E and U′; the fourth is adversarial and protected, which is public for E but is protected from U′; and the last one is adversarial and unprotected, which is public for E and U′. Similarly, the first output is secret, which is protected from E and U′; the second is protected, which may be public for E but not U′; and the third is unprotected, which may be public for both E and U′.
The following security definition ensures that bothE and U′ cannot obtain any information about the private inputs and outputs of TU, even if T uses the malicious software U′ written by E.Definition 2 (outsource-security).
LetAlg be an algorithm with outsourceI/O. TU is called an outsource-secure implementation ofAlg if the following conditions hold:(1)Correctness: TU is a correct implementation ofAlg(2)Security: for all probabilistic polynomial-time (PPT) adversaries A=E,U′, there exist two PPT simulators S1,S2 such that the following pairs of random variables are computationally indistinguishablePair One.
E
V
I
E
W
r
e
a
l
~
E
V
I
E
W
i
d
e
a
l, which means that the malicious environment E cannot gain anything interesting about the private inputs and outputs during the execution of TU. The detailed definitions of the real process and the ideal process are omitted because of limited space; please see [5] for the details.Pair Two.
U
V
I
E
W
r
e
a
l
~
U
V
I
E
W
i
d
e
a
l, which means that the untrusted software U′ written by E learns nothing about the inputs and outputs during the execution of TU. Please also see [5] for the detailed definitions.Assume thatTU is a correct implementation ofAlg; we have the following definitions.Definition 3 (α-efficient, secure outsourcing).
A pair of algorithmsT,U are α-efficient if the running time of Tis not more than an α-multiplicative factor of that ofAlg for any input x.Definition 4 (β-checkable, secure outsourcing).
A pair of algorithmsT,U are β-checkable if T detects any deviation of U′ from its advertised functionality during the implementation of TU′(x) with probability not less than β for any input x.Definition 5 (α,β-outsource-security).
A pair of algorithmsT,U are called an α,β-outsource-secure implementation ofAlg if they are both α-efficient and β-checkable.
The proposed algorithms are executed based on two untrusted program models introduced by [5]. In this model, the adversarial environment E writes two programs U′=U1′,U2′, and T installs these programs in a manner such that all subsequent communication between any two of E, U1′, and U2′ must pass through T. The new adversary attacking T is A=E,U1′,U2′. We assume that at most one of the programs misbehaves, but we do not know which one. It is named as the one-malicious version of two untrusted models. In the real world, it is equivalent to buying two copies of the untrusted software from different vendors and achieving the outsource security as long as one of them is honest [1].


## 2.1. Bilinear Pairings

Letq be a large prime, G,G^ are two cyclic addition groups of order q, and GT is a cyclic multiplicative group of order q. P,Q are generators of G,G^, respectively. e:G×G^→GT is a bilinear map with the following properties [15, 16, 21]:1.
Bilinear:ea0R,b0V=eR,Va0b0 for any R∈G,V∈G^, and a0,b0∈Zq∗2.
Nondegenerate: there existR0∈G,V0∈G^ such that eR0,V0≠13.
Computable: there is an efficient algorithm to computeeR,V for any R∈G,V∈G^The bilinear map and the bilinear pairing can be realized by supersingular elliptic curves or hyperelliptic curves over finite groups and Weil or Tate pairings, respectively [15, 16, 21].


## 2.2. Security Definition and Model

Now we review the formal security definition of an outsourcing algorithm introduced by [5]. An algorithmAlg includes a trusted part T and an untrusted program U, and TU denotes the works carried out by T invoking U. An adversary A is simulated by a pair of algorithms E,U′, where E denotes the adversarial environment that submits adversarial inputs forAlg and U′ represents adversarial software written by E. As described in [5], we assume that the two adversaries E,U′ can only make direct communication before the execution of TU, and, in other cases, they can only communicate with each other by passing messages through the outsourcer T.Definition 1 (algorithm with outsourceI/O).
An algorithmAlg takes five inputs and generates three outputs. The first three inputs are chosen by an honest party, and the last two inputs are generated by the environment E. The first input is honest and secret, which is unknown for both E and U′; the second is honest and protected, which may be public for E but is private for U′; the third is honest and unprotected, which may be public for both E and U′; the fourth is adversarial and protected, which is public for E but is protected from U′; and the last one is adversarial and unprotected, which is public for E and U′. Similarly, the first output is secret, which is protected from E and U′; the second is protected, which may be public for E but not U′; and the third is unprotected, which may be public for both E and U′.
The following security definition ensures that bothE and U′ cannot obtain any information about the private inputs and outputs of TU, even if T uses the malicious software U′ written by E.Definition 2 (outsource-security).
LetAlg be an algorithm with outsourceI/O. TU is called an outsource-secure implementation ofAlg if the following conditions hold:(1)Correctness: TU is a correct implementation ofAlg(2)Security: for all probabilistic polynomial-time (PPT) adversaries A=E,U′, there exist two PPT simulators S1,S2 such that the following pairs of random variables are computationally indistinguishablePair One.
E
V
I
E
W
r
e
a
l
~
E
V
I
E
W
i
d
e
a
l, which means that the malicious environment E cannot gain anything interesting about the private inputs and outputs during the execution of TU. The detailed definitions of the real process and the ideal process are omitted because of limited space; please see [5] for the details.Pair Two.
U
V
I
E
W
r
e
a
l
~
U
V
I
E
W
i
d
e
a
l, which means that the untrusted software U′ written by E learns nothing about the inputs and outputs during the execution of TU. Please also see [5] for the detailed definitions.Assume thatTU is a correct implementation ofAlg; we have the following definitions.Definition 3 (α-efficient, secure outsourcing).
A pair of algorithmsT,U are α-efficient if the running time of Tis not more than an α-multiplicative factor of that ofAlg for any input x.Definition 4 (β-checkable, secure outsourcing).
A pair of algorithmsT,U are β-checkable if T detects any deviation of U′ from its advertised functionality during the implementation of TU′(x) with probability not less than β for any input x.Definition 5 (α,β-outsource-security).
A pair of algorithmsT,U are called an α,β-outsource-secure implementation ofAlg if they are both α-efficient and β-checkable.
The proposed algorithms are executed based on two untrusted program models introduced by [5]. In this model, the adversarial environment E writes two programs U′=U1′,U2′, and T installs these programs in a manner such that all subsequent communication between any two of E, U1′, and U2′ must pass through T. The new adversary attacking T is A=E,U1′,U2′. We assume that at most one of the programs misbehaves, but we do not know which one. It is named as the one-malicious version of two untrusted models. In the real world, it is equivalent to buying two copies of the untrusted software from different vendors and achieving the outsource security as long as one of them is honest [1].


## 3. Verifiable Secure Outsourcing of Bilinear Pairing

As [5], a subroutine named Rand is used to speed up the computations. The inputs for Rand are a prime q, two cyclic addition groups G,G^ of order q, and a bilinear map e:G×G^→GT, where GT is a cyclic multiplicative group of order q and the output for each invocation is a random, independent vector of the following form:(1)t1,t2,a1P+a2P,a3P,a4P,b1P+b2P,b3P,-a1P+a2P+b3P,-t2a1P+a2P,-a1P+t2a2P,a1Q+a2Q,a3Q,b1Q+b2Q,b3Q,b4Q,-b1Q+b2Q+a3Q,-t1b1Q+b2Q,-b1Q+t1b2Q,ea3P,a3Q,eb3P,b3Q,ea4P,b1Q+b2Qt1+1,ea1P+a2P,b4Qt2+1,ea1P+a2P,b1Q+b2Q-1,where a1,a2,a3,a4,b1,b2,b3,b4∈RZq∗,t1,t2∈2,3,…,s, and s is a small number.We can use the table-lookup method to implement this functionality. First, a trusted server computes a table of random, independent vectors in advance and then stores it into the memory ofT. For each invocation ofi, T needs to retrieves a new vector in the table.


### 3.1. Verifiable Outsourcing Algorithm

We propose a noninteractive verifiable outsourcing algorithmNIVBP for bilinear pairing in the one-malicious model. InNIVBP algorithm, T outsources its bilinear pairing computations to U1 and U2 by invoking the subroutine Rand. A requirement forNIVBP is that the adversary A cannot know any useful information about the inputs and outputs ofNIVBP.Letq be a large prime. The input ofNIVBP is A∈G and B∈G^, and the output is eA,B. A and B are both computationally blinded to U1 and U2. The proposedNIVBP algorithm is described as follows:(1)T firstly runs Rand one time to create a blinding vector as (1).(2)T queries U1 in random order as follows:(2)U1A+a1P+a2P,B+b1Q+b2Q⟶α11=eA+a1P+a2P,B+b1Q+b2Q,U1A+b1P+b2P,a3Q⟶α12=eA+b1P+b2P,a3Q,U1-b3P-a1P-a2P,B+b3Q⟶α13=e-b3P-a1P-a2P,B+b3Q,U1A+a4P,-t1b1Q-b2Q⟶α14=eA+a4P,-t1b1Q-b2Q,U1-t2a1P-a2P,B+b4Q⟶α15=e-t2a1P-a2P,B+b4Q.Similarly,T queries U2 in random order as follows:(3)U2A+a1P+a2P,B+b1Q+b2Q⟶α21=eA+a1P+a2P,B+b1Q+b2Q,U2A+a3P,-a3Q-b1Q-b2Q⟶α22=eA+a3P,-a3Q-b1Q-b2Q,U2b3P,B+a1Q+a2Q⟶α23=eb3P,B+a1Q+a2Q,U2A+a4P,-b1Q-t1b2Q⟶α24=eA+a4P,-b1Q-t1b2Q,U2-a1P-t2a2P,B+b4Q⟶α25=e-a1P-t2a2P,B+b4Q.(3)T verifies whether U1 and U2 generate the correct outputs, which means that (4)–(6) hold.
(a)(4)α11=α21(b)(5)α12·α22·ea3P,a3Qt1+1=α14·α24·ea4P,b1Q+b2Qt1+1(c)(6)α13·α23·eb3P,b3Qt2+1=α15·α25·ea1P+a2P,b4Qt2+1.If not,T outputs “error”; otherwise, T outputs(7)α12·α22·ea3P,a3Q=eA,b1Q+b2Q-1,α13·α23·eb3P,b3Q=ea1P+a2P,B-1,(8)eA,B=α11·eA,b1Q+b2Q-1·ea1P+a2P,B-1·ea1P+a2P,b1Q+b2Q-1.Correctness. It is obvious that formula (4) holds if two servers are all honest. In addition,(9)α12·α22·ea3P,a3Q=eb1P+b2P,a3QeA+a3P,-b1Q-b2Q=eA,b1Q+b2Q-1,(10)α13·α23·eb3P,b3Q=e-a1P-a2P,B+b3Qeb3P,a1Q+a2Q=ea1P+a2P,B-1,(11)α12α22ea3P,a3Qt1+1=α14α24ea4P,b1Q+b2Qt1+1=eA+a4P,b1Q+b2Q-t1+1ea4P,b1Q+b2Qt1+1=eA,b1Q+b2Q-t1+1,(12)α13α23eb3P,b3Qt2+1=α15α25ea1P+a2P,b4Qt2+1=ea1P+a2P,B+b4Q-t2+1ea1P+a2P,b4Qt2+1=ea1P+a2P,B-t2+1.Therefore, formulas (4)–(6) hold according to the above analysis. Finally, T obtains eA,B as (8).Remark 6.
If one of the servers is dishonest, the results could be verified successfully with a probability close to 1 except that the dishonest server knows the values ofα11,α12,α13,α14,α15 (or α21,α22,α23,α24,α25) and t1,t2. As we know, five queries sent to U1 and U2 are submitted in random order and t1,t2∈2,3,…,s. So, the dishonest server could guess the values of α11,α12,α13,α14,α15(or α21,α22,α23,α24,α25) and t1,t2 with the probabilities of 1/5! and 1/s-12, respectively. Therefore, the checkability of theNIVBP algorithm is (13)1-15!s-12=1-1120s-12≈1.Remark 7.
The proposed algorithmNIVBP is also applicative in the condition where G,G^ are two cyclic multiplication groups. Let g,g^ be generators of G,G^, respectively. e:G×G^→GT is a bilinear map. In this case, the inputs ofNIVBP are also A∈G and B∈G^, and the output is also eA,B. The details are also omitted because of limited space.


### 3.2. Security Analysis

Theorem 8.
In the one-malicious model, the proposed algorithmT,U1,U2 is an outsource-secure implementation ofNIVBP, where the input A,B may be honest and secret or honest and protected or adversarial and protected.Proof.
LetA=E,U1′,U2′ be a PPT adversary that interacts with a PPT algorithm T in the one-malicious model.
First, we prove thatEVIEWreal~EVIEWideal, which means that the environment E learns nothing during the execution of (T,(U1,U2)). If the input (A,B) is honest and protected or adversarial and protected, it is obvious that the simulator S1 behaves the same as in the real execution. Therefore, we only need to prove the case where A,B is an honest, secret input.
So, suppose thatA,B is an honest, secret input. The simulator S1 in the ideal experiment behaves as follows. On receiving the input on round i, S1 ignores it and instead makes five random queries of the form αj,βj to both U1′ and U2′ Finally, S1 randomly checks one output eαj,βj from each program. If an error is detected, S1 saves all states and outputs Ypi = “error,” Yui=⌀,repi=1, and thus the final output for ideal process is (estatei, “error,” ⌀). If no error is detected, S1 checks the remaining four outputs. If all checks pass, S1 outputs Ypi=⌀,Yui=⌀,repi=0; that is, the final output for ideal process is estatei,ypi,yui; otherwise, S1 selects a random element r and outputs Ypi=r,Yui=⌀,repi=1, and the output for ideal process is estatei,r,⌀.In addition, we need to show that the inputs toU1′,U2′ in the real experiment are computationally indistinguishable from those in the ideal one. In the ideal experiment, the inputs are selected uniformly at random. In the real one, each part of all five queries that T makes to any program is generated by invoking the subroutine Rand and thus is computationally indistinguishable from random numbers. Therefore, we consider three possible conditions. If U1′,U2′ both are honest in round i, EVIEWreali~EVIEWideali, since the outputs ofNIVBP are not replaced and repi=0; if one of (U1′,U2′) is dishonest in round i, the fault must be detected by both T and S1 with a probability close to 1, resulting in an output of “error”; otherwise, the output ofNIVBP is corrupted with a probability of 1/120(s-1)2. In the real experiment, the five outputs generated by U1′,U2′ are multiplied together along with a random value. Thus, EVIEWreali~EVIEWideali even when one of U1′,U2′ misbehaves, so we conclude that EVIEWreal~EVIEWideal.Second, we prove thatUVIEWreal~UVIEWideal, which means that the untrusted software U1′,U2′ learns nothing during the execution of T,U1′,U2′. In the ideal experiment, the simulator S2 always behaves as follows: when receiving the input on round i, S2 ignores it but submits five random queries of the form αj,βj to U1′ and U2′. Then S2 saves its states and those of U1′,U2′. Since the honest, secret or honest, protected or adversarial, protected inputs are all private for U1′,U2′, the simulator S2 is applicable to all those conditions. As shown in Pair One, the inputs to U1′,U2′ in the real experiment are computationally indistinguishable from those in the ideal one randomly chosen by S2. Thus, UVIEWreali~UVIEWideali for each round i, and so UVIEWreal~UVIEWideal.Theorem 9.
In the one-malicious model, the proposed algorithmT,U1,U2 in Section 3.1 is verifiable; that is, the outsourcer can test the error with a probability close to 1 if one of the servers outputs the false result.Proof.
Assume thatU1 is an honest server and U2 is a malicious server. At the end of the algorithm, the outsourcer verifies the results by formulas (4)–(6). It is obvious that U2 must generate the correct value of α21; otherwise, formula (4) cannot pass the verification with a probability of 1. Thus, the only possibility of U2 cheating T is returning the false value of α21,α22,α23,α24,α25, which is denoted by α21¯,α22¯,α23¯,α24¯,α25¯, respectively.
Assume thatα21¯,α22¯,α23¯,α24¯,α25¯ could pass the verification of formulas (5) and (6); that is, (14)α12·α22¯·ea3P,a3Qt1+1=α14·α24¯·ea4P,b1Q+b2Qt1+1,α13·α23¯·eb3P,b3Qt2+1=α15·α25¯·ea1P+a2P,b4Qt2+1,which means that(15)α22-t1+1α24¯=α14·ea4P,b1Q+b2Qt1+1α12t1+1·ea3P,a3Qt1+1,α23-t1+1α25¯=α15·ea1P+a2P,b4Qt2+1α13t2+1·eb3P,b3Qt2+1.
SinceU1 is an honest server, α11,α12,α13,α14,α15 must be correct. In addition, ea3P,a3Q,eb3P,b3Q,ea4P,b1Q+b2Qt1+1,ea1P+a2P,b4Qt2+1 are generated randomly by Rand subroutine, and so these values must be true. Thus, the values of α22-t1+1/α24¯ and α23-t2+1/α25¯ should be true even if α21¯,α22¯,α23¯,α24¯,α25¯ are incorrect; otherwise, they could not pass the verification of formulas (5) and (6).
In order to obtain the true values ofα22-t1+1/α24¯ and α23-t2+1/α25¯, U2 must guess the values of α21,α22,α23, α24,α25 and t1,t2. As shown in Section 3.1, the probabilities of guessing the true values of α21,α22,α23,α24,α25 and t1,t2 are 1/5! and 1/s-12, respectively. Therefore, the outsourcer can test the error with a probability of 1-1/5!(s-1)2=1-1/120s-12≈1.Theorem 10.
In the one-malicious model, the proposed algorithmT,U1,U2 is an Os/m,≈1-outsource-secure implementation ofNIVBP, where s is a small positive integer and m is the bit length of q and q is the order of G,G^.Proof.
The proposed algorithmNIVBP makes one call to Rand and 8 point additions (PA) in G or G^ and Os multiplication in GT in order to compute eA,B. As shown in [24], it takes roughly Om multiplications in resulting finite field to compute the bilinear pairing, where m is the bit length of q. Thus, the proposed algorithm is an O(s/m)-efficient implementation ofNIVBP. On the other hand, it must be detected with a probability close to 1 if U1 or U2 fails during any execution ofNIVBP from Theorem 9.


### 3.3. Comparison

We compare the outsourcing algorithms for bilinear pairing with input privacy in Table1, where s is a small positive integer and “PA” and “M” denote the operation of point addition in G or G^ and multiplication in GT, respectively.Table 1
Comparison of the outsourcing algorithms for bilinear pairing.
Algorithm
Pair [24]
TZR1 [25]
TZR2 [25] (s=4)
VBP [26]
NIVBP(s=4)
PA(T)
5
4
11
8
8
M(T)
4
3
9
11
19
Invoke (Rand)
3
1
2
2
1
Pair(U)
8
6
6
6
10
MExp(U)
0
0
0
4
0
Interactive
No
No
No
Yes
No
Servers
Two
Two
Two
Two
Two
Checkability
0.5
0.5
0.84
1
0.999From Table1, we conclude that theNIVBP algorithm increases checkability of the outsourcer, though a little computation cost is appended compared with Pair and TZR1 algorithms. In addition, theNIVBP algorithm improves computation efficiency and checkability of the outsourcer simultaneously compared with TZR2 algorithm for the same parameter: s=4. The efficiency and checkability of theNIVBP algorithm are nearly the same as those of VBP algorithm, but it decreases the communication cost, since it is noninteractive while the VBP algorithm is interactive. Therefore, theNIVBP algorithm increases checkability and decreases communication cost of the outsourcer, although a little computation cost is appended.


## 3.1. Verifiable Outsourcing Algorithm

We propose a noninteractive verifiable outsourcing algorithmNIVBP for bilinear pairing in the one-malicious model. InNIVBP algorithm, T outsources its bilinear pairing computations to U1 and U2 by invoking the subroutine Rand. A requirement forNIVBP is that the adversary A cannot know any useful information about the inputs and outputs ofNIVBP.Letq be a large prime. The input ofNIVBP is A∈G and B∈G^, and the output is eA,B. A and B are both computationally blinded to U1 and U2. The proposedNIVBP algorithm is described as follows:(1)T firstly runs Rand one time to create a blinding vector as (1).(2)T queries U1 in random order as follows:(2)U1A+a1P+a2P,B+b1Q+b2Q⟶α11=eA+a1P+a2P,B+b1Q+b2Q,U1A+b1P+b2P,a3Q⟶α12=eA+b1P+b2P,a3Q,U1-b3P-a1P-a2P,B+b3Q⟶α13=e-b3P-a1P-a2P,B+b3Q,U1A+a4P,-t1b1Q-b2Q⟶α14=eA+a4P,-t1b1Q-b2Q,U1-t2a1P-a2P,B+b4Q⟶α15=e-t2a1P-a2P,B+b4Q.Similarly,T queries U2 in random order as follows:(3)U2A+a1P+a2P,B+b1Q+b2Q⟶α21=eA+a1P+a2P,B+b1Q+b2Q,U2A+a3P,-a3Q-b1Q-b2Q⟶α22=eA+a3P,-a3Q-b1Q-b2Q,U2b3P,B+a1Q+a2Q⟶α23=eb3P,B+a1Q+a2Q,U2A+a4P,-b1Q-t1b2Q⟶α24=eA+a4P,-b1Q-t1b2Q,U2-a1P-t2a2P,B+b4Q⟶α25=e-a1P-t2a2P,B+b4Q.(3)T verifies whether U1 and U2 generate the correct outputs, which means that (4)–(6) hold.
(a)(4)α11=α21(b)(5)α12·α22·ea3P,a3Qt1+1=α14·α24·ea4P,b1Q+b2Qt1+1(c)(6)α13·α23·eb3P,b3Qt2+1=α15·α25·ea1P+a2P,b4Qt2+1.If not,T outputs “error”; otherwise, T outputs(7)α12·α22·ea3P,a3Q=eA,b1Q+b2Q-1,α13·α23·eb3P,b3Q=ea1P+a2P,B-1,(8)eA,B=α11·eA,b1Q+b2Q-1·ea1P+a2P,B-1·ea1P+a2P,b1Q+b2Q-1.Correctness. It is obvious that formula (4) holds if two servers are all honest. In addition,(9)α12·α22·ea3P,a3Q=eb1P+b2P,a3QeA+a3P,-b1Q-b2Q=eA,b1Q+b2Q-1,(10)α13·α23·eb3P,b3Q=e-a1P-a2P,B+b3Qeb3P,a1Q+a2Q=ea1P+a2P,B-1,(11)α12α22ea3P,a3Qt1+1=α14α24ea4P,b1Q+b2Qt1+1=eA+a4P,b1Q+b2Q-t1+1ea4P,b1Q+b2Qt1+1=eA,b1Q+b2Q-t1+1,(12)α13α23eb3P,b3Qt2+1=α15α25ea1P+a2P,b4Qt2+1=ea1P+a2P,B+b4Q-t2+1ea1P+a2P,b4Qt2+1=ea1P+a2P,B-t2+1.Therefore, formulas (4)–(6) hold according to the above analysis. Finally, T obtains eA,B as (8).Remark 6.
If one of the servers is dishonest, the results could be verified successfully with a probability close to 1 except that the dishonest server knows the values ofα11,α12,α13,α14,α15 (or α21,α22,α23,α24,α25) and t1,t2. As we know, five queries sent to U1 and U2 are submitted in random order and t1,t2∈2,3,…,s. So, the dishonest server could guess the values of α11,α12,α13,α14,α15(or α21,α22,α23,α24,α25) and t1,t2 with the probabilities of 1/5! and 1/s-12, respectively. Therefore, the checkability of theNIVBP algorithm is (13)1-15!s-12=1-1120s-12≈1.Remark 7.
The proposed algorithmNIVBP is also applicative in the condition where G,G^ are two cyclic multiplication groups. Let g,g^ be generators of G,G^, respectively. e:G×G^→GT is a bilinear map. In this case, the inputs ofNIVBP are also A∈G and B∈G^, and the output is also eA,B. The details are also omitted because of limited space.


## 3.2. Security Analysis

Theorem 8.
In the one-malicious model, the proposed algorithmT,U1,U2 is an outsource-secure implementation ofNIVBP, where the input A,B may be honest and secret or honest and protected or adversarial and protected.Proof.
LetA=E,U1′,U2′ be a PPT adversary that interacts with a PPT algorithm T in the one-malicious model.
First, we prove thatEVIEWreal~EVIEWideal, which means that the environment E learns nothing during the execution of (T,(U1,U2)). If the input (A,B) is honest and protected or adversarial and protected, it is obvious that the simulator S1 behaves the same as in the real execution. Therefore, we only need to prove the case where A,B is an honest, secret input.
So, suppose thatA,B is an honest, secret input. The simulator S1 in the ideal experiment behaves as follows. On receiving the input on round i, S1 ignores it and instead makes five random queries of the form αj,βj to both U1′ and U2′ Finally, S1 randomly checks one output eαj,βj from each program. If an error is detected, S1 saves all states and outputs Ypi = “error,” Yui=⌀,repi=1, and thus the final output for ideal process is (estatei, “error,” ⌀). If no error is detected, S1 checks the remaining four outputs. If all checks pass, S1 outputs Ypi=⌀,Yui=⌀,repi=0; that is, the final output for ideal process is estatei,ypi,yui; otherwise, S1 selects a random element r and outputs Ypi=r,Yui=⌀,repi=1, and the output for ideal process is estatei,r,⌀.In addition, we need to show that the inputs toU1′,U2′ in the real experiment are computationally indistinguishable from those in the ideal one. In the ideal experiment, the inputs are selected uniformly at random. In the real one, each part of all five queries that T makes to any program is generated by invoking the subroutine Rand and thus is computationally indistinguishable from random numbers. Therefore, we consider three possible conditions. If U1′,U2′ both are honest in round i, EVIEWreali~EVIEWideali, since the outputs ofNIVBP are not replaced and repi=0; if one of (U1′,U2′) is dishonest in round i, the fault must be detected by both T and S1 with a probability close to 1, resulting in an output of “error”; otherwise, the output ofNIVBP is corrupted with a probability of 1/120(s-1)2. In the real experiment, the five outputs generated by U1′,U2′ are multiplied together along with a random value. Thus, EVIEWreali~EVIEWideali even when one of U1′,U2′ misbehaves, so we conclude that EVIEWreal~EVIEWideal.Second, we prove thatUVIEWreal~UVIEWideal, which means that the untrusted software U1′,U2′ learns nothing during the execution of T,U1′,U2′. In the ideal experiment, the simulator S2 always behaves as follows: when receiving the input on round i, S2 ignores it but submits five random queries of the form αj,βj to U1′ and U2′. Then S2 saves its states and those of U1′,U2′. Since the honest, secret or honest, protected or adversarial, protected inputs are all private for U1′,U2′, the simulator S2 is applicable to all those conditions. As shown in Pair One, the inputs to U1′,U2′ in the real experiment are computationally indistinguishable from those in the ideal one randomly chosen by S2. Thus, UVIEWreali~UVIEWideali for each round i, and so UVIEWreal~UVIEWideal.Theorem 9.
In the one-malicious model, the proposed algorithmT,U1,U2 in Section 3.1 is verifiable; that is, the outsourcer can test the error with a probability close to 1 if one of the servers outputs the false result.Proof.
Assume thatU1 is an honest server and U2 is a malicious server. At the end of the algorithm, the outsourcer verifies the results by formulas (4)–(6). It is obvious that U2 must generate the correct value of α21; otherwise, formula (4) cannot pass the verification with a probability of 1. Thus, the only possibility of U2 cheating T is returning the false value of α21,α22,α23,α24,α25, which is denoted by α21¯,α22¯,α23¯,α24¯,α25¯, respectively.
Assume thatα21¯,α22¯,α23¯,α24¯,α25¯ could pass the verification of formulas (5) and (6); that is, (14)α12·α22¯·ea3P,a3Qt1+1=α14·α24¯·ea4P,b1Q+b2Qt1+1,α13·α23¯·eb3P,b3Qt2+1=α15·α25¯·ea1P+a2P,b4Qt2+1,which means that(15)α22-t1+1α24¯=α14·ea4P,b1Q+b2Qt1+1α12t1+1·ea3P,a3Qt1+1,α23-t1+1α25¯=α15·ea1P+a2P,b4Qt2+1α13t2+1·eb3P,b3Qt2+1.
SinceU1 is an honest server, α11,α12,α13,α14,α15 must be correct. In addition, ea3P,a3Q,eb3P,b3Q,ea4P,b1Q+b2Qt1+1,ea1P+a2P,b4Qt2+1 are generated randomly by Rand subroutine, and so these values must be true. Thus, the values of α22-t1+1/α24¯ and α23-t2+1/α25¯ should be true even if α21¯,α22¯,α23¯,α24¯,α25¯ are incorrect; otherwise, they could not pass the verification of formulas (5) and (6).
In order to obtain the true values ofα22-t1+1/α24¯ and α23-t2+1/α25¯, U2 must guess the values of α21,α22,α23, α24,α25 and t1,t2. As shown in Section 3.1, the probabilities of guessing the true values of α21,α22,α23,α24,α25 and t1,t2 are 1/5! and 1/s-12, respectively. Therefore, the outsourcer can test the error with a probability of 1-1/5!(s-1)2=1-1/120s-12≈1.Theorem 10.
In the one-malicious model, the proposed algorithmT,U1,U2 is an Os/m,≈1-outsource-secure implementation ofNIVBP, where s is a small positive integer and m is the bit length of q and q is the order of G,G^.Proof.
The proposed algorithmNIVBP makes one call to Rand and 8 point additions (PA) in G or G^ and Os multiplication in GT in order to compute eA,B. As shown in [24], it takes roughly Om multiplications in resulting finite field to compute the bilinear pairing, where m is the bit length of q. Thus, the proposed algorithm is an O(s/m)-efficient implementation ofNIVBP. On the other hand, it must be detected with a probability close to 1 if U1 or U2 fails during any execution ofNIVBP from Theorem 9.


## 3.3. Comparison

We compare the outsourcing algorithms for bilinear pairing with input privacy in Table1, where s is a small positive integer and “PA” and “M” denote the operation of point addition in G or G^ and multiplication in GT, respectively.Table 1
Comparison of the outsourcing algorithms for bilinear pairing.
Algorithm
Pair [24]
TZR1 [25]
TZR2 [25] (s=4)
VBP [26]
NIVBP(s=4)
PA(T)
5
4
11
8
8
M(T)
4
3
9
11
19
Invoke (Rand)
3
1
2
2
1
Pair(U)
8
6
6
6
10
MExp(U)
0
0
0
4
0
Interactive
No
No
No
Yes
No
Servers
Two
Two
Two
Two
Two
Checkability
0.5
0.5
0.84
1
0.999From Table1, we conclude that theNIVBP algorithm increases checkability of the outsourcer, though a little computation cost is appended compared with Pair and TZR1 algorithms. In addition, theNIVBP algorithm improves computation efficiency and checkability of the outsourcer simultaneously compared with TZR2 algorithm for the same parameter: s=4. The efficiency and checkability of theNIVBP algorithm are nearly the same as those of VBP algorithm, but it decreases the communication cost, since it is noninteractive while the VBP algorithm is interactive. Therefore, theNIVBP algorithm increases checkability and decreases communication cost of the outsourcer, although a little computation cost is appended.


## 4. Applications

In this section, we introduce two applications of the proposedNIVBP algorithm: anonymous identity-based encryption (AIBE) scheme [27] and identity-based signature (IBS) scheme [28].LetG,G^,GT be three cyclic multiplication groups of order q, and let g,g^ be generators of G,G^, respectively. e:G×G^→GT is a bilinear map. In the following schemes, G=G^.


### 4.1. Boyen-Waters AIBE Scheme with Outsourcing Decryption

The proposed outsource-secure AIBE scheme consists of the following algorithms.Setup. It chooses a random generator g∈G, random group elements g0,g1∈G, and random exponents ω,t1,t2,t3,t4∈Zq. The master key MSK={ω,t1,t2, t3,t4}, and the public parameters PK are as follows:(16)eg,gt1t2ω,g,g0,g1,v1=gt1,v2=gt2,v3=gt3,v4=gt4.Extract (MSK, ID).To issue a private key for identity ID, it chooses two random exponents r1,r2∈Zq and computes the private key SKID={d0,d1,d2,d3,d4} as follows:(17)d0=gr1t1t2+r2t3t4,d1=g-ωt2g0g1ID-r1t2,d2=g-ωt1g0g1ID-r1t1,d3=g0g1ID-r2t4,d4=g0g1ID-r2t3.Encrypt (PK, ID, M). To encrypt a message M∈GT for an identity ID, it chooses random s,s1,s2∈Zq and creates the ciphertext CT=C′,C0,C1,C2,C3,C4 as follows: (18)Meg,gt1t2ωs,g0g1IDs,v1s-s1,v2s1,v3s-s2,v4s2.Decrypt (PK, ID, CT).The outsourcer T executes theNIVBP algorithm for five times and obtains(19)eCi,di=NIVBPCi,di,i=0,1,2,3,4and then computes C′∏i=04eCi,di=M.


### 4.2. Paterson-Schuldt IBS Scheme with Outsourcing Verification

The detailed scheme is shown as follows.Setup.It picks α∈Zq,g2∈G, and computes g1=gα. Further, choose u′,m′∈G and vectors U=ui, M=mi of length nu and nm, respectively, where ui,mi are random elements from G. The public parameters are PK=g,g1,g2,u′,U,m′,M,eg2,g1 and the master secret key is g2α.Extract.Let u be a bit string of length nu representing an identity and let u[i] be the i-th bit of u. Set U⊂1,2,…,nu as the set of index i such that ui=1. To construct the private key du of the identity u, pick ru∈Zq and compute (20)du=g2αu′∏i∈Uuiru,gru.Sign. Let M⊂1,…,nm be the set of index j such that mj=1, where m is a message and mj is the j-th bit of m. To generate a signature σ for the message m, randomly choose rm∈Zq and compute(21)σ=g2αu′∏i∈Uuirum′∏j∈Mmjrm,gru,grm.Verify. Given a signature σ=V,Ru,Rm of an identity u for a message m, the outsourcer T executes theNIVBP algorithm and obtains (22)eV,g=NIVBPV,g,eu′∏i∈Uui,Ru=NIVBPu′∏i∈Uui,Ru,eu′∏i∈Uui,Ru=NIVBPm′∏j∈Mmj,Rm.And verify (23)eV,g=eg2,g1eu′∏i∈Uui,Rueu′∏i∈Uui,Ru.It is obvious that the two outsourcing schemes are verifiable and secure, since theNIVBP algorithm is verifiable with input privacy as described in Section 3.


## 4.1. Boyen-Waters AIBE Scheme with Outsourcing Decryption

The proposed outsource-secure AIBE scheme consists of the following algorithms.Setup. It chooses a random generator g∈G, random group elements g0,g1∈G, and random exponents ω,t1,t2,t3,t4∈Zq. The master key MSK={ω,t1,t2, t3,t4}, and the public parameters PK are as follows:(16)eg,gt1t2ω,g,g0,g1,v1=gt1,v2=gt2,v3=gt3,v4=gt4.Extract (MSK, ID).To issue a private key for identity ID, it chooses two random exponents r1,r2∈Zq and computes the private key SKID={d0,d1,d2,d3,d4} as follows:(17)d0=gr1t1t2+r2t3t4,d1=g-ωt2g0g1ID-r1t2,d2=g-ωt1g0g1ID-r1t1,d3=g0g1ID-r2t4,d4=g0g1ID-r2t3.Encrypt (PK, ID, M). To encrypt a message M∈GT for an identity ID, it chooses random s,s1,s2∈Zq and creates the ciphertext CT=C′,C0,C1,C2,C3,C4 as follows: (18)Meg,gt1t2ωs,g0g1IDs,v1s-s1,v2s1,v3s-s2,v4s2.Decrypt (PK, ID, CT).The outsourcer T executes theNIVBP algorithm for five times and obtains(19)eCi,di=NIVBPCi,di,i=0,1,2,3,4and then computes C′∏i=04eCi,di=M.


## 4.2. Paterson-Schuldt IBS Scheme with Outsourcing Verification

The detailed scheme is shown as follows.Setup.It picks α∈Zq,g2∈G, and computes g1=gα. Further, choose u′,m′∈G and vectors U=ui, M=mi of length nu and nm, respectively, where ui,mi are random elements from G. The public parameters are PK=g,g1,g2,u′,U,m′,M,eg2,g1 and the master secret key is g2α.Extract.Let u be a bit string of length nu representing an identity and let u[i] be the i-th bit of u. Set U⊂1,2,…,nu as the set of index i such that ui=1. To construct the private key du of the identity u, pick ru∈Zq and compute (20)du=g2αu′∏i∈Uuiru,gru.Sign. Let M⊂1,…,nm be the set of index j such that mj=1, where m is a message and mj is the j-th bit of m. To generate a signature σ for the message m, randomly choose rm∈Zq and compute(21)σ=g2αu′∏i∈Uuirum′∏j∈Mmjrm,gru,grm.Verify. Given a signature σ=V,Ru,Rm of an identity u for a message m, the outsourcer T executes theNIVBP algorithm and obtains (22)eV,g=NIVBPV,g,eu′∏i∈Uui,Ru=NIVBPu′∏i∈Uui,Ru,eu′∏i∈Uui,Ru=NIVBPm′∏j∈Mmj,Rm.And verify (23)eV,g=eg2,g1eu′∏i∈Uui,Rueu′∏i∈Uui,Ru.It is obvious that the two outsourcing schemes are verifiable and secure, since theNIVBP algorithm is verifiable with input privacy as described in Section 3.


## 5. Performance Evaluation

In this section, we provide an experimental evaluation of the proposed outsourcing algorithms. Our experiment is simulated on two machines with Intel Xeon Processor running at 3.4 GHz with 32 G memory (cloud server) and Intel Celeron Processor running at 1.2 GHz with 2 G memory (the outsourcer), respectively. The programming language is Java, using Java Pairing-Based Cryptography (JPBC) Library. The parameterq is a 160-bit prime that is randomly generated.In Figure1, we provide the simulation ofNIVBP algorithm, which means that the fault can be found with a probability close to 1 if one of the servers misbehaves. It is obvious that the time cost for the outsourcer T is much smaller than that for directly computing bilinear pairing, since a number of computations have been delegated to two servers. Therefore, the proposedNIVBP algorithm is the implementation of secure and verifiable outsourcing for bilinear pairing.Figure 1
Simulation for the NIVBP algorithm.In Figure2, we compare the evaluation times of the outsourcing algorithms for bilinear pairing proposed in [24–26] and this paper, respectively. From Figure 2, we conclude that, for the outsourcer T, theNIVBP algorithm is superior to TZR2 algorithm in efficiency, and it appends small computation cost to improve the checkability compared with Pair and TZR1 algorithms. In addition, theNIVBP algorithm is nearly the same as VBP algorithm in efficiency, but it is noninteractive and decreases the communication cost of the outsourcer. Thus, the proposedNIVBP algorithm improves the checkability and decreases communication cost for the outsourcer simultaneously based on two servers in the one-malicious model.Figure 2
Efficiency comparison of the outsourcing algorithms for bilinear pairing.


## 6. Conclusions

In this paper, we propose a noninteractive verifiable outsource-secure algorithm for bilinear pairing. The security model of our proposed algorithm is based on two noncolluding servers, and the outsourcer can detect any failure with a probability close to 1 if one of the servers misbehaves. Compared with the previous ones, the proposed algorithm improves the checkability and communication efficiency simultaneously for the outsourcer.



---

*Source: 4892814-2017-10-15.xml*