# Scalable and Soundness Verifiable Outsourcing Computation in Marine Mobile Computing

Authors: Kai Zhang; Lifei Wei; Xiangxue Li; Haifeng Qian
Journal: Wireless Communications and Mobile Computing
 (2017)

---

## Abstract

Outsourcing computation with verifiability is a merging notion in cloud computing, which enables lightweight clients to outsource costly computation tasks to the cloud and efficiently check the correctness of the result in the end. This advanced notion is more important in marine mobile computing since the oceangoing vessels are usually constrained with less storage and computation resources. In such a scenario, vessels always firstly outsource data set and perform a function computing over them or at first outsource computing functions and input data set into them. However, vessels may choose which delegation computation type to outsource, which generally depends on the actual circumstances. Hence, we propose a scalable verifiable outsourcing computation protocol (SV-OC) in marine cloud computing at first and extract a single-mode version of it (SM-SV-OC), where both protocols allow anyone who holds verification tokens to efficiently verify the computed result returned from cloud. In this way, the introduced “scalable” property lets vessels adjust the protocol to cope with different delegation situations in practice. We additionally prove both SV-OC and SM-SV-OC achieving selective soundness in the random oracle model and evaluate their performance in the end.


---

## Body

## 1. Introduction

Cloud computing [1], a shared pool of massive configurable computing resources, provides resource-constrained clients with various capabilities to access computation resources in an on-demand way. The merging development of hardware (e.g., sensor, wearable-device unit) makes it possible for mobile devices [2, 3] feeling free to use and enjoy the cloud service in mobile computing category [4, 5].This is especially important for the marine mobile computing filed since marine ecosystems should be exploited and treated seriously from both environmental side and economic side. In order to monitor the changes of marine ecosystems, scientific vessels need to perform a series of mathematical or statical analysis over collected data [6]. This includes calculating the average temperature of ocean in an instantaneous moment or during a time period and reporting the variance of the dissolved oxygen during 24 hours, 72 hours, 6 months, or more [7, 8].However, the vessels are usually not supported by powerful data collection devices and large-scale computation processers. As a result, marine sensor units should collect marine data at first and send the collected data to vessels or base stations. Also, they may outsource some expensive computations to the cloud server and expect to use the result enjoyably after an efficient verification phase (since the cloud may return an incorrect answer for some profits). Moreover, a public verification method is preferable; namely, anyone holding the verification token can run the verification procedure in public.Moreover, we notice that the vessel’s usual outsourcing computation in marine mobile computing comes from the following two types (as in Table1).Table 1
Outsourcing computation types in mobile computing.
Delegation type
Type I
Type II
Importing parts
(Function, data set)
or
(Data set)
⇓
⇓
⇓
Outsourced parts
(Data set, function)
(Function)
Remarks
Combining inputs
Single inputType I.A client outsources a combined input tuple containing data set and function together as inputs at first and then types into an importing function over the outsourced data and an importing data set towards the outsourced function in a combined way.Type II.A client outsources a function as an input at first and then types into an importing data set towards the outsourced function. (Here, we do not consider a delegation type where a client outsources a data set at first and takes inputs on it. A detailed analysis on this can be found in Section 5.)Maybe, clients should flexibly switch Type I and Type II due to their actual demands in reality. If we design and deploy two respective outsourcing computation protocol systems for respective delegation type, there is no doubt that this will cause a big waste of resources, which is even not feasible in marine WSNs. Hence, a “scalable” property for an outsourcing computation protocol should be highlighted. Apart from this, some desirable features for verifiable outsourcing computation protocols in marine WSNs should also be considered seriously.Therefore, we may have the following doubt:whether an efficient scalable outsourcing computation protocol with public verifiability towards Type I or/and Type II delegation in marine mobile computing field exists or not?Our Results.To give an affirmative answer to this expectation, we manage to design a public verifiable outsourcing computation protocol for Type I outsourcing and moreover extend it to support Type II outsourcing as well, which are inspired by [9–11]. Specifically, our contributions in this work can be summarized as the following four parts:(i)
Aiming for securely performing Type I computation outsourcing, we put forward a scalable public verifiable outsourcing computation protocol in marine mobile computing, namely,SV-OC. This protocol allows anyone to use a granted verification token to verify the result originated from any vessel’s Type I computation request.(ii)
By treating the outsourced data set as an “on-the-fly” input ofSV-OC, we extract a single-mode version (i.e., for Type II computation) with adding a slight additional cost. As a result, vessels can just use a SV-OC protocol enough for both Type I and Type II computation as they like, which shows the “scalable property’s” flexibility at a maximum extent.(iii)
Both ourSV-OC and SM-SV-OC protocols are proven to achieve perfect correctness and selective soundness in the random oracle model. Furthermore, the efficiency analysis and concrete performance evaluations on both two protocols are provided.(iv)
We motivate an intuition that theSV-OC protocol can be viewed as a hierarchical public VC protocol towards only outsourced function (Type II), where the subjective function accepts the outsourced data which can be viewed as a hierarchical access control procedure.


### 1.1. Problem Statement

In this subsection, we present design goals and system overview for our introduced protocols.Design Goals.To achieve both functionalities and privacy-preserving requirements for an outsourcing computation protocol in marine mobile computing, the design goals can be thought from the following five parts.(1) Scalability.The protocol should be able to flexibly vary its shapes depending on the type of outsourcing computation.(2) Public Verifiability.Anyone with verification tokens can check the correctness of the result.(3) Public Delegation.Any client can outsource a computation assignment to the cloud once the system is set up.(4) Correctness.A dishonest cloud cannot return an incorrect output that passes verification.(5) Soundness.A public (verifiable) outsourcing computation protocol should be secure and sound (cf. Section 2.3).System Description.Our SV-OC or SM-SV-OC protocol consists of the following three entities.(i) Cloud Server.It receives the outsourcing computation request from any vessel and returns a result.(ii) Vessels (consisting of a pilot one and a number of nonpilot ones). They delegate outsourcing computation tasks to the cloud and expect to receive the correct computational outcome.(iii) Satellite.It provides a wireless communication channel between cloud server and vessels.High-Level Roadmap.Figure 1 gives a high-level system overview on a group verifiable outsourcing computation protocol, namely, both SV-OC protocol and SM-SV-OC protocol. To be specific, the cloud server provides a verifiable outsourcing computation service for group vessels through the wireless channel supplied by the satellite. Note that a pilot vessel in a group of vessels initializes the public verifiable outsourcing computation service by outsourcing the delegation computing function (and accompanied outsourced data set), as well as sending the generated public system information to the whole system and the generated evaluation key information about computing function (and accompanied data set) to the cloud. In this way, any vessel in this group can delegate computations by directly typing inputs into the computing function (and accompanied data set). Then the cloud server performs a computation for the outsourcing request from a vessel. Finally, anyone who possesses a legal verification token (granted from the delegating vessel) is able to verify the result. We note that the above procedure path is highly similar to Type II (and Type I) outsourcing computation, that is, SV-OC or SM-SV-OC protocol, respectively, where the only difference is the clients’ outsourcing type and importing type.Figure 1
Scalable and soundness verifiable outsourcing computation in marine mobile computing.


### 1.2. Related Work

