# PMDP: A Framework for Preserving Multiparty Data Privacy in Cloud Computing

Authors: Ji Li; Jianghong Wei; Wenfen Liu; Xuexian Hu
Journal: Security and Communication Networks
 (2017)

---

## Abstract

The amount of Internet data is significantly increasing due to the development of network technology, inducing the appearance of big data. Experiments have shown that deep mining and analysis on large datasets would introduce great benefits. Although cloud computing supports data analysis in an outsourced and cost-effective way, it brings serious privacy issues when sending the original data to cloud servers. Meanwhile, the returned analysis result suffers from malicious inference attacks and also discloses user privacy. In this paper, to conquer the above privacy issues, we propose a general framework forPreservingMultipartyDataPrivacy (PMDP for short) in cloud computing. ThePMDP framework can protect numeric data computing and publishing with the assistance of untrusted cloud servers and achieve delegation of storage simultaneously. Our framework is built upon several cryptography primitives (e.g., secure multiparty computation) and differential privacy mechanism, which guarantees its security against semihonest participants without collusion. We further instantiatePMDP with specific algorithms and demonstrate its security, efficiency, and advantages by presenting security analysis and performance discussion. Moreover, we propose a security enhanced frameworksPMDP to resist malicious inside participants and outside adversaries. We illustrate that bothPMDP andsPMDP are reliable and scale well and thus are desirable for practical applications.


---

## Body

## 1. Introduction

