# An Efficient HPRA-Based Multiclient Verifiable Computation: Transform and Instantiation

Authors: Shuaijianni Xu
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Choi, Katz, Kumaresan, and Cid put forward the conception of multiclient noninteractive verifiable computation (MVC), enabling a group of clients to outsource computation of a function off. CKKC’s MVC is impractical due to their dependence on fully homomorphic encryption (FHE) and garbled circuits (GCs). In this paper, with the goal of satisfying practical requirements, a general transform is presented from the homomorphic proxy re-authenticator (HPRA) of Deler, Ramacher, and Slamanig to MVC schemes. MVC constructions in this particular study tend to be more efficient once the underlying HPRA avoids introducing FHE and GCs. By deploying the transform to DRS’s HPRA scheme, a specific MVC scheme for calculating the linear combinations of vectors has been proposed. It can be understood that it is the first feasible and implementable MVC scheme so far, and the instantiation solution has a great advantage in efficiency compared with related works.


---

## Body

## 1. Introduction

The past several years have witnessed a rapid growth of attention on outsourcing computation due to the popularity of cloud computing: the on-demand availability of computer system resources, including data storage and computing power, without maintaining infrastructure by the client. The proliferation of mobile devices is also one of the reasons why outsourced computing is getting more attention.Outsourcing computation allows relatively weak devices (phones, tablets, laptops, and PCs) to offload work (storage, image processing, and video encoding) to powerful cloud servers. However, many things can (and do) go wrong in cloud computing scenarios. One must worry about bugs, misconfigurations, operator error, natural disasters, or even malicious cloud servers. The servers may have considerable financial incentives to perform dishonestly, and the servers may offer fast but faulty computations to reduce the occupation of computational resources. In the above cases, the client needs some measures to ensure that computation was processed in the expected way and has not been tampered with. Moreover, when the client’s data (e.g., function and inputs or/and outputs) are not encrypted, the servers may misuse the data. How to ensure that the correctness of the calculations and how to ensure that the clients’ data are not misused are two critical security topics in the outsourcing computation area.Gennaro et al. [1] proposed the conception of noninteractive verifiable computation (VC) for the single-client scenario. The VC scheme allows client with weak computing power to outsource the computation task of a function f on a set of inputs x1,x2,…,xn to a server, ensuring that client can detect the malicious or malfunctioning server by verifying the results returned, but their efficiency is problematic due to the dependence on expensive cryptographic primitives, for example, fully homomorphic encryption (FHE) and garbled circuits (GCs). The initial proposal and construction of VC led to a long line of follow-up work, which provided further exploration on optimizing the efficiency of outsourced computations for restricted classes of functions.Some researchers extended VC into different scenarios. There are, however, scenarios in which it would be meaningful to extend this functionality to multiclient case. For example, with limited infrastructure,n resource-constrained nodes cannot directly communicate with each other while are only given access to a central server. It may be desirable for the nodes to get evaluation result of a function f over their joint inputs. At this point, only the central server is responsible for collecting the data and reporting the computation results, thereby letting the nodes to adjust the modalities.Choi et al. [2] initiated the study of this setting, extending the single-client VC model to the multiclient noninteractive verifiable computation (MVC) model. They assumed no client-client communication involved and focused on noninteractive solutions, where each evaluation of the function f required only a single round of communication, i.e., noninteractive. In a single round of communication, n clients send the representation of joint inputs x11,…,xn1 to the server, and server returns the evaluation result accompanied by a proof. MVC ensures that a malicious server can neither fool any client into accepting a wrong result nor misuse the inputs of the clients. In the scheme, they consider the case where only the first client obtains output (a more general case is dealt with by simply making the clients execute the scheme several times in parallel, with each client playing the role of the first client in one round of execution). They also presented a construction for outsourcing the evaluation of universal Boolean circuits by integrating the scheme of Gennaro et al. [1] with the proxy oblivious transfer. Since FHE and GCs are still the main technical primitives in their construction, the efficiency issue remains unresolved.Reducing the use of these expensive cryptographic primitives is necessary for constructing a more practical MVC scheme. Unfortunately, if we are limited to the outsourcing of arbitrary computations on confidential data, then using these primitives is somehow unavoidable. In order to go further in efficiency, we sacrifice the generality of the outsourced functions. This paper is primarily concerned with efficient MVC schemes for specific functions, especially for calculating the linear combination of vectors.


### 1.1. Our Contribution

The main contributions in this paper are twofold. The first one is a proposal of general transform from the homomorphic proxy re-authenticator (HPRA) [3], a tool providing security and verifiability guarantees to the multiuser data aggregation scenarios, to the MVC schemes. The HPRA makes distinct signers authenticate input data under private keys and allows an aggregator to transform all authenticators into an MAC under the receiver’s secret key. The evaluation of a function f on the data along with an aggregate authenticated message vector is computed by the aggregator; therefore, the receiver can verify whether the computation is correct or not. Compared with the MVC, there is an additional receiver in the HPRA that obtains and verifies the function output; by contrast, in the MVC, the first client not only performs verification but also provides its own function input.A very natural idea is thus generated: what will happen if we map the parties in the HPRA into those in the MVC? Taking into account the different properties and functionalities of all the entities, the first step was to merge the receiver with the first signer in the HPRA and then to consider this merged participant as the first client in the MVC. Second, we consider each of the remaining signers play as a different client in the MVC. Third, we regard the aggregator in the HPRA as a cloud server in the MVC. Following this idea, we construct a general transform that can be applied to any HPRA scheme, resulting in an MVC with the following properties:(i)
No malicious server can generate an incorrect output passing the verification of the client, except with a nonnegligible probability.(ii)
For each client, any information on the client’s input should not be leaked to the other entities.(iii)
No malicious server can learn anything about the result of the computation beyond what the description off would leak.(iv)
There is no client-client communication, and all the involved parties do not share a secret key. As an alternative, the clients use independent private keys generated by themselves to encrypt and authenticate the data.(v)
Compared with the HPRA, no extracomputational consumption is introduced. Our MVC construction has nothing to do with FHE and GCs as long as the underlying HPRA avoids introducing these expensive cryptographic primitives.(vi)
Compared with the HPRA, no extracryptographic assumption is introduced. Our MVC construction relies only on the assumptions required in the HPRA.The second contribution is an MVC scheme implementable by applying a particular HPRA scheme of Derler et al.’s [3] to the transform, which allows n clients to jointly outsource the linear combination of n vectors of length ℓ. It can be seen that it is the first time to implement an MVC scheme.A model was developed by Parno et al. [4] to analyze the efficiency of the computational performance of the FHE + GC-based VC schemes [1,2]. They estimated that the client would take ≥1011 seconds to outsource the multiplication of two 100 by 100 matrices in the MVC by Choi et al. [2] as our MVC can also be adjusted to outsource the matrix multiplications as well. The experimental results show that, in our MVC scheme instance, calculating the multiplication of two 100 by 100 matrices takes only ≈103 seconds at the client side. Our proposed scheme evidently has a great advantage in terms of efficiency.


### 1.2. Related Works

A single-client noninteractive VC model was presented by Gennaro et al. [1], and an instantiation by considering FHE and GCs as main technical tools was constructed. Parno et al. [4] and Setty et al. [5] gave general-purpose VC protocols on the basis of the quadratic arithmetic programs (QAPs) [6]. To provide noninteractive, publicly verifiable computation and zero-knowledge proofs, many recent systems [7–10] have converged on the Pinocchio protocol [4] as a cryptographic primitive. Benabbas et al. [11] initiated a line of research about efficient protocols for specific functions. Following this line, a series of subsequent outsourcing computations systems [12–15] developed schemes with improved efficiency for restricted classes of functions. Some research studies [16,17] are dedicated to provide additional security, ensuring that the outsourced polynomial remains hidden.Choi et al. [2] firstly formed the conception of multiclient noninteractive verifiable computation. In a nutshell, MVC is like VC with an extra feature, allowing multiple clients to jointly outsource a computation under different secret keys. They also proposed an FHE-based construction for outsourcing the computation of arbitrary Boolean circuits by integrating Gennaro et al.’s scheme [1] with proxy oblivious transfer. However, their scheme still uses FHE and GCs as main technical tools and would thus leave the efficiency problem. Moreover, if a malicious server is allowed to send malformed responses and observe the reaction of the first client, the soundness might be threatened. This problem was resolved by Gordon et al. [18], and they provide solutions against a malicious server or multiple colluding clients. However, as they used the falsifiable assumption which is not as mature as the well-known assumptions such as DLOG, CDH, and DDH, they may have potential weakness. The falsifiable assumption introduced the dependence on the circuit depth, and the efficiency is also sacrificed.Multi-input functional encryption (MIFE) is a generalization of the functional encryption into the case of multi-input functions. MIFE has a great variety of applications related to computation over the encrypted data from multiple sources. However, the construction of MIFE assumed indistinguishability obfuscation (iO) for circuits, which introduces a strong assumption as the work of Goldwasser et al. revealed [19]. Moreover, current MIFE schemes have prohibitively large overhead. Fiore et al. [20] built a multikey homomorphic authenticator (multikey HA), allowing multiple clients to authenticate and outsource a large collection of data, together with the corresponding authenticators, to a malicious server. Backes et al. [12] added a crucial efficiency property for the verification of multikey HAs. Based on the line of multikey HAs, the HPRA introduced by Derler et al. [3] allows a group of signers to authenticate data under private keys and allows an aggregator to transform all the single authenticators into an MAC under the secret key of receiver. Following this research line of multikey HAs, Schabhüser et al. [21] presented a publicly verifiable homomorphic authenticator scheme with efficient and context hiding verification in the case of multiple clients. However, in their scheme, the result of the outsourced computation is public to all entities, thus leading to privacy breaches.


### 1.3. Organization of the Paper

The preliminaries, such as MVC and HPRA, are highlighted in Section2. The HPRA to MVC transform and related security proof are presented in Section 3. A concrete construction is then provided in Section 4. The implementation of concrete instantiation and analysis of results are illustrated in Section 5. Conclusions are drawn based on this particular research in Section 6.


## 1.1. Our Contribution

The main contributions in this paper are twofold. The first one is a proposal of general transform from the homomorphic proxy re-authenticator (HPRA) [3], a tool providing security and verifiability guarantees to the multiuser data aggregation scenarios, to the MVC schemes. The HPRA makes distinct signers authenticate input data under private keys and allows an aggregator to transform all authenticators into an MAC under the receiver’s secret key. The evaluation of a function f on the data along with an aggregate authenticated message vector is computed by the aggregator; therefore, the receiver can verify whether the computation is correct or not. Compared with the MVC, there is an additional receiver in the HPRA that obtains and verifies the function output; by contrast, in the MVC, the first client not only performs verification but also provides its own function input.A very natural idea is thus generated: what will happen if we map the parties in the HPRA into those in the MVC? Taking into account the different properties and functionalities of all the entities, the first step was to merge the receiver with the first signer in the HPRA and then to consider this merged participant as the first client in the MVC. Second, we consider each of the remaining signers play as a different client in the MVC. Third, we regard the aggregator in the HPRA as a cloud server in the MVC. Following this idea, we construct a general transform that can be applied to any HPRA scheme, resulting in an MVC with the following properties:(i)
No malicious server can generate an incorrect output passing the verification of the client, except with a nonnegligible probability.(ii)
For each client, any information on the client’s input should not be leaked to the other entities.(iii)
No malicious server can learn anything about the result of the computation beyond what the description off would leak.(iv)
There is no client-client communication, and all the involved parties do not share a secret key. As an alternative, the clients use independent private keys generated by themselves to encrypt and authenticate the data.(v)
Compared with the HPRA, no extracomputational consumption is introduced. Our MVC construction has nothing to do with FHE and GCs as long as the underlying HPRA avoids introducing these expensive cryptographic primitives.(vi)
Compared with the HPRA, no extracryptographic assumption is introduced. Our MVC construction relies only on the assumptions required in the HPRA.The second contribution is an MVC scheme implementable by applying a particular HPRA scheme of Derler et al.’s [3] to the transform, which allows n clients to jointly outsource the linear combination of n vectors of length ℓ. It can be seen that it is the first time to implement an MVC scheme.A model was developed by Parno et al. [4] to analyze the efficiency of the computational performance of the FHE + GC-based VC schemes [1,2]. They estimated that the client would take ≥1011 seconds to outsource the multiplication of two 100 by 100 matrices in the MVC by Choi et al. [2] as our MVC can also be adjusted to outsource the matrix multiplications as well. The experimental results show that, in our MVC scheme instance, calculating the multiplication of two 100 by 100 matrices takes only ≈103 seconds at the client side. Our proposed scheme evidently has a great advantage in terms of efficiency.