The studied problem is usually solved through a verification computation (VC) [12, 13] method, which starts with outsourcing a computing function to the cloud at first and then takes inputs on it. However, current VC protocols do not satisfy the listed design goals simultaneously in specific marine cloud computing. The other way to consider the verifiable outsourcing computation field is designed for running some verifiable delegations on outsourced data sets [14, 15], which is a little different from the formal VC concept where it differs in outsourcing whether it is a computing function or a data set at first. Also some works focused on performing computations towards outsourced functions (outsourcing at first) have been proposed [9, 13, 16–18]. For the public delegation and the public verifiable property, Applebaum et al.’s works did not satisfy them, as well as the work presented in [13, 14, 19]. Reference [11] presented SV-OC protocol supported Type I computation outsourcing but neglected Type II one, so was thehybrid [20, 21] notion for verifiable computation failing the scalable property.We note that all approaches to construct VC protocols except for functional encryption-based method failed to providepublic delegation property for a verifiable outsourcing protocol towards a group of clients. From this point of view, our proposed solution is more enjoyable for such a scenario. More importantly, current works fail to achieve all the mentioned design goals simultaneously.Organization.In Section 2, we introduce the system model and security definition for our protocol. Section 3 gives the SV-OC protocol and its security analysis is provided in Section 4. An extracted version for single-mode public verifiable outsourcing computation protocol towards just outsourced function is shown in Section 5. Section 6 evaluates the performance and Section 7 gives a conclusion.


## 1.1. Problem Statement

In this subsection, we present design goals and system overview for our introduced protocols.Design Goals.To achieve both functionalities and privacy-preserving requirements for an outsourcing computation protocol in marine mobile computing, the design goals can be thought from the following five parts.(1) Scalability.The protocol should be able to flexibly vary its shapes depending on the type of outsourcing computation.(2) Public Verifiability.Anyone with verification tokens can check the correctness of the result.(3) Public Delegation.Any client can outsource a computation assignment to the cloud once the system is set up.(4) Correctness.A dishonest cloud cannot return an incorrect output that passes verification.(5) Soundness.A public (verifiable) outsourcing computation protocol should be secure and sound (cf. Section 2.3).System Description.Our SV-OC or SM-SV-OC protocol consists of the following three entities.(i) Cloud Server.It receives the outsourcing computation request from any vessel and returns a result.(ii) Vessels (consisting of a pilot one and a number of nonpilot ones). They delegate outsourcing computation tasks to the cloud and expect to receive the correct computational outcome.(iii) Satellite.It provides a wireless communication channel between cloud server and vessels.High-Level Roadmap.Figure 1 gives a high-level system overview on a group verifiable outsourcing computation protocol, namely, both SV-OC protocol and SM-SV-OC protocol. To be specific, the cloud server provides a verifiable outsourcing computation service for group vessels through the wireless channel supplied by the satellite. Note that a pilot vessel in a group of vessels initializes the public verifiable outsourcing computation service by outsourcing the delegation computing function (and accompanied outsourced data set), as well as sending the generated public system information to the whole system and the generated evaluation key information about computing function (and accompanied data set) to the cloud. In this way, any vessel in this group can delegate computations by directly typing inputs into the computing function (and accompanied data set). Then the cloud server performs a computation for the outsourcing request from a vessel. Finally, anyone who possesses a legal verification token (granted from the delegating vessel) is able to verify the result. We note that the above procedure path is highly similar to Type II (and Type I) outsourcing computation, that is, SV-OC or SM-SV-OC protocol, respectively, where the only difference is the clients’ outsourcing type and importing type.Figure 1
Scalable and soundness verifiable outsourcing computation in marine mobile computing.


## 1.2. Related Work

The studied problem is usually solved through a verification computation (VC) [12, 13] method, which starts with outsourcing a computing function to the cloud at first and then takes inputs on it. However, current VC protocols do not satisfy the listed design goals simultaneously in specific marine cloud computing. The other way to consider the verifiable outsourcing computation field is designed for running some verifiable delegations on outsourced data sets [14, 15], which is a little different from the formal VC concept where it differs in outsourcing whether it is a computing function or a data set at first. Also some works focused on performing computations towards outsourced functions (outsourcing at first) have been proposed [9, 13, 16–18]. For the public delegation and the public verifiable property, Applebaum et al.’s works did not satisfy them, as well as the work presented in [13, 14, 19]. Reference [11] presented SV-OC protocol supported Type I computation outsourcing but neglected Type II one, so was thehybrid [20, 21] notion for verifiable computation failing the scalable property.We note that all approaches to construct VC protocols except for functional encryption-based method failed to providepublic delegation property for a verifiable outsourcing protocol towards a group of clients. From this point of view, our proposed solution is more enjoyable for such a scenario. More importantly, current works fail to achieve all the mentioned design goals simultaneously.Organization.In Section 2, we introduce the system model and security definition for our protocol. Section 3 gives the SV-OC protocol and its security analysis is provided in Section 4. An extracted version for single-mode public verifiable outsourcing computation protocol towards just outsourced function is shown in Section 5. Section 6 evaluates the performance and Section 7 gives a conclusion.


## 2. Background Knowledge

Notations 1.
We denote bys←$S the fact that s is picked uniformly at random from a finite set S. We denote PPT as a probabilistic polynomial-time algorithm. We use · to denote multiplication (or group operation) as well as component-wise multiplication.


### 2.1. Outsourcing Functions’ Description Using Access Structures

Definition 2.
A (monotone)access structureA=(M∈Zpl×l′,ρ:[l]→U) for set universe U. One may hold the fact for an attribute set ψ⊆U: A accepts ψ⇔1∈spanMψ. Here, 1=(1,0,…,0)∈Zpl′ is a row vector; as Mj represents the jth row vector of matrix M, a linear span spanMψ is a collection of vectors Mψ={Mj:ρ(j)∈ψ} over Zp.Remark 3.
In this paper, we mainly focus on giving a verifiable outsourcing computation protocol for Boolean formula delegating functions. When we manage to enable our protocol to be usable for multibitsF rather than one bit (Boolean formula), we usually take the following steps to realize: (1)
Split the computing functionF in to some subfunctions f1,…,fn, where fi is the ith output bit of the computing function F.(2)
Now we can run theSV-OC and SM-SV-OC (for Boolean formula function) with conducting each subfunction fi.Therefore, we can obtain a scalable outsourcing computation protocol for (polynomial many) multibits output forF∈F, where F can be implemented by a polynomial-size Boolean formula’s circuit. In this case, any outsourcing function F∈F can be computed by a polynomial-size Boolean formula and can thus be described by a (monotone) access structure [22]. We therefore use the access structures to symbolize the aiming outsourced (Boolean) functions F throughout this paper.


### 2.2. Underlying Security Guarantee

The security of our protocol relies on the decisionalq-BDHE assumption. Let G, GT be two cyclic groups of prime order p and a generator g of group G along with an efficient computable map e:G×G→GT. Randomly choose generators g,h←$G and α←$Zp and a tuple D=(hα,gα2,…,gαq,gαq+2,…,g2q,Z), and an adversary A should distinguish a computed value e(g,h)αq+1 from a random element Z in GT. Finally, A outputs b∈{0,1} having an advantage ϵ in solving the decisional q-BDHE problem if |Pr[A(g,h,D,e(gαq+1,h))=0]-Pr[A(g,h,D,Z)=0]|≥ϵ.Definition 4.
One says that the decisionalq-BDHE assumption holds in (G,GT) if, for any PPT adversary A, its advantage in above game is negligible in security parameter λ.


### 2.3. Definition for Scalable Verifiable Outsourcing Computation

