Hybrid Privacy Scheme
Yavor Litchev, Abigail Thomas

Abstract
Local Differential Privacy (LDP) is a security algorithm thatallows a central server to compute on data submitted bymultiple users while maintaining the privacy of each user
(Bebensee 2019). LDP is an efficient approach to privacy
because it runs very quickly; however, as privacy increases,
the accuracy of the computations decreases. Multi-Party
Computation (MPC) is a process by which multiple parties
work together to compute the output of a function without
revealing their individual information (Goldreich 1998).
MPC is highly secure and accurate for such computations,but it is very computationally expensive and slow. The
proposed hybrid privacy model harnesses the benefits ofboth LDP and MPC to create a secure, accurate, and fastalgorithm for machine learning.
Keywords: privacy, local differential privacy, multi-party
computation

Introduction
People are becoming more and more aware of the importance of data privacy, as secret data breaches could negatively impact subjects. Instances such as identity fraud,
stalking, and surveillance directly infringe on the rights andliberties of individuals. Moreover, leaked critical data could
result in discrimination, economic losses, or even physical injury to individuals. For example, protecting medical
records of individuals is crucial as it could result in future
job discrimination, harassment, etc. Another example that illustrates the importance of privacy is the protection of voter
identities as the leakage of such can make voters feel insecure, and as a result, not vote in their best interest, thus
compromising the effectiveness of the political system. As
shown by the examples, the protection of data privacy, while
computations are being done on it, is crucial.
There are many existing algorithms designed to protect
data privacy. Some of them achieve this by changing theunderlying mechanism. One example is Federated Learning (Yang et al. 2019). It is a type of distributed machinelearning algorithm where a number of machines, each witha piece of data stored locally, train a model jointly. It is
assumed to protect data privacy because the machines do
Copyright © 2021, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved.

not have to exchange the raw data with each other. However, even if they do not transmit the raw data, propertiesof the private data can still be inferred from the gradient information they shared with each other (Yang et al. 2019).
Therefore, information about the data is still leaking. In thisproject, we would like to propose a scheme that takes information leakage other than the raw data into consideration.
Besides designing a new scheme, there are also generalefforts to protect data privacy. Data encryption converts theplaintext data into ciphertexts. Without a decryption key, theciphertexts look like random bits. However, this only serves
store-only purposes. Because of the security, no meaningful operations can be done on the ciphertexts. Homomorphic encryption schemes allow a party to perform computations directly on the ciphertexts while hiding the plaintexts(Gentry and Boneh 2009). Using homomorphic encryption
could trivially eliminate privacy leakage, but as of today, it
is too computationally expensive to be deployed in the realworld. Differential privacy schemes add random noise to thedata to hide the plain contents (Bebensee 2019). Differential privacy schemes are usually efficient because they only
incur an overhead of sampling the random noise and later
aggregating them. However, this leads to inaccurate results.
Secure Multi-Party Computation (MPC) is a type of cryptographic protocol that allows multiple parties to compute afunction regarding their private inputs without leaking any
computationally reasonable information regarding these private inputs (Goldreich 1998; Beaver and Goldwasser 1989;
Damgård et al. 2009; Canetti et al. 1996). MPC produces
accurate computation results. However, similar to homomorphic encryption schemes, MPCs are usually computationallyexpensive.
In this paper, we present a hybrid approach to combine theadvantages of differential privacy and MPC to protect data
privacy with reasonable efficiency and accuracy. We also define a new notion of privacy considering both the loss implied by the final model (or the forwarding result computedby this model) and the loss during the training process. We
also formally prove that our approach is secure. Our scheme
provides a parameterized tradeoff between accuracy and privacy. We also present a theoretical analysis of the scheme.
We implemented this hybrid approach on a support vector
machine in order to train a model using the MNIST dataset.
The model (when a MASCOT MPC protocol is used in theHybrid Model) achieves an accuracy of 91% compared to
the LDP baseline accuracy of 89%, and the model takes
roughly 19 hours to run compared to the projected MPC
baseline runtime of approximately 190 hours, showing that
our hybrid model is better than each of the individual algorithms. These results are still seen when different MPC protocols are used: with a semi-honest Shamir secret sharing
MPC protocol, the Hybrid Model achieves an accuracy of
96% as opposed to 89%, and takes about 19 minutes to run
as opposed to 3 hours. Finally, when malicious Shamir secretsharing MPC protocol is used, the Hybrid Model reaches
an accuracy of 96% as opposed to 89%, and takes approximately half an hour to run as opposed to over 5 hours.
This paper is organized as follows: Related Works outlines existing security algorithms, the Hybrid Privacy for
Federated Learning section describes in more detail eachof the algorithms, the Hybrid Model section outlines the
specifics of our Hybrid Model as well as a short proof on
why it is secure, the Evaluation presents and discusses theresults from our model, and the Conclusion summarizes thesignificance of our findings.