## 1.2. Related Works

A single-client noninteractive VC model was presented by Gennaro et al. [1], and an instantiation by considering FHE and GCs as main technical tools was constructed. Parno et al. [4] and Setty et al. [5] gave general-purpose VC protocols on the basis of the quadratic arithmetic programs (QAPs) [6]. To provide noninteractive, publicly verifiable computation and zero-knowledge proofs, many recent systems [7–10] have converged on the Pinocchio protocol [4] as a cryptographic primitive. Benabbas et al. [11] initiated a line of research about efficient protocols for specific functions. Following this line, a series of subsequent outsourcing computations systems [12–15] developed schemes with improved efficiency for restricted classes of functions. Some research studies [16,17] are dedicated to provide additional security, ensuring that the outsourced polynomial remains hidden.Choi et al. [2] firstly formed the conception of multiclient noninteractive verifiable computation. In a nutshell, MVC is like VC with an extra feature, allowing multiple clients to jointly outsource a computation under different secret keys. They also proposed an FHE-based construction for outsourcing the computation of arbitrary Boolean circuits by integrating Gennaro et al.’s scheme [1] with proxy oblivious transfer. However, their scheme still uses FHE and GCs as main technical tools and would thus leave the efficiency problem. Moreover, if a malicious server is allowed to send malformed responses and observe the reaction of the first client, the soundness might be threatened. This problem was resolved by Gordon et al. [18], and they provide solutions against a malicious server or multiple colluding clients. However, as they used the falsifiable assumption which is not as mature as the well-known assumptions such as DLOG, CDH, and DDH, they may have potential weakness. The falsifiable assumption introduced the dependence on the circuit depth, and the efficiency is also sacrificed.Multi-input functional encryption (MIFE) is a generalization of the functional encryption into the case of multi-input functions. MIFE has a great variety of applications related to computation over the encrypted data from multiple sources. However, the construction of MIFE assumed indistinguishability obfuscation (iO) for circuits, which introduces a strong assumption as the work of Goldwasser et al. revealed [19]. Moreover, current MIFE schemes have prohibitively large overhead. Fiore et al. [20] built a multikey homomorphic authenticator (multikey HA), allowing multiple clients to authenticate and outsource a large collection of data, together with the corresponding authenticators, to a malicious server. Backes et al. [12] added a crucial efficiency property for the verification of multikey HAs. Based on the line of multikey HAs, the HPRA introduced by Derler et al. [3] allows a group of signers to authenticate data under private keys and allows an aggregator to transform all the single authenticators into an MAC under the secret key of receiver. Following this research line of multikey HAs, Schabhüser et al. [21] presented a publicly verifiable homomorphic authenticator scheme with efficient and context hiding verification in the case of multiple clients. However, in their scheme, the result of the outsourced computation is public to all entities, thus leading to privacy breaches.


## 1.3. Organization of the Paper

The preliminaries, such as MVC and HPRA, are highlighted in Section2. The HPRA to MVC transform and related security proof are presented in Section 3. A concrete construction is then provided in Section 4. The implementation of concrete instantiation and analysis of results are illustrated in Section 5. Conclusions are drawn based on this particular research in Section 6.


## 2. Preliminaries

To facilitate the comprehension of our work, we give some notations and review some preliminaries pertaining to our research work, namely, multiclient noninteractive verifiable computation and homomorphic proxy re-authenticator.


### 2.1. Notation

The Greek letterκ stands for the security parameter of schemes. A function fκ is considered to be negligible in κ if fκ=oκ−c under every constant c>0, and we denote all such functions as neglκ and otherwise denoted as non−neglκ. When a function can be represented as a polynomial, we use the notation poly⋅. For any n∈N, we refer to n as n≔1,…,n. We use a⟶ to denote a vector a⟶=a1,a2,…,an and a to denote a sequence of vectors a=a⟶1,a⟶2,…,a⟶n. For vectors with subscript in their variable name, say a⟶1, we use a⟶1i to indicate the i-th element in vector a⟶1. Given a set S, the notation s←RS remains for the process of sampling s from S uniformly.


### 2.2. Multiclient Verifiable Computation

In ann-party MVC introduced by Choi et al. [2], there are n clients P1,P2,…,Pn who expect to outsource the evaluation of some functions over their joint inputs to a server for several times. In the i-th evaluation, client P1,P2,…,Pn inputs are denoted as x1i,x2i,…,xni, respectively. To ensure the data privacy, the clients encode the original inputs into χ1i,…,χni and send it to a server along with the encoded function Φ of function f. The server is expected to evaluate Φχ1i,…,χni and respond with encoded output ωi. P1 is designated to verify the correctness of ωi with a decoding secret ξ and restore the real result yi=fx1i,x2i,…,xni from ωi.For the convenience of follow-up research, we made some reasonable modifications to the MVC model: (1) we replace the security parameter1κ with public parameter set pp containing the information of 1κ and the public outsourcing function f. (2) Let P1 runs KeyGen1 algorithm first and let pk1 be one of the inputs of algorithm KeyGenj, for j=2,…,n. As MVC has assumed the existence of a public-key infrastructure (PKI), which makes all the public keys of clients be accessible to all other entities. This change makes other client Pj to wait for client P1 to finish running KeyGen1 but does not affect security. (3) As EnFunc is run by client P1, taking P1’s private key sk1 as an extrainput of EnFunc is also reasonable.Definition 1.
(MVC). Ann-party MVC scheme Π=KeyGenjj=1n,EnFunc,EnInputjj=1n,Compute,Verify) for a function family ℱ consists of 2n+3 algorithms as follows and in Figure 1:(i)
pk1,sk1←KeyGen1pp. Client P1 will execute this algorithm on public parameters pp to produce a public key pk1 and a private key sk1.(ii)
pkj,skj←KeyGenjpp,pk1. For j=2,…,n, client Pj will execute this algorithm to produce a public key pkj and a private key skj.(iii)
ϕ,ξ←EnFuncpk⟶,sk1,f. Client P1 will execute this algorithm with pk⟶=pk1,pk2,…,pkn and sk1 to encode any f∈ℱ to an encoded function ϕ and send ϕ to the server. Then, Client P1 will produce a decoding secret ξ and keep it private.(iv)
χ1i,τi←EnInput1i,pk⟶,sk1,ξ,x1i. When out sourcing the i-th computation to the server, P1 will execute this algorithm to encode its input x1i to an encoded input χ1i and send χ1i to the server. Then, Client P1 will produce a decoding secret τi and keep it private.(v)
χji←EnInputji,pk⟶,skj,xji. When outsourcing the i-th computation to the server, each client Pj (j≠1) will execute the algorithm to encode its input xji to an encoded input χji and send χji to the server. We denote χ⟶i=χ1i,…,χni.(vi)
ωi←Computei,pk⟶,ϕ,χ⟶i. The server will execute the algorithm to obtain an encoded output ωi.(vii)
yi∪⊥←Verifyi,ξ,τi,ωi. Client P1 will implement this algorithm to return either an evaluation result yi=fx1i,…xni or a symbol ⊥ informing that the server returned an incorrect result.
Required by [2,18], an MVC scheme should be correct, sound, and input private. An MVC satisfies the property of correctness if all the involving algorithms are honestly executed; an honest server will always produce output corresponding to the evaluation of f on those inputs and will always pass the verification.
An MVC scheme satisfies the property of soundness if no malicious server can fool clients into obtaining a wrong evaluation on given inputs, even if the server is given access to an oracle, which can generate arbitrary valid input encodings:(i)
OracleℐNx1,…,xn(ii)
i≔i+1;(iii)
recordx1i,…,xni≔x1,…,xn;(iv)
χ1i,τi←EnInput1i,pk⟶,sk1,ξ,x1i;(v)
forj=2,…,n:χji←EnInputji,pk⟶,skj,xji;(vi)
outputχ1i,…,χni.Figure 1
Multiclient verifiable computation model.Definition 2.
(soundness). For schemeΠ, consider an experiment ExpAsoundΠ,f,κ,n with a malicious server A: for j=1,…,n, the public/private key pairs pkj,skj are produced; an encoded function ϕ and a decoding secret ξ are produced. A is given inputs pk⟶ and ϕ and access to OracleℐN and returns a forge ω∗. The challenger obtains y∗ by executing Verify; if y∗∉⊥,fx1i,…,xni, the output of ExpAsoundΠ,f,κ,n is defined to be 1 and 0 otherwise. Scheme Π satisfies the property of soundness if for all n=polyκ, all functions f∈ℱ, and all probabilistic polynomial-time adversary (PPT) adversary A; there is a negligible function negl⋅ such that PrExpAsoundΠ,f,κ,n=1≤neglκ.
An MVC scheme satisfies the property of input privacy if no information about the inputs is leaked to all the other entities including both server and other clients. While the clients except the first one apparently had no opportunity to learn any information about the others’ input data, the input privacy of the MVC scheme includes two properties: privacy against the first client and privacy against the server.Definition 3.
(privacy against the first client). The schemeΠ achieves the privacy against the first client if for any x⟶0=x1,x2,…,xn,x⟶1=x1,x2′,…,xn′ with fx⟶0=fx⟶1, the view of P1 executing Π if all clients holding x⟶0 cannot be distinguished from the view of P1 when executing with all clients holding x⟶1.
Privacy against the server requires that the server should not be able to distinguish the encoded inputs from two distinct inputs, even if the malicious server gains access to theOracleℐN.Definition 4.
(privacy against the server). Consider an experimentExpAprivΠ,f,κ,n,b with an adversarial server A: for j=1,…,n, the public/private key pairs pkj,skj are generated, so are an encoded function ϕ and a decoding secret ξ. The adversary A is given inputs pk⟶ and ϕ and access to OracleℐN and outputs two series of jointly inputs x10,…,xn0,x11,…,xn1. The challenge ciphertext χ1b,…,χnb is computed and given to A. A continues to have oracle access to ℐN and outputs a guess b′ of b. The advantage of A in the experiment above is defined as(1)AdvAprivΠ,f,κ,n=PrExpAprivΠ,f,κ,n,0=1−PrExpAprivΠ,f,κ,n,1=1.
The MVC schemeΠ is private against the server if for any n=polyκ, any function f∈ℱ, and any PPT adversary A, there is a negligible function negl⋅ such that AdvAprivΠ,f,κ,n≤neglκ.


### 2.3. Homomorphic Proxy Re-Authenticator (HPRA)