In this subsection, we present the system definition, correctness definition, security definition, and privacy definition for a scalable verifiable outsourcing computation protocol.System Definition.A scalable verifiable outsourcing computation SV-OC protocol is composed of the following four PPT algorithms:(i)
KeyGen(F,ψ,1λ): given a security parameter 1λ, on input a function F and an accompanied outsourced data set ψ, the pilot vessel outputs a public key pkF and an evaluation key ekF.(ii)
ProbGen(pkF,ω,G): on input pkF, any (pilot or nonpilot) vessel can use it to encode an input ω into a problem description σω,G, as well as outputting a verification key vkω,G.(iii)
Compute(ekF,ψ,σω,G): on input ekF,ψ and a problem description σω,G, the data center (cloud) computes an outcome σot.(iv)
Verify(vkω,G,σot): with input of the cloud’s output σot, anyone returns an output ot∈{0,1}∗ or ⊥ (rejects the cloud’s answer σot using vkω,G).Correctness Definition.Given a security parameter λ, for any outsourced data set ψ∈U′ and outsourced function F∈F and any subjective function G∈F′ and for any objective data set ω∈U, (σω,G,vkω,G)←$ProbGen(pkF,ω,G), σot←$Compute(ekF,ψ,σω,G), then (1)PrVerifyvkω,G,σot=Fω,G=1.Security Definition.We define a security experiment against adaptive (adaptively chosen outsourced function and data sets) adversaries, which is played by a challenger and a stateful adversary A=(A1,A2).ASV-OC protocol achievesselective soundness if for all PPT adversaries A and for any F∈F and ψ∈U′, A’s winning advantage (2)PrExpA,SV-OCSel-SoundnessF,ψ,λ,q=PrExpA,SV-OCSel-SoundnessF,ψ,λ=1 under the following condition, ExperimentExpA,SV-OCSel-SoundnessF,ψ,λ
ω∗,G∗←$ApkF,ekF←Setup1λ,F,ψ;ω∗,G∗,st←A1O·pkF;σω∗,G∗,vkω∗,G∗←ProbGenpkF,ω∗,G∗σot∗←A2O·st,σω∗,G∗,vkF,ψ,ekF;ot∗←Verifyvkω∗,G∗,σot∗;Ifot∗∉{⊥,F(ω∗)} outputs “1”,is negligible in security parameterλ, where O(·) means that the adversary A1/A2 can submit q pairs {(Fi,ψi)}i=[q] that make the experiment always output “1.”Privacy Definition.The clients’ outsourced/input computing function and data set are altogether kept hidden from the adversary’s view. Moreover, the cloud’s output for the problem solution does also not leak any information on the problem description. In this paper, we consider these asoutsourcing privacy,input privacy, andoutput privacy.


## 2.1. Outsourcing Functions’ Description Using Access Structures

Definition 2.
A (monotone)access structureA=(M∈Zpl×l′,ρ:[l]→U) for set universe U. One may hold the fact for an attribute set ψ⊆U: A accepts ψ⇔1∈spanMψ. Here, 1=(1,0,…,0)∈Zpl′ is a row vector; as Mj represents the jth row vector of matrix M, a linear span spanMψ is a collection of vectors Mψ={Mj:ρ(j)∈ψ} over Zp.Remark 3.
In this paper, we mainly focus on giving a verifiable outsourcing computation protocol for Boolean formula delegating functions. When we manage to enable our protocol to be usable for multibitsF rather than one bit (Boolean formula), we usually take the following steps to realize: (1)
Split the computing functionF in to some subfunctions f1,…,fn, where fi is the ith output bit of the computing function F.(2)
Now we can run theSV-OC and SM-SV-OC (for Boolean formula function) with conducting each subfunction fi.Therefore, we can obtain a scalable outsourcing computation protocol for (polynomial many) multibits output forF∈F, where F can be implemented by a polynomial-size Boolean formula’s circuit. In this case, any outsourcing function F∈F can be computed by a polynomial-size Boolean formula and can thus be described by a (monotone) access structure [22]. We therefore use the access structures to symbolize the aiming outsourced (Boolean) functions F throughout this paper.


## 2.2. Underlying Security Guarantee

The security of our protocol relies on the decisionalq-BDHE assumption. Let G, GT be two cyclic groups of prime order p and a generator g of group G along with an efficient computable map e:G×G→GT. Randomly choose generators g,h←$G and α←$Zp and a tuple D=(hα,gα2,…,gαq,gαq+2,…,g2q,Z), and an adversary A should distinguish a computed value e(g,h)αq+1 from a random element Z in GT. Finally, A outputs b∈{0,1} having an advantage ϵ in solving the decisional q-BDHE problem if |Pr[A(g,h,D,e(gαq+1,h))=0]-Pr[A(g,h,D,Z)=0]|≥ϵ.Definition 4.
One says that the decisionalq-BDHE assumption holds in (G,GT) if, for any PPT adversary A, its advantage in above game is negligible in security parameter λ.


## 2.3. Definition for Scalable Verifiable Outsourcing Computation

In this subsection, we present the system definition, correctness definition, security definition, and privacy definition for a scalable verifiable outsourcing computation protocol.System Definition.A scalable verifiable outsourcing computation SV-OC protocol is composed of the following four PPT algorithms:(i)
KeyGen(F,ψ,1λ): given a security parameter 1λ, on input a function F and an accompanied outsourced data set ψ, the pilot vessel outputs a public key pkF and an evaluation key ekF.(ii)
ProbGen(pkF,ω,G): on input pkF, any (pilot or nonpilot) vessel can use it to encode an input ω into a problem description σω,G, as well as outputting a verification key vkω,G.(iii)
Compute(ekF,ψ,σω,G): on input ekF,ψ and a problem description σω,G, the data center (cloud) computes an outcome σot.(iv)
Verify(vkω,G,σot): with input of the cloud’s output σot, anyone returns an output ot∈{0,1}∗ or ⊥ (rejects the cloud’s answer σot using vkω,G).Correctness Definition.Given a security parameter λ, for any outsourced data set ψ∈U′ and outsourced function F∈F and any subjective function G∈F′ and for any objective data set ω∈U, (σω,G,vkω,G)←$ProbGen(pkF,ω,G), σot←$Compute(ekF,ψ,σω,G), then (1)PrVerifyvkω,G,σot=Fω,G=1.Security Definition.We define a security experiment against adaptive (adaptively chosen outsourced function and data sets) adversaries, which is played by a challenger and a stateful adversary A=(A1,A2).ASV-OC protocol achievesselective soundness if for all PPT adversaries A and for any F∈F and ψ∈U′, A’s winning advantage (2)PrExpA,SV-OCSel-SoundnessF,ψ,λ,q=PrExpA,SV-OCSel-SoundnessF,ψ,λ=1 under the following condition, ExperimentExpA,SV-OCSel-SoundnessF,ψ,λ
ω∗,G∗←$ApkF,ekF←Setup1λ,F,ψ;ω∗,G∗,st←A1O·pkF;σω∗,G∗,vkω∗,G∗←ProbGenpkF,ω∗,G∗σot∗←A2O·st,σω∗,G∗,vkF,ψ,ekF;ot∗←Verifyvkω∗,G∗,σot∗;Ifot∗∉{⊥,F(ω∗)} outputs “1”,is negligible in security parameterλ, where O(·) means that the adversary A1/A2 can submit q pairs {(Fi,ψi)}i=[q] that make the experiment always output “1.”Privacy Definition.The clients’ outsourced/input computing function and data set are altogether kept hidden from the adversary’s view. Moreover, the cloud’s output for the problem solution does also not leak any information on the problem description. In this paper, we consider these asoutsourcing privacy,input privacy, andoutput privacy.


## 3. Our Scalable Verifiable Outsourcing Computation Protocol:SV-OC

Inspired by the dual-policy attribute-based encryption (ABE) scheme [10, 23], we present the first publicly verifiable outsourcing computation protocol towards both (Boolean formula) outsourced functions and outsourced data sets altogether, which also relies on our introduced variant transformation [11] of the general relationship between ABE and public VC [9].Specifically specifying the example in Section1, the pilot vessel first initializes the SV-OC service by inputting an outsourced function and an accompanied data set to generate a public key pkF and an evaluation key ekF and sends them to the cloud and other vessels. Thus, any vessel in this fleet can directly input the objective input ω for F and an accompanied computation function G over data set G along with randomly chosen messages m, m′ altogether, to generate a problem description σω,G and a verification key vkω,G. Once receiving pkF and ekF, the cloud computes the problem result σot on the problem σω,G. Finally the vessel (or a legal granted anyone) can use the verification key vkω,G to efficiently check the result σω,G’s correctness.