With the significantly increasing data size and the rapid development of the corresponding data analysis technology, the original data, which usually has characteristics of big volume, heterogeneity, and low quality, begins to play a very important role in various fields, such as healthcare, advertisement, government decision-making, and transportation. This is mainly because making deep mining and analysis over these large datasets (i.e., big data) would reveal some hidden and valuable information, and further produces great benefits. On the other hand, owing to the characters of big data and the pursuit of better outputs with more complex analysis, big data processing requires more computational overhead and resource expenditure, which challenges the traditional data processing model.Cloud computing provides a ubiquitous and on-demand approach of accessing a shared pool of configurable computing resources, which can be rapidly provisioned and released with minimal management effort [1]. Therefore, it gives a desirable platform for big data processing and enables users to outsource their computations to cloud servers with powerful computing capabilities sufficient for big data processing. To this end, users need to outsource their original data to cloud servers. However, this will bring serious security and privacy issues, especially when the data is sensitive for users. For exemplary purpose, we consider the following scenario.The mobile wearable device has been very popular in recent years. With a smart band on your wrist, you can not only collect your own health data like sleep time, heart rate. and motion trail, but also compare your quantity of motion with average level or other people’s level. In this case, the data containing your privacy is collected, aggregated, analyzed, and published by businesses with the assistance of cloud servers, which may result in privacy disclosure of users. Some related reports have been published (https://techcrunch.com/2016/11/03/fitbit-jawbone-garmin-and-mio-fitness-bands-criticized-for-privacy-failings/). Even worse, with the appearance of the sharing economy, user privacy issues become increasingly prominent. For instance, Uber, which brings convenience by providing car-ride service, is accused of allowing its employees to look through and gather users’ travel data and device information at will, and its application named God View has always been criticized since it can track users even after they get off the car (https://www.nbcnews.com/tech/tech-news/uber-fined-settlement-ny-over-god-view-tracking-n491706.).To guarantee data confidentiality and preserve user privacy, various security mechanisms have been developed and employed in each phase of the data life cycle, which roughly includes data storage, data processing, and data publishing (there also exist security issues in the process of data acquisition and data destruction, but they are out of the scope of this paper). For example, attribute-based encryption schemes [2, 3] are used to secure data storage in public cloud servers, secure multiparty computation schemes [4, 5] are introduced to protect data aggregation, and differential privacy mechanisms [6] provide a way to quantize the disclosed privacy in data publishing. In addition, we also note that there are several works proposed to protect data processing and data publishing by combining differential privacy with other cryptography primitives. However, there are few studies concerning the entire privacy preservation throughout the full life cycle of multiparty data, especially in the context of cloud computing. On the other hand, from a practical viewpoint, once the data privacy gets exposed in some phase of the data life cycle, the security mechanisms deployed in other phases would be useless. Therefore, it is necessary to conquer the privacy issues of big data in cloud computing from a global perspective.


### 1.1. Our Contribution

In this paper we propose a general framework for Preserving Multiparty Data Privacy (PMDP for short) in cloud computing, which provides complete protection throughout the entire life cycle of users’ data and is suitable for securing multiparty data aggregation and publication with the assistance of anuntrusted cloud server. Specifically, the contributions of this study can be summarized as follows:(1)
Based on well studied security mechanisms for preserving user privacy in the process of data storage, processing, and publishing, respectively, we combine these techniques in a nontrivial and tight manner and propose thePMDP framework that covers the full lifecycle of multiple users’ data.(2)
We present the principles of choosing the building security mechanisms involved in thePMDP framework and a specific instance. Furthermore, to illustrate the advantage and practicability of thePMDP framework, we evaluate the performance of the instance in terms of efficiency and functionalities by comparing it with other related works.(3)
We formally discuss the security of thePMDP framework. Concretely speaking, we reduce its security to the security of the building mechanisms including fully homomorphic encryption, secure multiparty computation, and differential privacy, which are all with the feature of provable security. Thus, thePMDP framework is also provably secure.(4)
We put forward a reinforced version of thePMDP framework namedsPMDP, to provide stronger security and privacy guarantee. In addition, we also show the application scenarios of thePMDP andsPMDP frameworks.


### 1.2. Outline

The remainder of the paper is organized as follows. In Section2, we review the related work on techniques for data privacy in different phases. Section 3 introduces some preliminary knowledge used in this paper. ThePMDP framework is presented in Section 4. Section 5 illustrates an instantiation of the framework. In Section 6, we evaluate the performance of the framework and discuss its security along with its application scenarios. We propose the reinforced frameworksPMDP and analyze its security in Section 7. Finally, some concluding remarks are given in Section 8.


## 1.1. Our Contribution

In this paper we propose a general framework for Preserving Multiparty Data Privacy (PMDP for short) in cloud computing, which provides complete protection throughout the entire life cycle of users’ data and is suitable for securing multiparty data aggregation and publication with the assistance of anuntrusted cloud server. Specifically, the contributions of this study can be summarized as follows:(1)
Based on well studied security mechanisms for preserving user privacy in the process of data storage, processing, and publishing, respectively, we combine these techniques in a nontrivial and tight manner and propose thePMDP framework that covers the full lifecycle of multiple users’ data.(2)
We present the principles of choosing the building security mechanisms involved in thePMDP framework and a specific instance. Furthermore, to illustrate the advantage and practicability of thePMDP framework, we evaluate the performance of the instance in terms of efficiency and functionalities by comparing it with other related works.(3)
We formally discuss the security of thePMDP framework. Concretely speaking, we reduce its security to the security of the building mechanisms including fully homomorphic encryption, secure multiparty computation, and differential privacy, which are all with the feature of provable security. Thus, thePMDP framework is also provably secure.(4)
We put forward a reinforced version of thePMDP framework namedsPMDP, to provide stronger security and privacy guarantee. In addition, we also show the application scenarios of thePMDP andsPMDP frameworks.


## 1.2. Outline

The remainder of the paper is organized as follows. In Section2, we review the related work on techniques for data privacy in different phases. Section 3 introduces some preliminary knowledge used in this paper. ThePMDP framework is presented in Section 4. Section 5 illustrates an instantiation of the framework. In Section 6, we evaluate the performance of the framework and discuss its security along with its application scenarios. We propose the reinforced frameworksPMDP and analyze its security in Section 7. Finally, some concluding remarks are given in Section 8.


## 2. Related Work

In this section, under the background of cloud computing, we briefly introduce the security mechanisms used to protect data privacy in each phase of the life cycle of data.Secure Data Storage. When the data storage is outsourced to cloud servers, data owner completely loses the access control of his/her data. But data owner hopes that the outsourced data can only be accessed by authorized users for privacy issues. A natural solution is to encrypt the data before sending it to cloud servers so that the users holding corresponding secret keys can decrypt the data. Although traditional public key encryption schemes can guarantee data security, they suffer from the limitation of efficiency. A new approach is identity-based encryption, but it is faced with some new challenges [7]. As an extension of identity-based encryption, attribute-based encryption (ABE) [8] enables the data owner to place fine-grained access policy over the outsourced data and can perfectly conquer the problem of securing data storage in cloud computing. For this reason, many ABE schemes [9, 10] with extended functionalities have been proposed. In addition, there are also various privacy-preserving authentication protocols, like two-factor authentication [11, 12], three-factor authentication [13, 14], end-to-end authentication [15], and so on. And some new works focus on practical application fields, such as smart metering [16], Internet of Things [17], and WBAN [18].Secure Data Processing. The purpose of aggregating and storing data is to make analysis on them and further find the valuable information. However, when the data is outsourced to cloud servers with the above encryption mechanisms, the data analyst has to download and decrypt the data before processing it, which is not convenient enough to satisfy the data analyzing demands under the background of big data. Fortunately, fully homomorphic encryption (FHE) [19], which has the feature of allowing cloud servers to evaluate arbitrary functions on the encrypted data without decryption, can simultaneously guarantee the security of the data in phases of storage and processing. Due to its significant advantages of securing data sharing, many FHE schemes were proposed to improve the security and efficiency of the original one. Besides, some frameworks for efficient and privacy-preserving outsourced computation have been proposed based on FHE, such asEPOM [20],POFD [21], andPOCR [22].Another important security mechanism used to secure data processing is secure multiparty computation (MPC), which enables multiple users to perform the assigned computation on their collected data and obtain the computation result without getting any information about one another’s data. To improve the efficiency of MPC in the context of cloud computing, several variants of MPC have been proposed, such as on-the-fly MPC [23] and cloud-assisted MPC. In addition, motivated by security requirements of practical applications (e.g., outsourced database query, private set intersection, and information retrieval), some efficient and specific cloud-based MPC protocols [24, 25] have been designed.Secure Data Publishing. The significance of output privacy is remarkable especially under the background of big data. Due to the technology upgrade of data mining, preserving data privacy is getting more and more difficult since the sensitive information in original data would suffer from direct and indirect (via inference) exposure during the mining process. Namely, not only the original data but also the data mining output can lead to the disclosure of sensitive information. So it is necessary to pay attention to output privacy. Anonymization technologies are widely used to preserve data privacy in the process of data publishing. Although classical anonymization methods (e.g., k-anonymity, l-diversity, and t-closeness) have been well studied and there are various corresponding algorithms, they cannot resist structure-based deanonymization attacks [26], which implies that the published data would reveal user privacy. In contrast, differential privacy [27] provides strong theoretical guarantees on the privacy of data by adding noise with specific distributions to raw data. Roughly, the research of differential privacy applied to data publishing is comprised of two aspects, interactive data publishing and noninteractive data publishing. In the first one, the fundamental methods are about responding to queries by disturbing the outcome derived from the original dataset, including Laplace mechanism and exponential mechanism [27]. These methods are easy to implement but the noises achieving privacy protection are relatively big. Afterwards, researchers developed techniques [28] providing responses to queries according to the histogram with noise generated from raw data, which have low sensitivity and comparatively small noise. As for the noninteractive mode, the research results at present are mostly focusing on batch query [29], contingency tab publishing [30], grouping and generalization [31], and sanitized dataset publishing [32].Secure Data in Multiphase. The MPC technique can protect data privacy in the input and computation process, but it is not designed for output privacy. From the theoretical perspective, it is obvious that MPC cannot guarantee output privacy. With the rapid development of database technology and cloud computing, researchers begin to design security schemes with the capability of preserving data privacy in multiple phases of its lifecycle simultaneously. For instance, Pettai and Laud [33] gave a good example of combining MPC and differential privacy with reasonable performance to achieve both computational and output privacy. However, their framework, which we call DPSharemind, is built uponGUPT [34], which is secure under the assumption of the existence of atrusted third party. Consequently, in the situation where multiple clients intend to delegate the computation of a joint function on their data to an untrusted cloud, it can not guarantee the security of the framework. Bindschaedler et al. [35] showed how to obtain a noisy (differentially private) aggregation result in a star network topology using Shamir secret sharing scheme and additively homomorphic encryption; we call their work DPStar. They also ensured that the amount of noise in the final result would neither be reduced by colluding entities nor be influenced by a cheating aggregator secretly, which had important practical significance.


## 3. Preliminaries

In this section we review the concepts of secure multiparty computation and differential privacy, which are building tools of ourPMDP framework.


### 3.1. Secure Multiparty Computation

Our framework is partially built upon the on-the-fly MPC protocol that is constructed from multikey FHE. In this paper we use the FHE from NTRU encryption scheme of Hoffstein with the modifications of Stehlé and Steinfeld [36]. So we start from the NTRU encryption.NTRU Encryption. The NTRU cryptosystem is constructed over the ring R=defZ[x]/xn+1, where n=2u for some integer u∈N. Let q be an odd prime number and χ be a B-bounded distribution over R  (B≪q). Denote the polynomial ring R/qR by Rq and the coefficient-wise reduction modulo q into the set -q/2,…,q/2 by ·q. Roughly, given a security parameter κ, the NTRU cryptosystem is specialized as follows.Keygen(1κ): the key generation algorithm samples polynomials f′,g←χ and lets f=2f′+1. Particularly, if f is not invertible in Rq, then f′ is resampled. Denote the inverse of f in Rq by f-1; then the public keypk and the secret keysk are calculated as follows:(1)sk=f,pk=h=2gf-1q.Enc(pk,m): the encryption algorithm samples polynomials s,e←χ for plaintext m∈0,1, and outputs the corresponding ciphertext as follows: (2)c=hs+2e+mq.Dec(sk,c): the decryption algorithm decrypts the ciphertext c by computing m=fcq mod 2.With the NTRU encryption scheme and the conversion techniques introduced in [23], we can derive a multikey fully homomorphic encryption scheme. Denote by {E(N)=(Keygen,Enc,Dec,Eval)}N>0 the family of the resulting multikey fully homomorphic encryption schemes and by U the collection of parties. The notationEval means the homomorphic evaluation performed by the cloud (relinearization and squashing involved in the homomorphic multiplication are not detailed due to space limitations). Then, an on-the-fly MPC protocol secure against semimalicious adversaries can be constructed as follows.Step 1.
For eachi∈U, the participant Pi samples a key tuple (pki,ski,eki)←Keygen(1κ;ri) and uses pki to encrypt his/her input xi:ci←Enc(pki,xi), where eki is an evaluation key. Then (pki,eki,ci) is sent to a cloud server S. At this point a function F, represented as a circuit C, has been selected on {xi}i∈V for some V⊆U. Let N=|V|.Step 2.
The cloud serverS performs homomorphic evaluation on ciphertexts(3)c⟵EvalC,c1,pk1,ek1,…,cN,pkN,ekN,and broadcasts c to parties P1,…,PN.Step 3.
By running a general secure MPC protocolΠdecmul, these parties P1,…,PN compute the function (4)gcsk1,…,skN⟵Decsk1,…,skN,c.The above on-the-fly MPC protocol can be modified to achieve security againstmalicious adversaries by adding zero-knowledge proofs and succinct noninteractive arguments of knowledge system, which is used in both of our frameworks to guarantee their security property.


### 3.2. Differential Privacy

Informally, differential privacy guarantees that a single record in a dataset being missing has only limited impact on the outputs of the queries executed on the dataset. The formal definition is captured as follows.Definition 1 (ϵ-differential privacy [27]).
An algorithmA satisfies ϵ-differential privacy (ϵ-DP) if for any pair of neighboring datasets D and D′, and any S⊆Range(A), it holds that (5)PrAD=S≤eϵ·PrAD′=S, where Range(A) denotes the collection of all possible outputs of the algorithm A.The datasetsD and D′ are neighboring provided that they differ by only one tuple. We denote this by D≃D′. We can see that the change in the probability distribution of the output caused by adding/removing any single tuple is bounded by eϵ.As a majorϵ-differential privacy mechanism, Laplace mechanism perturbs the output of a function fDP on a dataset D by adding to fDP(D) a noise randomly sampled from the Laplace distribution. We define the global sensitivity of fDP as (6)Δf=maxD,D′:D≃D′fDPD-fDPD′.Then a Laplace mechanism Af is given as follows:(7)AfDPD=fDPD+LapΔfϵ, where (8)Lapb=defLapx∣b=12bexp-xb.Sample-and-Aggregate. The Sample-and-Aggregate technique provides a way to lower the global sensitivity and improve the parallel degree of algorithm and further results in a differentially private method of computing a function f. The basic mechanism is specified as shown in Algorithm 1.Algorithm 1:Sample-and-Aggregate algorithm [37].
Input:
DatasetT∈Rn, length of the dataset n, privacy parameter ϵ,
clipping range(Bleft,Bright).
(
1
) Let l=n0.4
(
2
) Randomly partition T into l disjoint blocks T1,…,Tl
(
3
)
for
i
=
1 to ldo
(
4
)  OTi← output of fDP operates on dataset Ti
(
5
)   If OTi<Bleft, then OTi←Bleft
(
6
)   If OTi>Bright, then OTi←Bright
(
7
)
end for
(
8
)
return
1
/
l
∑
i
=
1
l
O
T
i
+
L
a
p
B
r
i
g
h
t
-
B
l
e
f
t
/
l
⋅
ϵ;


## 3.1. Secure Multiparty Computation

Our framework is partially built upon the on-the-fly MPC protocol that is constructed from multikey FHE. In this paper we use the FHE from NTRU encryption scheme of Hoffstein with the modifications of Stehlé and Steinfeld [36]. So we start from the NTRU encryption.NTRU Encryption. The NTRU cryptosystem is constructed over the ring R=defZ[x]/xn+1, where n=2u for some integer u∈N. Let q be an odd prime number and χ be a B-bounded distribution over R  (B≪q). Denote the polynomial ring R/qR by Rq and the coefficient-wise reduction modulo q into the set -q/2,…,q/2 by ·q. Roughly, given a security parameter κ, the NTRU cryptosystem is specialized as follows.Keygen(1κ): the key generation algorithm samples polynomials f′,g←χ and lets f=2f′+1. Particularly, if f is not invertible in Rq, then f′ is resampled. Denote the inverse of f in Rq by f-1; then the public keypk and the secret keysk are calculated as follows:(1)sk=f,pk=h=2gf-1q.Enc(pk,m): the encryption algorithm samples polynomials s,e←χ for plaintext m∈0,1, and outputs the corresponding ciphertext as follows: (2)c=hs+2e+mq.Dec(sk,c): the decryption algorithm decrypts the ciphertext c by computing m=fcq mod 2.With the NTRU encryption scheme and the conversion techniques introduced in [23], we can derive a multikey fully homomorphic encryption scheme. Denote by {E(N)=(Keygen,Enc,Dec,Eval)}N>0 the family of the resulting multikey fully homomorphic encryption schemes and by U the collection of parties. The notationEval means the homomorphic evaluation performed by the cloud (relinearization and squashing involved in the homomorphic multiplication are not detailed due to space limitations). Then, an on-the-fly MPC protocol secure against semimalicious adversaries can be constructed as follows.Step 1.
For eachi∈U, the participant Pi samples a key tuple (pki,ski,eki)←Keygen(1κ;ri) and uses pki to encrypt his/her input xi:ci←Enc(pki,xi), where eki is an evaluation key. Then (pki,eki,ci) is sent to a cloud server S. At this point a function F, represented as a circuit C, has been selected on {xi}i∈V for some V⊆U. Let N=|V|.Step 2.
The cloud serverS performs homomorphic evaluation on ciphertexts(3)c⟵EvalC,c1,pk1,ek1,…,cN,pkN,ekN,and broadcasts c to parties P1,…,PN.Step 3.
By running a general secure MPC protocolΠdecmul, these parties P1,…,PN compute the function (4)gcsk1,…,skN⟵Decsk1,…,skN,c.The above on-the-fly MPC protocol can be modified to achieve security againstmalicious adversaries by adding zero-knowledge proofs and succinct noninteractive arguments of knowledge system, which is used in both of our frameworks to guarantee their security property.


## 3.2. Differential Privacy

Informally, differential privacy guarantees that a single record in a dataset being missing has only limited impact on the outputs of the queries executed on the dataset. The formal definition is captured as follows.Definition 1 (ϵ-differential privacy [27]).
An algorithmA satisfies ϵ-differential privacy (ϵ-DP) if for any pair of neighboring datasets D and D′, and any S⊆Range(A), it holds that (5)PrAD=S≤eϵ·PrAD′=S, where Range(A) denotes the collection of all possible outputs of the algorithm A.The datasetsD and D′ are neighboring provided that they differ by only one tuple. We denote this by D≃D′. We can see that the change in the probability distribution of the output caused by adding/removing any single tuple is bounded by eϵ.As a majorϵ-differential privacy mechanism, Laplace mechanism perturbs the output of a function fDP on a dataset D by adding to fDP(D) a noise randomly sampled from the Laplace distribution. We define the global sensitivity of fDP as (6)Δf=maxD,D′:D≃D′fDPD-fDPD′.Then a Laplace mechanism Af is given as follows:(7)AfDPD=fDPD+LapΔfϵ, where (8)Lapb=defLapx∣b=12bexp-xb.Sample-and-Aggregate. The Sample-and-Aggregate technique provides a way to lower the global sensitivity and improve the parallel degree of algorithm and further results in a differentially private method of computing a function f. The basic mechanism is specified as shown in Algorithm 1.Algorithm 1:Sample-and-Aggregate algorithm [37].
Input:
DatasetT∈Rn, length of the dataset n, privacy parameter ϵ,
clipping range(Bleft,Bright).
(
1
) Let l=n0.4
(
2
) Randomly partition T into l disjoint blocks T1,…,Tl
(
3
)
for
i
=
1 to ldo
(
4
)  OTi← output of fDP operates on dataset Ti
(
5
)   If OTi<Bleft, then OTi←Bleft
(
6
)   If OTi>Bright, then OTi←Bright
(
7
)
end for
(
8
)
return
1
/
l
∑
i
=
1
l
O
T
i
+
L
a
p
B
r
i
g
h
t
-
B
l
e
f
t
/
l
⋅
ϵ;


## 4. Our Framework

In this section, we first introduce the entities involved in thePMDP framework and then provide an overview of thePMDP framework, followed by its details. Before presenting the details of our framework, we summarize the basic notations used throughout this paper in Notations.


### 4.1. Involved Entities

ThePMDP framework involves the following entities:(1)
Completely trusted authority: the authority takes charge of producing secret keys for all legal system users. Since the authority can decrypt any ciphertext generated by any user, we thus suppose that it is completely trusted.(2)
Semitrusted cloud server: a cloud server has powerful resources of storage and computation that can be easily accessed when required by system users. In the framework it is in charge of performing evaluation part of FHE in a MPC protocol and is assumed to be semitrusted. Namely, the cloud server will honestly complete the given computation assignments but will try to learn the information of the outsourced data.(3)
System users: in thePMDP framework, several system users can compute the value of a public function on their private data. Each participant is associated with a unique identifier Pi  (i=1,2,…,N) and holds the corresponding secure key issued by the authority. Let U be the collection of all parties. Each user is possible to be corrupted by adversaries, which results in the disclosure of the user’s secret key.(4)
Malicious adversaries: in fact, malicious adversaries do not participate in the procedure of thePMDP framework. But they do exist when we consider the security of the framework. In this paper, only adversaries that can corrupt any subset of t<N parties are considered. In the privacy analysis of our framework, we assume that adversaries have strong background knowledge.


### 4.2. Overview of thePMDP Framework

Roughly, the PMDP framework is a nontrivial and tight integration of MPC and DP proposed by using the Sample-and-Aggregate mechanism, and the enhanced framework sPMDP in Section7 is also nontrivial and even tighter because it is based on PMDP and its noise addition part is conducted on the cloud in the evaluation stage of MPC.ThePMDP framework consists of the following six stages.Stage
0. Initially, the authority sets up the system by generating public parameters and corresponding secret keys. Like most of other frameworks, the setup procedure is important to make it work correctly.Stage
1. Each participant encrypts his/her private data with a multikey fully homomorphic encryption scheme and outsources the resulting ciphertext to the cloud server.Stage
2. The cloud server identifies the parties involved in the multiparty computation of the corresponding ciphertexts and partitions them into some blocks.Stage
3. The cloud server operates on the encrypted data with on-the-fly MPC and outputs the calculated results to their corresponding blocks in the form of ciphertext.Stage
4. These parties in the same block decrypt the returned ciphertext. Furthermore, all these decrypted results from different blocks are aggregated into a final result in accordance with the partition and sample method in the second stage.Stage
5. Finally, to ensure output privacy, a designated participant first runs a differential privacy mechanism on the final result and then publishes the designated result.


### 4.3. Details of thePMDP Framework

Now we present the details of thePMDP framework. As shown in Figure 1, the entire procedure is comprised of the following phases.Figure 1
ThePMDP Framework.


#### 4.3.1. System Setup

Initially, the authority makes the framework specific by choosing appropriate algorithms for each part and presetting related parameters. Since our framework is mainly based on the on-the-fly MPC from multikey FHE, the following components are necessary:(a)
A collection of multikey fully homomorphic encryption schemes with semantical security(9)E=EN=Keygen,Enc,Dec,EvalN>0.(b)
A NIZK argument system(10)Ωenc=Setupenc,Proveenc,Verifyenc,Simenc,for the NP relation(11)Renc=pk,c,x,s∣c=Encpk,x;s.(c)
An adaptively extractable SNARK system(12)Φ=SetupΦ,ProveΦ,VerifyΦ,ExtΦ,for all of NP.(d)
A family of collision-resistant hash functions(13)H=Hhk:0,1∗⟶0,1κhk.(e)
AnN-party MPC protocol Πdecmul secure against malicious adversaries corrupting t<N parties, for computing the family of decryption functions(14)gc,pk1,ek1,…,pkN,ekNsk1,r1,…,skN,rN=defDecsk1,…,skN,c,ifPversuc,⊥,otherwise,where(15)Pversuc=pki,ski,eki=Keygen1κ;ri,∀i∈N.In addition, the method of sampling and partitioningΨS&P should also be determined in this part, after which the aggregation mechanism Λagg would be explicit. Note that we use differential privacy in the last stage. Since there are several available mechanisms to achieve differential privacy and many variants of the original definition of ϵ-differential privacy, participants should pay attention to select an appropriate one in the light of the function to be computed on the cloud sever.Moreover, the authority specializes the NIZK proof systemΩenc according to a security parameter κ and send the resulting common reference string crsenc to the cloud server and all parties. The privacy budget ϵ in differential privacy is also initialized.


#### 4.3.2. Data Encryption and Uploading

In this phase all parties encrypt their data and upload them to the cloud server, before making the decision of performing which kind of multiparty computation on the outsourced data. Namely, this phase can be completed in an offline way, which reduces the communication delay of the framework. Specifically, to encrypt his/her dataxi, each party Pi∈U runs the following algorithms: (16)pki,ski,eki⟵Keygen1κ;ri,ci⟵Encpki,xi;si,πienc⟵Proveencpki,ci,xi,si.In addition,Pi samples a hash key hki and computes a hash value of the ciphertext as di=Hhki(ci). Moreover, Pi generates a tuple of verification reference string and private verification key vrsi,privi←SetupΦ1κ. After that, Pi sends the tuple pki,eki,ci,πienc,hki,di,vrsi to the cloud server and keeps the corresponding secret/private keys and random values as secret.Note that after receiving the tuple fromPi, the cloud server will check whether the ciphertext ci is well formed by verifying the associated proof πienc.


#### 4.3.3. Sampling and Partitioning

In this phase all participants agree on the mechanism of sampling and partitioning. So far, there are a variety of sampling and partitioning mechanisms with different features for differential privacy when dealing with datasets, such as random sampling, uniform (fixed size) sampling, fraction sampling, Bernoulli sampling, random partitioning, and cell-based and kd-tree-based partitioning. Such mechanisms can not only decrease the sensitivity of the function to be computed, but also make the computation paralleled on the cloud server.Typically, if sampling is not necessary, random partitioning is a common choice due to its simplicity, effectiveness, and practicability. This is the first step of the well-known Sample-and-Aggregate algorithm. By randomly partitioning the original datasetG into l disjoint subsets {Gj∣1≤j≤l} with almost the same size, we can perform the secure delegation of multiparty computation on each subset in the next phase. When the original dataset is partitioned, the corresponding collection of parties U is also partitioned into several subsets Uj∣1≤j≤l. The parties belonging to the same Uj form a group.It is suggested that the size of the blocks obtained from sampling and partitioning should be in the range ofN0.5,N0.6, since a too big size makes the sampling and partitioning operation meaningless, and a too small size will threaten the data privacy of participants.


#### 4.3.4. Homomorphic Evaluation

In this phase the cloud server first represents the functionF to be computed as a circuit C, and then performs the multiparty computation on each subset Gj(1≤j≤l).Concretely, for eachj∈{1,…,l}, let the size of Gj be N, and the corresponding parties be {P1,…,PN}. The cloud server computes (17)oj⟵EvalC,c1,pk1,ek1,…,cN,pkN,ekN,and produces succinct arguments φii∈N for the following NP language: (18)L=pki,eki,hki,di∣∃c~1,π~1enc,…,c~N,π~Nencs.t.di=Hhkic~i,Verifyencpki,c~i,π~ienc=1,oj=EvalC,c~1,pk1,ek1,…,c~N,pkN,ekN.


#### 4.3.5. Decryption and Aggregation

In this phase all participants decrypt the evaluated ciphertext and further aggregate the resulting data.First, forj=1 to l, each participant Pi belonging to the group Gj runs the algorithm VerifyΦ({(pki,eki,hki,di)}i∈[N],φi) to verify the validity of the argument φi. If the verification is successful for all parties in the same group, then the MPC protocol Πdecmul is performed to compute(19)Oj=goj,pk1,ek1,…,pkN,ekNsk1,r1,…,skN,rN=defDecsk1,…,skN,oj,ifPversuc,⊥,otherwise.Second, these participants from different groups merge their outputs into a common output by performing the aggregation mechanism(20)O⟵ΛaggOj,j=1,…,l.To simplify the above aggregation procedure, the party with the most computing power in each group will be assigned as the agent of the group, and all these agents are designated to accomplish the aggregation work. Moreover, the aggregation procedure can also be outsourced to the cloud server by using a secure delegation protocol, for example, the cloud-assisted MPC from threshold FHE [5].


#### 4.3.6. Privacy-Preserving Result Release

To preserve the output privacy well, in this phase, the noise generated by differential privacy mechanisms is added to the aggregated output. Specifically, the following issues should be synthetically considered by parties before sampling the noise.First, since there are a few variants ofϵ-differential privacy, it is necessary and important to make a proper choice among them according to the participants’ requirements. Particularly, the (ϵ,δ)-differential privacy is the most widely used one and is adaptable to the situation with less restriction of privacy loss. Personalized differential privacy provides more accurate control of the consumption of privacy budget at an individual level and is usually used in interactive queries. Concentrated differential privacy gives high probability bounds for cumulative loss of numerical computations and works well in the aspect of preserving group privacy. All in all, the choice should be based on the computation to be made on the cloud server and the desired privacy-preserving level.Second, researchers have developed several differential privacy mechanisms, which can achieve the same DP definition in different application scenes. For example, the Laplace mechanism can achieveϵ-DP for real valued queries, while the exponential mechanism is a ϵ-DP method of sampling from a discrete set of candidate outputs. Thus, if parties want to publish their average wage in a differentially private way, the Laplace mechanism is available; but if they want to release the result of their secure voting for a new leader, the exponential mechanism is a better option.Third, by the definition of differential privacy, we know that the sensitivity of the function is an important parameter in the specific realization of differential privacy. Additionally, the computation outsourced to the cloud server and the used aggregation mechanism significantly affect the magnitude of sensitivity. Therefore, it is essential to pay attention to both of them.The last issue needed to be considered is which party should be responsible for generating, handling, and adding the noise. It seems that any party can take on such a task. But this is built upon the assumption that all parties are at least semihonest without collusion in the result release phase. Otherwise, malicious participants may try to reduce the differential privacy of honest participants through sampling a noise that is smaller than the required magnitude, and semihonest participants may collude to disclose the information of honest participants by sharing their input data and subtracting the noise term from the published result. In our framework we assume that all participants are honest, or at least semihonest without collusion in this phase. As a result, the output privacy can be guaranteed by selecting an agent of all parties to run the differential privacy mechanism on the aggregated result.


## 4.1. Involved Entities

ThePMDP framework involves the following entities:(1)
Completely trusted authority: the authority takes charge of producing secret keys for all legal system users. Since the authority can decrypt any ciphertext generated by any user, we thus suppose that it is completely trusted.(2)
Semitrusted cloud server: a cloud server has powerful resources of storage and computation that can be easily accessed when required by system users. In the framework it is in charge of performing evaluation part of FHE in a MPC protocol and is assumed to be semitrusted. Namely, the cloud server will honestly complete the given computation assignments but will try to learn the information of the outsourced data.(3)
System users: in thePMDP framework, several system users can compute the value of a public function on their private data. Each participant is associated with a unique identifier Pi  (i=1,2,…,N) and holds the corresponding secure key issued by the authority. Let U be the collection of all parties. Each user is possible to be corrupted by adversaries, which results in the disclosure of the user’s secret key.(4)
Malicious adversaries: in fact, malicious adversaries do not participate in the procedure of thePMDP framework. But they do exist when we consider the security of the framework. In this paper, only adversaries that can corrupt any subset of t<N parties are considered. In the privacy analysis of our framework, we assume that adversaries have strong background knowledge.


## 4.2. Overview of thePMDP Framework

Roughly, the PMDP framework is a nontrivial and tight integration of MPC and DP proposed by using the Sample-and-Aggregate mechanism, and the enhanced framework sPMDP in Section7 is also nontrivial and even tighter because it is based on PMDP and its noise addition part is conducted on the cloud in the evaluation stage of MPC.ThePMDP framework consists of the following six stages.Stage
0. Initially, the authority sets up the system by generating public parameters and corresponding secret keys. Like most of other frameworks, the setup procedure is important to make it work correctly.Stage
1. Each participant encrypts his/her private data with a multikey fully homomorphic encryption scheme and outsources the resulting ciphertext to the cloud server.Stage
2. The cloud server identifies the parties involved in the multiparty computation of the corresponding ciphertexts and partitions them into some blocks.Stage
3. The cloud server operates on the encrypted data with on-the-fly MPC and outputs the calculated results to their corresponding blocks in the form of ciphertext.Stage
4. These parties in the same block decrypt the returned ciphertext. Furthermore, all these decrypted results from different blocks are aggregated into a final result in accordance with the partition and sample method in the second stage.Stage
5. Finally, to ensure output privacy, a designated participant first runs a differential privacy mechanism on the final result and then publishes the designated result.


## 4.3. Details of thePMDP Framework

Now we present the details of thePMDP framework. As shown in Figure 1, the entire procedure is comprised of the following phases.Figure 1
ThePMDP Framework.


### 4.3.1. System Setup

Initially, the authority makes the framework specific by choosing appropriate algorithms for each part and presetting related parameters. Since our framework is mainly based on the on-the-fly MPC from multikey FHE, the following components are necessary:(a)
A collection of multikey fully homomorphic encryption schemes with semantical security(9)E=EN=Keygen,Enc,Dec,EvalN>0.(b)
A NIZK argument system(10)Ωenc=Setupenc,Proveenc,Verifyenc,Simenc,for the NP relation(11)Renc=pk,c,x,s∣c=Encpk,x;s.(c)
An adaptively extractable SNARK system(12)Φ=SetupΦ,ProveΦ,VerifyΦ,ExtΦ,for all of NP.(d)
A family of collision-resistant hash functions(13)H=Hhk:0,1∗⟶0,1κhk.(e)
AnN-party MPC protocol Πdecmul secure against malicious adversaries corrupting t<N parties, for computing the family of decryption functions(14)gc,pk1,ek1,…,pkN,ekNsk1,r1,…,skN,rN=defDecsk1,…,skN,c,ifPversuc,⊥,otherwise,where(15)Pversuc=pki,ski,eki=Keygen1κ;ri,∀i∈N.In addition, the method of sampling and partitioningΨS&P should also be determined in this part, after which the aggregation mechanism Λagg would be explicit. Note that we use differential privacy in the last stage. Since there are several available mechanisms to achieve differential privacy and many variants of the original definition of ϵ-differential privacy, participants should pay attention to select an appropriate one in the light of the function to be computed on the cloud sever.Moreover, the authority specializes the NIZK proof systemΩenc according to a security parameter κ and send the resulting common reference string crsenc to the cloud server and all parties. The privacy budget ϵ in differential privacy is also initialized.


### 4.3.2. Data Encryption and Uploading

In this phase all parties encrypt their data and upload them to the cloud server, before making the decision of performing which kind of multiparty computation on the outsourced data. Namely, this phase can be completed in an offline way, which reduces the communication delay of the framework. Specifically, to encrypt his/her dataxi, each party Pi∈U runs the following algorithms: (16)pki,ski,eki⟵Keygen1κ;ri,ci⟵Encpki,xi;si,πienc⟵Proveencpki,ci,xi,si.In addition,Pi samples a hash key hki and computes a hash value of the ciphertext as di=Hhki(ci). Moreover, Pi generates a tuple of verification reference string and private verification key vrsi,privi←SetupΦ1κ. After that, Pi sends the tuple pki,eki,ci,πienc,hki,di,vrsi to the cloud server and keeps the corresponding secret/private keys and random values as secret.Note that after receiving the tuple fromPi, the cloud server will check whether the ciphertext ci is well formed by verifying the associated proof πienc.


### 4.3.3. Sampling and Partitioning

In this phase all participants agree on the mechanism of sampling and partitioning. So far, there are a variety of sampling and partitioning mechanisms with different features for differential privacy when dealing with datasets, such as random sampling, uniform (fixed size) sampling, fraction sampling, Bernoulli sampling, random partitioning, and cell-based and kd-tree-based partitioning. Such mechanisms can not only decrease the sensitivity of the function to be computed, but also make the computation paralleled on the cloud server.Typically, if sampling is not necessary, random partitioning is a common choice due to its simplicity, effectiveness, and practicability. This is the first step of the well-known Sample-and-Aggregate algorithm. By randomly partitioning the original datasetG into l disjoint subsets {Gj∣1≤j≤l} with almost the same size, we can perform the secure delegation of multiparty computation on each subset in the next phase. When the original dataset is partitioned, the corresponding collection of parties U is also partitioned into several subsets Uj∣1≤j≤l. The parties belonging to the same Uj form a group.It is suggested that the size of the blocks obtained from sampling and partitioning should be in the range ofN0.5,N0.6, since a too big size makes the sampling and partitioning operation meaningless, and a too small size will threaten the data privacy of participants.


### 4.3.4. Homomorphic Evaluation

In this phase the cloud server first represents the functionF to be computed as a circuit C, and then performs the multiparty computation on each subset Gj(1≤j≤l).Concretely, for eachj∈{1,…,l}, let the size of Gj be N, and the corresponding parties be {P1,…,PN}. The cloud server computes (17)oj⟵EvalC,c1,pk1,ek1,…,cN,pkN,ekN,and produces succinct arguments φii∈N for the following NP language: (18)L=pki,eki,hki,di∣∃c~1,π~1enc,…,c~N,π~Nencs.t.di=Hhkic~i,Verifyencpki,c~i,π~ienc=1,oj=EvalC,c~1,pk1,ek1,…,c~N,pkN,ekN.


### 4.3.5. Decryption and Aggregation

In this phase all participants decrypt the evaluated ciphertext and further aggregate the resulting data.First, forj=1 to l, each participant Pi belonging to the group Gj runs the algorithm VerifyΦ({(pki,eki,hki,di)}i∈[N],φi) to verify the validity of the argument φi. If the verification is successful for all parties in the same group, then the MPC protocol Πdecmul is performed to compute(19)Oj=goj,pk1,ek1,…,pkN,ekNsk1,r1,…,skN,rN=defDecsk1,…,skN,oj,ifPversuc,⊥,otherwise.Second, these participants from different groups merge their outputs into a common output by performing the aggregation mechanism(20)O⟵ΛaggOj,j=1,…,l.To simplify the above aggregation procedure, the party with the most computing power in each group will be assigned as the agent of the group, and all these agents are designated to accomplish the aggregation work. Moreover, the aggregation procedure can also be outsourced to the cloud server by using a secure delegation protocol, for example, the cloud-assisted MPC from threshold FHE [5].


### 4.3.6. Privacy-Preserving Result Release

To preserve the output privacy well, in this phase, the noise generated by differential privacy mechanisms is added to the aggregated output. Specifically, the following issues should be synthetically considered by parties before sampling the noise.First, since there are a few variants ofϵ-differential privacy, it is necessary and important to make a proper choice among them according to the participants’ requirements. Particularly, the (ϵ,δ)-differential privacy is the most widely used one and is adaptable to the situation with less restriction of privacy loss. Personalized differential privacy provides more accurate control of the consumption of privacy budget at an individual level and is usually used in interactive queries. Concentrated differential privacy gives high probability bounds for cumulative loss of numerical computations and works well in the aspect of preserving group privacy. All in all, the choice should be based on the computation to be made on the cloud server and the desired privacy-preserving level.Second, researchers have developed several differential privacy mechanisms, which can achieve the same DP definition in different application scenes. For example, the Laplace mechanism can achieveϵ-DP for real valued queries, while the exponential mechanism is a ϵ-DP method of sampling from a discrete set of candidate outputs. Thus, if parties want to publish their average wage in a differentially private way, the Laplace mechanism is available; but if they want to release the result of their secure voting for a new leader, the exponential mechanism is a better option.Third, by the definition of differential privacy, we know that the sensitivity of the function is an important parameter in the specific realization of differential privacy. Additionally, the computation outsourced to the cloud server and the used aggregation mechanism significantly affect the magnitude of sensitivity. Therefore, it is essential to pay attention to both of them.The last issue needed to be considered is which party should be responsible for generating, handling, and adding the noise. It seems that any party can take on such a task. But this is built upon the assumption that all parties are at least semihonest without collusion in the result release phase. Otherwise, malicious participants may try to reduce the differential privacy of honest participants through sampling a noise that is smaller than the required magnitude, and semihonest participants may collude to disclose the information of honest participants by sharing their input data and subtracting the noise term from the published result. In our framework we assume that all participants are honest, or at least semihonest without collusion in this phase. As a result, the output privacy can be guaranteed by selecting an agent of all parties to run the differential privacy mechanism on the aggregated result.


## 4.3.1. System Setup

Initially, the authority makes the framework specific by choosing appropriate algorithms for each part and presetting related parameters. Since our framework is mainly based on the on-the-fly MPC from multikey FHE, the following components are necessary:(a)
A collection of multikey fully homomorphic encryption schemes with semantical security(9)E=EN=Keygen,Enc,Dec,EvalN>0.(b)
A NIZK argument system(10)Ωenc=Setupenc,Proveenc,Verifyenc,Simenc,for the NP relation(11)Renc=pk,c,x,s∣c=Encpk,x;s.(c)
An adaptively extractable SNARK system(12)Φ=SetupΦ,ProveΦ,VerifyΦ,ExtΦ,for all of NP.(d)
A family of collision-resistant hash functions(13)H=Hhk:0,1∗⟶0,1κhk.(e)
AnN-party MPC protocol Πdecmul secure against malicious adversaries corrupting t<N parties, for computing the family of decryption functions(14)gc,pk1,ek1,…,pkN,ekNsk1,r1,…,skN,rN=defDecsk1,…,skN,c,ifPversuc,⊥,otherwise,where(15)Pversuc=pki,ski,eki=Keygen1κ;ri,∀i∈N.In addition, the method of sampling and partitioningΨS&P should also be determined in this part, after which the aggregation mechanism Λagg would be explicit. Note that we use differential privacy in the last stage. Since there are several available mechanisms to achieve differential privacy and many variants of the original definition of ϵ-differential privacy, participants should pay attention to select an appropriate one in the light of the function to be computed on the cloud sever.Moreover, the authority specializes the NIZK proof systemΩenc according to a security parameter κ and send the resulting common reference string crsenc to the cloud server and all parties. The privacy budget ϵ in differential privacy is also initialized.


## 4.3.2. Data Encryption and Uploading

In this phase all parties encrypt their data and upload them to the cloud server, before making the decision of performing which kind of multiparty computation on the outsourced data. Namely, this phase can be completed in an offline way, which reduces the communication delay of the framework. Specifically, to encrypt his/her dataxi, each party Pi∈U runs the following algorithms: (16)pki,ski,eki⟵Keygen1κ;ri,ci⟵Encpki,xi;si,πienc⟵Proveencpki,ci,xi,si.In addition,Pi samples a hash key hki and computes a hash value of the ciphertext as di=Hhki(ci). Moreover, Pi generates a tuple of verification reference string and private verification key vrsi,privi←SetupΦ1κ. After that, Pi sends the tuple pki,eki,ci,πienc,hki,di,vrsi to the cloud server and keeps the corresponding secret/private keys and random values as secret.Note that after receiving the tuple fromPi, the cloud server will check whether the ciphertext ci is well formed by verifying the associated proof πienc.


## 4.3.3. Sampling and Partitioning

In this phase all participants agree on the mechanism of sampling and partitioning. So far, there are a variety of sampling and partitioning mechanisms with different features for differential privacy when dealing with datasets, such as random sampling, uniform (fixed size) sampling, fraction sampling, Bernoulli sampling, random partitioning, and cell-based and kd-tree-based partitioning. Such mechanisms can not only decrease the sensitivity of the function to be computed, but also make the computation paralleled on the cloud server.Typically, if sampling is not necessary, random partitioning is a common choice due to its simplicity, effectiveness, and practicability. This is the first step of the well-known Sample-and-Aggregate algorithm. By randomly partitioning the original datasetG into l disjoint subsets {Gj∣1≤j≤l} with almost the same size, we can perform the secure delegation of multiparty computation on each subset in the next phase. When the original dataset is partitioned, the corresponding collection of parties U is also partitioned into several subsets Uj∣1≤j≤l. The parties belonging to the same Uj form a group.It is suggested that the size of the blocks obtained from sampling and partitioning should be in the range ofN0.5,N0.6, since a too big size makes the sampling and partitioning operation meaningless, and a too small size will threaten the data privacy of participants.


## 4.3.4. Homomorphic Evaluation

In this phase the cloud server first represents the functionF to be computed as a circuit C, and then performs the multiparty computation on each subset Gj(1≤j≤l).Concretely, for eachj∈{1,…,l}, let the size of Gj be N, and the corresponding parties be {P1,…,PN}. The cloud server computes (17)oj⟵EvalC,c1,pk1,ek1,…,cN,pkN,ekN,and produces succinct arguments φii∈N for the following NP language: (18)L=pki,eki,hki,di∣∃c~1,π~1enc,…,c~N,π~Nencs.t.di=Hhkic~i,Verifyencpki,c~i,π~ienc=1,oj=EvalC,c~1,pk1,ek1,…,c~N,pkN,ekN.


## 4.3.5. Decryption and Aggregation

In this phase all participants decrypt the evaluated ciphertext and further aggregate the resulting data.First, forj=1 to l, each participant Pi belonging to the group Gj runs the algorithm VerifyΦ({(pki,eki,hki,di)}i∈[N],φi) to verify the validity of the argument φi. If the verification is successful for all parties in the same group, then the MPC protocol Πdecmul is performed to compute(19)Oj=goj,pk1,ek1,…,pkN,ekNsk1,r1,…,skN,rN=defDecsk1,…,skN,oj,ifPversuc,⊥,otherwise.Second, these participants from different groups merge their outputs into a common output by performing the aggregation mechanism(20)O⟵ΛaggOj,j=1,…,l.To simplify the above aggregation procedure, the party with the most computing power in each group will be assigned as the agent of the group, and all these agents are designated to accomplish the aggregation work. Moreover, the aggregation procedure can also be outsourced to the cloud server by using a secure delegation protocol, for example, the cloud-assisted MPC from threshold FHE [5].


## 4.3.6. Privacy-Preserving Result Release

To preserve the output privacy well, in this phase, the noise generated by differential privacy mechanisms is added to the aggregated output. Specifically, the following issues should be synthetically considered by parties before sampling the noise.First, since there are a few variants ofϵ-differential privacy, it is necessary and important to make a proper choice among them according to the participants’ requirements. Particularly, the (ϵ,δ)-differential privacy is the most widely used one and is adaptable to the situation with less restriction of privacy loss. Personalized differential privacy provides more accurate control of the consumption of privacy budget at an individual level and is usually used in interactive queries. Concentrated differential privacy gives high probability bounds for cumulative loss of numerical computations and works well in the aspect of preserving group privacy. All in all, the choice should be based on the computation to be made on the cloud server and the desired privacy-preserving level.Second, researchers have developed several differential privacy mechanisms, which can achieve the same DP definition in different application scenes. For example, the Laplace mechanism can achieveϵ-DP for real valued queries, while the exponential mechanism is a ϵ-DP method of sampling from a discrete set of candidate outputs. Thus, if parties want to publish their average wage in a differentially private way, the Laplace mechanism is available; but if they want to release the result of their secure voting for a new leader, the exponential mechanism is a better option.Third, by the definition of differential privacy, we know that the sensitivity of the function is an important parameter in the specific realization of differential privacy. Additionally, the computation outsourced to the cloud server and the used aggregation mechanism significantly affect the magnitude of sensitivity. Therefore, it is essential to pay attention to both of them.The last issue needed to be considered is which party should be responsible for generating, handling, and adding the noise. It seems that any party can take on such a task. But this is built upon the assumption that all parties are at least semihonest without collusion in the result release phase. Otherwise, malicious participants may try to reduce the differential privacy of honest participants through sampling a noise that is smaller than the required magnitude, and semihonest participants may collude to disclose the information of honest participants by sharing their input data and subtracting the noise term from the published result. In our framework we assume that all participants are honest, or at least semihonest without collusion in this phase. As a result, the output privacy can be guaranteed by selecting an agent of all parties to run the differential privacy mechanism on the aggregated result.


## 5. An Instantiation of the Framework

In this section, to illustrate the effectiveness of thePMDP framework, we present an instance of thePMDP framework and show how to use it to solve the problem that N parties securely compute and publish their average wage with the help of a semitrusted cloud sever. Specifically, this instantiated framework consists of the following stages.Stage
0. The authority chooses the following cryptographic primitives:(a)
The family of multikey FHE schemes proposed by Stehlé and Steinfeld [36] (21)ELA=EN=KeygenLA,EncLA,DecLA,EvalLAN>0.(b)
The NIZK argument system constructed by Groth et al. [38] (22)ΩLAenc=SetupLAenc,ProveLAenc,VerifyLAenc,SimLAenc,for the NP relation(23)Renc=pk,c,x,s∣c=Encpk,x;s.Letcrsenc be the common reference string for ΩLAenc.(c)
The adaptively extractable SNARK system presented by Bitansky et al. [39](24)ΦLA=SetupLAΦ,ProveLAΦ,VerifyLAΦ,ExtLAΦ,for all of NP.(d)
The family of cryptographically collision-resistant hash functions HmacSHA256(25)HI=HhkI:0,1∗⟶0,1256hk.(e)
The cloud-assistedN-party MPC protocol proposed by Asharov et al. [5] for computing the family of decryption functions(26)gc,pk1,ek1,…,pkN,ekNLAsk1,r1,…,skN,rN=defDecNTRUsk1,…,skN,c,ifPversuc256,⊥,otherwise,Pversuc256=pki,ski,eki=Keygen1256;ri,∀i∈N.Stage
1. Each party Pi∈U first performs the following algorithms:(27)hi,fi,γi,ζi=pki,ski,eki⟵KeygenLA1κ;ri,ci=hisi+2ei+xiq⟵Encpki,xi;si,πienc⟵Proveencpki,ci,xi,si,di=HhkiIci,vrsi,privi⟵SetupLAΦ1256,where si,ei are randomly sampled from χ and xi is Pi’s wage (the new symbols γ(i),ζ(i) are related toek, which can be further referred to in [23]).Then,Pi sends the tuple pki,eki,ci,πienc,hki,di,vrsi to the cloud server, who will verify the correctness of the proof πienc. These values fi,ri, hki,di, and privi are locally maintained by Pi.Stage
2. After gathering the encrypted data from all parties, the cloud sever forms them as a ciphertext dataset G. Then, by calling the Sample-and-Aggregate algorithm [37], it randomly partitions G into l=⌊N0.4⌋ disjoint subsets {Gj∣1≤j≤l}, which are with almost the same size. Meanwhile, the collection of all parties U is also partitioned into several corresponding groups {Uj∣1≤j≤l}.Stage
3. Since the problem is to compute the average wage of all parties, the cloud server needs to conduct the mean value function (28)Favr=1N·∑i=1Nxi,which is represented as a circuit Cavr. To this end, for each subgroup Gj={P1,…,PNj} (1≤j≤l), the cloud server computes (29)oj⟵EvalLACavr,c1,h1,ek1,…,cNj,hNj,ekNj, and generates the succinct arguments φii∈Nj for the following NP language: (30)Lj=pki,eki,hki,dii∈Nj∣∃c~1,π~1enc,…,c~Nj,π~Njencs.t.di=HhkiIc~i,Verifyencpki,c~i,π~ienc=1,oj=Eval⁡C,c~1,pk1,ek1,…,c~Nj,pkNj,ekNj.Stage
4. Fist, each party Pi belonging to Uj  (1≤j≤l) runs the algorithm VerifyLAΦpki,eki,hki,dii∈Nj,φi to verify the argument φi. If verification is successful for all parties in the same group, they perform the cloud-assisted MPC protocol to compute the following function.(31)Oj=goj,h1,ek1,…,hN,ekNLAf1,r1,…,fNj,rNj=deff1⋯fNj·ojqmod2,ifPversuc256,⊥,otherwise. Then, the cloud server broadcasts c,φ1,…,φNj to all the parties P1,…,PNj in the same group Uj together with the tuple hi,eki,hki,dii∈[Nj].Then, the agent in the groupGj computes (32)Oj=Bleft,ifOj<Bleft,Oj,ifBleft≤Oj≤Bright,Bright,ifOj>Bright, where Bleft, Bright are the left and right bounds in the Sample-and-Aggregate algorithm.Furthermore, all agents calculate the following function with the help of on-the-fly MPC protocol:(33)O=1l·∑j=1lOj.Stage
5. All parties vote for a publisher from all subgroup agents and authorize him/her to sample a noise (34)η0⟵LapBright-Bleftl·ϵ,and publish the finial average wage of all parties as (35)ODP=O+η0,where ϵ is the privacy budget.


## 6. Performance Discussion and Security Analysis

In this section we first systematically analyze the security of thePMDP framework along with its application scenarios. Then, we roughly discuss the performance of thePMDP framework in terms of computation overhead and security property.


### 6.1. Security Analysis

To simplify the security analysis of thePMDP framework, we separate participants into two categories, honest and semihonest, as in the security analysis of MPC protocol. On the other hand, the cloud server is always assumed to be untrusted. In addition, since the framework uses the differential privacy mechanism, we thus take the background knowledge attack into consideration. Below we present the security analysis of our framework in honest model and semihonest model, respectively. Since we extend the security models in traditional MPC protocols to those in our sPMDP framework, in the following security analysis we mainly focus on demonstrating that the output privacy cannot be violated since the input and computational privacy are already proven to be guaranteed by former works on MPC [23].


#### 6.1.1. Honest Model

We first show that thePMDP framework does preserve the data privacy under the assumption that all participants are honest and do not attempt to get others’ information. That is, each participant will honestly follow the framework procedure as required.Specifically, in Stage2 of the framework, each participant’s data is encrypted with FHE and then outsourced to the cloud server. Thus, the data privacy in the storage phase is ensured by the security of the underlying FHE. In Stage 4, all data are computed in the form of ciphertext with on-the-fly MPC protocol based on multikey FHE, whose security and correctness have been proved before. Therefore, data privacy in the processing phase is also protected, which means that each participant will only know his/her input and the output of his/her group. The operations of sampling, partitioning, and aggregation in Stages 3 and 5 do not influence the data privacy or the correctness of intermediate results if chosen appropriately, though there may be accuracy loss. The aggregated result is transformed into differentially private form and published in Stage 6, which ensures the output privacy owing to the theoretical guarantee of differential privacy. To sum up, in the honest model, we can see that thePMDP framework preservers the data privacy of all participants throughout its lifecycle, without affecting the data usability.Although the framework in the honest model is very simple and seems to be idealized, it can be deployed in particular applications. An actual example is that some medical facilities try to obtain meaningful insights on health according to analyses of their clients’ health data. Obviously, these facilities have the need for health data storage, processing, and release. By calling our framework, these facilities can be regarded as participants, whose data is taken good advantage of without any risk of privacy disclosure. In this instance, the medical facilities only care about the features, objective laws, and tendency of the collectivity rather than information of individuals, so it complies with the definition of honest model.


#### 6.1.2. Semihonest Model

In the semihonest model, a semihonest participant will follow the framework procedure but will also try to learn information about other parties. Moreover, a semihonest participant may collude with others, including other semihonest participants and external adversaries with background knowledge. In this work we assume that there is at least one honest party in the collection of all parties. We will show that thePMDP framework is secure only when there is no collusion in the semihonest model.Firstly, we consider the noncolluding situation. For a semihonest participantPs∈Us, he/she knows his/her input xs∈Gs, the local result of his/her group Os, the aggregated global result of all groups O, the noise η0, and the output ODP. Besides, he/she knows the method of sampling, partitioning, and aggregation, the function F computed on the cloud server, and who are in the same group Us with him/her. If he/she does not collude with anyone, he/she can not infer anyone’s input from what has been known, and the reason is not far to seek. From what has been known, Ps has the following equation. (36)Fxi∣xi∈Gs=Os.As we suggested before, the size of each group is at least N0.5. Considering our framework is designed to meet the challenge of big data privacy, we can assume that N≥10, which implies that Gs≥3. For Ps, he/she only knows xs, so there are at least 2 unknown elements in (36), meaning that it is unsolvable and Ps can not get others’ inputs.Now we consider the colluding situation. We present two possible attacks aiming at thePMDP framework from semihonest participants colluding with others.Case 1.
In each groupUj, there is only one honest party P∗; the others are semihonest and can collude with one another. Then, these semihonest parties can infer the input of P∗ as follows. Recall that in the following equation: (37)Fx1,x2,…,xP∗,…,xN=Oj,the only unknown variable is xP∗. It is not hard to solve (37) if the function F is not too complicated. If there is an external adversary who corrupts N-1 parties of an N-party group, he/she can conduct a similar attack.Case 2.
In each groupUj, there is only one semihonest party P∘, and the others are honest. Suppose that the party P∘ is corrupted by an external adversary with strong background knowledge; for example, the adversary knows the input of each party in Gj except a party P∗. Then, the adversary can obtain Oj from P∘ and launch an attack by solving the equation in Case 1 to get xP∗.We note that an entity who wants to attack the framework must possess the inputs of at leastN-1 parties in an N-party group. The condition is a little strict, but if the cloud server is corrupted and the sampling and partitioning method is decided by the cloud server, it will be much easier.The above two cases suggest that the framework may suffer from potential attacks when some participants are semihonest. To avoid these attacks in the semihonest model, the framework needs to be reformed.


### 6.2. Performance Discussion

Since thePMDP framework involves several general security mechanisms, it is difficult to accurately evaluate its computation and computation costs. Thus, we show its efficiency by discussing the performance of the instance presented in prior section.In the instance, each general partyPi, who is not assigned to be an agent, needs to generate his/her public/secret keys and perform encryption and NIZK operations in Stage 2. Moreover, Pi is also in charge of running the verification and decryption algorithms in Stage 5. Thus, Pi’s computation cost is roughly the same as that of each party in an on-the-fly MPC protocol. According to López-Alt et al.’s [23] analysis, we know that the computation cost of each general party Pi is at most polylogarithmic in the circuit size C and the total size of all inputs and polynomial in his/her own input xi. For an assigned agent, he/she has an extra calculation task, that is, the aggregation operation. Mostly, the aggregation complexity is OUj for the agent of group Uj. In addition, since we assume that the cloud server has sufficient computation resources, we thus omit its computation overhead.In Table1 we compare thePMDP framework with other related works from the aspect of security properties, including delegation of storage, privacy in different processes, the reliability of cloud server, security model, and whether they support distributing computation. We select three representative works for comparison, namely, theGUPT system [34], the scheme designed by Pettai and Laud [33], which we call DPSharemind, and the protocol from Bindschaedler et al. [35], which we call DPStar. The last row is about thesPMDP framework, which we will introduce later.Table 1
Comparisons of security properties with other related works.
Related works
Delegation of storage
Input privacy
Computational privacy
Output privacy
Cloud-assisted
Distributed computing
Server type
Security model
GUPT [34]
×
×
×
√
√
×
Trusted
Noncolluding & Semihonest
DPSharemind [33]
×
√
√
√
√
√
Trusted
Noncolluding & Semihonest
DPStar [35]
×
√
√
√
√
×
Untrusted
Semihonest
PMDP
√
√
√
√
√
√
Untrusted
Noncolluding & Semihonest
sPMDP
√
√
√
√
√
√
Untrusted
Malicious
The security model is about the types of the participants of the works.From Table1, we can see that overallPMDP overweighs the works in the first three rows. Firstly,PMDP enjoys the advantage in delegation of storage, which is important in the era of big data. This is because it employs FHE, whileGUPT does not consider data storage and both DPSharemind and DPStar employ secret sharing, thus breaking the integrity of data. Consequently, all works butGUPT can provide lifelong data privacy guarantee, covering input privacy, computational privacy, and output privacy. All of the works can be cloud-assisted, but onlyPMDP and DPStar allow the cloud server to be untrusted. The security model is mainly about the participants of the works. We have shown thatPMDP is secure under noncolluding semihonest model, and this is where it is weaker than DPStar. However, DPStar does not support distributed computing; onlyPMDP and DPSharemind do since they use sampling and aggregation. In order to make up for the shortcoming ofPMDP in security model, we propose thesPMDP framework in the next section.Before introducingsPMDP, we further illustrate the differences betweenPMDP andDPStar, which is a latest public work in addressing the privacy concerns related to multiparty computation. The fundamental difference is thatDPStar uses Shamir secret sharing and homomorphic encryption, andPMDP uses on-the-fly MPC from multikey FHE. As a result, the security model ofPMDP can be strengthened easily while that ofDPStar can not. Besides, in [35]DPStar is firstly introduced as a summation protocol and extended to other queries including count queries, histograms, and linear combinations, meaning that it has to be readjusted and several new operations have to be added when facing different queries. By contrast,PMDP is a framework and all of its details have been explained; thus it can be easily applied to different queries. So the generality and usability ofDPStar is not as well asPMDP. From what has been mentioned above, we can conclude thatDPStar has good security properties and important practical significance, and ourPMDP framework has advantage over it in delegation of storage, distributed computing, generality, and usability. As a reinforced version ofPMDP,sPMDP also has advantage overDPStar in security model, and we prove this in the next section.


## 6.1. Security Analysis

To simplify the security analysis of thePMDP framework, we separate participants into two categories, honest and semihonest, as in the security analysis of MPC protocol. On the other hand, the cloud server is always assumed to be untrusted. In addition, since the framework uses the differential privacy mechanism, we thus take the background knowledge attack into consideration. Below we present the security analysis of our framework in honest model and semihonest model, respectively. Since we extend the security models in traditional MPC protocols to those in our sPMDP framework, in the following security analysis we mainly focus on demonstrating that the output privacy cannot be violated since the input and computational privacy are already proven to be guaranteed by former works on MPC [23].


### 6.1.1. Honest Model

We first show that thePMDP framework does preserve the data privacy under the assumption that all participants are honest and do not attempt to get others’ information. That is, each participant will honestly follow the framework procedure as required.Specifically, in Stage2 of the framework, each participant’s data is encrypted with FHE and then outsourced to the cloud server. Thus, the data privacy in the storage phase is ensured by the security of the underlying FHE. In Stage 4, all data are computed in the form of ciphertext with on-the-fly MPC protocol based on multikey FHE, whose security and correctness have been proved before. Therefore, data privacy in the processing phase is also protected, which means that each participant will only know his/her input and the output of his/her group. The operations of sampling, partitioning, and aggregation in Stages 3 and 5 do not influence the data privacy or the correctness of intermediate results if chosen appropriately, though there may be accuracy loss. The aggregated result is transformed into differentially private form and published in Stage 6, which ensures the output privacy owing to the theoretical guarantee of differential privacy. To sum up, in the honest model, we can see that thePMDP framework preservers the data privacy of all participants throughout its lifecycle, without affecting the data usability.Although the framework in the honest model is very simple and seems to be idealized, it can be deployed in particular applications. An actual example is that some medical facilities try to obtain meaningful insights on health according to analyses of their clients’ health data. Obviously, these facilities have the need for health data storage, processing, and release. By calling our framework, these facilities can be regarded as participants, whose data is taken good advantage of without any risk of privacy disclosure. In this instance, the medical facilities only care about the features, objective laws, and tendency of the collectivity rather than information of individuals, so it complies with the definition of honest model.


### 6.1.2. Semihonest Model

In the semihonest model, a semihonest participant will follow the framework procedure but will also try to learn information about other parties. Moreover, a semihonest participant may collude with others, including other semihonest participants and external adversaries with background knowledge. In this work we assume that there is at least one honest party in the collection of all parties. We will show that thePMDP framework is secure only when there is no collusion in the semihonest model.Firstly, we consider the noncolluding situation. For a semihonest participantPs∈Us, he/she knows his/her input xs∈Gs, the local result of his/her group Os, the aggregated global result of all groups O, the noise η0, and the output ODP. Besides, he/she knows the method of sampling, partitioning, and aggregation, the function F computed on the cloud server, and who are in the same group Us with him/her. If he/she does not collude with anyone, he/she can not infer anyone’s input from what has been known, and the reason is not far to seek. From what has been known, Ps has the following equation. (36)Fxi∣xi∈Gs=Os.As we suggested before, the size of each group is at least N0.5. Considering our framework is designed to meet the challenge of big data privacy, we can assume that N≥10, which implies that Gs≥3. For Ps, he/she only knows xs, so there are at least 2 unknown elements in (36), meaning that it is unsolvable and Ps can not get others’ inputs.Now we consider the colluding situation. We present two possible attacks aiming at thePMDP framework from semihonest participants colluding with others.Case 1.
In each groupUj, there is only one honest party P∗; the others are semihonest and can collude with one another. Then, these semihonest parties can infer the input of P∗ as follows. Recall that in the following equation: (37)Fx1,x2,…,xP∗,…,xN=Oj,the only unknown variable is xP∗. It is not hard to solve (37) if the function F is not too complicated. If there is an external adversary who corrupts N-1 parties of an N-party group, he/she can conduct a similar attack.Case 2.
In each groupUj, there is only one semihonest party P∘, and the others are honest. Suppose that the party P∘ is corrupted by an external adversary with strong background knowledge; for example, the adversary knows the input of each party in Gj except a party P∗. Then, the adversary can obtain Oj from P∘ and launch an attack by solving the equation in Case 1 to get xP∗.We note that an entity who wants to attack the framework must possess the inputs of at leastN-1 parties in an N-party group. The condition is a little strict, but if the cloud server is corrupted and the sampling and partitioning method is decided by the cloud server, it will be much easier.The above two cases suggest that the framework may suffer from potential attacks when some participants are semihonest. To avoid these attacks in the semihonest model, the framework needs to be reformed.


## 6.1.1. Honest Model

We first show that thePMDP framework does preserve the data privacy under the assumption that all participants are honest and do not attempt to get others’ information. That is, each participant will honestly follow the framework procedure as required.Specifically, in Stage2 of the framework, each participant’s data is encrypted with FHE and then outsourced to the cloud server. Thus, the data privacy in the storage phase is ensured by the security of the underlying FHE. In Stage 4, all data are computed in the form of ciphertext with on-the-fly MPC protocol based on multikey FHE, whose security and correctness have been proved before. Therefore, data privacy in the processing phase is also protected, which means that each participant will only know his/her input and the output of his/her group. The operations of sampling, partitioning, and aggregation in Stages 3 and 5 do not influence the data privacy or the correctness of intermediate results if chosen appropriately, though there may be accuracy loss. The aggregated result is transformed into differentially private form and published in Stage 6, which ensures the output privacy owing to the theoretical guarantee of differential privacy. To sum up, in the honest model, we can see that thePMDP framework preservers the data privacy of all participants throughout its lifecycle, without affecting the data usability.Although the framework in the honest model is very simple and seems to be idealized, it can be deployed in particular applications. An actual example is that some medical facilities try to obtain meaningful insights on health according to analyses of their clients’ health data. Obviously, these facilities have the need for health data storage, processing, and release. By calling our framework, these facilities can be regarded as participants, whose data is taken good advantage of without any risk of privacy disclosure. In this instance, the medical facilities only care about the features, objective laws, and tendency of the collectivity rather than information of individuals, so it complies with the definition of honest model.


## 6.1.2. Semihonest Model

In the semihonest model, a semihonest participant will follow the framework procedure but will also try to learn information about other parties. Moreover, a semihonest participant may collude with others, including other semihonest participants and external adversaries with background knowledge. In this work we assume that there is at least one honest party in the collection of all parties. We will show that thePMDP framework is secure only when there is no collusion in the semihonest model.Firstly, we consider the noncolluding situation. For a semihonest participantPs∈Us, he/she knows his/her input xs∈Gs, the local result of his/her group Os, the aggregated global result of all groups O, the noise η0, and the output ODP. Besides, he/she knows the method of sampling, partitioning, and aggregation, the function F computed on the cloud server, and who are in the same group Us with him/her. If he/she does not collude with anyone, he/she can not infer anyone’s input from what has been known, and the reason is not far to seek. From what has been known, Ps has the following equation. (36)Fxi∣xi∈Gs=Os.As we suggested before, the size of each group is at least N0.5. Considering our framework is designed to meet the challenge of big data privacy, we can assume that N≥10, which implies that Gs≥3. For Ps, he/she only knows xs, so there are at least 2 unknown elements in (36), meaning that it is unsolvable and Ps can not get others’ inputs.Now we consider the colluding situation. We present two possible attacks aiming at thePMDP framework from semihonest participants colluding with others.Case 1.
In each groupUj, there is only one honest party P∗; the others are semihonest and can collude with one another. Then, these semihonest parties can infer the input of P∗ as follows. Recall that in the following equation: (37)Fx1,x2,…,xP∗,…,xN=Oj,the only unknown variable is xP∗. It is not hard to solve (37) if the function F is not too complicated. If there is an external adversary who corrupts N-1 parties of an N-party group, he/she can conduct a similar attack.Case 2.
In each groupUj, there is only one semihonest party P∘, and the others are honest. Suppose that the party P∘ is corrupted by an external adversary with strong background knowledge; for example, the adversary knows the input of each party in Gj except a party P∗. Then, the adversary can obtain Oj from P∘ and launch an attack by solving the equation in Case 1 to get xP∗.We note that an entity who wants to attack the framework must possess the inputs of at leastN-1 parties in an N-party group. The condition is a little strict, but if the cloud server is corrupted and the sampling and partitioning method is decided by the cloud server, it will be much easier.The above two cases suggest that the framework may suffer from potential attacks when some participants are semihonest. To avoid these attacks in the semihonest model, the framework needs to be reformed.


## 6.2. Performance Discussion

Since thePMDP framework involves several general security mechanisms, it is difficult to accurately evaluate its computation and computation costs. Thus, we show its efficiency by discussing the performance of the instance presented in prior section.In the instance, each general partyPi, who is not assigned to be an agent, needs to generate his/her public/secret keys and perform encryption and NIZK operations in Stage 2. Moreover, Pi is also in charge of running the verification and decryption algorithms in Stage 5. Thus, Pi’s computation cost is roughly the same as that of each party in an on-the-fly MPC protocol. According to López-Alt et al.’s [23] analysis, we know that the computation cost of each general party Pi is at most polylogarithmic in the circuit size C and the total size of all inputs and polynomial in his/her own input xi. For an assigned agent, he/she has an extra calculation task, that is, the aggregation operation. Mostly, the aggregation complexity is OUj for the agent of group Uj. In addition, since we assume that the cloud server has sufficient computation resources, we thus omit its computation overhead.In Table1 we compare thePMDP framework with other related works from the aspect of security properties, including delegation of storage, privacy in different processes, the reliability of cloud server, security model, and whether they support distributing computation. We select three representative works for comparison, namely, theGUPT system [34], the scheme designed by Pettai and Laud [33], which we call DPSharemind, and the protocol from Bindschaedler et al. [35], which we call DPStar. The last row is about thesPMDP framework, which we will introduce later.Table 1
Comparisons of security properties with other related works.
Related works
Delegation of storage
Input privacy
Computational privacy
Output privacy
Cloud-assisted
Distributed computing
Server type
Security model
GUPT [34]
×
×
×
√
√
×
Trusted
Noncolluding & Semihonest
DPSharemind [33]
×
√
√
√
√
√
Trusted
Noncolluding & Semihonest
DPStar [35]
×
√
√
√
√
×
Untrusted
Semihonest
PMDP
√
√
√
√
√
√
Untrusted
Noncolluding & Semihonest
sPMDP
√
√
√
√
√
√
Untrusted
Malicious
The security model is about the types of the participants of the works.From Table1, we can see that overallPMDP overweighs the works in the first three rows. Firstly,PMDP enjoys the advantage in delegation of storage, which is important in the era of big data. This is because it employs FHE, whileGUPT does not consider data storage and both DPSharemind and DPStar employ secret sharing, thus breaking the integrity of data. Consequently, all works butGUPT can provide lifelong data privacy guarantee, covering input privacy, computational privacy, and output privacy. All of the works can be cloud-assisted, but onlyPMDP and DPStar allow the cloud server to be untrusted. The security model is mainly about the participants of the works. We have shown thatPMDP is secure under noncolluding semihonest model, and this is where it is weaker than DPStar. However, DPStar does not support distributed computing; onlyPMDP and DPSharemind do since they use sampling and aggregation. In order to make up for the shortcoming ofPMDP in security model, we propose thesPMDP framework in the next section.Before introducingsPMDP, we further illustrate the differences betweenPMDP andDPStar, which is a latest public work in addressing the privacy concerns related to multiparty computation. The fundamental difference is thatDPStar uses Shamir secret sharing and homomorphic encryption, andPMDP uses on-the-fly MPC from multikey FHE. As a result, the security model ofPMDP can be strengthened easily while that ofDPStar can not. Besides, in [35]DPStar is firstly introduced as a summation protocol and extended to other queries including count queries, histograms, and linear combinations, meaning that it has to be readjusted and several new operations have to be added when facing different queries. By contrast,PMDP is a framework and all of its details have been explained; thus it can be easily applied to different queries. So the generality and usability ofDPStar is not as well asPMDP. From what has been mentioned above, we can conclude thatDPStar has good security properties and important practical significance, and ourPMDP framework has advantage over it in delegation of storage, distributed computing, generality, and usability. As a reinforced version ofPMDP,sPMDP also has advantage overDPStar in security model, and we prove this in the next section.


## 7. Security EnhancedPMDP Framework

The main reason that thePMDP framework suffers from the above attacks is that too much information is accessible to participants. If the intermediate result Oj of each group Gj is unknown to each one, then some attacks are not effective anymore. Furthermore, the aggregated result O and noise η0 should also be not available to any participant; otherwise the adversary with strong background knowledge might be able to infer users’ inputs. Motivated by the above observations, we propose a security enhancedPMDP framework (sPMDP for short).Since the initialization mechanism and cryptography primitives used in thesPMDP framework are similar to that inPMDP, we briefly introduce its details. As shown in Figure 2, thesPMDP framework consists of the following stages.Figure 2
Security enhancedPMDP framework.Stage
0. Initialize the system as in thePMDP framework.Stage
1. N parties encrypt their inputs with multikey FHE and upload the resulting ciphertexts to the cloud server.Stage
2. Parties decide the method of sampling and partitioning and obtain groups {Gj∣1≤j≤l∗}.Stage
3. Each party samples a noise ηi as the agent does in thePMDP framework, and all parties calculate the ciphertext of the average noise of all parties with the help of an on-the-fly MPC protocol. Particularly, we use the protocol without the decryption, and the ciphertext of average noise will be used in the next stage. The average noise is denoted by η¯ and its ciphertext is denoted by η¯enc. The value of η¯ will not be known by any entity in the whole procedure.Stage
4. All parties (or an agent of all parties) firstly merge the original function F to be computed on each group and the aggregation function for all groups Λagg into one function F′, which is taken as inputs of all parties’ inputs (38)F′=MergeF,Λagg=ΛaggFGj,j=1,…,l∗. Moreover, let F∗ denote the sum of F′ and η¯: (39)F∗=F′+η¯.Then, the function F∗ is represented as a circuit C∗, and the cloud server computes (40)o∗⟵EvalC∗,c1,pk1,ek1,…,cN,pkN,ekN. The cloud server also produces succinct arguments {φi∗}i∈[N] for the NP language L∗ similar to the language L in the original framework.Stage
5. Each party Pi runs the algorithm (41)VerifyΦpki,eki,hki,dii∈N,φi∗,to verify the validity of the argument φi∗. If the verification is successful for all parties in the same group, they run an MPC protocol Πdec∗ to compute the function(42)ODP=go∗,pk1,ek1,…,pkN,ekNsk1,r1,…,skN,rN=defDecsk1,…,skN,o∗,ifPversuc,⊥,otherwise,Pversuc=pki,ski,eki=Keygen1κ;ri,∀i∈N,and ODP is released as the final result.As to the security of sPMDP against malicious adversaries, we prove it from two different perspectives. Firstly, we demonstrate the security by theoretical proof. The difference betweenPMDP andsPMDP  is obvious. InsPMDP, we integrate the operations of sampling, aggregation, generating, and adding noise into the on-the-fly MPC scheme, thus letting the on-the-fly MPC scheme provide global security guarantee. The aim of merging functions is to turn the original evaluation function and the function of average noise addition into one function conducted by the cloud, thus protecting the amount of noise against malicious participants. Another advantage of merging functions besides enhancing security is that it optimizes the structure ofPMDP framework, reducing participants assignments and achieving a better combination between different techniques. SosPMDP is a tighter combination between MPC protocol and differential privacy. It has been proved in [23] that the on-the-fly MPC scheme is secure against malicious adversary, which means thatsPMDP is secure under malicious model. So the security property ofsPMDP is better thanPMDP andDPStar. It is remarkable that the computation of encrypted average noise also uses the on-the-fly MPC scheme, thus ensuring that no one will know about others’ noise or the value of average noise.Now we roughly explain the security of thesPMDP framework from another perspective. Note that each party insPMDP only knows his/her own input xi, noise ηi, and the final result ODP. With all these values, each party can only get the equation (43)F∗xi,ηi,i=1,…,N=ODP;that is to say (44)F′xi,i=1,…,N+1NU∑i=1NUηi=ODP.Because there is at least one honest party, w.l.o.g., we assume that party P∗ is honest, who will not reveal his input xP∗ and noise ηP∗ to others. Therefore there are at least two unknowns, namely, xP∗ and ηP∗, in (44) for parties other than P∗. From the perspective of solutions of the equation, the equation has infinitely many solutions when it has more than one unknown with no more conditions. Therefore the input and the noise of party P∗ will always be unknown to others. Again, we see that insPMDP the privacy of honest parties will be preserved.As the cost of stronger security guarantees, the computation overhead of each party insPMDP is larger than that inPMDP, and the additional part comes from the computation of the encrypted average noise in Stage 4. Overall, its computation cost also follows the on-the-fly MPC protocol.


## 8. Conclusion

In this work we focus on the problem of how to preserve multiparty data privacy throughout its lifecycle in cloud computing and propose a privacy-reserving framework namedPMDP. This framework is built upon the on-the-fly MPC, sampling, partitioning, and aggregation mechanisms, and differential privacy, thus guaranteeing input privacy, computational privacy, and output privacy in cloud computing simultaneously, even if the cloud server is untrusted. The security analysis shows that the framework can achieve intended security goals in the honest model. To conquer those potential attacks in the semihonest model, we further present a security enhancedPMDP framework. The performance discussion indicates that the proposed framework owns advantages in security guarantees and thus is more desirable for secure multiparty data aggregation and publishing.



---

*Source: 6097253-2017-12-12.xml*