The HPRA scheme introduced by Derler et al. [3] consists of nine algorithms: Gen,SGen,VGen,Sign,Verify, SRGen, VRGen, Agg, and AVerify. And there are three types of parties: a set of signers, an aggregator, and a receiver. In a nutshell, HPRA allows n signers to authenticate data items m⟶1,m⟶2,…,m⟶n with signatures under their own distinct keys and allows the aggregator to convert their signatures to one under the receiver’s key. The aggregator outputs an aggregate authenticated message vector Λ consists of an evaluation result of function f on the inputs, and a signature corresponds to the result.Definition 5.
(HPRA). A homomorphic proxy re-authenticator schemeΣ=Gen,SGen,VGen,Sign,Verify,SRGen,VRGen,Agg,AVerify is composed of nine polynomial-time algorithms as follows and demonstrated in Figure 2.(i)
pp←Gen1κ,ℓ: given a security parameter 1κ and a constant ℓ, the algorithm generates public parameter set pp, which defines a message space ℳℓ, a function family ℱ=f|f:ℳℓn⟶ℳℓ, and a tag space.(ii)
id,sk,pk←SGenpp: each signer Pi will execute this algorithm on public parameter set pp to output a signer key, including an identifier id, a private key sk, and a public key pk.(iii)
mk,aux←VGenpp: the receiver will execute this algorithm on public parameters pp to obtain an MAC key mk and an auxiliary information aux.(iv)
σ←Signsk,m⟶,μ: each signer will execute this algorithm to sign its input m⟶ as a signature σ, which will be sent to the aggregator. For all the signers P1,…,Pn, we denote their signatures as σ⟶=σ1,…,σn.(v)
b←Verifypk,m⟶,μ,σ: any entity with m⟶ can verify the validation of a signature σ with the algorithm and outputs a bit b←0,1.(vi)
rki←SRGenski,aux: each signer will generate a re-encryption key rki with the algorithm.(vii)
aki←VRGenpki,mk,rki: with this algorithm, an aggregation key aki can be generated by the receiver, which will be sent to the aggregator.(viii)
Λ←Aggak⟶,σ⟶,μ,f: the aggregator will generate the aggregate authenticated message vector Λ by the algorithm. Let ak⟶=ak1,…,akn.(ix)
m⟶,μ/⊥,⊥←AVerifymk,Λ,ID,f: the receiver will generate a pair m⟶,μ with the algorithm and otherwise output ⊥,⊥ showing that the aggregator tries to cheat.
Required by [3], an HPRA scheme is required to be correct, input private, signer unforgeable, and aggregator unforgeable.
The correctness of an HPRA should meet the requirement that if all the involving algorithms are honestly executed, the aggregate authenticated message vectorΛ will always pass the verification and extract the real result of evaluation m⟶=fm⟶1,m⟶2,…,m⟶n.
The input privacy of HPRA should meet the requirement that an aggregate authenticated message vectorΛ should not leak any more information of the signers’ data m⟶1,m⟶2,…,m⟶n compared with what can be directly speculated from f and the real result of evaluation m⟶.Figure 2
Homomorphic proxy re-authenticator model.Definition 6.
(input privacy). The HPRA schemeΣ for ℱ is input private if for any κ∈ℕ, any f∈ℱ, all tags μ, and all m1=m⟶11,…,m⟶n1∈ℳℓn and m2=m⟶12,…,m⟶n2∈ℳℓn with fm⟶11,…,m⟶n1=fm⟶12,…,m⟶n2, all pp←Gen1κ,ℓ, all mk,aux←VGenpp, for i=1,…,n, ski,pki←SGenpp, rki←SRGenski,aux, and aki←VRGenpki,mk,rki. We denote QUOTE sk⟶=sk1,…sknsk⟶=sk1,…skn. The following distributions are identical:(2)Aggak⟶,Signsk⟶,m1,μ,μ,f,Aggak⟶,Signsk⟶,m2,μ,μ,f.
The signer unforgeability of an HPRA requires that if the aggregator always remains honest, no coalition of dishonest signers can produce a validΛ with respect to the function f∈ℱ such that Λ is outside of the range of f evaluated on arbitrary combinations of the actually signed vectors. The aggregator unforgeability is the natural counterpart of signer unforgeability; if the signers always remain honest, malicious aggregator cannot output a valid aggregate authenticated message vector with respect to the function f, such that the aggregate authenticated message vector is out of the range of f evaluated on the virtually signed vectors.
LetT represent “Signer” or “Aggregator.” In both definitions, the adversary gains access to a set OT of oracles, where OT≔SG,SKey,SR,VR,A for T = “Signer” and OT≔SG,Sig,SR,VR,VRKey for T = “Aggregator.” The oracles maintain some sets S, AK, RK, and SIG which are initially empty and work as follows, let i=1,…,n represents the index of client Pi, and we do not consider the corruption between the signers:(i)
SGi: works as SGen, sets Si←id,sk,pk and returns id,pk.(ii)
Skeyi: returns Si.(iii)
Sig1,…,n,m: works as Sign, sets SIGμ←SIGμ∪m⟶i,Si for i=1,…,n, returns σ⟶=σ1…σn and μ. Let m=m⟶1,…,m⟶n.(iv)
SRi: works as SRGen, returns RKi=rki.(v)
VRi: works as VRGen but without returning anything, sets AKi=aki.(vi)
VRKeyi: returns AKi.(vii)
Aσ⟶,1,…,n,μ,f: works as Agg, returns Λ.Definition 7.
(T-unforgeability). For the HPRA scheme Σ, consider an experiment ExpAT−unforgeΣ,κ,n,l with regard to a PPT adversary A: Public parameter pp is generated by running Gen1κ,ℓ; the MAC key and the auxiliary information mk,aux are generated by running VGenpp. A is given inputs pp and aux and access to oracle OT and outputs a forge Λ⋆,ID⋆,f⋆. The challenger carries out AVerifymk,Λ⋆,ID⋆,f⋆ and obtains m⟶,μ; if m⟶,μ≠⊥,⊥ and ∄m:∀i∈n:m⟶i,id∗∈SIGμ∧f⋆m⟶1…,m⟶n=m⟶, it outputs 1 and otherwise outputs 0. The HPRA scheme Σ is T-unforgeable; if for all PPT adversaries A, there is a negligible function negl⋅ such that PrExpAT−unforgeΣ,κ,n,ℓ=1≤neglκ.
There is an optional property for HPRA and output privacy, which simulates the situation that the aggregator learns nothing about either the inputs or the function’s output. In order to formally give a definition of output privacy, we define an oracleRoS as follows:(i)
RoSi,m,b: If Si=⊥, it returns ⊥. Otherwise, it samples μ uniformly at random, and if b=0, for i=1,…,n, it computes σi←SignSi2,m⟶i,μ. Else, it randomly chooses r⟶=r1,…,rn←ℳℓn, and for i=1,…,n, it computes σi←SignSi2,r⟶i,μ and returns σ⟶=σ1,…,σn.Definition 8.
(output privacy). For the HPRA schemeΣ, assuming an experiment ExpAoutprivΣ,κ,n,ℓ with a PPT adversaries A: public parameter pp is gained by executing Gen1κ,ℓ, the MAC key, and the auxiliary information mk,aux are gained by executing VGenpp. A is given input pp and access to oracle O. A random bit b←0,1 is chosen by the challenger, and a challenge ciphertext σ⟶ is computed and given to A. A continues to have oracle access to QUOTE O≔SG,SKey,RoSb,SR,VR,VRKeyO≔SG,SKey,RoSb,SR,VR,VRKey and outputs a guess b′ of b.
An HPRA for a family of function classesℱ is output private; if for all PPT adversaries A, there is a negligible function negl⋅ such that PrExpAoutprivΣ,κ,n,ℓ=1≤1/2+neglκ.


## 2.1. Notation

The Greek letterκ stands for the security parameter of schemes. A function fκ is considered to be negligible in κ if fκ=oκ−c under every constant c>0, and we denote all such functions as neglκ and otherwise denoted as non−neglκ. When a function can be represented as a polynomial, we use the notation poly⋅. For any n∈N, we refer to n as n≔1,…,n. We use a⟶ to denote a vector a⟶=a1,a2,…,an and a to denote a sequence of vectors a=a⟶1,a⟶2,…,a⟶n. For vectors with subscript in their variable name, say a⟶1, we use a⟶1i to indicate the i-th element in vector a⟶1. Given a set S, the notation s←RS remains for the process of sampling s from S uniformly.


## 2.2. Multiclient Verifiable Computation

In ann-party MVC introduced by Choi et al. [2], there are n clients P1,P2,…,Pn who expect to outsource the evaluation of some functions over their joint inputs to a server for several times. In the i-th evaluation, client P1,P2,…,Pn inputs are denoted as x1i,x2i,…,xni, respectively. To ensure the data privacy, the clients encode the original inputs into χ1i,…,χni and send it to a server along with the encoded function Φ of function f. The server is expected to evaluate Φχ1i,…,χni and respond with encoded output ωi. P1 is designated to verify the correctness of ωi with a decoding secret ξ and restore the real result yi=fx1i,x2i,…,xni from ωi.For the convenience of follow-up research, we made some reasonable modifications to the MVC model: (1) we replace the security parameter1κ with public parameter set pp containing the information of 1κ and the public outsourcing function f. (2) Let P1 runs KeyGen1 algorithm first and let pk1 be one of the inputs of algorithm KeyGenj, for j=2,…,n. As MVC has assumed the existence of a public-key infrastructure (PKI), which makes all the public keys of clients be accessible to all other entities. This change makes other client Pj to wait for client P1 to finish running KeyGen1 but does not affect security. (3) As EnFunc is run by client P1, taking P1’s private key sk1 as an extrainput of EnFunc is also reasonable.Definition 1.
(MVC). Ann-party MVC scheme Π=KeyGenjj=1n,EnFunc,EnInputjj=1n,Compute,Verify) for a function family ℱ consists of 2n+3 algorithms as follows and in Figure 1:(i)
pk1,sk1←KeyGen1pp. Client P1 will execute this algorithm on public parameters pp to produce a public key pk1 and a private key sk1.(ii)
pkj,skj←KeyGenjpp,pk1. For j=2,…,n, client Pj will execute this algorithm to produce a public key pkj and a private key skj.(iii)
ϕ,ξ←EnFuncpk⟶,sk1,f. Client P1 will execute this algorithm with pk⟶=pk1,pk2,…,pkn and sk1 to encode any f∈ℱ to an encoded function ϕ and send ϕ to the server. Then, Client P1 will produce a decoding secret ξ and keep it private.(iv)
χ1i,τi←EnInput1i,pk⟶,sk1,ξ,x1i. When out sourcing the i-th computation to the server, P1 will execute this algorithm to encode its input x1i to an encoded input χ1i and send χ1i to the server. Then, Client P1 will produce a decoding secret τi and keep it private.(v)
χji←EnInputji,pk⟶,skj,xji. When outsourcing the i-th computation to the server, each client Pj (j≠1) will execute the algorithm to encode its input xji to an encoded input χji and send χji to the server. We denote χ⟶i=χ1i,…,χni.(vi)
ωi←Computei,pk⟶,ϕ,χ⟶i. The server will execute the algorithm to obtain an encoded output ωi.(vii)
yi∪⊥←Verifyi,ξ,τi,ωi. Client P1 will implement this algorithm to return either an evaluation result yi=fx1i,…xni or a symbol ⊥ informing that the server returned an incorrect result.
Required by [2,18], an MVC scheme should be correct, sound, and input private. An MVC satisfies the property of correctness if all the involving algorithms are honestly executed; an honest server will always produce output corresponding to the evaluation of f on those inputs and will always pass the verification.
An MVC scheme satisfies the property of soundness if no malicious server can fool clients into obtaining a wrong evaluation on given inputs, even if the server is given access to an oracle, which can generate arbitrary valid input encodings:(i)
OracleℐNx1,…,xn(ii)
i≔i+1;(iii)
recordx1i,…,xni≔x1,…,xn;(iv)
χ1i,τi←EnInput1i,pk⟶,sk1,ξ,x1i;(v)
forj=2,…,n:χji←EnInputji,pk⟶,skj,xji;(vi)
outputχ1i,…,χni.Figure 1
Multiclient verifiable computation model.Definition 2.
(soundness). For schemeΠ, consider an experiment ExpAsoundΠ,f,κ,n with a malicious server A: for j=1,…,n, the public/private key pairs pkj,skj are produced; an encoded function ϕ and a decoding secret ξ are produced. A is given inputs pk⟶ and ϕ and access to OracleℐN and returns a forge ω∗. The challenger obtains y∗ by executing Verify; if y∗∉⊥,fx1i,…,xni, the output of ExpAsoundΠ,f,κ,n is defined to be 1 and 0 otherwise. Scheme Π satisfies the property of soundness if for all n=polyκ, all functions f∈ℱ, and all probabilistic polynomial-time adversary (PPT) adversary A; there is a negligible function negl⋅ such that PrExpAsoundΠ,f,κ,n=1≤neglκ.
An MVC scheme satisfies the property of input privacy if no information about the inputs is leaked to all the other entities including both server and other clients. While the clients except the first one apparently had no opportunity to learn any information about the others’ input data, the input privacy of the MVC scheme includes two properties: privacy against the first client and privacy against the server.Definition 3.
(privacy against the first client). The schemeΠ achieves the privacy against the first client if for any x⟶0=x1,x2,…,xn,x⟶1=x1,x2′,…,xn′ with fx⟶0=fx⟶1, the view of P1 executing Π if all clients holding x⟶0 cannot be distinguished from the view of P1 when executing with all clients holding x⟶1.
Privacy against the server requires that the server should not be able to distinguish the encoded inputs from two distinct inputs, even if the malicious server gains access to theOracleℐN.Definition 4.
(privacy against the server). Consider an experimentExpAprivΠ,f,κ,n,b with an adversarial server A: for j=1,…,n, the public/private key pairs pkj,skj are generated, so are an encoded function ϕ and a decoding secret ξ. The adversary A is given inputs pk⟶ and ϕ and access to OracleℐN and outputs two series of jointly inputs x10,…,xn0,x11,…,xn1. The challenge ciphertext χ1b,…,χnb is computed and given to A. A continues to have oracle access to ℐN and outputs a guess b′ of b. The advantage of A in the experiment above is defined as(1)AdvAprivΠ,f,κ,n=PrExpAprivΠ,f,κ,n,0=1−PrExpAprivΠ,f,κ,n,1=1.
The MVC schemeΠ is private against the server if for any n=polyκ, any function f∈ℱ, and any PPT adversary A, there is a negligible function negl⋅ such that AdvAprivΠ,f,κ,n≤neglκ.