### 3.1. System Initialization Phase

Given an outsourced functionF∈F with input size n as inputs, define two hash functions H:Zp→G, H′:Zp→G. The pilot vessel randomly chooses g,g¯←$G and s,s¯,α,α¯←$Zp. Then it generates and outputs two master public/secret key pairs of information pieces: (3)mpk≔g,eg,gs,gα,H,H′,msk≔γ,α;mpk¯≔g¯,eg¯,g¯s¯,g¯α¯,H,H′,msk¯≔γ¯,α¯.


### 3.2. Evaluation Key Generation Phase

For an encoded objective outsourced functionF∈F’s access structure A′≔(N∈Zpl′×k′,π:[l′]→[n′]), as well as a subjective outsourced data set ψ⊂U′, pick a random vector v←$Zpk′ such that 1→v=γ+αr for r←$Zp and set ηi=Ni·v,i∈[l′]. Output (4)skF,ψ≔K,Kxx∈ψ,Ki′,Ki′′i∈l′=gr,Hxrx∈ψ,gηiH′πi-ri,grii∈l′.Similarly, we obtain the corresponding secret keyskF¯,ψ using uniformly and randomly chosen independent “xx¯”-type variables. (Here, we omit the descriptions on the sampling process on “xx¯”, since it is almost same as that for skF,ψ) Then, (5)sk¯F¯,ψ≔K¯,K¯x¯x¯∈ψ,K¯i,Ki′i∈l¯′=g¯r¯,Hx¯r¯x¯∈ψ,g¯η¯iH′π¯i-r¯i,g¯r¯ii∈l¯′,where F- denotes the complement function of the outsourced function F. Hence, output the public key and the evaluation key information as (6)pkF≔mpk,mpk¯ekF≔skF,ψ,sk¯F-,ψ.


### 3.3. Problem Generation Phase

Given an objective data setω⊂U and the access structure A≔(M∈Zpl×k,ρ:[l]→[n]) of an encoded subjective function G∈G altogether as inputs, randomly choose a random vector u←$Zpk such that 1u=s for s←$Zp and set λi=Mi·u, i∈[l]. Pick two messages m, m¯ and output (7)ctω,G≔C,C′,Cii∈l,Cx′′x∈ω=M·eg,gs,gs,gαλiHρi-si∈l,H′xsx∈ωand similarly we generate ct¯ω,G (by introducing new “xx¯”-type parameters to generate ct¯ω,G by using mbk¯):(8)ct¯ω,G≔C¯,C¯′,C¯ii∈l,C¯x′′x∈ω=m¯·eg¯,g¯s,g¯s,g¯αλiHρi-si∈l,H′xsx∈ω.Hence, output the problem description and the verification key information as (9)σω,G≔ctω,G,ct¯ω,G,vkω,G≔Hm,Hm¯,where H is a one-way function.


### 3.4. Compute Phase

Upon the problem descriptionσω,G and the evaluation key ekF,ψ, compute (10)m′⟵C·∏i∈i∣ρi∈ψeCi,K·eC′,Kρjui∏j∈i∣πi∈ωeKj′,C′·eKj′′,Cπj′′vj,m¯′⟵C¯·∏i∈i∣ρi∈ψeC¯i,K¯·eC¯′,K¯ρjui∏j∈i∣π¯i∈ωeK¯j′,C¯′·eK¯j′′,C¯π¯j′′vj.Output the problem solution σot:=(m′,m¯′).Here, we note that this compute process can be realized efficiently (reducing the number of pairing operations) but just add a few exponentiation operations as a tradeoff.


### 3.5. Verification Phase

Inputvkω,G=H(m),H(m¯) and σot=(m′,m¯′). Output (11)δ≔0,ifHm′=Hm;1,ifHm-′=Hm-,Hm′≠Hm;⊥,ifHm-′≠Hm-,Hm′≠Hm.Remark 5.
The verifiability ofSV-OC is mainly against the outsourced function since the concept of the complement data sets of ψ does not make sense in practice compared to F-. Hence, our SV-OC can be served as a hierarchical public VC protocol towards just outsourced function, which regards the subjective function accepting outsourced data set as a hierarchical (fine-grained) access control condition.


## 3.1. System Initialization Phase

Given an outsourced functionF∈F with input size n as inputs, define two hash functions H:Zp→G, H′:Zp→G. The pilot vessel randomly chooses g,g¯←$G and s,s¯,α,α¯←$Zp. Then it generates and outputs two master public/secret key pairs of information pieces: (3)mpk≔g,eg,gs,gα,H,H′,msk≔γ,α;mpk¯≔g¯,eg¯,g¯s¯,g¯α¯,H,H′,msk¯≔γ¯,α¯.


## 3.2. Evaluation Key Generation Phase

For an encoded objective outsourced functionF∈F’s access structure A′≔(N∈Zpl′×k′,π:[l′]→[n′]), as well as a subjective outsourced data set ψ⊂U′, pick a random vector v←$Zpk′ such that 1→v=γ+αr for r←$Zp and set ηi=Ni·v,i∈[l′]. Output (4)skF,ψ≔K,Kxx∈ψ,Ki′,Ki′′i∈l′=gr,Hxrx∈ψ,gηiH′πi-ri,grii∈l′.Similarly, we obtain the corresponding secret keyskF¯,ψ using uniformly and randomly chosen independent “xx¯”-type variables. (Here, we omit the descriptions on the sampling process on “xx¯”, since it is almost same as that for skF,ψ) Then, (5)sk¯F¯,ψ≔K¯,K¯x¯x¯∈ψ,K¯i,Ki′i∈l¯′=g¯r¯,Hx¯r¯x¯∈ψ,g¯η¯iH′π¯i-r¯i,g¯r¯ii∈l¯′,where F- denotes the complement function of the outsourced function F. Hence, output the public key and the evaluation key information as (6)pkF≔mpk,mpk¯ekF≔skF,ψ,sk¯F-,ψ.


## 3.3. Problem Generation Phase

Given an objective data setω⊂U and the access structure A≔(M∈Zpl×k,ρ:[l]→[n]) of an encoded subjective function G∈G altogether as inputs, randomly choose a random vector u←$Zpk such that 1u=s for s←$Zp and set λi=Mi·u, i∈[l]. Pick two messages m, m¯ and output (7)ctω,G≔C,C′,Cii∈l,Cx′′x∈ω=M·eg,gs,gs,gαλiHρi-si∈l,H′xsx∈ωand similarly we generate ct¯ω,G (by introducing new “xx¯”-type parameters to generate ct¯ω,G by using mbk¯):(8)ct¯ω,G≔C¯,C¯′,C¯ii∈l,C¯x′′x∈ω=m¯·eg¯,g¯s,g¯s,g¯αλiHρi-si∈l,H′xsx∈ω.Hence, output the problem description and the verification key information as (9)σω,G≔ctω,G,ct¯ω,G,vkω,G≔Hm,Hm¯,where H is a one-way function.


## 3.4. Compute Phase

Upon the problem descriptionσω,G and the evaluation key ekF,ψ, compute (10)m′⟵C·∏i∈i∣ρi∈ψeCi,K·eC′,Kρjui∏j∈i∣πi∈ωeKj′,C′·eKj′′,Cπj′′vj,m¯′⟵C¯·∏i∈i∣ρi∈ψeC¯i,K¯·eC¯′,K¯ρjui∏j∈i∣π¯i∈ωeK¯j′,C¯′·eK¯j′′,C¯π¯j′′vj.Output the problem solution σot:=(m′,m¯′).Here, we note that this compute process can be realized efficiently (reducing the number of pairing operations) but just add a few exponentiation operations as a tradeoff.