1989; Damgård et al. 2009; Canetti et al. 1996) is a familyof cryptographic protocols that allow a number of parties tocollaboratively compute a function y = f (x1 , x2 , . . . , xn )where xi is a private input from the i-th party, such thatexcept any information can be inferred from y (which isinevitable as y will be made public), no other information
about xi is revealed. The privacy guarantee from MPC isstrong. However, similar to homomorphic encryption, MPC
schemes usually incur a large computational overhead compared to computing the target function f natively. There
have been efforts in applying MPC in machine learning (Juvekar, Vaikuntanathan, and Chandrakasan 2018; Riazi et al.
2018; Rouhani, Riazi, and Koushanfar 2018).

Related Works

Definition of Federated Learning

Federated Learning (Kairouz et al. 2019) is a machine learning scheme that allows a number of parties to collaboratively
train a model with their data kept in local storage. It mitigates the data privacy concern by not exchanging the raw
data over the network. It has many applications, especiallyin scenarios where data privacy is critical, such as medical
records (Ju et al. 2020). However, even though the algorithm
does not send training data, some aggregated information
about the training data could leak by the communication data
(e.g. the gradients) (McMahan et al. 2017; Bonawitz et al.
2017).
To protect the data privacy further, a number of approaches are explored in recent literature. Encrypting thedata and operating directly on ciphertexts (Popa et al. 2011)
could provide computationally secure privacy because without a decryption key, the ciphertexts look similar to random bits. A number of schemes are proposed to train amodel over encrypted training data (Gilad-Bachrach et al.
2016; Chou et al. 2018; Hesamifard, Takabi, and Ghasemi
2017; Bourse et al. 2018; Zhang et al. 2020). But the resulting overhead from techniques like homomorphic encryption (Gentry and Boneh 2009) prohibits heavy tasks liketraining a large scale machine learning model from being
used in practice. Another paradigm that can mitigate the privacy issue is differential privacy (DP) (Dwork 2008). Differentially private schemes proceed by adding controlled noise
to the input data such that distinguishing two datasets thatdiffer minimally is statistically difficult. DP has already beenused in improving machine learning privacy (Mohassel and
Zhang 2017; McMahan et al. 2017; Gong et al. 2020). However, differential privacy by its definition sacrifices the accuracy of the results, namely, the model from a differentiallyprivate training algorithm would always be away from optimality. Moreover, the more privacy the scheme guarantees,
the less accuracy the users enjoy. Secure Multi-Party computation (MPC) (Goldreich 1998; Beaver and Goldwasser

Federated Learning is formally defined as follows:
Definition 1. Federated Learning Define N data owners
F1 , ...FN , all of whom wish to train a machine learningmodel by consolidating their respective data D1 , ...DN . A
conventional method is to put all data together and use
D = D1 ∪ ... ∪ DN to train a model MSU M . A federated
learning system is a learning process in which the data owners collaboratively train a model MF ED , in which process
any data owner Fi does not expose its data Di directly toothers. Often, a central server that is computationally powerful is involved (Yang et al. 2019).
More generally, we formalize the federated learning process as a multi-round query-answer protocol, where the central server, which does the computation in each round r,(r)
sends a query qi to the data owner Fi iteratively, and upon(r)
receiving the query Fi , computes answers ai based on
their local data Di . With these answers, the central server
updates the weights of the model. Finally, the trained modelis revealed.
In the process of federated learning, the local data is notdirectly exposed, but since an aggregated result related to thedata is transmitted to the central server, we argue that important statistical properties about the local data are still leaked.
Such leakage in some situations could harm privacy. For
example, multiple healthcare institutes with private patient
information participate in a collaborative machine learning
task. An average of the geographical information could directly reveal the community identity of the cohort. In anotherscenario, the average income of citizens within a certain area
can be used to accurately estimate the salaries of people inthat area, thus revealing personal financial information.

Hybrid Privacy for Federated Learning
Now that we have outlined the intuition behind some otherprivacy schemes, let us formally introduce federated learning, LDP, and MPC. The following section will also qualify
what information is revealed during such schemes. This will
be important later on when qualifying the level of privacy
guaranteed by the hybrid scheme.

Definition of Local Differential Privacy
Local differential privacy is an algorithm that protects
individual inputs by locally adding random noise to theindividual user’s inputs before performing computations
on the data. This protects each user’s privacy because thetrue values are masked by a margin of uncertainty due
to the noise, which gives users plausible deniability as towhat their actual inputs are. However, even with the added
noise, one can still analyze general trends and perform
computations on the data, albeit less accurately due tothe noise. This provides a powerful and simple privacy
mechanism.
Local Differential Privacy is formally defined as follows:
Definition 2 (LDP Security). We say that an algorithm πsatisfies ε-Local Differential Privacy where ε > 0 if andonly if for any input v and v 0 that are adjacent∀y ∈ Range(π) :Pr[π(v) = y]≤ eεPr[π(v 0 ) = y]where Range(π) denotes every possible output of the algorithm π (Bebensee 2019).
In terms of a query-answer model, one way to make theprotocol differentially private is to add noise to the answers
generated by data owners:
g
(r)
(r)
ai = ai + e,
where e denotes random noise. Since each party submitsg(r)
ai to the protocol, the protocol leaks the users’ noisy datawhen active. Furthermore, by publicizing the final result of
the protocol, the aggregate information of the users’ noisy
data is also leaked. However, this information is not enoughto leak individual user’s data; therefore, LDP is acceptably
secure in ensuring privacy to the users.

Definition of Multi-Party Computation
An MPC protocol is an algorithm where parties jointly compute a function given private user inputs. What makes MPC
so powerful is that no information that could be used to reveal the users’ inputs is leaked, aside from information thatthe final function value reveals. Specifically, the intermediary values leaked while jointly computing the function value
cannot be used to infer the individual inputs from the parties.
In terms of our query-answer model, we have N parties
F1 , . . . FN , each with data D1 , . . . DN . They seek to compute f (D1 , . . . DN ). The parties follow a specific protocol(r)where Fi sends a query qi,j,k to party Fj , where k represents
the kth interaction between the two parties and r represents(r)round r. Party Fj sends party Fi answer ai,j,k , where party(r)

Fj may now perform computations on ai,j,k and perform
additional queries/receive additional answers. The specificqueries and answers depend on the MPC protocol, however
through these queries the parties compute f (D1 , . . . DN )without revealing D1 , . . . DN .
Now, let us define the terms used to define MPC security.
Denote the set of corrupted parties C, who may collaborate

and share additional values private to themselves besides
those publicly available. Denote the fault tolerance of an
MPC f . The fault tolerance is the maximum number ofparties that may be corrupt in an MPC scheme while stillpreserving user privacy. Let xi and yi be inputs and outputs
from party Fj , and viewj is Fj ’s view of the program
during the simulation.
Definition 3 (MPC Security). An MPC protocol is called
secure if there exists an efficient simulator S such thatthe simulated message transcript S({xj , yj }Fj ∈C ) :={viewj }Fj ∈C and the real leaked values {viewj }Fj ∈Chave computationally indistinguishable distributions: forany transcript t̄ ∈ {viewj }Fj ∈C and t ∈ {viewj }Fj ∈C ,for any p.p.t. adversary A, the distribution of t and the distribution of t̄ are computationally indistinguishable.
The MPC protocol guarantees that a minimal amountof information is leaked regarding the users’ inputs;
however, it is still important to note this leakage. The
final function output of the MPC may be used to infer
information regarding the users. However, this leakagepresents minimal risk for a party’s privacy since the output
function contains only aggregate information regarding theusers’ inputs. Since this protocol will be paired with LDP
later on, it is also important to consider LDP’s leakage.
LDP leaks the parties’ noisy data as well as the aggregate
information of the users’ data. Thus, when the MPC phaseruns after the LDP phase, the difference in the aggregate
information publicized after the LDP phase to that after
the MPC and LDP phases can be used to compute theaggregate information of just the MPC phase. However,as described earlier, the risk posed by the leakage ofthis information is minimal. Furthermore, the leakage
of information from the LDP phase can be mitigated by
not revealing the aggregate information after the LDP phase.
Now that we have defined Federated Learning, LDP, and
MPC, let us describe the hybrid model.

The Hybrid ModelIn this subsection, we introduce our Hybrid Model. We firstpresent a pseudocode algorithm, and then formally define
the security for such a protocol, followed by a proof of security.

Pseudocode
The pseudocode of the hybrid privacy scheme is shown in
Algorithm 1. We define the functions and variables used asfollows:
addN oise(x): adds sufficient noise to input value x suchthat ε-Local Differential Privacy is satisfied.
train(x1 , x2 , . . . xN , weights): performs a training algorithm such that the variable weights is modified based on
input values x1 , x2 , . . . xN . The output of the function are
the weights to a specific party (the weights are not necessarily publicized).
cW eights: Weights that are only known by the central
server.

Algorithm 1: Hybrid privacy algorithm(r)Input: N parties each with answer xi = ai , where(r)
ai is computed from Di for
i ∈ {1, 2, . . . N },array of weights all equal to 0;
Result: Weights will be trained and optimized
securely
Initialization:// Each Party computes x0i locallyfor i=1 to N do
x0i = addN oise(xi );end
cWeights = trainLDP (x01 , x02 , . . . x0N , weights)// LDP Portion// Switch to MPC when model has
reached peak performance during
LDP
weights = trainM P C (x1 , x2 , . . . xN , cW eights)// MPC Portion

trainLDP (x1 , x2 , . . . xN , weights): trains the weights inaccordance with the LDP protocol. It is assumed that
x1 , x2 , . . . xN are already noisy, so essentially trainLDP () =train(). The trained weights are only revealed to the centralized server.
trainM P C (x1 , x2 , . . . xN , cW eights): trains the weights
using an MPC protocol, such that all operations present
in train() are securely performed to satisfy MPC privacy.
Trained weights are made public after training.
Round rs denotes the switch point. rs is determined before the protocol commences such that rounds
1, 2, . . . , rs − 1 optimize the model to its peak performance,
and then the switch point occurs. Rounds 1, 2, . . . , rs − 1
are the differential privacy phase. Rounds rs + 1, . . . , rn are
the secure multiparty computation phase. The query-answer
protocol proceeds in two phases.
The Differential Privacy Phase: Users will first add
noise to their data Di . The central server will start withan array of weights all equal to 0. For each round r ∈(r){1, . . . rs − 1}, the central server sends query qi to Fi forg(r)
i ∈ {1, . . . N }. Fi sends ai to the central server, whereg(r)
ai is defined under the definition of Local Differential Privacy. The central server then trains the weights using thetrainLDP () algorithm.
The Switch Point On round rs , the LDP training willstop. The weights that the central server has (cW eights) are
not revealed and will instead be submitted directly to the
MPC protocol as if the central server is a party FN +1 withdata DN +1 , where DN +1 = cW eights.
The Secure Multiparty Computation Phase: Forround r ∈ {rs + 1, . . . rn }, the parties seek to com-pute trainM P C (x1 , x2 , . . . xN , cW eights), where x1 =D1 , x2 = D2 , . . . xN = DN , weights = DN +1 =cW eights . trainM P C () performs the exact same operations
as trainLDP (), except that such operations are performed
in a manner that is compliant with the security definition
for MPC. For more information regarding the query-answer
model for MPC and its security, please refer to the subsection that defines MPC. cW eights will be made public after
the MPC phase.

Security of the Hybrid Model
Now that the protocol of the Hybrid Model is established,
the next section explains privacy is preserved during the execution of the protocol. This is done by first defining the security of a Hybrid Protocol and then proving the model satisfies
such security. Hybrid Security is informally defined throughthe security of the MPC-phase of the protocol and states thatthe Hybrid Model is secure as long as the MPC-protocol remains secure despite LDP leakage. More formally:
Definition 4 (Hybrid Security). We say a Hybrid Model issecure if there exists an efficient simulator S such that, given
the answers in the DP phase, the simulated message tran(r)sscript S({ai }|rr=1, {xj , yj }Fj ∈C ) := {viewj }Fj ∈C andthe real leaked values {viewj }Fj ∈C are close: for any transcript t̄ ∈ {viewj }Fj ∈C and t ∈ {viewj }Fj ∈C , for any
p.p.t. adversary A
Pr[A(t) = 1] ≤ eε Pr[A(t̄) = 1]
for a constant ε. We say such a scheme satisfies ε Hybrid
Model privacy.
We now seek to prove the security of our Hybrid Model.
This will be accomplished by first constructing a simulator
for the Hybrid Model. We will then show that if there exists
an adversary that can break the Hybrid Model, then there
must also exist another adversary that can break the LDP
security using the simulator and the first adversary. This will
break an earlier assumption that LDP is secure, which will
form a contradiction. Thus, we will create a sketch of a proof
by contradiction.
Theorem 1. Assume the MPC protocol is secure, and the
LDP is ε differentially private, then the hybrid protocol issecure.
We sketch the proof of the above theorem using a proof
by contradiction.
Proof: Assume the MPC protocol is secure, and denote its
simulator SM P C . Let us define a simulator S as follows:
1. The simulator virtually runs N parties and the central
server, exactly following the hybrid protocol.
2. trainLDP () is performed using Di ∈ C where C is
the set of corrupted parties, and uses the leaked values(r)s{ai }|rr=1
as the rest of the inputs. Although the simulator does not know the private inputs Di of the honest parties, the simulator answers the servers queries such that(r)whenever the central server queries qi to Fi in round r,(r)
the simulator will produce answer ai using leaked values given in the input.

3. After the LDP protocol finishes, everything needed for the
MPC protocol is available except for the private inputs Di
where Fi 6∈ C.
4. The simulator SM P C commences using {xj , yj }Fj ∈C .
5. Return the transcript t that is produced by the simulator
SM P C .
We proceed through a proof by contradiction. Assume
there exists an adversary AH that may compromise the security of the Hybrid Protocol. We show that with AH , wecan construct an adversary ALDP to break the security of
the LDP scheme. ALDP performs the following steps:
1. Given an LDP instance, ALDP seeks to compromise its
security. ALDP participates in the scheme per usual withother honest parties.
2. Using S, ALDP simulates a transcript t̄ for the MPC portion of the hybrid protocol.
3. ALDP then sends the combined LDP and MPC transcript
to AH .
4. By assumption, AH breaks the security of the Hybrid Protocol.
5. AH gives the output to ALDP . ALDP may now break the
LDP scheme. Since the adversary is a surjective mapping,
the fact that the distribution of the output from the adversary challenges the ε-local differential privacy indicatesthe input of the adversary also challenges the ε-local differential privacy.
6. This contradicts our earlier assumption of LDP being (ε)
differentially private. Thus, our Hybrid Protocol must satisfy ε Hybrid Privacy.
The security of the hybrid model is slightly weaker thanLDP or MPC alone if the parameters are the same, due tothe additional parameters. However, the Hybrid Model provides a better accuracy (compared to LDP) and better runtime (compared to MPC), so such a trade-off is beneficial insome cases. The parameter rs plays a role in this trade-off.
For example, if rs = 0, then the protocol degrades to a pure
M P C algorithm. If rs = rn , then the protocol degrades toa pure LDP algorithm.

Instantiation
Our project applies LDP and MPC on a Support Vector Machine (SVM) to train on the MNIST dataset, which will output a set of weights that accurately predict what digit an image is while maintaining the privacy of the users who submit images. The model consists of 3 main parts: LDP, MPC,
and the point where the algorithm switches from LDP to
MPC. As described earlier, using just LDP or MPC to compute a function (in our case to train an SVM) has both costs
and benefits, and we wish to reap the benefits of both approaches. This is where the switch point comes in. The idea
is that the SVM is trained through LDP for some time using
MNIST images with added noise. After the loss reported by
the SVM reaches a plateau, the weights transfer to an MPC
framework where they are further modified based on unaltered images of the MNIST data set. This way, the SVM

can be trained quickly with LDP for most of the way until it
approaches the global minimum of the loss function. Afterthe loss function plateaus, the SVM can transfer to an MPC
framework, which will allow the SVM to get much closer tothe global minimum because it is now training on the actual
pixel values of the images. Since the SVM has been trained
most of the way, it will spend less time on the much slower
MPC calculations. As a result, we get a fast, secure, and accurate algorithm.
Now, let us describe the specifics of our SVM training
program. First, the weights are initialized to 0. Although thenumber of parties is flexible, we have tested our programon five parties. Only four of the parties will submit image
data to train the model, and the final party serves as the centralized server to train the model. Our protocol implements
LDP via a random response scheme that adds noise to each
image submitted by the user (these images are all part of the
MNIST dataset). It works in the following way: consider aprobability value of l. Each pixel within an image has a 21 lchance of assigning 0 to the pixel, a 21 l chance of assigning 1 to the pixel value, and a 1 − l chance of assigning
the true value to the pixel. Then, the images are given to
the SVM to train on them via gradient descent. This grants
the parties privacy as it allows each image to have plausible
deniability to its actual value; thus, anyone who intercepts
the altered image cannot confirm the true digit of the image.
However, the totality of all the MNIST images will overcome this noise while the SVM trains on it, and as a result, asemi-accurate model can be achieved. The calculations section describes specifically how our program satisfies ε-Local
Differential Privacy based on the epsilon value that is passed
into our program, as it will then compute the necessary valueof l needed to give each image enough plausible deniability.
After the LDP phase, the weights transfer to the second
phase of the protocol, where MPC is used to securely perform the operations and functions of an SVM. Specifically,
we took an MP-SPDZ framework that has many MPC algorithms (Keller 2020). In particular, we used a MASCOT
protocol which does efficient arithmetic operations due to it
using arithmetic circuits (Keller, Orsini, and Scholl 2016).
It also provides malicious, dishonest majority computation,and therefore it has a fault tolerance of f = N − 1, where
N is the number of parties. Additionally, the MASCOT protocol uses oblivious transfer in order to achieve fast multiplication. This is useful as gradient and loss function computations use lots of multiplication; therefore, our MPC portion is as fast as possible. We have also
a semi-honest used
Shamir secret sharing protocol (f = N2 ) as well as a malicious Shamir secret sharing protocol (f = N − 1) fromthe same framework and achieved similar results to that of
MASCOT. Using one of these protocols, four users eachsubmit an image, and one user (the same user who served
as a central server for the LDP phase) submits the weights
obtained from the LDP portion to the MPC. The weights
are then further optimized using the MPC. After a new setof weights have been created, the centralized server submits
the resulting weights to the MPC again, and each of the four
users also submits a new image. This process repeats fivetimes, such that the SVM trains on 20 images during the

MPC phase. Note that the weights may be revealed after all
20 images have been used to train the SVM; the intermediary weights do not have to be revealed.
As a result, we have a secure hybrid protocol, and our
research demonstrates the ability to merge LDP and MPC.
When the two approaches are combined, the resulting algorithm is more accurate than LDP alone and faster than MPC
alone.

Calculations
Using the definition of LDP, described in the Definition ofDifferential Privacy Section, we can solve for epsilon to implement it in our local differential privacy scheme (Bebensee
2019). We implement epsilon-pixel-level DP, which guarantees security for each pixel of the input images. Though thisis a weaker notion of privacy, it is necessary to obtain usable
results without using an extremely large value of epsilon.
A low epsilon value means the images would be extremely
modified, to the point where the SVM would not be able toaccurately classify the images, making the results unusable.
Assuming we discretize the input into 0 and 1 by rounding. To get

Figure 1: Hybrid Model Accuracy Over Number of Updates.
MASCOT MPC Protocol was Used

Pr[π(v) = y] ≤ Pr[π(v 0 ) = y] · eConsider a random response scheme per pixel bi,j (the biton the ith row and jth column). The party outputs
0b0i,j = 1

bi,j

1
2l
1
2l

Figure 2: Hybrid Model Loss Over Number of Updates.
MASCOT MPC Protocol was Used

1−lwhere l is the probability of the pixel value being reassigned.
Then for a single pixel, we have∀i,j , Pr[b0i,j = 1|bi,j = 1] =11l+1−l =1− l22Pr[b0i,j = 1|bi,j = 0] =1
l2

so for a single pixel,
11
1 − l ≤ l · e222−l=⇒  ≥ lnl
Now that  is expressed in terms of l, we can use this to findl in terms of  to make this parameter adjustable.
2−l
l
2
l≥ 
e +1

 ≥ lnThe program takes in  as a parameter when running andcalculates l to be used in the random response scheme. The
experiments run in this paper use an epsilon value of ln 3,
which translates to an l value of l = 21 .

Evaluation
After running our hybrid model using the MASCOT MPC
protocol on the MNIST dataset1 , we then graphed theaccuracy and loss2 of the LDP and MPC portions of thealgorithm respectively over the number of program updates
that have elapsed3 .
The results are presented in Figure 1 and Figure 2. The
x-axis displays the number of updates. In the LDP phase,
each update consists of one input image. In the MPC phase,
each update consists of four input images. In the first figure,the y-axis graphs the accuracy when the model is evaluatedon the test dataset, whereas the second figure graphs the lossof the test dataset. Even though there are many more updates that occurred during LDP training than MPC training,the LDP portion of the program trained very quickly, taking
1.063 seconds to reach a final accuracy of 89%. However,after some initial volatility in the accuracy metric for the
LDP, the accuracy increase for the LDP stagnated. This is1

We modified the MNIST dataset such that the digit 0 appears
approximately 50% of the timeP
2
Loss Formula: J(w) = 21 ||w||2 + C[ n1 ni=0 max(0, 1 − yi ∗(w · xi + b))], where w is the weights, xi and yi are the input
images and their labels, n is the number of images, C is a constant,and b = 0
3
Data retrieved from training on computer with 8th gen core i7,
16GB RAM, no GPU

Figure 3: Hybrid Model Accuracy Over Number of Updates.
Semi-Honest Shamir MPC Protocol was Used

Figure 5: Hybrid Model Accuracy Over Number of Updates.
Malicious Shamir MPC Protocol was Used

Figure 4: Hybrid Model Loss Over Number of Updates.
Semi-Honest Shamir MPC Protocol was Used

Figure 6: Hybrid Model Loss Over Number of Updates. Malicious Shamir MPC was Used

seen in the small blue plateau on the graph shortly before the
21st update has elapsed (Figure 1). After the switch-point
occurs, the MPC portion of the program starts to train themodel, and the accuracy is optimized to reach approximately
91%. However, this process is excruciatingly slow, as the
MPC portion ran for 19 hours. This shows that although the
LDP portion quickly optimized the SVM model, it quickly
stagnated in its progression of optimizing the model. The
MPC portion that ensued was very slow, but it fine-tuned theweights even further.
Towards the middle of the LDP portion of the graph, one
may observe volatility in the accuracy of the model. We hypothesize that this is caused by the random noise that is
added to the images during the LDP phase, which at firstmodifies the model in a somewhat-random fashion. This
would lead to rapid changing of the model’s accuracy due
to the model being changed quickly, and we believe that thisleads to the volatility of the graph. However, as more images are inputted to the model, the model is already partiallytrained and therefore images with random noise do not modify the model by a significant margin.
Similar results are observed when one considers the lossof the model. The LDP portion of the training had a muchhigher loss when compared to the MPC portion of the program. Despite this, the LDP partially optimized the loss, andthe MPC further refined the loss. On the LDP portion of thegraph, one can see a spike in the loss values incurred at theat around the 17th update. We believe that this is a resultof the noise having a greater effect on the loss function due
to the weights being closer to the optimal when comparedto the start of the program and that this is not indicative offaulty weights (as shown by the LDP accuracy reaching approximately 89% at the same time as the loss spike). Clearly,
the LDP quickly produced a good yet somewhat inaccurate
model, and the MPC refined the model further.
Semi-honest and malicious Shamir MPC protocols produce very similar results when compared to the MASCOT
protocol, as is shown in Figure 3, Figure 4, Figure 5, andFigure 6. Each protocol was tested 3 times, and the resultsfor each protocol were averaged and graphed. It should be
noted that the number of updates performed during the LDP
phase could differ for each trial, but since each trial produced
at least 21 updates, and since all the trials were very close to
21 updates (no more than 2-3 updates), we only graphed 21of the LDP updates (as subsequent updates did not improvethe model by a large margin, as evidenced by the plateau of
the LDP phase in Figure 3 and Figure 5). The LDP phasefor the Hybrid Protocol that used semi-honest Shamir secretsharing had an LDP phase that lasted 1.066 seconds on average and achieved a final accuracy of 90%. The malicous
Shamir had an LDP phase that lasted 1.119 seconds on average and achieved a final accuracy of 89%. The similarity between these results and the results of the Hybrid Model with
MASCOT is expected, as the LDP phase of all three Hybrid

SVM Training
LDP Portion
Test Cost
Test Accuracy
Runtime
MPC Portion
Cost
Accuracy
RuntimeBaseline

Hybrid Model

55,718.1
0.89601.734 seconds

49,839.3
0.88781.063 seconds

1007.91
0.9721190.077 hours

2,449.83
0.908919.049 hours

Table 1: Table of Hybrid Results (with MASCOT) vs Baseline
Models are the same. However, the MPC phase of the semihonest Shamir protocol took 19.356 minutes to run, whereas
the malicious Shamir protocol took 33.055 minutes to run.
They achieved final accuracies of approximately 96%. Both
protocols were faster than the MASCOT protocol, however
all 3 MPC protocols were much slower when compared to
the LDP phase. Furthermore, we estimate that if only MPC
was used, the semi-honest Shamir protocol would take 3.226
hours to run, and the malicious Shamir protocol would take
5.509 hours. Thus, we can see through these trials that the
LDP phase quickly improved the model, whereas the MPC
phase fine-tunes the model in order to reach a higher accuracy, irrespective of the MPC protocol used.
Table 1 shows the data of the hybrid model that utilized
the MASCOT protocol, and further exemplifies the benefitsof the hybrid protocol. The hybrid model achieved a higher
accuracy and a lower loss when compared to a pure LDP
scheme. Furthermore, the hybrid model took much less time
to run than a pure MPC scheme. The table shows that should
the user desire a higher final accuracy for the hybrid model,
the MPC phase of the hybrid protocol may be prolonged inorder to achieve an accuracy and loss that approaches that ofa pure MPC scheme. Thus, we can conclude that the LDP
portion of our model quickly optimizes the weights, and the
MPC portion of our model further calibrates the weights.

Conclusion
This project aimed to create a privacy scheme that combines
existing privacy algorithms: Local Differential Privacy andMulti-Party Computation. We were able to accomplish thisusing our Hybrid Model, which harnesses the benefits ofboth algorithms and avoids the drawbacks, all while maintaining privacy. Looking at Table 1, the Hybrid Model thatutilized MASCOT achieves an accuracy of 90.9% comparedto the LDP baseline accuracy of 89.6%, and the model takes
roughly 19 hours to run compared to the projected MPC
baseline runtime of 190 hours, showing that our Hybrid
Model is better than each of the individual algorithms. We
achieved very similar results with hybrid models involving
different MPC protocols: with the semi-honest Shamir MPC
protocol, the Hybrid Model reaches an accuracy of 96% asopposed to the 89% LDP baseline accuracy, and took about
19 minutes to run as opposed to 3 hours. When the malicious
Shamir MPC protocol is used, the Hybrid Model achieves
an accuracy of 96%, compared to 89% LDP baseline accuracy, and takes approximately 30 minutes to run as opposed

to over 5 hours. These results demonstrate that our Hybrid
Model can be applied in the real world to securely perform complex computations, such as machine learning algorithms, on data. For example, many artificial intelligencemodels have been developed for disease prediction; however, the PHI they are run on must remain secure. By utilizing our Hybrid Scheme, these models can be run securely
and efficiently.

Limitations
This study has some limitations due to the computational
power of the machine used to run the model. The MPC phaseof the model only trains using twenty images. Though thesetwenty images do significantly increase the accuracy and decrease the cost, these benefits could be amplified by training
on more images. The computational power also limited what
Machine Learning algorithms we could use. Additionally,
due to the nature of Machine Learning, this Hybrid Model
will never be able to achieve completely perfect accuracy
or cost without over-fitting; however, a higher accuracy andlower cost could possibly be achieved by using a more advanced algorithm such as Convolutional Neural Networks.

Further Research
One area for future research is to implement the model onother machine learning problems. For example, the CIFAR
dataset may also be run with such a model.
Another area for future research is looking into other
MPC algorithms. The MASCOT, the semi-honest Shamir,
and the malicious Shamir protocols used in this demonstration are very robust, but there exist other MPC protocols
such as the ones based on Yao’s Garbled circuits among others.
Finally, another area for development is to implement theHybrid Model on more advanced architectures. The SVM
may have difficulties with modeling more complex datasets,
and thus the use of more complex architectures such as convolutional neural networks may be more practical in the realworld.

Acknowledgements
We would like to thank our mentor Yu Xia for his continued
support and guidance for this project, as well as the MIT
PRIMES program for giving us this research opportunity.

References
Beaver, D.; and Goldwasser, S. 1989. Multiparty computation with faulty majority. In Conference on the Theory andApplication of Cryptology, 589–590. Springer.
Bebensee, B. 2019. Local Differential Privacy: a tutorial.
Bonawitz, K.; Ivanov, V.; Kreuter, B.; Marcedone, A.;
McMahan, H. B.; Patel, S.; Ramage, D.; Segal, A.; andSeth, K. 2017. Practical secure aggregation for privacypreserving machine learning. In Proceedings of the 2017
ACM SIGSAC Conference on Computer and Communications Security, 1175–1191.

Bourse, F.; Minelli, M.; Minihold, M.; and Paillier, P. 2018.
Fast homomorphic evaluation of deep discretized neural networks. In Annual International Cryptology Conference,
483–512. Springer.
Canetti, R.; Feige, U.; Goldreich, O.; and Naor, M. 1996.
Adaptively secure multi-party computation. In Proceedingsof the twenty-eighth annual ACM symposium on Theory ofcomputing, 639–648.
Chou, E.; Beal, J.; Levy, D.; Yeung, S.; Haque, A.; andFei-Fei, L. 2018. Faster cryptonets: Leveraging sparsity for real-world encrypted inference. arXiv preprint
arXiv:1811.09953 .
Damgård, I.; Geisler, M.; Krøigaard, M.; and Nielsen, J. B.
2009. Asynchronous multiparty computation: Theory andimplementation. In International workshop on public key
cryptography, 160–179. Springer.
Dwork, C. 2008. Differential privacy: A survey of results.
In International conference on theory and applications ofmodels of computation, 1–19. Springer.

Z.; Yang, Q.; Yu, F. X.; Yu, H.; and Zhao, S. 2019. Advancesand Open Problems in Federated Learning.
Keller, M. 2020. MP-SPDZ: A Versatile Framework forMulti-Party Computation. IACR Cryptol. ePrint Arch. 2020:
521.
Keller, M.; Orsini, E.; and Scholl, P. 2016. MASCOT:
faster malicious arithmetic secure computation with oblivious transfer. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, 830–
842.
McMahan, H. B.; Ramage, D.; Talwar, K.; and Zhang, L.
2017. Learning differentially private recurrent language
models. arXiv preprint arXiv:1710.06963 .
Mohassel, P.; and Zhang, Y. 2017. Secureml: A system forscalable privacy-preserving machine learning. In 2017 IEEE
Symposium on Security and Privacy (SP), 19–38. IEEE.

Gentry, C.; and Boneh, D. 2009. A fully homomorphic encryption scheme, volume 20. Stanford university Stanford.

Popa, R. A.; Redfield, C. M.; Zeldovich, N.; and Balakrishnan, H. 2011. CryptDB: protecting confidentiality withencrypted query processing. In Proceedings of the TwentyThird ACM Symposium on Operating Systems Principles,
85–100.

Gilad-Bachrach, R.; Dowlin, N.; Laine, K.; Lauter, K.;
Naehrig, M.; and Wernsing, J. 2016. Cryptonets: Applying
neural networks to encrypted data with high throughput andaccuracy. In International Conference on Machine Learning, 201–210.

Riazi, M. S.; Weinert, C.; Tkachenko, O.; Songhori, E. M.;
Schneider, T.; and Koushanfar, F. 2018. Chameleon: A hybrid secure computation framework for machine learning
applications. In Proceedings of the 2018 on Asia Conference on Computer and Communications Security, 707–721.

Goldreich, O. 1998.
Secure multi-party computation.
Manuscript Preliminary version .
Gong, M.; Xie, Y.; Pan, K.; Feng, K.; and Qin, A. K. 2020.
A Survey on Differentially Private Machine Learning. IEEE
Comput. Intell. Mag. 15(2): 49–64.
Hesamifard, E.; Takabi, H.; and Ghasemi, M. 2017. Cryptodl: Deep neural networks over encrypted data. arXiv
preprint arXiv:1711.05189 .
Ju, C.; Zhao, R.; Sun, J.; Wei, X.; Zhao, B.; Liu, Y.; Li,
H.; Chen, T.; Zhang, X.; Gao, D.; et al. 2020. Privacypreserving technology to help millions of people: Federated prediction model for stroke prevention. arXiv preprint
arXiv:2006.10517 .
Juvekar, C.; Vaikuntanathan, V.; and Chandrakasan, A.
2018. {GAZELLE}: A low latency framework for secureneural network inference. In 27th {USENIX} Security Symposium ({USENIX} Security 18), 1651–1669.
Kairouz, P.; McMahan, H. B.; Avent, B.; Bellet, A.; Bennis,
M.; Bhagoji, A. N.; Bonawitz, K.; Charles, Z.; Cormode,G.; Cummings, R.; D’Oliveira, R. G. L.; Rouayheb, S. E.;
Evans, D.; Gardner, J.; Garrett, Z.; Gascón, A.; Ghazi, B.;
Gibbons, P. B.; Gruteser, M.; Harchaoui, Z.; He, C.; He, L.;
Huo, Z.; Hutchinson, B.; Hsu, J.; Jaggi, M.; Javidi, T.; Joshi,G.; Khodak, M.; Konečný, J.; Korolova, A.; Koushanfar, F.;
Koyejo, S.; Lepoint, T.; Liu, Y.; Mittal, P.; Mohri, M.; Nock,R.; Özgür, A.; Pagh, R.; Raykova, M.; Qi, H.; Ramage, D.;
Raskar, R.; Song, D.; Song, W.; Stich, S. U.; Sun, Z.; Suresh,
A. T.; Tramèr, F.; Vepakomma, P.; Wang, J.; Xiong, L.; Xu,

Rouhani, B. D.; Riazi, M. S.; and Koushanfar, F. 2018.
Deepsecure: Scalable provably-secure deep learning. In
Proceedings of the 55th Annual Design Automation Conference, 1–6.
Yang, Q.; Liu, Y.; Chen, T.; and Tong, Y. 2019. Federated
Machine Learning: Concept and Applications.
Zhang, C.; Li, S.; Xia, J.; Wang, W.; Yan, F.; and Liu, Y.
2020. BatchCrypt: Efficient Homomorphic Encryption for
Cross-Silo Federated Learning. In 2020 {USENIX} Annual
Technical Conference ({USENIX} {ATC} 20), 493–506.