## 2.3. Homomorphic Proxy Re-Authenticator (HPRA)

The HPRA scheme introduced by Derler et al. [3] consists of nine algorithms: Gen,SGen,VGen,Sign,Verify, SRGen, VRGen, Agg, and AVerify. And there are three types of parties: a set of signers, an aggregator, and a receiver. In a nutshell, HPRA allows n signers to authenticate data items m⟶1,m⟶2,…,m⟶n with signatures under their own distinct keys and allows the aggregator to convert their signatures to one under the receiver’s key. The aggregator outputs an aggregate authenticated message vector Λ consists of an evaluation result of function f on the inputs, and a signature corresponds to the result.Definition 5.
(HPRA). A homomorphic proxy re-authenticator schemeΣ=Gen,SGen,VGen,Sign,Verify,SRGen,VRGen,Agg,AVerify is composed of nine polynomial-time algorithms as follows and demonstrated in Figure 2.(i)
pp←Gen1κ,ℓ: given a security parameter 1κ and a constant ℓ, the algorithm generates public parameter set pp, which defines a message space ℳℓ, a function family ℱ=f|f:ℳℓn⟶ℳℓ, and a tag space.(ii)
id,sk,pk←SGenpp: each signer Pi will execute this algorithm on public parameter set pp to output a signer key, including an identifier id, a private key sk, and a public key pk.(iii)
mk,aux←VGenpp: the receiver will execute this algorithm on public parameters pp to obtain an MAC key mk and an auxiliary information aux.(iv)
σ←Signsk,m⟶,μ: each signer will execute this algorithm to sign its input m⟶ as a signature σ, which will be sent to the aggregator. For all the signers P1,…,Pn, we denote their signatures as σ⟶=σ1,…,σn.(v)
b←Verifypk,m⟶,μ,σ: any entity with m⟶ can verify the validation of a signature σ with the algorithm and outputs a bit b←0,1.(vi)
rki←SRGenski,aux: each signer will generate a re-encryption key rki with the algorithm.(vii)
aki←VRGenpki,mk,rki: with this algorithm, an aggregation key aki can be generated by the receiver, which will be sent to the aggregator.(viii)
Λ←Aggak⟶,σ⟶,μ,f: the aggregator will generate the aggregate authenticated message vector Λ by the algorithm. Let ak⟶=ak1,…,akn.(ix)
m⟶,μ/⊥,⊥←AVerifymk,Λ,ID,f: the receiver will generate a pair m⟶,μ with the algorithm and otherwise output ⊥,⊥ showing that the aggregator tries to cheat.
Required by [3], an HPRA scheme is required to be correct, input private, signer unforgeable, and aggregator unforgeable.
The correctness of an HPRA should meet the requirement that if all the involving algorithms are honestly executed, the aggregate authenticated message vectorΛ will always pass the verification and extract the real result of evaluation m⟶=fm⟶1,m⟶2,…,m⟶n.
The input privacy of HPRA should meet the requirement that an aggregate authenticated message vectorΛ should not leak any more information of the signers’ data m⟶1,m⟶2,…,m⟶n compared with what can be directly speculated from f and the real result of evaluation m⟶.Figure 2
Homomorphic proxy re-authenticator model.Definition 6.
(input privacy). The HPRA schemeΣ for ℱ is input private if for any κ∈ℕ, any f∈ℱ, all tags μ, and all m1=m⟶11,…,m⟶n1∈ℳℓn and m2=m⟶12,…,m⟶n2∈ℳℓn with fm⟶11,…,m⟶n1=fm⟶12,…,m⟶n2, all pp←Gen1κ,ℓ, all mk,aux←VGenpp, for i=1,…,n, ski,pki←SGenpp, rki←SRGenski,aux, and aki←VRGenpki,mk,rki. We denote QUOTE sk⟶=sk1,…sknsk⟶=sk1,…skn. The following distributions are identical:(2)Aggak⟶,Signsk⟶,m1,μ,μ,f,Aggak⟶,Signsk⟶,m2,μ,μ,f.
The signer unforgeability of an HPRA requires that if the aggregator always remains honest, no coalition of dishonest signers can produce a validΛ with respect to the function f∈ℱ such that Λ is outside of the range of f evaluated on arbitrary combinations of the actually signed vectors. The aggregator unforgeability is the natural counterpart of signer unforgeability; if the signers always remain honest, malicious aggregator cannot output a valid aggregate authenticated message vector with respect to the function f, such that the aggregate authenticated message vector is out of the range of f evaluated on the virtually signed vectors.
LetT represent “Signer” or “Aggregator.” In both definitions, the adversary gains access to a set OT of oracles, where OT≔SG,SKey,SR,VR,A for T = “Signer” and OT≔SG,Sig,SR,VR,VRKey for T = “Aggregator.” The oracles maintain some sets S, AK, RK, and SIG which are initially empty and work as follows, let i=1,…,n represents the index of client Pi, and we do not consider the corruption between the signers:(i)
SGi: works as SGen, sets Si←id,sk,pk and returns id,pk.(ii)
Skeyi: returns Si.(iii)
Sig1,…,n,m: works as Sign, sets SIGμ←SIGμ∪m⟶i,Si for i=1,…,n, returns σ⟶=σ1…σn and μ. Let m=m⟶1,…,m⟶n.(iv)
SRi: works as SRGen, returns RKi=rki.(v)
VRi: works as VRGen but without returning anything, sets AKi=aki.(vi)
VRKeyi: returns AKi.(vii)
Aσ⟶,1,…,n,μ,f: works as Agg, returns Λ.Definition 7.
(T-unforgeability). For the HPRA scheme Σ, consider an experiment ExpAT−unforgeΣ,κ,n,l with regard to a PPT adversary A: Public parameter pp is generated by running Gen1κ,ℓ; the MAC key and the auxiliary information mk,aux are generated by running VGenpp. A is given inputs pp and aux and access to oracle OT and outputs a forge Λ⋆,ID⋆,f⋆. The challenger carries out AVerifymk,Λ⋆,ID⋆,f⋆ and obtains m⟶,μ; if m⟶,μ≠⊥,⊥ and ∄m:∀i∈n:m⟶i,id∗∈SIGμ∧f⋆m⟶1…,m⟶n=m⟶, it outputs 1 and otherwise outputs 0. The HPRA scheme Σ is T-unforgeable; if for all PPT adversaries A, there is a negligible function negl⋅ such that PrExpAT−unforgeΣ,κ,n,ℓ=1≤neglκ.
There is an optional property for HPRA and output privacy, which simulates the situation that the aggregator learns nothing about either the inputs or the function’s output. In order to formally give a definition of output privacy, we define an oracleRoS as follows:(i)
RoSi,m,b: If Si=⊥, it returns ⊥. Otherwise, it samples μ uniformly at random, and if b=0, for i=1,…,n, it computes σi←SignSi2,m⟶i,μ. Else, it randomly chooses r⟶=r1,…,rn←ℳℓn, and for i=1,…,n, it computes σi←SignSi2,r⟶i,μ and returns σ⟶=σ1,…,σn.Definition 8.
(output privacy). For the HPRA schemeΣ, assuming an experiment ExpAoutprivΣ,κ,n,ℓ with a PPT adversaries A: public parameter pp is gained by executing Gen1κ,ℓ, the MAC key, and the auxiliary information mk,aux are gained by executing VGenpp. A is given input pp and access to oracle O. A random bit b←0,1 is chosen by the challenger, and a challenge ciphertext σ⟶ is computed and given to A. A continues to have oracle access to QUOTE O≔SG,SKey,RoSb,SR,VR,VRKeyO≔SG,SKey,RoSb,SR,VR,VRKey and outputs a guess b′ of b.
An HPRA for a family of function classesℱ is output private; if for all PPT adversaries A, there is a negligible function negl⋅ such that PrExpAoutprivΣ,κ,n,ℓ=1≤1/2+neglκ.


## 3. The HPRA to MVC Transform