## 3.5. Verification Phase

Inputvkω,G=H(m),H(m¯) and σot=(m′,m¯′). Output (11)δ≔0,ifHm′=Hm;1,ifHm-′=Hm-,Hm′≠Hm;⊥,ifHm-′≠Hm-,Hm′≠Hm.Remark 5.
The verifiability ofSV-OC is mainly against the outsourced function since the concept of the complement data sets of ψ does not make sense in practice compared to F-. Hence, our SV-OC can be served as a hierarchical public VC protocol towards just outsourced function, which regards the subjective function accepting outsourced data set as a hierarchical (fine-grained) access control condition.


## 4. Security Analysis

In this section, we give correctness and efficiency analysis on ourSV-OC protocol at first and sketch a security analysis and privacy analysis on it as well.


### 4.1. Correctness Analysis

Based on the correctness of [10] dual-policy attribute-based encryption along with our modified transformation [11] between ABE and public VC in terms of [9], the correctness follows straightforwardly when both the following two conditions hold: (1) the outsourced function F accepts the data set ω; (2) the outsourced data set ψ satisfies the function G.In the compute phase, the recovery process ofm¯′ is parallel to that of m¯. Here, we just show the correctness of the m¯ case: (12)C·∏i∈i∣ρi∈ψeCi,K·eC′,Kρjui∏j∈i∣πi∈ωeKj′,C′·eKj′′,Cπj′′vj=C·∏i∈i∣ρi∈ψegαλiHρi-s,gr·egs,Hρirui∏j∈i∣πi∈ωegηiH′πj-rj,gs·egrj,H′πjsvj=C·∏i∈i∣ρi∈ψegαλi,grui∏j∈i∣πi∈ωegηj,gsvj=C·egαs,gregγ+αr,gs=C·1eg,gγs=m,where the fourth equation follows the linear reconstruction property of Definition 2, and we have(13)∑i∈i∣ρi∈ψuiλi=s,∑j∈i∣πi∈ωviηi=γ+αr.Remark 6.
The correctness of the above compute phase is similar to that of the decryption process in [10].


### 4.2. Efficiency Analysis

In this part, we give a time and a size efficiency analysis forSV-OC. Concretely, Table 3 lists the dominant time operations (i.e., pairing, exponentiation, and multiplication) in group that belongs to each step of SV-OC, and moreover Table 2 gives the size calculations.Table 2
Size analysis of ourSV-OC protocol. In the table, “|G|, |GT|” denote the size of a group element in groups G and GT, respectively; “n, l,” respectively, represent the maximum input size and the row’s number in the sharing matrix M.
Description
Sizes
pk
F
Public key
4
G
+
2
G
T
ek
F
Evaluation key
4
l
+
2
n
+
2
G
σ
ω
,
G
Problem description
2
l
+
2
n
+
2
G
+
2
G
T
vk
ω
,
G
Verification key
2
GTable 3
Group operations analysis in each phase of ourSV-OC protocol. In the table, “Pairing” represents a paring operation in the protocol; ExpG and ExpGT denote an exponentiation operation in groups G and GT, respectively; similarly, MulG and MulGT denote a multiplication operation in group G and GT, respectively; “n, l,” respectively, represent the maximum input size and the row’s number in the sharing matrix M.
Step
Description
Performer
Operations
(1)
System initialization
Pilot vessel
2Pairing+2ExpGT+2ExpG
(2)
Evaluation key generation
Pilot vessel
(6l+2n)ExpG+(2n+2l)H+2lMulG
(3)
Problem generation
Any vessel
(4l+2)ExpG+(2l+2n+2)H+2lMulG
(4)
Compute
Cloud
8nPairing+2nExpGT
(5)
Verification
Anyone
2
HRemark 7.
The compute phase’s overhead can be optimized up to(2n+4)Pairing+8nExpGT.In theSV-OC protocol, Step (1) and Step (2) are altogether done by the pilot vessel, any vessel can perform Step (3), and the data center (e.g., cloud) completes Step (4) along with the fact that anyone can carry out Step (5).As the bandwidth between each entity across this marine WSNs is low [5, 24], the low parameter size is highly demanded. From Table 3, we find that most operations that need high cost reside in the data center side. Consequently, the pilot vessel can certainly afford the VC service initialization computation overhead. In this way, the overhead of the problem description paid by any vessel is short, and anyone’s verification cost on the result is very little as well. Therefore, the efficiency of the obtained SV-OC is enjoyably applicable to the marine wireless sensor networks.


### 4.3. Security Analysis

Theorem 8 (main theorem).
LetF be a class of Boolean functions (implemented by a family of circuits C), and let F-={F-∣F∈F} be a class of the complement function F- of each function F and the class of the outsourced data set U′={ψ∣ψ∈U′} and H be any one-way function. Suppose Definition 4 holds; then the SV-OC protocol in Section 3 achieves selective soundness property according to the security definition in Section 2.3.We can easily reduce the security ofSV-OC with adaptive soundness to the adaptive security of the dual-policy ABE [10] and the general transformation between them, since one can obtain the SV-OC protocol by running the ABE scheme twice along with other techniques. More technical details can be found in Section 4.2 of [10] and Appendix A of [9].


### 4.4. Privacy Analysis

During theSV-OC protocol’s process carried out, the specific contents of the outsourced part and the input part are encoded as another form. Specifically, the clients’ outsourced computing function and accompanied data set are encoded as an evaluation key ekF and any client’s input ω, and G is encoded as a problem generation ctω,G, in such a way that the cloud cannot obtain any knowledge about theoutsourcing privacy andinput privacy. For the output privacy, the random message m is also hidden by a owe-way function H; thus the cloud can just get H(m) and is unable to recover m from it (except a negligible advantage) which is considered to achieveoutput privacy as well.


## 4.1. Correctness Analysis

Based on the correctness of [10] dual-policy attribute-based encryption along with our modified transformation [11] between ABE and public VC in terms of [9], the correctness follows straightforwardly when both the following two conditions hold: (1) the outsourced function F accepts the data set ω; (2) the outsourced data set ψ satisfies the function G.In the compute phase, the recovery process ofm¯′ is parallel to that of m¯. Here, we just show the correctness of the m¯ case: (12)C·∏i∈i∣ρi∈ψeCi,K·eC′,Kρjui∏j∈i∣πi∈ωeKj′,C′·eKj′′,Cπj′′vj=C·∏i∈i∣ρi∈ψegαλiHρi-s,gr·egs,Hρirui∏j∈i∣πi∈ωegηiH′πj-rj,gs·egrj,H′πjsvj=C·∏i∈i∣ρi∈ψegαλi,grui∏j∈i∣πi∈ωegηj,gsvj=C·egαs,gregγ+αr,gs=C·1eg,gγs=m,where the fourth equation follows the linear reconstruction property of Definition 2, and we have(13)∑i∈i∣ρi∈ψuiλi=s,∑j∈i∣πi∈ωviηi=γ+αr.Remark 6.
The correctness of the above compute phase is similar to that of the decryption process in [10].


## 4.2. Efficiency Analysis