Following the definition in Section2, some similarities between the two models are figured out through observation: (1) the clients in MVC and signers in HPRA play similar roles in providing inputs; (2) the server in MVC and the aggregator in HPRA play similar roles in computing an encoded output with a corresponding proof; (3) the first client in MVC and the receiver in HPRA play similar roles in extracting the evaluation result and verifying its correctness. A very straightforward idea is that we can achieve the goal of transforming HPRA to MVC by constructing a mapping of the participants in the two schemes as follows, which can be depicted in Figure 3: (1) let the aggregator in HPRA take over the work of the server in MVC; (2) merge the receiver with the first signer in HPRA, and let this merged participant take over the work of the first client in MVC; (3) let each of the rest signers play a different client in MVC.Figure 3
Idea of transform.LetΣ=Gen,SGen,VGen,Sign,Verify,SRGen,VRGen,Agg,AVerify⊲ be an HPRA scheme for a function family ℱ. The general transform from Σ to Π=KeyGenjj=1n,EnFunc,EnInputjj=1n,EnInputjj=1n,Compute,Verify, an MVC scheme for ℱ, will be explained in elaborate as follows. Let pp←Σ.Gen1κ,ℓ be a set of public parameters. In the proposed MVC scheme, we consider the computation of a function f on inputting x⟶1i,…,x⟶ni, where x⟶ji∈ℳℓ is a vector over a finite field of each client Pj.(i)
pk1,sk1←KeyGen1pp. On inputting public parameter pp, client P1 executes HPRA’s signer’s key generation algorithm Σ.SGenpp and obtains an identifier id1 and a public/private key pair sk1,pk1. Client P1 runs receiver’s key generation algorithm. Σ.VGenpp gets an MAC key mk and auxiliary information aux. On private key sk1 and auxiliary information aux, client P1 executes signer’s re-encryption key generation algorithm Σ.SRGensk1,aux, and obtains re-encryption key rk1. Client P1 sets pk1=id1,pk1,aux,rk1, sk1=sk1,mk.(ii)
pkj,skj←KeyGenjpp,pk1. On inputting public parameter pp and client P1’s public key pk1, for j=2,…,n, each client Pj executes HPRA’s signer’s key generation algorithm Σ.SGenpp and obtains an identifier idj and a public/private key pair skj,pkj. On inputting private key skj and auxiliary information aux, client Pj executes signer’s re-key generation algorithm Σ.SRGenskj,aux and obtains a re-encryption key rkj. Client Pj individually sets pkj=idj,pkj,rkj, skj=skj.(iii)
ϕ,ξ←EnFuncpk⟶,sk1,f. For j=1…n, takes a public key pkj and the private key sk1 of client P1, client P1 executes Σ.VRGenpkj,mk,rkj and obtains an aggregation key akj. Client P1 sets the encoded function ϕ=f,ak⟶ and the decoding secret ξ=∅.(iv)
χ1i,τi←EnInput1i,pk⟶,sk1,ξ,x⟶1i. When out sourcing the i-th computation to the server, it takes a time period i, the public keys pk⟶, the private key sk1 of client P1, an input message vector x⟶1i, the decoding secret ξ, the first client P1 gets a tag μ∈G, executes the sign algorithm Σ.Signsk1,x⟶1i,μ, gets a signature σ1, and sets χ1i=σ1, τi=mk.(v)
χji←EnInputji,pk⟶,skj,x⟶ji. When outsourcing the i-th computation to the server, each client Pj takes a time period i, the public keys pk⟶, the signer secret key skj of client Pj, and input message vector x⟶ji; Pj (with j≠1) obtains a tag μ∈G, and then he executes the algorithm Σ.Signskj,x⟶ji,μ, gets signature σj, and sets χji=σj.(vi)
ωi←Computei,pk⟶,ϕ,χ⟶i. Given the public keys pk⟶, the encoded function ϕ, and the encoded inputs χ⟶i, the server executes the algorithm Σ.Aggak⟶,χ⟶i,μ,ϕ, gets aggregate authenticated message vector Λ, and sets ωi=Λ.(vii)
yi∪⊥←Verifyi,pk⟶,ξ,τi,ωi. Take the public keys pk⟶, the decoding secrets ξ,τi, and an encoded output ωi as inputs, and the first client P1 executes the receiver’s verification algorithm Σ.AVerifymk,Λ,ID,f which outputs pair of message vector and tag m⟶,μ, on success, and ⊥,⊥ otherwise. Set yi=m⟶ and otherwise return ⊥ informing that the server tries to cheat.SchemeΠ should satisfy the properties of correctness, soundness, and privacy. While the correctness is quite obvious, we start with soundness.Theorem 1.
(soundness). IfΣ is a T-unforgeable HPRA scheme, where T = “Aggregator,” then Π described above is a sound MVC scheme.Proof.
This study demonstrates that if there is a probabilistic polynomial-time (PPT) adversaryA for which break soundness (Definition 2) of Π and let PrExpAsoundΠ,f,κ,n=1≥non−neglκ. A PPT adversary ℬ can be constructed that breaks the T-unforgeability (Definition 7) of Σ for T = “Aggregator.” ℬ is given inputs 1κ,n,ℓ and an oracle OT≔SG,Sig,SR,VR,VRKey, and its goal is to output a forge that can successfully convince the challenger. In detail, the following holds:ExperimentExpℬT−unforgeΣ,κ,n,ℓ:(1)
The challenger executespp←Gen1κ,ℓ, mk,aux←VGenpp and sends pp and aux to ℬ.(2)
Forj=1,…n, ℬ queries the following oracles and obtains idj,pkj←SGj, rkj←SRj; ℬ also queries the oracle VRj to produce akj and queries akj←VRKeyj.(3)
ℬ then sets pk1=id1,pk1,aux,rk1; for j=2…n, pkj=idj,pkj,rkj, ϕ=f,ak, and sends them to A. Let f be the function on which A can break MVC soundness.(4)
ℬ initializes a counter i≔0.(5)
WheneverA queries its encryption Oracle ℐN with inputs x⟶1,…,x⟶n, ℬ answers the queries as follows:(a)
Seti≔i+1.(b)
Recordx⟶1i,…,x⟶ni≔x⟶1,…,x⟶n.(c)
Query and getσji,μ←Sig1,…,n,xi. Let xi=x⟶1i,…,x⟶ni, and denote σ⟶i=σ1i,…,σni.(d)
Set and returnχ⟶i≔σ⟶i.(6)
WhenA outputs ω⋆, ℬ sets Λ⋆≔ω⋆ and sends Λ⋆,ID⋆,f⋆ to the challenger, where ID⋆≔id1,…,idn, f⋆=f.(7)
The challenger executes the algorithmAVerifymk,Λ⋆,ID⋆,f⋆.(8)
Ifm⟶,μ≠⊥,⊥ and ∄x:∀j∈n:x⟶j,id⋆∈SIGμ∧f⋆x⟶1…,x⟶n=m⟶ (i.e., 1. f⋆x⟶1,…,x⟶n=m⟶, and at least one x⟶j has not been queried by A in the i-th query or 2. f⋆x⟶1,…,x⟶n≠m⟶) outputs 1 and otherwise outputs 0.
A PPT adversaryA will find a ω⋆ such that the challenger gets y∗∉⊥,fx⟶1i,…,x⟶ni when running Verify if A is considered to be able to break Π with non-neglκ As Π.Verify in our transform directly calls Σ.AVerify, if such a ω∗ is produced, ℬ can directly consider ω∗ as an input of Σ.AVerify. Clearly, if A can cheat Π.Verify and make ExpAsoundΠ,f,κ,n=1, ℬ can definitely also fool Σ.AVerify and let ExpℬT−unforgeΣ,κ,n,ℓ equal to 1. Then, we successfully construct such an adversary ℬ who breaks T-unforgeability when T = “Aggregator” with non-neglκ: PrExpℬT−unforgeΣ,κ,n,ℓ=1≥PrExpAsoundΠ,f∗,κ,n=1≥non−neglκ.
However, it has been proved thatΣ is a T-unforgeable HPRA [3], which contradicts our derivation; that is, soundness is guaranteed in MVC based on the T-unforgeability of HPRA.Theorem 2.
(privacy against the first client). IfΣ is an input private HPRA scheme, then Π is an MVC scheme with the privacy against the first client.Proof.
The privacy against the first client (Definition3) can be directly derived from the input privacy of HPRA. Recall Definition 6, an HPRA Π scheme is called input private if for all m⟶11,…,m⟶n1 and m⟶12,…,m⟶n2, where fm⟶11,…,m⟶n1=fm⟶12,…,m⟶n2, and the following distributions are identical:(3)Λ1←Π.Aggak⟶,σ⟶1,μ,f,Λ2←Π.Aggak⟶,σ⟶2,μ,f,where σ⟶1 is the signatures of m⟶11,…,m⟶n1 from Σ.Sign and σ⟶2 is the signatures of m⟶12,…,m⟶n2 from Σ.Sign.
Recall Definition3; an MVC scheme Σ is called privacy against the first client if the view of the first client when executing Σ with clients holding inputs x⟶1,x⟶2,…,x⟶n is distributed identically from the view of the first client when running Σ with clients holding inputs x⟶1,x⟶2′,…,x⟶n′.
Since the first clientP1 has no other opportunity to access information from all other entities when performing Σ, except when running the algorithm Verify: P1 obtains an encoded output ωi, which may reveal some information. As a result, it is only necessary to prove that the distributions below are identical:(4)ωi⟵Σ.Computei,pk⟶j,ϕ,χ⟶i,ω′i⟵Σ.Computei,pk⟶j,ϕ,χ⟶′i.
Letχ⟶i be the encoded inputs of x⟶1,x⟶2,…,x⟶n, generated by Π.EnInput1 and Π.EnInputj. And let χ⟶′i be the encoded inputs of x⟶1,x⟶2′,…,x⟶n′, generated by Π.EnInput1 and Π.EnInputj. Without loss of generality, we set x⟶1,x⟶2,…,x⟶n and x⟶1,x⟶2′,…,x⟶n′, be any two vectors with the same first component such that fx⟶1,x⟶2,x⟶1,x⟶2′,…,x⟶n′ at the same time. Intuitively speaking, both Π.EnInput1 and Π.EnInputj directly call the algorithm Σ.Sign, except that Π.EnInput1 returns mk additionally; in other words, χ⟶i=σ⟶1 and χ⟶′i=σ⟶2. Furthermore, Π.Compute calls Σ.Agg, and ωi and ω′i are calculated exactly in the same way as in the definition of input privacy of HPRA, i.e., ωi=Λ1 and ω′i=Λ2. Because of the input privacy of HPRA, ωi and ω′i are identical. As a result, privacy against the first client of MVC scheme Σ is guaranteed.Theorem 3.
(privacy against the server). IfΣ is an output private HPRA scheme, then Π will be an MVC scheme with the privacy against the server property.Proof.
If there is a PPT adversaryA for which privacy against the server of Π (Definition 4) on function f does not hold, then a PPT adversary ℬ that breaks the output privacy of Σ (Definition 8) can be constructed. ℬ is given inputs 1κ,n,ℓ and access to an oracle O≔SG,SKey,RoSb,SR,VR,VRKey. We follow the assumption of MVC that all the clients are honest but curious, and we do not consider corrupted client situation. In detail, the following holds:(i)
ExperimentExpℬoutprivΣ,κ,n,ℓ:(1)
The challenger carries outpp←Gen1κ,ℓ, mk,aux←VGenpp and selects a random bit b←0,1 and then returns pp and aux to ℬ.(2)
Forj=1,…,n, ℬ queries the oracles and obtains idj,pkj←SGj, rkj←SRj. ℬ also queries the oracle VRj to yield akj, and queries akj←VRKeyj.(3)
ℬ then sets pk1=id1,pk1,aux,rk1, for j=2,…,n, pkj=idj,pkj,rkj, ϕ=f,ak⟶, and sends them to A. Let f be the function on which A can break the MVC soundness.(4)
ℬ initializes a counter i≔0.(5)
WhenA queries the encryption oracle ℐN with inputs x⟶1,…,x⟶n, ℬ answers the queries as follows:(a)
Seti≔i+1.(b)
Recordx⟶1i,…,x⟶ni≔x⟶1,…,x⟶n.(c)
Query the oracle and obtainσ⟶i,μ←Sig1,…,n,x⟶jij∈n.(d)
Letχ⟶i≔σ⟶i and return χ⟶i to A.(ii)
WhenA outputs x0=x⟶10,…,x⟶n0, x1=x⟶11,…,x⟶n1, ℬ picks a random bit b0←0,1 and works as follows:QueriesRoSj,xb0,b and gets σ1b0,c1b0,…,σnb0,cnb0.Returns the challenge ciphertextχ⟶b0≔σ⟶b0 to A.(iii)
WhileA gives a bit b1 to ℬ, ℬ outputs 1, if b0=b1; otherwise, ℬ outputs 0.
Intuitively speaking, whenb0=b1, A outputs a successful guess b′=b of which one of the inputs x0,x1 is signed, then ℬ guesses that its challenge string given by RoSb must be a signature and outputs a guess b′=1 of b. Otherwise, while if A does not succeed, ℬ guesses that its challenge string given by RoSb must be random and generates a guess bit b′=0 of b. When the privacy against the server (Definition 3) of Π against A does not hold, we have(5)AdvAprivΠ,f,κ,n=PrExpAprivΠ,f,κ,n,0=1−PrExpAprivΠ,f,κ,n,1=1≥non−neglκ.
Without loss of generality, letPrExpAprivΠ,f,κ,n,1=1 be bigger than PrExpAprivΠ,f,κ,n,0=1.
Asxb0=x⟶1b0,…,x⟶nb0 is encrypted by RoSb when b=0, then the view of A when runs as a subroutine by ℬ is indistinguishable to the view of A in experiment ExpAprivΠ,f,κ,n,b0. As a result,(6)PrExpℬoutprivΣ,κ,n,ℓ=1|b=0=Prb0=0−Prb0=0⋅PrExpAprivΠ,f,κ,n,0=1+Prb0=1⋅PrExpAprivΠ,f,κ,n,1=1.
Becauseb0 is randomly picked by ℬ, Prb0=0=Prb0=1=1/2, we have(7)PrExpℬoutprivΣ,κ,n,ℓ=1|b=0≥12+12⋅non−neglκ.
A string of random numbers is encrypted byRoSb when b=1, then the view of A when runs as a subroutine by ℬ is indistinguishable to the view of A in an experiment of guessing random numbers. Thus,(8)PrExpℬoutprivΣ,κ,n,ℓ=1|b=1=12.
Considering the above two equations, because the challenger choosesb randomly, Prb=0=Prb=1=1/2, if adversary A can break the privacy against the server and ℬ can determine whether its challenge string is a true signature or a random string with probability:(9)PrExpℬoutprivΣ,κ,n,ℓ=1=12⋅Prb′=1|b=0+12⋅Prb′=1|b=1≥12+14⋅non−neglκ.
But the output privacy has been confirmed [3], which leads to a contradiction. In other words, privacy against the server is guaranteed in our MVC scheme based on the output privacy of HPRA.


## 4. A Concrete Instantiation

To explain our transform in more detailed way, we give a concrete instantiation. Essentially, we build an MVC for the family of linear functionF over Zq based on a concrete HPRA scheme 4 in [3].


### 4.1. Bilinear Map

LetG1=g1, G2=g2, and GT=g be cyclic groups of prime order q. Let g1,g2 be generators of groups G1 and G2, respectively, and a paring e:G1×G2⟶GT is a bilinear map if the following features hold:(i)
Bilinearity:eua,vb=eu,vab for any u∈G1,v∈G2 and a,b∈Zq.(ii)
Nondegeneracy:eg1,g2≠1GT.(iii)
Computability: there is an efficient algorithm to computeeu,v for any inputs u∈G1, v∈G2.For simplicity, assuming there is a symmetric bilinear map such thatG1=G2=g. Let BG←BGGen1κ be a bilinear group generation algorithm, and the output BG is the generator g,g of G and GT with a bilinear pairing e: G×G⟶GT.


### 4.2. Overview of a Detailed HPRA Scheme

Scheme 4 in [3] is said to be an input private, T-unforgeable, and output private HPRA scheme. They allow the signer to report an encrypted data with its signature under their own keys; the aggregator re-encrypts the ciphertexts and converts them to the ciphertexts under the receiver’s key and homomorphically evaluates the function f on ciphertexts.For more details, to achieve the output privacy and the homomorphism, they employ an ElGamal-like encryption scheme: encode messagex∈Zq into the exponent and encrypt gx. One can decrypt and get x′=gx and then additionally compute x=loggx′ to obtain x, with size of the message space being polynomial in security parameter κ. As one can verify the guesses for signed messages using solely the signatures, they blind signer Pj’s signature with a random element grj. Unfortunately, because of some flaws in this scheme, even if the aggregator performs honestly, the evaluation result still cannot pass AVerify; that is, the Scheme 4 in [3] is not a correct HPRA scheme.We slightly modified Scheme 4 in [3] and turned it into a correct HPRA scheme: we blinded the input od signer Pj with a random element grj instead of blinding signer of Pj with a random element grj and prevented verifying guesses for signed messages as well. It has been proven that the revised HPRA scheme still maintains input privacy, T-unforgeability, and output privacy (see Appendix A for more details of the origin scheme 4 in [3] and how we revised it; Appendix B gives the security proof).


### 4.3. The Construction

We describen clients where each client Pj holds an ℓ-length input x⟶j=x⟶j1,…,x⟶jℓ∈Zqℓ and a tag μ∈G which is related to the set of inputs. Here, f is a linear function represented by its coefficient q1,…,qn. It is worth noting that when the inputs of f are vectors, e.g., given nℓ-length input vectors x⟶1,…,x⟶ℓ, we define f as a function calculated column by column, that is,(10)fx⟶1,…,x⟶n≔∑j=1nx⟶j1⋅qj,…,∑j=1nx⟶jℓ⋅qj.An additional symbol is placed at the end of the ciphertext to indicate the state of the ciphertext: “1” stands for first-level ciphertext, which is not allowed to re-encrypt, “2” stands for second-level ciphertext, which is allowed to be re-encrypted, and “R” means that this ciphertext has already been re-encrypted. In this instantiation, we describe the process for one time period i to simplify.We fix a hash functionH: G×G⟶G, which can later be used as a public random oracle. We also choose g⟶=g1,…,gℓ←Gℓ and publish the public parameter pp←BG,H,g⟶,ℓ:(1)
pk1,sk1←KeyGen1pp.(a)
On inputting public parameterpp, client P1 randomly chooses a vector a⟶1=a⟶11,…,a⟶1ℓ+1←RZqℓ+1, and β1←RZq yields an identifier and a public/private key pair set:(11)id1=g1/β1,pk1=ga⟶11,…,ga⟶1ℓ+1,gβ1,g1/β1,pp,sk1=a⟶1,β1.(b)
The first clientP1 randomly chooses α←RZq, b⟶=b1,…,bℓ+1←RZqℓ+1 and obtains an MAC key mk and the auxiliary information aux:(12)mk=α,b⟶,aux=gb1,…,gbℓ+1.(c)
ClientP1 obtains the re-encryption key rk1=gb1a⟶11,…,gbℓ+1a⟶1ℓ+1.(d)
ClientP1 sets and outputs:(13)pk1=id1,pk1,aux,rk1,sk1=sk1,mk.(2)
pkj,skj←KeyGenjpp,pk1.(a)
On inputting public parameterpp, client Pj randomly chooses a⟶j=a⟶j1,…,a⟶jℓ+1←RZql+1, and βj←RZq produces an identifier and a public/private key pair set:(14)idj=g1/βj,pkj=ga⟶j1,⋯,ga⟶jℓ+1,gβj,g1/βj,pp,skj=a⟶j,βj.(b)
Forj=2,…,n, client Pj obtains the re-encryption key rkj=gb1a⟶j1,…,gbℓ+1a⟶jℓ+1.(c)
ClientPj sets and outputs:(15)pkj=idj,pkj,rkj,skj=skj.(3)
ϕ,ξ←EnFuncpk⟶,sk1,f.(a)
On inputtingpk⟶, public parameter pp, MAC key mk, and function f, for j=1,…,n, client P1 obtains aggregation key akj=g1/βjα.(b)
P1 sets and outputs:(16)ϕ=f,ak,ξ=∅.(4)
χ1,τ←EnInput1pk⟶,sk1,ξ,x⟶1. Client P1 randomly chooses μ∈G, parses sk1 as sk1,mk, parses pk1 as id1,pk1,⋅,⋅, and randomly chooses r1,k1←RZq2.(a)
ClientP1 computes σ1′:(17)σ1′=Hμid1⋅∏t=1ℓgtx⟶1t⋅gr1β1.(b)
ClientP1 computes the encryption x⟶1 which consists of ℓ+3 components, denoted as c⟶1=c⟶11,…,c⟶1ℓ+3.The first component:(18)c⟶11=gk1.The following componentsc⟶12 to c⟶1ℓ+1 are x⟶1 covered by pk1 and random number k1, such that for all t=2,…,ℓ+1:(19)c⟶1t=gx⟶1t−1⋅ga⟶1t−1k1.Theℓ+2-th component in c⟶1 contains the information of random number r1 instead of an element in x⟶1:(20)c⟶1ℓ+2=gr1⋅ga⟶1ℓ+1k1.ClientP1 sets the last component c⟶1ℓ+3=2, in order to remark the state of the cipher text: c⟶1 is a second-level ciphertext:(c)
Setsσ1=σ1',c⟶1 and outputs χ1,τ=σ1,mk.(5)
χj←EnInputjpk⟶,skj,x⟶j. For j=2,…,n, client Pj parses sk1 as sk1,⋅, parses pkj as idj,pkj,⋅, and randomly chooses rj,kj←RZq2.(a)
ClientPj computes:(21)σj′=Hμidj⋅∏t=1ℓgtx⟶jt⋅grjβj.(b)
ClientPj computes the encryption x⟶j which consists of ℓ+3 components, denoted as c⟶j=c⟶j1,…,c⟶jℓ+3.The first component:(22)c⟶j1=gkj.The following componentsc⟶j2 to c⟶jℓ+1 are information of x⟶j covered by pkj and a random number kj, such that for all t=2,…,ℓ+1:(23)c⟶jt=gx⟶jt−1⋅ga⟶jt−1kj.Theℓ+2-th component in c⟶j contains the information of a random number rj instead of x⟶j:(24)c⟶jℓ+2=grj⋅ga⟶jℓ+1kj.ClientPj sets the last component c⟶ℓ+3=2 to remark the state of the ciphertext: c⟶j is a second-level ciphertext.(c)
Setsσj=σj′,c⟶j, outputs χj,τ=σj,mk, and denotes χ⟶=χ1,…,χn.(6)
ω←Computepk⟶,ϕ,χ⟶. Parses χj as σj, parses pk1 as ⋅,⋅,⋅,rk1, parses pkj for j=2,…,n as ⋅,⋅,rkj, parses ϕ as f,ak⟶.(a)
Forj=1,…,n, the server computes a re-encryption of the client Pj’s ciphertext cj which consists of 2ℓ+3 components, denoted as c⟶j′=c⟶j′1,…,c⟶j′2ℓ+3.The server first calculates pairings betweenc⟶j1 and each component of rkj and set the 1-st to ℓ+1-th components to be the pairing result, that is, for all t=1,…,ℓ+1:(25)c⟶j′t=ec⟶j1,gbta⟶jt.Fort=ℓ+2,…,2ℓ+2, the server directly sets(26)c⟶j′t=c⟶jt−ℓ.Server setsc⟶j′ℓ+3=R to remark the state of the ciphertext, where the c⟶j′ is a re-encrypted ciphertext.(b)
After the server finished the above for eachc⟶j, where j=1,…,n, the server begins to evaluate the function f on these re-encrypt ciphertext, and the evaluation is denoted as c⟶′=c⟶′1,…,c⟶′2ℓ+3.Forj=1,…,n and t=1,…,2ℓ+2, the server calculates the qj-th power of c⟶j′t. Puts all these powered components together and considers it as an×2ℓ+2 matrix, and the server gets a 2ℓ+2-length vector by adding the n components of the matrix in each column such that for all t=1,…,2ℓ+2:(27)c⟶′t=∏j=1nc⟶j′tqj.The server sets the last componentc⟶′2ℓ+3=R in order to remark the state of the ciphertext, where the new vector denoted as c′ is a re-encrypted ciphertext.(c)
The server computesσ′ with ak, where(28)σ′=∏j=1neσj′qj,akj.(d)
The server sets and outputsω=c⟶′,σ′,μ.(7)
y⟶∪⊥←Verifypk⟶,ξ,τ,ω. Parses ω as c⟶′,σ′,μ, τ as mk, let y⟶=y1,y2,…,yℓ denote the result of fx⟶1,…,x⟶n evaluated by the server, and let r denote the random element evaluated by the server.(a)
If the last component ofc⟶′ is label “R,” the first client P1 decrypts and obtains and ⊥ otherwise. For t=1,…,ℓ, the server calculates gyt and gr as follows:(29)gyt=c⟶′t+1⋅c⟶′1−1/bt,gr=c⟶′ℓ+2⋅c⟶′1−1/bℓ+1.(b)
Solving the discrete log problem and returny⟶ if the following equation holds and ⊥ otherwise:(30)σ′⋅gr−α=∏j=1ngqj,Hμidj⋅e∏t=1ℓgtytgα.


### 4.4. Correctness

We now present the proof of the correctness, if the server runsCompute honestly, the result will pass Verify. We start with showing an honest server do return expected y⟶=fx⟶1,…,x⟶n, according to the equation (29), for t=0,…,ℓ:(31)gyt=∏j=1ngx⟶jt⋅ga⟶jtkjqj⋅egkj,gbta⟶jtqj−1/bt=∏j=1ngx⟶jtqj+a⟶jtkjqj−a⟶jtkjqj=∏j=1ngx⟶jtqj,and, for gr in equation (29), we can also do the same calculation as above and find gr=∏j=1ngrjqj.ClientP1 requires an alternative decryption strategy for the vector components gy1,…,gyℓ,gr, as r is uniformly chosen in Zq and can thus not be efficiently recovered, when decrypting the vector components gy1,…,gyℓ,gr, and client P1 cannot directly obtain the plaintext. Fortunately, obtaining r∈Zq is unnecessary, and it is sufficient to unblind the signature by gr (resp., gr). We now present the left side and the right side of the equation (30) always keeps equal as long as the server remains honest. Here, we re-emphasize that gt is randomly chosen from G and do not mix it up with the generator g of group GT The left-hand side of the equation (30) is equal to(32)LHS=∏j=1neσj′qj,akj⋅gr−α=∏j=1neHμjidj⋅∏t=1ℓgtx⟶jt⋅grjβjqj,gα/βj⋅g−αr=∏j=1neHμjidj⋅∏t=1ℓgtx⟶jtqj,gα,and the right-hand side of the equation (30) is equal to(33)RHS=∏j=1negqj,Hμjidj.e∏t=1ℓgt∑j=1nx⟶jt⋅qjgα=∏j=1negα,Hμjidjqj⋅∏j=1ne∏t=1ℓgtx⟶jt⋅qjgα=∏j=1neHμjidj⋅∏t=1ℓgtx⟶jtqj,gα.We can clearly find that the two sides of the equation (30) are equal and thus conclude that our detailed construction meets the correctness definition. Furthermore, following the security proof of general construction, the detailed construction is a sound, private against the first client, and private against server MVC scheme.


## 4.1. Bilinear Map

LetG1=g1, G2=g2, and GT=g be cyclic groups of prime order q. Let g1,g2 be generators of groups G1 and G2, respectively, and a paring e:G1×G2⟶GT is a bilinear map if the following features hold:(i)
Bilinearity:eua,vb=eu,vab for any u∈G1,v∈G2 and a,b∈Zq.(ii)
Nondegeneracy:eg1,g2≠1GT.(iii)
Computability: there is an efficient algorithm to computeeu,v for any inputs u∈G1, v∈G2.For simplicity, assuming there is a symmetric bilinear map such thatG1=G2=g. Let BG←BGGen1κ be a bilinear group generation algorithm, and the output BG is the generator g,g of G and GT with a bilinear pairing e: G×G⟶GT.


## 4.2. Overview of a Detailed HPRA Scheme

Scheme 4 in [3] is said to be an input private, T-unforgeable, and output private HPRA scheme. They allow the signer to report an encrypted data with its signature under their own keys; the aggregator re-encrypts the ciphertexts and converts them to the ciphertexts under the receiver’s key and homomorphically evaluates the function f on ciphertexts.For more details, to achieve the output privacy and the homomorphism, they employ an ElGamal-like encryption scheme: encode messagex∈Zq into the exponent and encrypt gx. One can decrypt and get x′=gx and then additionally compute x=loggx′ to obtain x, with size of the message space being polynomial in security parameter κ. As one can verify the guesses for signed messages using solely the signatures, they blind signer Pj’s signature with a random element grj. Unfortunately, because of some flaws in this scheme, even if the aggregator performs honestly, the evaluation result still cannot pass AVerify; that is, the Scheme 4 in [3] is not a correct HPRA scheme.We slightly modified Scheme 4 in [3] and turned it into a correct HPRA scheme: we blinded the input od signer Pj with a random element grj instead of blinding signer of Pj with a random element grj and prevented verifying guesses for signed messages as well. It has been proven that the revised HPRA scheme still maintains input privacy, T-unforgeability, and output privacy (see Appendix A for more details of the origin scheme 4 in [3] and how we revised it; Appendix B gives the security proof).