In this part, we give a time and a size efficiency analysis forSV-OC. Concretely, Table 3 lists the dominant time operations (i.e., pairing, exponentiation, and multiplication) in group that belongs to each step of SV-OC, and moreover Table 2 gives the size calculations.Table 2
Size analysis of ourSV-OC protocol. In the table, “|G|, |GT|” denote the size of a group element in groups G and GT, respectively; “n, l,” respectively, represent the maximum input size and the row’s number in the sharing matrix M.
Description
Sizes
pk
F
Public key
4
G
+
2
G
T
ek
F
Evaluation key
4
l
+
2
n
+
2
G
σ
ω
,
G
Problem description
2
l
+
2
n
+
2
G
+
2
G
T
vk
ω
,
G
Verification key
2
GTable 3
Group operations analysis in each phase of ourSV-OC protocol. In the table, “Pairing” represents a paring operation in the protocol; ExpG and ExpGT denote an exponentiation operation in groups G and GT, respectively; similarly, MulG and MulGT denote a multiplication operation in group G and GT, respectively; “n, l,” respectively, represent the maximum input size and the row’s number in the sharing matrix M.
Step
Description
Performer
Operations
(1)
System initialization
Pilot vessel
2Pairing+2ExpGT+2ExpG
(2)
Evaluation key generation
Pilot vessel
(6l+2n)ExpG+(2n+2l)H+2lMulG
(3)
Problem generation
Any vessel
(4l+2)ExpG+(2l+2n+2)H+2lMulG
(4)
Compute
Cloud
8nPairing+2nExpGT
(5)
Verification
Anyone
2
HRemark 7.
The compute phase’s overhead can be optimized up to(2n+4)Pairing+8nExpGT.In theSV-OC protocol, Step (1) and Step (2) are altogether done by the pilot vessel, any vessel can perform Step (3), and the data center (e.g., cloud) completes Step (4) along with the fact that anyone can carry out Step (5).As the bandwidth between each entity across this marine WSNs is low [5, 24], the low parameter size is highly demanded. From Table 3, we find that most operations that need high cost reside in the data center side. Consequently, the pilot vessel can certainly afford the VC service initialization computation overhead. In this way, the overhead of the problem description paid by any vessel is short, and anyone’s verification cost on the result is very little as well. Therefore, the efficiency of the obtained SV-OC is enjoyably applicable to the marine wireless sensor networks.


## 4.3. Security Analysis

Theorem 8 (main theorem).
LetF be a class of Boolean functions (implemented by a family of circuits C), and let F-={F-∣F∈F} be a class of the complement function F- of each function F and the class of the outsourced data set U′={ψ∣ψ∈U′} and H be any one-way function. Suppose Definition 4 holds; then the SV-OC protocol in Section 3 achieves selective soundness property according to the security definition in Section 2.3.We can easily reduce the security ofSV-OC with adaptive soundness to the adaptive security of the dual-policy ABE [10] and the general transformation between them, since one can obtain the SV-OC protocol by running the ABE scheme twice along with other techniques. More technical details can be found in Section 4.2 of [10] and Appendix A of [9].


## 4.4. Privacy Analysis

During theSV-OC protocol’s process carried out, the specific contents of the outsourced part and the input part are encoded as another form. Specifically, the clients’ outsourced computing function and accompanied data set are encoded as an evaluation key ekF and any client’s input ω, and G is encoded as a problem generation ctω,G, in such a way that the cloud cannot obtain any knowledge about theoutsourcing privacy andinput privacy. For the output privacy, the random message m is also hidden by a owe-way function H; thus the cloud can just get H(m) and is unable to recover m from it (except a negligible advantage) which is considered to achieveoutput privacy as well.


## 5. Extracted Single-Mode Version ofSV-OC Protocol

In some cases, the clients (e.g., vessels) may just outsource either data sets or computing function to the cloud; therefore we have to ask the following question:Can we transform the dual-mode verifiable outsourcing computation into a single-mode one?Intuitively, setting one of the outsourced data sets and outsourced function as “on-the-fly” input ofSV-OC protocol, we hence assume obtaining two single-mode public VC protocols towards respective outsourced function and outsourced data sets. However, this assumption fails due to the nonexistence of a single-mode SV-OC for outsourcing data sets. The reasons are as follows:(1)
Firstly, we should observe that the complement class of the outsourced data setsψ does not make any sense in practice, which is not similar to the relation between F- and F. It is also not easy to obtain the complement class of ψ.(2)
Secondly, one can run the key-policy ABE (KP-ABE) mode of dual-policy ABE (DP-ABE) in [10] twice for respective F and F-, but the relation between ciphertext-policy ABE and public VC is not known so far. In this way, the checkability of the single-mode SV-OC over outsourcing data sets cannot achieve “1.”Hence, we can just obtain the single-mode variant ofSM-SV-OC for outsourced computing function at first, namely, Type II delegation type.


### 5.1. Construction for Single-ModeSV-OC for Just Outsourcing Functions: SM-SV-OC

Inspired by the KP-ABE mode of dual-policy ABE [10] and our SV-OC protocol, we give thesingle-mode publicly verifiable outsourcing computation towards outsourcing computing functions’ construction.(1) System Initialization Phase.This step is same as that of SV-OC except for adding special data T0 as a new input.(2) Evaluation Key Generation Phase.This stage is same as that of SV-OC except by randomly choosing r0,r-0←$Zp and setting (14)K0′=gγ+αrHT0-r0,K0′′=gr0,K-0′=g-γ-+α-r-HT0-r-0,K-0′′=g-r-0.Hence the evaluation key behaves as (15)ekF≔skF,ψ,sk¯F-,ψ=K,Kxx∈ψ,Ki′,Ki′′i∈l′,K0′,K0′′,K-,K-x-x-∈ψ,K-i,K-i′i∈l-′,K-0′,K-0′′.(3) Problem Generation Phase.This is almost same as that of SV-OC except for sampling s←$Zp and setting (16)C=m·eg,gs,C′=gαs,C0=gs,Cx′′x∈ω=Hxsx∈ω,C-=m¯·eg-,g-s,C-′=g-αs,C-0=g-s,C-x′′x∈ω=Hxsx∈ω.Hence, the problem description behaves as (17)σω,G≔ctω,G,ct¯ω,G=C,C′,C0,Cx′′x∈ω,C-,C-′,C-0,C-x′′x∈ω.(4) Compute Phase.In this case, this process computes as follows: (18)m′⟵C·eC0,K∏j∈i∣πi∈ωeKj′,C′·eKj′′,Cπj′′vj,m¯′⟵C·eC-0,K-∏j∈i∣π-i∈ωeK-j′,C-′·eK-j′′,C-π-j′′vj.Finally, output the problem solution σot:=(m′,m¯′).(5) Verification Phase.This step is exactly same as that of SV-OC.This concludes the construction description.


### 5.2. Analysis on the Single-ModeSV-OC for Just Outsourcing Computing Functions

In this subsection, we still give a correctness, efficiency, and security analysis on theSM-SV-OC protocol.


#### 5.2.1. Correctness Analysis

The correctness holds whenF accepts the data sets ω, where the secret shares’ reconstruction follows(19)∑j∈i∣πi∈ωviηi=γ+αr.⁡Definition2.


#### 5.2.2. Efficiency Analysis