## 4.3. The Construction

We describen clients where each client Pj holds an ℓ-length input x⟶j=x⟶j1,…,x⟶jℓ∈Zqℓ and a tag μ∈G which is related to the set of inputs. Here, f is a linear function represented by its coefficient q1,…,qn. It is worth noting that when the inputs of f are vectors, e.g., given nℓ-length input vectors x⟶1,…,x⟶ℓ, we define f as a function calculated column by column, that is,(10)fx⟶1,…,x⟶n≔∑j=1nx⟶j1⋅qj,…,∑j=1nx⟶jℓ⋅qj.An additional symbol is placed at the end of the ciphertext to indicate the state of the ciphertext: “1” stands for first-level ciphertext, which is not allowed to re-encrypt, “2” stands for second-level ciphertext, which is allowed to be re-encrypted, and “R” means that this ciphertext has already been re-encrypted. In this instantiation, we describe the process for one time period i to simplify.We fix a hash functionH: G×G⟶G, which can later be used as a public random oracle. We also choose g⟶=g1,…,gℓ←Gℓ and publish the public parameter pp←BG,H,g⟶,ℓ:(1)
pk1,sk1←KeyGen1pp.(a)
On inputting public parameterpp, client P1 randomly chooses a vector a⟶1=a⟶11,…,a⟶1ℓ+1←RZqℓ+1, and β1←RZq yields an identifier and a public/private key pair set:(11)id1=g1/β1,pk1=ga⟶11,…,ga⟶1ℓ+1,gβ1,g1/β1,pp,sk1=a⟶1,β1.(b)
The first clientP1 randomly chooses α←RZq, b⟶=b1,…,bℓ+1←RZqℓ+1 and obtains an MAC key mk and the auxiliary information aux:(12)mk=α,b⟶,aux=gb1,…,gbℓ+1.(c)
ClientP1 obtains the re-encryption key rk1=gb1a⟶11,…,gbℓ+1a⟶1ℓ+1.(d)
ClientP1 sets and outputs:(13)pk1=id1,pk1,aux,rk1,sk1=sk1,mk.(2)
pkj,skj←KeyGenjpp,pk1.(a)
On inputting public parameterpp, client Pj randomly chooses a⟶j=a⟶j1,…,a⟶jℓ+1←RZql+1, and βj←RZq produces an identifier and a public/private key pair set:(14)idj=g1/βj,pkj=ga⟶j1,⋯,ga⟶jℓ+1,gβj,g1/βj,pp,skj=a⟶j,βj.(b)
Forj=2,…,n, client Pj obtains the re-encryption key rkj=gb1a⟶j1,…,gbℓ+1a⟶jℓ+1.(c)
ClientPj sets and outputs:(15)pkj=idj,pkj,rkj,skj=skj.(3)
ϕ,ξ←EnFuncpk⟶,sk1,f.(a)
On inputtingpk⟶, public parameter pp, MAC key mk, and function f, for j=1,…,n, client P1 obtains aggregation key akj=g1/βjα.(b)
P1 sets and outputs:(16)ϕ=f,ak,ξ=∅.(4)
χ1,τ←EnInput1pk⟶,sk1,ξ,x⟶1. Client P1 randomly chooses μ∈G, parses sk1 as sk1,mk, parses pk1 as id1,pk1,⋅,⋅, and randomly chooses r1,k1←RZq2.(a)
ClientP1 computes σ1′:(17)σ1′=Hμid1⋅∏t=1ℓgtx⟶1t⋅gr1β1.(b)
ClientP1 computes the encryption x⟶1 which consists of ℓ+3 components, denoted as c⟶1=c⟶11,…,c⟶1ℓ+3.The first component:(18)c⟶11=gk1.The following componentsc⟶12 to c⟶1ℓ+1 are x⟶1 covered by pk1 and random number k1, such that for all t=2,…,ℓ+1:(19)c⟶1t=gx⟶1t−1⋅ga⟶1t−1k1.Theℓ+2-th component in c⟶1 contains the information of random number r1 instead of an element in x⟶1:(20)c⟶1ℓ+2=gr1⋅ga⟶1ℓ+1k1.ClientP1 sets the last component c⟶1ℓ+3=2, in order to remark the state of the cipher text: c⟶1 is a second-level ciphertext:(c)
Setsσ1=σ1',c⟶1 and outputs χ1,τ=σ1,mk.(5)
χj←EnInputjpk⟶,skj,x⟶j. For j=2,…,n, client Pj parses sk1 as sk1,⋅, parses pkj as idj,pkj,⋅, and randomly chooses rj,kj←RZq2.(a)
ClientPj computes:(21)σj′=Hμidj⋅∏t=1ℓgtx⟶jt⋅grjβj.(b)
ClientPj computes the encryption x⟶j which consists of ℓ+3 components, denoted as c⟶j=c⟶j1,…,c⟶jℓ+3.The first component:(22)c⟶j1=gkj.The following componentsc⟶j2 to c⟶jℓ+1 are information of x⟶j covered by pkj and a random number kj, such that for all t=2,…,ℓ+1:(23)c⟶jt=gx⟶jt−1⋅ga⟶jt−1kj.Theℓ+2-th component in c⟶j contains the information of a random number rj instead of x⟶j:(24)c⟶jℓ+2=grj⋅ga⟶jℓ+1kj.ClientPj sets the last component c⟶ℓ+3=2 to remark the state of the ciphertext: c⟶j is a second-level ciphertext.(c)
Setsσj=σj′,c⟶j, outputs χj,τ=σj,mk, and denotes χ⟶=χ1,…,χn.(6)
ω←Computepk⟶,ϕ,χ⟶. Parses χj as σj, parses pk1 as ⋅,⋅,⋅,rk1, parses pkj for j=2,…,n as ⋅,⋅,rkj, parses ϕ as f,ak⟶.(a)
Forj=1,…,n, the server computes a re-encryption of the client Pj’s ciphertext cj which consists of 2ℓ+3 components, denoted as c⟶j′=c⟶j′1,…,c⟶j′2ℓ+3.The server first calculates pairings betweenc⟶j1 and each component of rkj and set the 1-st to ℓ+1-th components to be the pairing result, that is, for all t=1,…,ℓ+1:(25)c⟶j′t=ec⟶j1,gbta⟶jt.Fort=ℓ+2,…,2ℓ+2, the server directly sets(26)c⟶j′t=c⟶jt−ℓ.Server setsc⟶j′ℓ+3=R to remark the state of the ciphertext, where the c⟶j′ is a re-encrypted ciphertext.(b)
After the server finished the above for eachc⟶j, where j=1,…,n, the server begins to evaluate the function f on these re-encrypt ciphertext, and the evaluation is denoted as c⟶′=c⟶′1,…,c⟶′2ℓ+3.Forj=1,…,n and t=1,…,2ℓ+2, the server calculates the qj-th power of c⟶j′t. Puts all these powered components together and considers it as an×2ℓ+2 matrix, and the server gets a 2ℓ+2-length vector by adding the n components of the matrix in each column such that for all t=1,…,2ℓ+2:(27)c⟶′t=∏j=1nc⟶j′tqj.The server sets the last componentc⟶′2ℓ+3=R in order to remark the state of the ciphertext, where the new vector denoted as c′ is a re-encrypted ciphertext.(c)
The server computesσ′ with ak, where(28)σ′=∏j=1neσj′qj,akj.(d)
The server sets and outputsω=c⟶′,σ′,μ.(7)
y⟶∪⊥←Verifypk⟶,ξ,τ,ω. Parses ω as c⟶′,σ′,μ, τ as mk, let y⟶=y1,y2,…,yℓ denote the result of fx⟶1,…,x⟶n evaluated by the server, and let r denote the random element evaluated by the server.(a)
If the last component ofc⟶′ is label “R,” the first client P1 decrypts and obtains and ⊥ otherwise. For t=1,…,ℓ, the server calculates gyt and gr as follows:(29)gyt=c⟶′t+1⋅c⟶′1−1/bt,gr=c⟶′ℓ+2⋅c⟶′1−1/bℓ+1.(b)
Solving the discrete log problem and returny⟶ if the following equation holds and ⊥ otherwise:(30)σ′⋅gr−α=∏j=1ngqj,Hμidj⋅e∏t=1ℓgtytgα.


## 4.4. Correctness

We now present the proof of the correctness, if the server runsCompute honestly, the result will pass Verify. We start with showing an honest server do return expected y⟶=fx⟶1,…,x⟶n, according to the equation (29), for t=0,…,ℓ:(31)gyt=∏j=1ngx⟶jt⋅ga⟶jtkjqj⋅egkj,gbta⟶jtqj−1/bt=∏j=1ngx⟶jtqj+a⟶jtkjqj−a⟶jtkjqj=∏j=1ngx⟶jtqj,and, for gr in equation (29), we can also do the same calculation as above and find gr=∏j=1ngrjqj.ClientP1 requires an alternative decryption strategy for the vector components gy1,…,gyℓ,gr, as r is uniformly chosen in Zq and can thus not be efficiently recovered, when decrypting the vector components gy1,…,gyℓ,gr, and client P1 cannot directly obtain the plaintext. Fortunately, obtaining r∈Zq is unnecessary, and it is sufficient to unblind the signature by gr (resp., gr). We now present the left side and the right side of the equation (30) always keeps equal as long as the server remains honest. Here, we re-emphasize that gt is randomly chosen from G and do not mix it up with the generator g of group GT The left-hand side of the equation (30) is equal to(32)LHS=∏j=1neσj′qj,akj⋅gr−α=∏j=1neHμjidj⋅∏t=1ℓgtx⟶jt⋅grjβjqj,gα/βj⋅g−αr=∏j=1neHμjidj⋅∏t=1ℓgtx⟶jtqj,gα,and the right-hand side of the equation (30) is equal to(33)RHS=∏j=1negqj,Hμjidj.e∏t=1ℓgt∑j=1nx⟶jt⋅qjgα=∏j=1negα,Hμjidjqj⋅∏j=1ne∏t=1ℓgtx⟶jt⋅qjgα=∏j=1neHμjidj⋅∏t=1ℓgtx⟶jtqj,gα.We can clearly find that the two sides of the equation (30) are equal and thus conclude that our detailed construction meets the correctness definition. Furthermore, following the security proof of general construction, the detailed construction is a sound, private against the first client, and private against server MVC scheme.


## 5. Implementation

To measure the performance of our transform, we implement concrete instantiation described in Section5 and conduct a variant of experiments and focus on evaluating the performance overhead. All the experiments are run on a PC with an Intel Core i7-4790K CPU running at 3.60 GHz and 8 GB of RAM on ubuntu-16.04.1. The implementation is in C with the help of PBC (pairing-based cryptography) library, which is designed to be the backbone of implementations of pairing-based cryptosystems [22]. More specifically, we use the symmetric pairings constructed on the curve y2=x3+x over the field Fq for some prime q=3mod4 with q=512.


### 5.1. Client Computation