In general, the size and time efficiency of the single-modeSV-OC protocol for only outsourcing computing functions are comparable to those of SV-OC one. Next, we present the time and size efficiency analysis for SV-OC in concrete way; Table 4 gives the size calculations and moreover Table 5 lists the dominant time operations (i.e., pairing, exponentiation, and multiplication) in group which performed in each step of single-mode SV-OC.Table 4
Size analysis of our single-modeSV-OC protocol. In the table, “|G|, |GT|” denote the size of a group element in groups G and GT, respectively; “n, l,” respectively, represent the maximum input size and the row’s number in the sharing matrix M.
Description
Sizes
pkF
Public key
4
|
G
|
+
2
|
G
T
|
ekF
Evaluation key
(
4
l
+
2
n
+
6
)
|
G
|
σω,G
Problem description
(
2
n
+
4
)
|
G
|
+
2
|
G
T
|
vkω,G
Verification key
2
|
G
|Table 5
Group operations analysis in each phase of our single-modeSV-OC protocol. In the table, “Pairing” represents a paring operation in the protocol; ExpG and ExpGT denote an exponentiation operation in group G or GT, respectively; similarly, MulG and MulGT denote a multiplication operation in groups G and GT, respectively; “n,l,” respectively, represent the maximum input size and the row’s number in the sharing matrix M.
Step
Description
Performer
Operations
(1)
System initialization
Pilot vessel
2
P
a
i
r
i
n
g
+
2
E
x
p
G
T
+
2
E
x
p
G
(2)
Evaluation key generation
Pilot vessel
(
6
l
+
2
n
+
6
)
E
x
p
G
+
(
2
n
+
2
l
+
2
)
H
+
(
2
l
+
2
)
M
u
l
G
(3)
Problem generation
Any vessel
(
2
n
+
4
)
E
x
p
G
+
(
2
n
)
H
+
2
M
u
l
G
(4)
Compute
Cloud
4
n
P
a
i
r
i
n
g
+
(
2
n
+
2
)
E
x
p
G
T
+
4
M
u
l
G
T
(5)
Verification
Anyone
2
HIn concrete way, the problem generation and verification overheads enjoy better efficiency than that inSV-OC, but its overhead on generating evaluation key is a little expensive (including the size of ekF) compared to SV-OC, since “on-the-fly” data set is involved to handle the construction. A tradeoff between Steps (1), (2),  and  (3) and Steps (4)  and  (5) over the above three steps does inevitably exist. Apart from this, the overall time and time overhead are almost same as that of SV-OC.As a result, the (non)pilot vessel or anyone can efficiently run the single-modeSV-OC service, and moreover the cloud’s running cost on computing the problem also turns out to be short. In this way, we can directly extract a highly efficient SM-SV-OC protocol from SV-OC.


#### 5.2.3. Security Analysis

Theorem 9 (main theorem).
LetF be a class of Boolean functions (implemented by a family of circuits C), and let F-={F-∣F∈F} be a class of the complement function F- of each function F and H be any one-way function. Suppose Definition 4 holds; then the single-mode SV-OC protocol for only outsourcing computing functions achieves selective soundness according to the security definition in Section 2.3.The proposed single-mode verifiable outsourcing computation protocolSV-OC can be seen as a special variant of SV-OC in fact, whereas their functionalities are merely not the same. Based on the security analysis on Theorem 8, Theorem 9 can be proved easily as well.


#### 5.2.4. Privacy Analysis

The privacy analysis on theSM-SV-OC protocol is same as that of the SV-OC protocol in Section 4.4.


## 5.1. Construction for Single-ModeSV-OC for Just Outsourcing Functions: SM-SV-OC

Inspired by the KP-ABE mode of dual-policy ABE [10] and our SV-OC protocol, we give thesingle-mode publicly verifiable outsourcing computation towards outsourcing computing functions’ construction.(1) System Initialization Phase.This step is same as that of SV-OC except for adding special data T0 as a new input.(2) Evaluation Key Generation Phase.This stage is same as that of SV-OC except by randomly choosing r0,r-0←$Zp and setting (14)K0′=gγ+αrHT0-r0,K0′′=gr0,K-0′=g-γ-+α-r-HT0-r-0,K-0′′=g-r-0.Hence the evaluation key behaves as (15)ekF≔skF,ψ,sk¯F-,ψ=K,Kxx∈ψ,Ki′,Ki′′i∈l′,K0′,K0′′,K-,K-x-x-∈ψ,K-i,K-i′i∈l-′,K-0′,K-0′′.(3) Problem Generation Phase.This is almost same as that of SV-OC except for sampling s←$Zp and setting (16)C=m·eg,gs,C′=gαs,C0=gs,Cx′′x∈ω=Hxsx∈ω,C-=m¯·eg-,g-s,C-′=g-αs,C-0=g-s,C-x′′x∈ω=Hxsx∈ω.Hence, the problem description behaves as (17)σω,G≔ctω,G,ct¯ω,G=C,C′,C0,Cx′′x∈ω,C-,C-′,C-0,C-x′′x∈ω.(4) Compute Phase.In this case, this process computes as follows: (18)m′⟵C·eC0,K∏j∈i∣πi∈ωeKj′,C′·eKj′′,Cπj′′vj,m¯′⟵C·eC-0,K-∏j∈i∣π-i∈ωeK-j′,C-′·eK-j′′,C-π-j′′vj.Finally, output the problem solution σot:=(m′,m¯′).(5) Verification Phase.This step is exactly same as that of SV-OC.This concludes the construction description.


## 5.2. Analysis on the Single-ModeSV-OC for Just Outsourcing Computing Functions

In this subsection, we still give a correctness, efficiency, and security analysis on theSM-SV-OC protocol.


### 5.2.1. Correctness Analysis

The correctness holds whenF accepts the data sets ω, where the secret shares’ reconstruction follows(19)∑j∈i∣πi∈ωviηi=γ+αr.⁡Definition2.


### 5.2.2. Efficiency Analysis

In general, the size and time efficiency of the single-modeSV-OC protocol for only outsourcing computing functions are comparable to those of SV-OC one. Next, we present the time and size efficiency analysis for SV-OC in concrete way; Table 4 gives the size calculations and moreover Table 5 lists the dominant time operations (i.e., pairing, exponentiation, and multiplication) in group which performed in each step of single-mode SV-OC.Table 4
Size analysis of our single-modeSV-OC protocol. In the table, “|G|, |GT|” denote the size of a group element in groups G and GT, respectively; “n, l,” respectively, represent the maximum input size and the row’s number in the sharing matrix M.
Description
Sizes
pkF
Public key
4
|
G
|
+
2
|
G
T
|
ekF
Evaluation key
(
4
l
+
2
n
+
6
)
|
G
|
σω,G
Problem description
(
2
n
+
4
)
|
G
|
+
2
|
G
T
|
vkω,G
Verification key
2
|
G
|Table 5
Group operations analysis in each phase of our single-modeSV-OC protocol. In the table, “Pairing” represents a paring operation in the protocol; ExpG and ExpGT denote an exponentiation operation in group G or GT, respectively; similarly, MulG and MulGT denote a multiplication operation in groups G and GT, respectively; “n,l,” respectively, represent the maximum input size and the row’s number in the sharing matrix M.
Step
Description
Performer
Operations
(1)
System initialization
Pilot vessel
2
P
a
i
r
i
n
g
+
2
E
x
p
G
T
+
2
E
x
p
G
(2)
Evaluation key generation
Pilot vessel
(
6
l
+
2
n
+
6
)
E
x
p
G
+
(
2
n
+
2
l
+
2
)
H
+
(
2
l
+
2
)
M
u
l
G
(3)
Problem generation
Any vessel
(
2
n
+
4
)
E
x
p
G
+
(
2
n
)
H
+
2
M
u
l
G
(4)
Compute
Cloud
4
n
P
a
i
r
i
n
g
+
(
2
n
+
2
)
E
x
p
G
T
+
4
M
u
l
G
T
(5)
Verification
Anyone
2
HIn concrete way, the problem generation and verification overheads enjoy better efficiency than that inSV-OC, but its overhead on generating evaluation key is a little expensive (including the size of ekF) compared to SV-OC, since “on-the-fly” data set is involved to handle the construction. A tradeoff between Steps (1), (2),  and  (3) and Steps (4)  and  (5) over the above three steps does inevitably exist. Apart from this, the overall time and time overhead are almost same as that of SV-OC.As a result, the (non)pilot vessel or anyone can efficiently run the single-modeSV-OC service, and moreover the cloud’s running cost on computing the problem also turns out to be short. In this way, we can directly extract a highly efficient SM-SV-OC protocol from SV-OC.


### 5.2.3. Security Analysis

Theorem 9 (main theorem).
LetF be a class of Boolean functions (implemented by a family of circuits C), and let F-={F-∣F∈F} be a class of the complement function F- of each function F and H be any one-way function. Suppose Definition 4 holds; then the single-mode SV-OC protocol for only outsourcing computing functions achieves selective soundness according to the security definition in Section 2.3.The proposed single-mode verifiable outsourcing computation protocolSV-OC can be seen as a special variant of SV-OC in fact, whereas their functionalities are merely not the same. Based on the security analysis on Theorem 8, Theorem 9 can be proved easily as well.


### 5.2.4. Privacy Analysis

The privacy analysis on theSM-SV-OC protocol is same as that of the SV-OC protocol in Section 4.4.


## 5.2.1. Correctness Analysis

The correctness holds whenF accepts the data sets ω, where the secret shares’ reconstruction follows(19)∑j∈i∣πi∈ωviηi=γ+αr.⁡Definition2.


## 5.2.2. Efficiency Analysis

In general, the size and time efficiency of the single-modeSV-OC protocol for only outsourcing computing functions are comparable to those of SV-OC one. Next, we present the time and size efficiency analysis for SV-OC in concrete way; Table 4 gives the size calculations and moreover Table 5 lists the dominant time operations (i.e., pairing, exponentiation, and multiplication) in group which performed in each step of single-mode SV-OC.Table 4
Size analysis of our single-modeSV-OC protocol. In the table, “|G|, |GT|” denote the size of a group element in groups G and GT, respectively; “n, l,” respectively, represent the maximum input size and the row’s number in the sharing matrix M.
Description
Sizes
pkF
Public key
4
|
G
|
+
2
|
G
T
|
ekF
Evaluation key
(
4
l
+
2
n
+
6
)
|
G
|
σω,G
Problem description
(
2
n
+
4
)
|
G
|
+
2
|
G
T
|
vkω,G
Verification key
2
|
G
|Table 5
Group operations analysis in each phase of our single-modeSV-OC protocol. In the table, “Pairing” represents a paring operation in the protocol; ExpG and ExpGT denote an exponentiation operation in group G or GT, respectively; similarly, MulG and MulGT denote a multiplication operation in groups G and GT, respectively; “n,l,” respectively, represent the maximum input size and the row’s number in the sharing matrix M.
Step
Description
Performer
Operations
(1)
System initialization
Pilot vessel
2
P
a
i
r
i
n
g
+
2
E
x
p
G
T
+
2
E
x
p
G
(2)
Evaluation key generation
Pilot vessel
(
6
l
+
2
n
+
6
)
E
x
p
G
+
(
2
n
+
2
l
+
2
)
H
+
(
2
l
+
2
)
M
u
l
G
(3)
Problem generation
Any vessel
(
2
n
+
4
)
E
x
p
G
+
(
2
n
)
H
+
2
M
u
l
G
(4)
Compute
Cloud
4
n
P
a
i
r
i
n
g
+
(
2
n
+
2
)
E
x
p
G
T
+
4
M
u
l
G
T
(5)
Verification
Anyone
2
HIn concrete way, the problem generation and verification overheads enjoy better efficiency than that inSV-OC, but its overhead on generating evaluation key is a little expensive (including the size of ekF) compared to SV-OC, since “on-the-fly” data set is involved to handle the construction. A tradeoff between Steps (1), (2),  and  (3) and Steps (4)  and  (5) over the above three steps does inevitably exist. Apart from this, the overall time and time overhead are almost same as that of SV-OC.As a result, the (non)pilot vessel or anyone can efficiently run the single-modeSV-OC service, and moreover the cloud’s running cost on computing the problem also turns out to be short. In this way, we can directly extract a highly efficient SM-SV-OC protocol from SV-OC.


## 5.2.3. Security Analysis

Theorem 9 (main theorem).
LetF be a class of Boolean functions (implemented by a family of circuits C), and let F-={F-∣F∈F} be a class of the complement function F- of each function F and H be any one-way function. Suppose Definition 4 holds; then the single-mode SV-OC protocol for only outsourcing computing functions achieves selective soundness according to the security definition in Section 2.3.The proposed single-mode verifiable outsourcing computation protocolSV-OC can be seen as a special variant of SV-OC in fact, whereas their functionalities are merely not the same. Based on the security analysis on Theorem 8, Theorem 9 can be proved easily as well.


## 5.2.4. Privacy Analysis

The privacy analysis on theSM-SV-OC protocol is same as that of the SV-OC protocol in Section 4.4.


## 6. Performance Evaluation

In this section, we give a performance evaluation on ourSV-OC and its extracted single-mode outsourcing computation protocol SM-SV-OC. Applying a certain implementation technique on realizing bilinear maps, we choose using an asymmetric bilinear group e:G1×G2→GT to implement the symmetric bilinear group e:G×G→GT for SV-OC and SM-SV-OC in the actual experiment as in [25].Standing by the standard NIST recommendation [26] and general remarks [25, 27] based on the Python language’s realizations along with its provided Charm-crypto Benchmark, we note that the charm tool [25] is an extensible Python-based framework under Pairing-Based Cryptography (PBC) library for rapidly prototyping cryptographic schemes and protocols, which is widely used in conducting functional encryption-based primitives. We remark that this is instantiated in an Ubuntu 12.04 operating system with 1 GB RAM (established in a MACBOOK Air Intel i5@1.8 GHz and 4 GB RAM equipped with a VMWare software). Next, we decide to employ the “SS512” elliptic curve for our performance evaluation. Finally, Table 7 shows the “SS512” curve’s element length; and moreover Table 6 gives a list of the “SS512” curve’s average running-times for each protocol step.Table 6
Element lengths of “SS512” elliptic curve.
G
1
G
2
G
T
Element length
512bits
512bits
1024bitsTable 7
Average running-time of “SS512” elliptic curve. In the table, the symbol “ms" denotes running-time in millisecond.
M
u
l
G
1
E
x
p
G
1
M
u
l
G
2
E
x
p
G
2
M
u
l
G
T
E
x
p
G
T
P
a
i
r
i
n
g
Running-time
0.024ms
3.7503ms
0.0201ms
3.7833ms
0.0055ms
0.4844ms
3.9723msSuppose that the size of the data setψ, ω is n and the value of l, l′ is 10. Based on the employed “SS512” elliptic curve [28], the actual size evaluation in Figure 2 and the time efficiency simulation in Figure 3 are both given. In addition, we use “+” to denote thedual-modeSV-OC protocol and “⋄” to denote theextracted single-modelSV-OC: SM-SV-OC protocol in both Figures 2 and 3.Figure 2
Size efficiency of theSV-OC protocol.Figure 3
Time efficiency of theSV-OC protocol.From Figures2 and 3, we can deduce the fact that both SV-OC and SM-SV-OC achieve high space and time efficiency. Our SV-OC protocol’s efficiency is comparable to the extracted SM-SV-OC one’s efficiency. Particularly, the overload that belongs to the weak clients’ sides is actual satisfactory.


## 7. Concluding Remarks

This paper presented a scalable and soundness verifiable outsourcing computation protocol in marine mobile cloud computing. OurSV-OC protocol enabled any client to delegate a computation task to the server and was also able to designate anyone to verify the result. In addition, an extracted single-mode outsourcing computation protocol SM-SV-OC from SV-OC was presented, which led to a fact that the client can adapt SV-OC based on the inputs’ option in terms of its interest or its own needs. However, we found that our SM-SV-OC protocol could just handle the outsourcing function as the single mode; hence a design of a verifiable outsourcing computation protocol towards outsourced function may be an open problem.



---

*Source: 6128437-2017-12-10.xml*