Following the theoretical analysis, the lengthℓ of the input vector, the maximum size xmax of the input vector element (any element in the input vector xj⟶i of client Pj is smaller than 2xmax), and the number of clients n in total largely influence the runtime of the algorithms. We give some notations for the basic cost units of our protocol: MulG/MulGT represents the runtime of a multiplication in G/GT. ExpG/ExpGT represents the runtime of an exponentiation in G/GT. PairG represents the runtime of a pairing in G. Log represents the runtime of solving a discrete log problem.Key generation. The key generation process includes both KeyGen1 and KeyGenj. We theoretically analyzed the computational performance of our key generation process, which is shown in Table 1. Figure 4 depicts the key generation process cost for our scheme, and we set the maximum size xmax of input vector element to a fixed size 20 bits and observe how the total number n and the length ℓ of the input vector affect the performance:(i)
Whenn remains constant, the runtime of the key generation process changes uniformly with respect to ℓ.(ii)
Whenℓ remains constant, the runtime of the key generation process changes uniformly with respect to n.(iii)
Compared ton, ℓ can determine the runtime to a greater extent.Function encoding. We did not conduct the experimental analysis of function encoding process which only contains EncFunc, and as shown in Table 1, the runtime changes uniformly with respect to the total number of the clients.Input encoding. We did not conduct the experimental analysis of clients’ encoding process which only contains EnInput, as shown in Table 1, and the runtime changes uniformly with respect to the length ℓ of the input vector.The algorithmVerify, involving computing discrete logarithm, is the only step in the verification process. Pollard’s kangaroo algorithm [29] is the known fastest algorithm to solve the discrete logarithm problem for a general elliptic curve, and the time complexity is Ox. x is the size of the input number of Pollard’s kangaroo algorithm, which is mainly determined by the maximum size xmax of input vector element. Based on the theoretical analysis in Table 1, we can find that the verification process requires a total of ℓ discrete logarithmic calculations. We fix n to 2 as it has relatively small influence on runtime, and the algorithm performance on different xmax and ℓ is given in Figure 5 with log2-type Y axis:(i)
Whenxmax remains constant, the runtime of verification process increases along with ℓ.(ii)
Whenℓ remains constant, the runtime of verification process increases along with xmax.(iii)
The increase inxmax has a greater impact on the runtime of verification process than the increase in ℓ.Table 1
Computational complexity of ourMVC
MulGExpGMulGTExpGTPairGLogKey generation02ℓ+n+40ℓ+100Function encoding0n0000Input encodingℓ+1ℓ+3ℓ2ℓ00Verification processℓ−1ℓ+nℓ+n+2ℓ+4ℓ+nℓServer computation0n2ℓ+3n−1+12ℓ+2nℓ+n+10Figure 4
Client’s key generation time.Figure 5
Client’s decryption time.Note that eachℓ discrete logarithm is computed separately; as a consequence, the ℓ computation can be parallelized and will greatly save the client’s runtime. However, as we assume that clients are usually devices with limited computing power, performing parallel computation is obviously against our assumptions, so we do not implement Verify algorithm in parallelized way.


### 5.2. Server Computation

As server only carries outCompute, the experiments of the server’s runtime focus on the parameters influence on the efficiency of Compute. We fix xmax to 20 bits for simplicity, and the results plotted in Figure 6 and Table 1 show the server’s runtime in relation to the total number n of the clients and the input vector length ℓ:(i)
Whenn is fixed, the server’s runtime increases along with the length ℓ.(ii)
Whenℓ is fixed, the server’s runtime increases along with total number n of the clients.Figure 6
Server’s runtime.


### 5.3. Analysis and Comparison

#### 5.3.1. Efficiency Analysis

The client computation overhead may be even higher than that of the server in some cases. According to both theoretical and experimental analyses, we show how to avoid these inefficiencies and under what circumstances an instance can be regarded as an efficient solution. Assume that the computational complexity of all group operations is constant and thatxmax+log2n−1 is the expected length of the evaluation results of the linear combinations of the n clients’ input vector with the maximum element size xmax. We hope that the runtime of any client in the scheme will be less than that of the server; however, client P1 runs most algorithms on the client side. Here, we denote the computational complexity of P1 as Tclient:(34)Tclient=12ℓ+5n+12+ℓxmax+log2n−1,Tclient≤7n+4n−1ℓ−1.By the above inequality, one can indicate that whenn becomes sufficiently large and xmax stays rather small, the runtime required on the server side will exceed the runtime required on the client side, and the gap will become more significant as n grows. Although the runtime of both sides is On, the coefficient of n on the server side is obviously larger and hence more sensitive to the increase in n. We fixed ℓ to 128 and let xmax be rather small, i.e., 20 bits. These theoretical analyses correspond well with the experimental results shown in Figure 7.Figure 7
Total runtime.


#### 5.3.2. Performance Relative to Prior Scheme

Parno et al. [4] built a model to estimate the performance of FHE + GC-based VC schemes according to the results for FHE [30]. Because of the similarities between FHE + GCs based VC and MVC, we can likewise use the method to estimate the performance of MVC.Parno et al. [4] used multiplication of two t×t matrices M1 and M2 as test application, and each component in M1 and M2 is at most 32 bits. As the multiplication of two t×t matrices can be viewed as t×t linear combinations of vectors with length t, we set both the clients’ number n and the length ℓ of the input vectors to t, and let the maximum size xmax of input vector elements equal to 32 bits in order to construct an MVC with the same computational scaling as above. We plot the time complexity for the verification process in Figure 8. Throughout the results, it can be observed that our scheme significantly improves performance and can be considered applicable in a practical setting.Figure 8
Comparison with [2].


## 5.1. Client Computation

Following the theoretical analysis, the lengthℓ of the input vector, the maximum size xmax of the input vector element (any element in the input vector xj⟶i of client Pj is smaller than 2xmax), and the number of clients n in total largely influence the runtime of the algorithms. We give some notations for the basic cost units of our protocol: MulG/MulGT represents the runtime of a multiplication in G/GT. ExpG/ExpGT represents the runtime of an exponentiation in G/GT. PairG represents the runtime of a pairing in G. Log represents the runtime of solving a discrete log problem.Key generation. The key generation process includes both KeyGen1 and KeyGenj. We theoretically analyzed the computational performance of our key generation process, which is shown in Table 1. Figure 4 depicts the key generation process cost for our scheme, and we set the maximum size xmax of input vector element to a fixed size 20 bits and observe how the total number n and the length ℓ of the input vector affect the performance:(i)
Whenn remains constant, the runtime of the key generation process changes uniformly with respect to ℓ.(ii)
Whenℓ remains constant, the runtime of the key generation process changes uniformly with respect to n.(iii)
Compared ton, ℓ can determine the runtime to a greater extent.Function encoding. We did not conduct the experimental analysis of function encoding process which only contains EncFunc, and as shown in Table 1, the runtime changes uniformly with respect to the total number of the clients.Input encoding. We did not conduct the experimental analysis of clients’ encoding process which only contains EnInput, as shown in Table 1, and the runtime changes uniformly with respect to the length ℓ of the input vector.The algorithmVerify, involving computing discrete logarithm, is the only step in the verification process. Pollard’s kangaroo algorithm [29] is the known fastest algorithm to solve the discrete logarithm problem for a general elliptic curve, and the time complexity is Ox. x is the size of the input number of Pollard’s kangaroo algorithm, which is mainly determined by the maximum size xmax of input vector element. Based on the theoretical analysis in Table 1, we can find that the verification process requires a total of ℓ discrete logarithmic calculations. We fix n to 2 as it has relatively small influence on runtime, and the algorithm performance on different xmax and ℓ is given in Figure 5 with log2-type Y axis:(i)
Whenxmax remains constant, the runtime of verification process increases along with ℓ.(ii)
Whenℓ remains constant, the runtime of verification process increases along with xmax.(iii)
The increase inxmax has a greater impact on the runtime of verification process than the increase in ℓ.Table 1
Computational complexity of ourMVC
MulGExpGMulGTExpGTPairGLogKey generation02ℓ+n+40ℓ+100Function encoding0n0000Input encodingℓ+1ℓ+3ℓ2ℓ00Verification processℓ−1ℓ+nℓ+n+2ℓ+4ℓ+nℓServer computation0n2ℓ+3n−1+12ℓ+2nℓ+n+10Figure 4
Client’s key generation time.Figure 5
Client’s decryption time.Note that eachℓ discrete logarithm is computed separately; as a consequence, the ℓ computation can be parallelized and will greatly save the client’s runtime. However, as we assume that clients are usually devices with limited computing power, performing parallel computation is obviously against our assumptions, so we do not implement Verify algorithm in parallelized way.


## 5.2. Server Computation

As server only carries outCompute, the experiments of the server’s runtime focus on the parameters influence on the efficiency of Compute. We fix xmax to 20 bits for simplicity, and the results plotted in Figure 6 and Table 1 show the server’s runtime in relation to the total number n of the clients and the input vector length ℓ:(i)
Whenn is fixed, the server’s runtime increases along with the length ℓ.(ii)
Whenℓ is fixed, the server’s runtime increases along with total number n of the clients.Figure 6
Server’s runtime.


## 5.3. Analysis and Comparison

### 5.3.1. Efficiency Analysis

The client computation overhead may be even higher than that of the server in some cases. According to both theoretical and experimental analyses, we show how to avoid these inefficiencies and under what circumstances an instance can be regarded as an efficient solution. Assume that the computational complexity of all group operations is constant and thatxmax+log2n−1 is the expected length of the evaluation results of the linear combinations of the n clients’ input vector with the maximum element size xmax. We hope that the runtime of any client in the scheme will be less than that of the server; however, client P1 runs most algorithms on the client side. Here, we denote the computational complexity of P1 as Tclient:(34)Tclient=12ℓ+5n+12+ℓxmax+log2n−1,Tclient≤7n+4n−1ℓ−1.By the above inequality, one can indicate that whenn becomes sufficiently large and xmax stays rather small, the runtime required on the server side will exceed the runtime required on the client side, and the gap will become more significant as n grows. Although the runtime of both sides is On, the coefficient of n on the server side is obviously larger and hence more sensitive to the increase in n. We fixed ℓ to 128 and let xmax be rather small, i.e., 20 bits. These theoretical analyses correspond well with the experimental results shown in Figure 7.Figure 7
Total runtime.


### 5.3.2. Performance Relative to Prior Scheme

Parno et al. [4] built a model to estimate the performance of FHE + GC-based VC schemes according to the results for FHE [30]. Because of the similarities between FHE + GCs based VC and MVC, we can likewise use the method to estimate the performance of MVC.Parno et al. [4] used multiplication of two t×t matrices M1 and M2 as test application, and each component in M1 and M2 is at most 32 bits. As the multiplication of two t×t matrices can be viewed as t×t linear combinations of vectors with length t, we set both the clients’ number n and the length ℓ of the input vectors to t, and let the maximum size xmax of input vector elements equal to 32 bits in order to construct an MVC with the same computational scaling as above. We plot the time complexity for the verification process in Figure 8. Throughout the results, it can be observed that our scheme significantly improves performance and can be considered applicable in a practical setting.Figure 8
Comparison with [2].


## 5.3.1. Efficiency Analysis

The client computation overhead may be even higher than that of the server in some cases. According to both theoretical and experimental analyses, we show how to avoid these inefficiencies and under what circumstances an instance can be regarded as an efficient solution. Assume that the computational complexity of all group operations is constant and thatxmax+log2n−1 is the expected length of the evaluation results of the linear combinations of the n clients’ input vector with the maximum element size xmax. We hope that the runtime of any client in the scheme will be less than that of the server; however, client P1 runs most algorithms on the client side. Here, we denote the computational complexity of P1 as Tclient:(34)Tclient=12ℓ+5n+12+ℓxmax+log2n−1,Tclient≤7n+4n−1ℓ−1.By the above inequality, one can indicate that whenn becomes sufficiently large and xmax stays rather small, the runtime required on the server side will exceed the runtime required on the client side, and the gap will become more significant as n grows. Although the runtime of both sides is On, the coefficient of n on the server side is obviously larger and hence more sensitive to the increase in n. We fixed ℓ to 128 and let xmax be rather small, i.e., 20 bits. These theoretical analyses correspond well with the experimental results shown in Figure 7.Figure 7
Total runtime.


## 5.3.2. Performance Relative to Prior Scheme

Parno et al. [4] built a model to estimate the performance of FHE + GC-based VC schemes according to the results for FHE [30]. Because of the similarities between FHE + GCs based VC and MVC, we can likewise use the method to estimate the performance of MVC.Parno et al. [4] used multiplication of two t×t matrices M1 and M2 as test application, and each component in M1 and M2 is at most 32 bits. As the multiplication of two t×t matrices can be viewed as t×t linear combinations of vectors with length t, we set both the clients’ number n and the length ℓ of the input vectors to t, and let the maximum size xmax of input vector elements equal to 32 bits in order to construct an MVC with the same computational scaling as above. We plot the time complexity for the verification process in Figure 8. Throughout the results, it can be observed that our scheme significantly improves performance and can be considered applicable in a practical setting.Figure 8
Comparison with [2].


## 6. Conclusions

We combined MVC with an efficient cryptographic protocol HPRA by providing a general transform. We also gave and implemented a concrete instantiation of MVC scheme for outsourcing the linear combinations of vectors over a finite field. The instantiation and implementation could give the way for the future research on the designs and optimizations of outsourcing computation. Our implementation requires solving discrete logarithm problem. How to avoid the usage of these expensive operations is an open question for further research.



---

*Source: 6612614-2021-02-17.xml*