Proceedings on Privacy Enhancing Technologies ; 2021 (1):188–208

Sameer Wagh*, Shruti Tople, Fabrice Benhamouda, Eyal Kushilevitz, Prateek Mittal, and Tal
Rabin

Falcon: Honest-Majority Maliciously Secure
Framework for Private Deep Learning
Abstract: We propose Falcon, an end-to-end 3-party
protocol for efficient private training and inference oflarge machine learning models. Falcon presents fourmain advantages – (i) It is highly expressive with support for high capacity networks such as VGG16 (ii) it
supports batch normalization which is important fortraining complex networks such as AlexNet (iii) Falcon guarantees security with abort against malicious
adversaries, assuming an honest majority (iv) Lastly,
Falcon presents new theoretical insights for protocol
design that make it highly efficient and allow it to outperform existing secure deep learning solutions. Compared to prior art for private inference, we are about 8×
faster than SecureNN (PETS’19) on average and comparable to ABY3 (CCS’18). We are about 16 − 200×
more communication efficient than either of these. For
private training, we are about 6× faster than SecureNN,
4.4× faster than ABY3 and about 2−60× more communication efficient. Our experiments in the WAN setting
show that over large networks and datasets, compute
operations dominate the overall latency of MPC, as opposed to the communication.
Keywords: Multi Party Computation, Secure Comparison, Deep Learning, Neural Networks
DOI 10.2478/popets-2021-0011
Received 2020-05-31; revised 2020-09-15; accepted 2020-09-16.

1 Introduction
With today’s digital infrastructure, tremendous
amounts of private data is continuously being generated– data which combined with deep learning algorithms*Corresponding Author: Sameer Wagh: Princeton University & UC Berkeley, E-mail: swagh@princeton.edu
Shruti Tople: Microsoft Research, E-mail:shruti.tople@microsoft.com
Fabrice Benhamouda: Algorand Foundation, E-mail: fabrice.benhamouda@normalesup.org
Eyal Kushilevitz: Technion, E-mail: eyalk@cs.technion.ac.il
Prateek Mittal: Princeton University, E-mail: pmittal@princeton.edu
Tal Rabin: Algorand Foundation, E-mail: talrny@yahoo.com

can transform the current social and technological landscape. For example, distribution of child exploitative imagery has plagued social media platforms [1, 2]. However, stringent government regulations hamper automated detection of such harmful content. Support for secure computation of state-of-the-art image classification
networks would aid in detecting child exploitative imagery on social media. Similarly, there is promise in analyzing medical data across different hospitals especiallyfor the treatment of rare diseases [3]. In both these scenarios, multiple parties (i.e., social media platforms or
hospitals) could co-operate to train efficient models thathave high prediction accuracy. However, the sensitive
nature of such data demands deep learning frameworks
that allow training on data aggregated from multiple entities while ensuring strong privacy and confidentiality
guarantees. A synergistic combination of secure computing primitives with deep learning algorithms would
enable sensitive applications to benefit from the highprediction accuracies of neural networks.
Secure multi-party computation (MPC) techniques
provide a transformative capability to perform secure
analytics over such data [4, 19, 20]. MPC provides a
cryptographically secure framework for computations
where the collaborating parties do not reveal their secret data to each other. The parties only learn the output of the computation on the combined data while revealing nothing about the individual secret inputs. Recently, there has been research in reducing the performance overhead of MPC protocols, specifically tailoredfor machine learning [5, 8, 9, 11, 12]. In this work, we focus on advancing the research in other dimensions suchas expressiveness, scalability to millions of parameters,
and stronger security guarantees (where parties can arbitrarily deviate from the protocol) that are necessary
for practical deployment of secure deep learning frameworks. We present Falcon — an efficient and expressive
3-party deep learning framework that provides support
for both training and inference with malicious security
guarantees. Table 1 provides a detailed comparison of
Falcon with prior work.
Contributions. Our contributions are as follows:

189

Framework

PrivateCapability

Threat
Model

#
#
#
#

#
#
#
#
#

Supported
LayersTechniques
Used

LAN/
WAN

2PC

3PC

4PC

ABY3 [11]SecureNN [12]CryptFlow [13]QuantizedNN [14]*ASTRA [15]BLAZE [16]Falcon (This Work)FLASH [17]Trident [18]

#
#
#
#

#
G
#
G
#

Net
VGG
-16

[6]

Alex

[5]

Fro
m

LeN
et

[4]

Fro
m

age
Net

Fro
m

y Im

Evaluation
DatasetTheoretical Metrics
MiniONN [6]
Chameleon [5]EzPC [7]Gazelle [8]SecureML [4]
XONN [9]Delphi [10]

Tin

C IF
AR1

MN
IST

WA
N

LAN

SS

GC

0

-No
rm

l

Bat
ch

HE

LU
poo
Max

tion

t Re

volu

Exa
c

Con

i-ho
nest
Mal
icio
us
Line
ar

Sem

ing
Tra
in

Infe
re

nce

Falcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning

Network
Architectures

Evaluation Metrics
#
#
#
#
#
G
#
#

#
#
G
#
G
#
#
#
#
#

#

#
#

#
#
G
#
#

#
#
#
#
G
#
#
#
#
#
#

#
#
#
#
#

#
G
#
G

#

#
#

#
G
#

#
#
#
#
#
#
G
#

#
#
#
#
#
#
#

#
#
#
#
G
#
#
#

#
#
#

#

#

#

#

#
#
#

#
#
#

G
#
#

#
#

#
#
#
#
#
#
#
#
#

#
G
#
#
#
#
#
#

#
#
#
#
#
G
#
#
G

#
#
#

#
#
#
#
#
#

#
#
G
#
#
G
#
#

#
#

#
#

#
#

Table 1. Comparison of various private deep learning frameworks. Falcon proposes efficient protocols for non-linear functionalities
such as ReLU and batch normalization (1) purely using modular arithmetic (2) under malicious corruptions (3) supporting both private training and inference. Falcon also provides a comprehensive evaluation (1) over larger networks and datasets (2) extensively
compares with related work (3) provides newer insights for future directions of PPML.
indicates the framework supports a feature,# indicates not supported feature, and G# refers to fair comparison difficult due to the following reasons: SecureNN provides malicious
privacy but not correctness and supports division but not batch norm, XONN supports a simplified batch norm specific to a binary activation layer, ABY3 does not present WAN results for neural networks, Chameleon evaluates over a network similar to AlexNet but
using the simpler mean-pooling operations, and due to the high round complexity and communication, SecureML provides an estimate of their WAN evaluation, Delphi evaluates over network such as ResNet-32, CryptFlow evaluates networks such as DenseNet-121,
ResNet-50, uses weaker network parameters in LAN and uses ImageNet dataset. QuantizedNN uses inherent quantization of the underlying NN and performs extensive evaluation over MobileNet architectures and * refers to 3PC version among the 8 protocols. BLAZE
uses a Parkinson disease dataset, similar in dimension to MNIST. FLASH and Trident use few other smaller datasets in their evaluation
as well as evaluate over increasing number of layers over the network architecture from [4].

(1) Malicious Security: Falcon provides strong security guarantees in an honest-majority adversarial setting. This assumption is similar to prior work where
majority of the parties (e.g., 2 out of three) behave honestly [11, 21]. Falcon proposes new protocols that are
secure against such corruptions and ensure that either
the computation always correctly completes or aborts
detecting malicious activity. We achieve this by designing new protocols for the computation of non-linear
functions (like ReLU). While MPC protocols are very
efficient at computing linear functions, computing nonlinear functions like ReLU is much more challenging. We
propose solutions both for the malicious security modeland provide even more efficient protocols where semihonest security is sufficient. We formally prove the security of Falcon using the standard simulation paradigm(see Section 4.1). We implement both the semi-honest
and malicious protocols in our end-to-end framework.
In this manner, Falcon provides a choice to the developers to select between either of the security guarantees

depending on the trust assumption among the parties
and performance requirements (improved performancefor semi-honest protocols).
(2) Improved Protocols: Falcon combines techniques from SecureNN [12] and ABY3 [11] that result in
improved protocol efficiency. We improve the theoreticalcomplexity of the central building block – derivative of
ReLU – by a factor of 2× through simplified algebra for
fixed point arithmetic. We demonstrate our protocols
in a smaller ring size, which is possible using an exact
yet expensive truncation algorithm. However, this enables the entire framework to use a smaller datatype,thus reducing their communication complexity at least
2×. This reduced communication is critical to the communication improvements of Falcon over prior work.
Furthermore, as can be seen in Section 5, these theoretical improvements lead to even larger practical improvements due to the recursive dependence of the complex
functionalities on the improved building blocks. Overall,
we demonstrate how to achieve maliciously secure pro-

Falcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning

tocols for non-linear operations using arithmetic secretsharing and avoiding the use of interconversion protocols (between arithmetic, Boolean and garbled circuits).
(3) Expressiveness: Our focus is to provide simple
yet efficient protocols for the fundamental functionalities commonly used in state-of-the-art neural networks.
Batch normalization, has been previously considered in
privacy-preserving inference as linear transformation using Homomorphic Encryption [22–24]. However, batchnormalization is critical for stable convergence of networks as well as to reduce the parameter tuning required
during training of neural networks. Falcon demonstrates full support for Batch-Normalization layers,both forward and backward pass, in private machinelearning. In other words, Falcon supports both private
training and private inference. This extensive support
makes Falcon expressive, thereby supporting evaluation of large networks with hundreds of millions parameters such as VGG16 [25] and AlexNet [26] over datasets
such as MNIST [27], CIFAR-10 [28] as well as Tiny
ImageNet [29] including in both the LAN and WAN
network settings. Designing secure protocols for training is more difficult due to the operations involved inback-propagation which are not required for inference.
A number of prior works assume training in a trusted environment and hence provide support for only inference
service [5–9]. However, sensitive data is often inaccessible even during training as described in our motivating
application in Section 2.
End-to-end Implementation and Results. We
implement both the semi-honest and malicious variantsof Falcon in our end-to-end framework. The codebase
is written in C++ in about 14.6k LOC and will be open
sourced. We experimentally evaluate the performance
overhead of Falcon for both private training and inference on multiple networks and datasets. We use 6 diverse networks ranging from simple 3-layer multi-layer
perceptrons (MLP) with about 118, 000 parameters tolarge networks with about 16-layers having 138 million
parameters. We trained these networks on MNIST [27],CIFAR-10 [28] and Tiny ImageNet [29] datasets as appropriate based on the network size. We note that Falcon is one of the few private ML frameworks to support training of high capacity networks such as AlexNet
and VGG16 on the Tiny ImageNet dataset. We perform extensive evaluation of our framework in both the
LAN and WAN setting as well as semi-honest and malicious adversarial setting. For private inference, we are
16× faster than XONN [9], 32× faster than Gazelle [8],8× faster than SecureNN, and comparable to ABY3 on
average. For private training, we are 4.4× faster than

190

ABY3 and 6× faster than SecureNN [12]. Depending on
the network, our protocols can provide up to an order ofmagnitude performance improvement. Falcon is up to
two orders of magnitude more communication efficientthan prior work for both private training and inference.
Our results in the WAN setting show that compute operations dominate the overall latency for large networks
in Falcon and not the communication rounds. Hence,
Falcon is an optimized 3-PC framework w.r.t. the communication which is often the bottleneck in MPC.

2 Falcon Overview
Next, we describe the application setting for Falcon, provide a motivating application, state the threat
model, and an overview of our technical contributions.

2.1 A 3-Party Machine Learning Service
We consider the following scenario. There are two
types of users, the first own data on which the learningalgorithm will be applied, we call them data holders.
The second are users who query the system after thelearning period, we call these query users. These two
sets of users need not be disjoint. We design a machinelearning service. This service is provided by 3 parties
which we call computing servers. We assume that government regulations or other social deterrents are sufficient enforcers for non-collusion between these computing servers. The service works in two phases: the training phase where the machine learning model of interest
is trained on the data of the data holders and the inference phase where the trained model can be queriedby the query users. The data holders share their data
in a replicated secret sharing form [30] between the 3computing servers. These 3 servers utilize the shareddata and privately train the network. After this stage,
query users can submit queries to the system and receive
answers based on the newly constructed model held inshared form by the three servers. This way, the dataholders’ input has complete privacy from each of the 3
servers. Moreover, the query is also submitted in sharedform and thus is kept secret from the 3 servers.
Recent advances in MPC have rendered 3PC protocols some of the most efficient protocols in the spaceof privacy-preserving machine learning. Though MPC is
not a broadly deployed technology yet, the 3PC adversarial model has enjoyed adoption [31–33] due to theirefficiency and simplicity of protocols. Below, we describe
a concrete motivating application that would benefit
from such a 3-party secure machine learning service.

Falcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning

2.1.1 Motivating Application: Detection of Child
Exploitative Images Online
In recent years, the distribution of child exploitative
imagery (CEI) has proliferated with the rise of social
media platforms – from half a million reported in between 1998-2008 to around 12 million reports in 2017and 45 million in 2018 [1, 2]. Given the severity of the
problem and stringent laws around the handling of such
incidents (18 U.S. Code §2251, 2252), it is important
to develop solutions that enable efficient detection andhandling of such data while complying with stringent
privacy regulations. Given the success of ML, especiallyfor image classification, it is important to leverage MLin detecting CEIs (a computer vision application). Falcon’s approach, in contrast to deployed systems suchas PhotoDNA [34], enables the use of ML for this usecase. However, the inability to generate a database of
the original images (due to legal regulations) leads toa problem of lack of training data. Falcon provides a
cryptographically secure framework for this conundrum,
where the client data is split into unrecognizable parts
among a number of non-colluding entities. In this way,
the solution is two-fold, MPC enables the ability to accumulate good quality training data and at the sametime can enable machine-learning-as-a-service (MLaaS)for the problem of CEIs. The 3 computing parties canbe Facebook, Google, and Microsoft, and will in turnbe the providers of such a service. A public API can be
exposed to entities willing to make use of this service,very similar to the PhotoDNA portal [34]. Organizations (clients of this service) that deal with significant
number of CEI’s can send automated requests to these3 servers and locally reconstruct the classification result
using the received responses. In terms of the adversarial model, we believe that the stringent legal frameworkaround this application is a sufficient deterrent for theselarge organizations to prevent collusion among the parties. Similarly, a maliciously secure adversarial model
further safeguards against individual servers being compromised. In this manner, MPC can enable an end-toend solution to automated detection of CEIs in social
media with strong privacy to the underlying data.

2.2 Threat Model
Our threat model assumes an honest majority
among the three parties in the setting described above.
This is a common adversarial setting considered in previous secure multi-party computation approaches [4, 11,
21, 30]. We consider that one of the three parties can beeither semi-honest or malicious. A semi-honest adver-191

sary passively tries to learn the secret data of the otherparties while a malicious adversary can arbitrarily deviate from the protocol. We assume the private keys ofeach of the parties are stored securely and not susceptible to leakage. We do not protect against denial ofservice attacks where parties refuse to cooperate. Here,
Falcon simply resorts to aborting the computation.
Assumptions & Scope. The 3 parties each haveshared point-to-point communication channels and pairwise shared seeds to use AES as a PRNG to generate cryptographically secure common randomness. We
note that as the query users receive the answers to thequeries in the clear Falcon does not guarantee protecting the privacy of the training data from attacks suchas model inversion, membership inference, and attributeinference [35–37]. Defending against these attacks is anorthogonal problem and out of scope for this work. We
assume that users provide consistent shares and thatmodel poisoning attacks are out of scope.

2.3 Technical Contributions
In this section, we summarize some of the main contributions of this work with a focus on techniques used
to achieve our results and improvements.
Hybrid Integration for Malicious Security.
Falcon consists of a hybrid integration of ideas from SecureNN and ABY3 along with newer protocol constructions for privacy-preserving deep learning. SecureNN
does not provide correctness in the presence of malicious adversaries. Furthermore, the use of semi-honest
parties in SecureNN makes it a significant challenge toconvert those protocols to provide security against malicious corruptions. We use replicated secret sharing (suchas in [11, 21, 30]) as our building block and use the redundancy to enforce correct behaviour in our protocols.
Note that changing from the 2-out-of-2 secret sharing
scheme in SecureNN to a 2-out-of-3 replicated secretsharing crucially alters some of the building blocks –these protocols are a new contribution of this work. We
work in the 3 party setting where at most one party
can be corrupt. We prove each building block secure in
the Universal Composability (UC) framework. We showthat our protocols are (1) perfectly secure in the standalone model, i.e., the distributions are identical and notjust statistically close in a model where the protocol is
executed only once; and (2) have straight-line black-box
simulators, i.e., only assume oracle access and do no
rewind. Theorem 1.2 from Kushilevitz et al. [38] thenimplies security under general concurrent composition.

Falcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning

Theoretical Improvements to Protocols. Falcon proposes more efficient protocols for common machine learning functionalities while providing stronger
security guarantees. We achieve this through a number of theoretical improvements for reducing both thecomputation as well as the communication. First, in
Falcon all parties execute the same protocol in contrast to SecureNN where the protocol is asymmetric.
The uniformity of the parties leads to more optimal resource utilization. Second, the protocol for derivativeof ReLU, in SecureNN [12] first transforms the inputs
using a Share Convert subroutine (into secret sharesmodulo an odd ring) and then invokes a Compute MSB
subroutine to compute the most significant bit (MSB)
which is closely related to the DReLU function. Notethat DReLU, when using fixed point encoding over aring ZL is defined as follows:(
0 if x > L/2
DReLU(x) =(1)
1 Otherwise
Each of these subroutines have roughly the same overhead. In Falcon, we show an easier technique using
new mathematical insights to compute DReLU which
reduces the overhead by over 2×. Note that ReLU and
DReLU, non-linear activation functions central to deeplearning, are typically the expensive operations in MPC.
The first two points above lead to strictly improved protocol for these. Third, Falcon uses a smaller ring size
while using an exact yet expensive truncation protocol.
This trade-off however allows the entire framework to
operate on smaller data-types, thus reducing the communication complexity at least 2×. Furthermore, thiscommunication improvement is amplified with the superlinear dependence of the overall communication on
the ring size (cf Table 9). This reduced communicationis critical to the communication improvements of Falcon over prior work. In other words, we notice strictly
larger performance improvements (than the theoreticalimprovements) in our end-to-end deployments of benchmarked networks presented in Section 5.
Improved Scope of ML Algorithms. Priorworks focus on implementing protocols for linear layers and important non-linear operations. We propose
and implement an end-to-end protocol for batch normalization (both forward and backward pass). Batchnormalization is widely used in practice for speedy training of neural networks and is critical for machine learning for two reasons. First, it speeds up training by allowing higher learning rates and prevents extreme values ofactivations [39]. This is an important component of theparameter tuning for neural networks as there is limited

192“seeing and learning” during private training. Second, it
reduces over-fitting by providing a slight regularization
effect and thus improves the stability of training [39]. In
other words, private training of neural networks withoutbatch normalization is generally difficult and requires
significant pre-training. To truly enable private deeplearning, efficient protocols for batch-normalization are
required. Implementing batch normalization in MPC is
hard for two reasons, first computing the inverse of anumber is generally difficult in MPC. Second, most approximate approaches require the inputs to be within acertain range, i.e., there is a trade-off between having
an approximate function for inverse of a number overa large range and the complexity of implementing it in
MPC. Through our implementation, we enable batchnormalization that can allow the training of complex
network architectures such as AlexNet (about 60 million parameters).
2.3.1 Comprehensive Evaluation
As shown in Table 1, there are a number of factors
involved in comparing different MPC protocols and thatnone of the prior works provide a holistic solution. We
also thoroughly benchmark our proposed system – weevaluate our approach over 6 different network architectures and over 3 standard datasets (MNIST, CIFAR10, and Tiny ImageNet). We also benchmark our system in both the LAN and WAN setting, for training
as well as for inference, and in both the semi-honest
and actively secure adversarial models. Finally, we provide a thorough performance comparison against priorstate-of-the-art works in the space of privacy preserving
machine learning (including 2PC, purely for the sakeof comprehensive comparison). We believe that such a
comparison, across a spectrum of deployment scenarios,
is useful for MPC practitioners.
Finally, we note that the insights and techniquesdeveloped in this work are broadly applicable. For instance, ReLU is essentially a comparison function which
can thus enable a number of other applications – private computation of decision trees, privacy-preserving
searching and thresholding, and private sorting.

3 Protocol Constructions
We begin by describing the notation used in thispaper. We then describe how basic operations are performed over the secret sharing scheme and then moveon to describe our protocols in detail.

Falcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning

3.1 Notation
Let P1 , P2 , P3 be the parties. We use Pi+1 , Pi−1
to denote the next and previous party for Pi (withperiodic boundary conditions). In other words, next
party for P3 is P1 and previous party for P1 is P3 . We
use JxKm to denote 2-out-of-3 replicated secret sharing(RSS) modulo m for a general modulus m. For any x let
JxKm = (x1 , x2 , x3 ) denote the RSS of a secret x modulo
m i.e., x ≡ x1 +x2 +x3 (mod m), but they are otherwise
random. We use the notation JxKm to mean (x1 , x2 ) is
held by P1 , (x2 , x3 ) by P2 , and (x3 , x1 ) by P3 . We denoteby x[i] the ith component of a vector x. In this work, we
focus on three different moduli L = 2` , a small prime p,
and 2. In particular, we use ` = 25 , p = 37. We use fixedpoint encoding with 13 bits of precision. In ΠMult overZp , the multiplications are performed using the sameprocedure with no truncation. ReLU, which comparesa value with 0 in this representation corresponds to acomparison with 2`−1 .

3.2 Basic Operations
To ease the exposition of the protocols, we first describe how basic operations can be performed over theabove secret sharing scheme. These operations are extensions of Boolean computations from Araki et al. [30]to arithmetic shares, similar to ABY3 [11]. However,ABY3 relies on efficient garbled circuits for non-linear
function computation which is fundamentally different
than the philosophy of this work which relies on simple modular arithmetic. In this manner, we propose ahybrid integration of ideas from SecureNN and ABY3 .
Correlated Randomness: Throughout this work,
we will need two basic random number generators. Bothof these can be efficiently implemented (using local computation) using PRFs. We describe them below:• 3-out-of-3 randomness: Random α1 , α2 , α3 such that
α1 + α2 + α3 ≡ 0 (mod L) and party Pi holds αi .
• 2-out-of-3 randomness: Random α1 , α2 , α3 such that
α1 + α2 + α3 ≡ 0 (mod L) and party Pi holds (αi , αi+1 ).
Given pairwise shared random keys ki (shared between parties Pi and Pi+1 ), the above two can be computed as αi = Fki (cnt) − Fki−1 (cnt) and (αi , αi−1 ) =(Fki (cnt), Fki−1 (cnt)) where cnt is a counter incremented
after each invocation. This is more formally describedlater on in ΠPrep in Fig. 6.
Linear Operations: Let a, b, c be public constants
and JxKm and Jy Km be secret shared. Then Jax+by +cKm
can be locally computed as (ax1 +by1 +c, ax2 +by2 , ax3 +by3 ) and hence are simply local computations.

193

Multiplications ΠMult : To multiply two sharedvalues together JxKm = (x1 , x2 , x3 ) and Jy Km =(y1 , y2 , y3 ), parties locally compute z1 = x1 y1 + x2 y1 +x1 y2 , z2 = x2 y2 +x3 y2 +x2 y3 and z3 = x3 y3 +x1 y3 +x3 y1 .
At the end of this, z1 , z2 and z3 form a 3-out-of-3 secretsharing of Jz = x · y Km . Parties then perform resharing
where 3-out-of-3 randomness is used to generate 2-outof-3 sharing by sending αi + zi to party i − 1 where {αi }form a 3-out-of-3 secret sharing of 0.
Convolutions and Matrix Multiplications: We
rely on prior work to perform convolutions and matrix
multiplications over secret shares. To perform matrix
multiplications, we note that ΠMult described above extends to incorporate matrix multiplications. To performconvolutions, we simply expand the convolutions into
matrix multiplications of larger dimensions (cf Section
5.1 of [12]) and invoke the protocol for matrix multiplications. With fixed-point arithmetic, each multiplication protocol has to be followed by the truncation protocol (cf Fig. 6) to ensure correct fixed-point precision. For
more details on fixed-point multiplication, semi-honest,
and malicious variants of this refer to [11, 21].
Reconstruction of JxKm : In the semi-honest setting, each party sends one ring element to the next
party, i.e., Pi sends share xi to Pi+1 . In the malicious
setting, each party sends xi to Pi+1 and xi+1 to Pi−1
and aborts if the two received values do not agree. In
either case, a single round of communication is required.
Select Shares ΠSS : We define a sub-routine ΠSS ,which will be used a number of times in the descriptionsof other functionalities. It takes as input shares of two
random values JxKL , Jy KL , and shares of a random bit
JbK2 . The output Jz KL is either JxKL or Jy KL depending onwhether b = 0 or b = 1. To do this, we assume access toshares of a random bit JcK2 and JcKL (pre-computation).
Then we open the bit (b ⊕ c) = e. If e = 1, we set
JdKL = J1 − cKL otherwise set JdKL = JcKL . Finally, we
compute Jz KL = J(y − x) · dKL + JxKL where J(y − x) · dKL
can be computed using ΠMult (y − x, d).
XOR with Public Bit b: Given shares of a bit
JxKm and a public bit b, we can locally compute sharesof bit Jy Km = Jx ⊕ bKm by noting that y = x + b −2b · x. Since b is public, this is a linear operation andcan be computed in both the semi-honest and malicious
adversary models.
Evaluating J(−1)β · xKm from JxKm and Jβ Km :We assume that β ∈ {0, 1}. We first compute J1 − 2β Km
and then perform the multiplication protocol describedabove to obtain J(1 − 2β) · xKm = J(−1)β · xKm . We split
our computations into data dependent online computa-

194

Falcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning

tions and data independent offline computations. Protocols for offline computations are presented in Fig. 6.

3.3 Private CompareThis function evaluates the bit x ≥ r where r is
public and the parties hold shares of bits of x in Zp .
Algorithm 1 describes this protocol. Note that β is necessary for privacy as β 0 reveals information about theoutput (x ≥ r) if not blinded by a random bit β. Eachof the bits are independent so a single blinding bit β issufficient to hide computation of (x ≥ r) or (r > x).
(A) Step 2: u[i] can be computed by first evaluating
shares of 2β − 1 and then computing the productof (2β − 1) and x[i] − r[i]. This can be done in asingle round using one invocation of ΠMult .
(B) Steps 3,4: These are simply local computations. For
instance, Jw[i]K = (w[i]1 , w[i]2 , w[i]3 ) can be computed as w[i]j = x[i]j + δj1 r[i] − 2r[i]x[i]j wherej ∈ {1, 2, 3} and δij is the Kronecker delta function
and is 1 if i = j and 0 otherwise.
(C) Step 6 can be computed in log2 ` + 1 rounds using sequential invocations of the ΠMult with smaller
strings (One additional round because of multiplication by random blinding factor).
(D) Steps 7,8: These are once again local computations.
This protocol is an example of the challenges of integrating approaches based on simple modular arithmetic withmalicious security. Both SecureNN and Falcon aim tofind if there exists an index i such that c[i] = 0. However,
the existence of a semi-honest third party makes checking this much easier in SecureNN. The two primary parties simply blind and mask their inputs and send themto the third party. This is not possible in Falcon due tothe stronger adversarial model and requires newer protocol constructions. In particular, we need to multiply
all the c[i]’s together along with a mask in Z∗p and reveal
this final product to compute the answer.

3.4 Wrap Function
Central to the computation of operations such as
ReLU and DReLU is a comparison function. The wrap
functions, wrap2 and wrap3 are defined below as a function of the secret shares of the parties and effectively
compute the “carry bit” when the shares are added together as integers. Eq. 11 shows that DReLU can beeasily computed using the wrap3 function. So all we
require is a secure protocol for wrap3 . We define twosimilar functions called “wrap” (denoted by wrap2 andwrap3 ). We call Eq. 3 the exact wrap function. For theremainder of the paper, we use the (mod 2) reduction

Algorithm 1 Private Compare ΠPC (P1 , P2 , P3 ):Input: P1 , P2 , P3 hold secret sharing of bits of x in Zp .
Output: All parties get shares of the bit (x ≥ r) ∈ Z2 .
Common Randomness: P1 , P2 , P3 hold a public ` bit integerr, shares of a random bit in two rings JβK2 and JβKp andshares of a random, secret integer m ∈ Z∗p .
1: for i = {` − 1, ` − 2, . . . , 0} do
2:Compute shares of u[i] = (−1)β (x[i] − r[i])3:Compute shares of w[i] = x[i] ⊕ r[i]P`
4:Compute shares of c[i] = u[i] + 1 +
w[k]
k=i+1
5: end forQ`−1
6: Compute and reveal d := JmKp · i=0 c[i] (mod p)
7: Let β 0 = 1 if (d 6= 0) and 0 otherwise.
8: return Shares of β 0 ⊕ β ∈ Z2of the wrap function defined in Equation 4 and refer toit as simply the wrap function.
(
0 if a1 + a2 < L
wrap2 (a1 , a2 , L) =(2)
1 OtherwiseP30 if i=1Pai < L
wrap3e (a1 , a2 , a3 , L) = 1 if L ≤ 3i=1 ai < 2L (3)2 if 2L ≤ P3 a < 3L
i=1i

wrap3 (a1 , a2 , a3 , L) = wrap3e (a1 , a2 , a3 , L) (mod 2) (4)Next we briefly describe the connection between
wrap3 computed on shares a1 , a2 , a3 and the most significant bit (MSB) of the underlying secret a. Notethat a = a1 + a2 + a3 (mod L) as ai ’s are shares ofa modulo L. Considering this sum as a logic circuit(for instance as a ripple carry adder), we can see that
MSB(a) = MSB(a1 ) + MSB(a2 ) + MSB(a3 ) + c (mod 2)
where c is the carry bit from the previous index. The
key insight here is that the carry c from the previous
index is simply the wrap3 function computed on ai ’s (ignoring their MSB’s) modulo L/2 (this is evident from
Eq. 3). And this last operation is synonymous with computing the wrap3 function on 2ai ’s modulo L. We willfurther describe the consequences of this connection in
Section 3.5 where we describe a protocol to compute
the ReLU and DReLU functions. Algorithm 2 gives the
protocol for securely computing the wrap3 function.
Note that wrap2 function is always computed locallyand hence a secure algorithm is not needed for the same.
Furthermore, note that the wrap2 function allows us towrite exact integer equations as follows: if a ≡ a1 + a2
(mod L) then a = a1 + a2 − wrap2 (a1 , a2 , L) · L where theformer relation is a congruence relation but the latter isan integer relation (and has exact equality). Finally, to
see the correctness of the wrap3 protocol, in reference toFalcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning

195

Algorithm 2 wrap3 ΠWA (P1 , P2 , P3 ):Algorithm 3 ReLU, ΠReLU (P1 , P2 , P3 ):Input: P1 , P2 , P3 hold shares of a in ZL .
Output: P1 , P2 , P3 get shares of a bit θ = wrap3 (a1 , a2 , a3 , L)
Common Randomness: P1 , P2 , P3 hold shares JxKL (of arandom number x), Jx[i]Kp (shares of bits of x) and JαK2
where α = wrap3 (x1 , x2 , x3 , L).

Input: P1 , P2 , P3 hold shares of a in ZL .
Output: P1 , P2 , P3 get shares of ReLU(a).
Common Randomness: JcK2 and JcKL (shares of a random
bit in two rings)

1: Compute rj ≡ aj + xj (mod L) and βj = wrap2 (aj , xj , L)P
2: Reconstruct r ≡rj (mod L)
3: Compute δ = wrap3 (r1 , r2 , r3 , L)
. In the clear
4: Run ΠPC on x, r + 1 to get η = (x ≥ r + 1).
5: return θ = β1 + β2 + β3 + δ − η − αAlgorithm 2, we can write the following set of equationsr =a+x−η·L(5)r = r1 + r2 + r3 − δe · L(6)ri = ai + xi − βi · L(7)∀i ∈ {1, 2, 3}x = x1 + x2 + x3 − αe · L(8)where δe , αe denote the exact wrap functions, Eq. 6,8
follow from the definition of the exact wrap function,
while Eq 7 follows from the definition of wrap2 function.
To see Eq. 5, note that r, a, x ∈ [0, L − 1] and that r ≡a + x (mod L). Hence a + x ≥ L iff r < x (or x ≥r + 1). Finally, assuming θe is the exact wrap function
on a1 , a2 , a3 i.e.,a = a1 + a2 + a3 − θe · L(9)Eqs. 5-9 together give a constraint among the Greek
symbols (in other words, (5) - (6) - (7) + (8) + (9)gives Eq. 10 below)
θe = β1 + β2 + β3 + δe − η − αe(10)Reducing Eq. 10 modulo 2 gives us θ = β1 +β2 +β3 +δ −
η − α which is used to compute wrap3 as in Algorithm 2.

3.5 ReLU and Derivative of ReLU
We now describe how to construct a protocol for
securely computing ReLU(a) and DReLU(a) for a given
secret a. Recall that we use fixed point arithmetic overZ2` for efficiency reasons. Using the natural encodingof native C++ data-types, we know that positive numbers are the first 2`−1 and have their most significant
bit equal to 0. Negative numbers, on the other hand are
the last 2`−1 numbers in the `-bit range and have theirmost significant bit equal to 1. Thus, the DReLU function defined by Eq. 1, has a simple connection with themost significant bit (MSB) of the fixed point representation viz., DReLU(a) = 1−MSB(a). Furthermore, in Section 3.4, we have seen the connection between MSB(a)1: Run ΠWA to get wrap3 (2a1 , 2a2 , 2a3 , L)
2: Compute JbK2 where b = DReLU(a) . Local comp. (Eq. 11)
3: return Output of ΠSS run on {a, 0} with b as selection.

and wrap3 . Together, these insights can be distilled into
the following equation:
DReLU(a) = MSB(a1 ) ⊕ MSB(a2 ) ⊕ MSB(a3 )⊕ wrap3 (2a1 , 2a2 , 2a3 , L) ⊕ 1(11)

In particular, Derivative of ReLU can be computed by
combining the output of the wrap function with local computations. Finally, for computing ReLU from
DReLU, we simply call ΠSS (which effectively performs
ΠMult on shares of a and shares of DReLU(a)). With
these observations, we can implement the ReLU and
Derivative of ReLU protocols (see Algorithm 3). Notethat the approach here is crucially different from theapproach SecureNN uses due to use of fundamentallydifferent building blocks as well as deeper mathematical insights such as Eq. 11. To achieve the DReLU functionality, SecureNN first uses a subroutine to transformthe shares of the secret into an odd modulus ring andthen uses another subroutine to compute the MSB (cf
Section 2.3). Both these subroutines have similar complexities. Falcon on the other hand uses the insightpresented in Eq. 11 to completely eliminate the needfor these subroutines, improving the efficiency by about
2× and simplifying the overall protocol. This also drastically improves the end-to-end performance (by over6.4×) as the ReLU and DReLU functionalities are thebuilding blocks of every comparison in the network.

3.6 Maxpool and Derivative of Maxpool
The functionality of maxpool simply takes as input a vector of secret shared values and outputs the
maximum value. For derivative of maxpool, we need aone-hot vector of the same size as the input where the
1 is at the location of the index of the maximum value.
Maxpool can be implemented using a binary sort on
the vector of inputs and small amounts of bookkeeping,where the comparisons can be performed using ReLUs.
Derivative of maxpool can be efficiently implemented
along with maxpool described in Algorithm 4.

Falcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning

Algorithm 4 Maxpool, ΠMaxpool (P1 , P2 , P3 ):Input: P1 , P2 , P3 hold shares of a1 , a2 , . . . an in ZL .
Output: P1 , P2 , P3 get shares of ak and ek where k =argmax{a1 , . . . an } and where ek = {e1 , e2 , . . . en } with
ei = 0 ∀i 6= k and ek = 1.
Common Randomness: No additional common randomness
required.
1: Set max ← a1 and ind ← e1 = {1, 0, . . . , 0}
2: for i = {2, 3, . . . n} do
3:Set dmax ← (max − ai ) and dind ← (ind − ei )4:b ← ΠDReLU (dmax ). b → Derivative of ReLU
5:
max ← ΠSS on inputs {ai , max, b}.
6:
ind ← ΠSS on inputs {ei , ind, b}.
7: end for
8: return max, ind

Algorithm 5 Bounding Power, ΠPow (P1 , P2 , P3 ):Input: P1 , P2 , P3 hold shares of x in ZL .
Output: P1 , P2 , P3 get α in the clear, where 2α ≤ x < 2α+1 .
Common Randomness: No additional common randomness
required.
1: Initialize α ← 0
2: for i = {` − 1, . . . , 1, 0} doi3:c ← ΠDReLU (x − 22 +α ) and reconstruct c
4:
Set α ← α + 2i if c = 1
5: end for
6: return α

3.7 Division and Batch Normalization
Truncation allows parties to securely eliminate
lower bits of a secret shared value (i.e., truncation by kbits of a secret a → a/2k ). However, the problem of dividing by a secret shared number is considerably harderand efficient algorithms rely on either (1) sequential
comparison (2) numerical methods. In this work, we use
the numerical methods approach for its efficiency. We
use the specific choices of initializations given in [40, 41]
to efficiently compute division over secret shares. A crucial component of numerical methods is the need to estimate the value of the secret within a range. We achieve
this using Algorithm 5. Note that Algorithm 5 outputs
the bounding power of 2, which is also what is guaranteed by the functionality. In this way, we only reveal thebounding power of 2 and nothing else.
Algorithm 6 is used to compute the value of a/b
where a, b are secret shared. The first step for the algorithm is to transform b → x where x ∈ [0.5, 1). Note thateven though b is a fixed-point precision of fp , for thecomputations in Algorithm 6, x has to be interpreted
as a value with fixed-point precision α + 1 where 2α ≤b < 2α+1 . Thus we first need to extract α (the appropriate range) using Algorithm 5. Let w0 = 2.9142 − 2x,1960 = 1 − x · w0 (cf. [40, 41] for choice of constants).
Then an initial approximation for 1/x is w0 · (1 + 0 ).
For higher order approximations, set i = 2i−1 and multiply the previous approximate result by (1 + i ) to geta better approximate result. Each successive iteration
increases the round complexity by 2. For our value of
fixed-point precision, we use the following approximation which works with high accuracy (refer to Section 5for details):
Algorithm 6 Division, ΠDiv (P1 , P2 , P3 ):Input: P1 , P2 , P3 hold shares of a, b in ZL .
Output: P1 , P2 , P3 get shares of a/b in ZL computed as integer
division with a given fixed precision fp .
Common Randomness: No additional common randomness
required.
1: Run ΠPow on b to get α such that 2α ≤ b < 2α+1
2: Compute w0 ← 2.9142 − 2b
3: Compute 0 ← 1 − b · w0 and 1 ← 20
4: return aw0 (1 + 0 )(1 + 1 )Algorithm 7 Batch Norm, ΠBN (P1 , P2 , P3 ):Input: P1 , P2 , P3 hold shares of a1 , a2 . . . am in ZL where m is
the size of each batch and shares of two learnable parametersγ, β.
Output: P1 , P2 , P3 get shares of γzi + β for i ∈ [m] and zi =PP√(ai − µ)/( σ 2 + ) where µ = 1/m
ai , σ 2 = 1/m (ai −µ)2 , and  is a set constant.
Common Randomness: No additional common randomness
required.

P

1: Set µ ← 1/m ·aiP
2: Compute σ 2 ← 1/m ·(ai − µ)2 and let b = σ 2 + 
3: Run ΠPow on b to find α such that 2α ≤ b < 2α+1
4: Set x0 ← 2−bα/2e
5: for i ∈ 0, . . . , 3 do
6:
Set xi+1 ← x2i (3 − bx2i )7: end for
8: return γ · xrnds · (ai − µ) + β for i ∈ [m]AppDiv(x) = w0 · (1 + 0 )(1 + 1 ) ≈

1
x

(12)

Batch-norm is another important component of neuralnetwork architectures. They improve the convergence aswell as help automate the training process. Algorithm 7
describes the protocol to compute batch-norm. For step3, we use Newton’s method and use 2−bα/2e as an initial√approximation of 1/ σ 2 + , where 2α ≤ σ 2 +  < 2α+1
and use the successive iterative formula:xn
xn+1 =
3 − ax2n(13)2Given the choice of initial guess, 4 rounds are sufficient for a close approximation with our choice of fixedpoint precision. However, batch normalization duringFalcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning√
training is computed by sequentially computing σ 2 + and then computing the inverse. This approach is used
to optimize the computation required during back√propagation which requires the values of σ 2 + . For
computing the square root of a value a, we use Newton’s
method given by Eq. 14. This can then be used in conjunction with the inverse computation given by Eq. 12
to complete the batch-norm computations.


1
a
(14)
xn+1 =xn +2
xn

4 Theoretical Analysis
We provide theoretical analysis of our framework
and protocols. In particular, we provide proofs of security and analyze the theoretical complexity.

4.1 Security Proofs
We model and prove the security of our constructionin the real world-ideal world simulation paradigm [42–44]. In the real interaction, the parties execute the protocol in the presence of an adversary and the environment. On the other hand, in the ideal interaction, theparties send their inputs to a trusted party that computes the functionality truthfully. Finally, to prove thesecurity of our protocols, for every adversary in the realinteraction, there exists a simulator in the ideal interaction such that the environment cannot distinguish between the two scenarios. In other words, whatever information the adversary extracts in the real interaction,
the simulator can extract it in the ideal world as well.
We show that our protocols are perfectly secure (i.e.,
the joint distributions of the inputs, outputs, and thecommunication transcripts are exactly the same andnot statistically close) in the stand-alone model (i.e.,
protocol is executed only once), and that they have astraight-line black-box simulators (i.e., only assume oracle access to the adversary and hence do no rewind). We
then rely on the result of Kushilevitz et al. [38] to provethat our protocols are secure under concurrent generalcomposition (Theorem 1.2 in [38]).
Due to space constraints, we formally describe thefunctionalities in Appendix E. We describe simulatorsfor ΠPC (Fig. 3), ΠWA (Fig. 4), ΠReLU (Fig. 5), ΠMaxpool(Fig. 7), ΠPow (Fig. 8), ΠDiv (Fig. 9), and ΠBN (Fig. 10)that achieve indistinguishability. FMult , FTrunc , FReconst
are identical to prior works [11, 21]. We prove security
using the standard indistinguishability argument. To
prove the security of a particular functionality, we setup hybrid interactions where the sub-protocols used inthat protocol are replaced by their corresponding ideal

197

functionalities and then prove that the interactions canbe simulated. This hybrid argument in effect sets up aseries of interactions I0 , I1 , . . . Ik for some k where I0
corresponds to the real interaction and Ik corresponds
to the ideal interaction. Each neighboring interaction,i.e., Ii , Ii+1 for i ∈ {0, . . . , k − 1} is then shown indistinguishable from each other, in effect showing that thereal and ideal interactions are indistinguishable. Without loss of generality, we assume that party P2 is corrupt. In the real world, the adversary A interacts withthe honest parties P0 and P1 . In the ideal world, thesimulator interacts with the adversary and simulates exact transcripts for interactions between the adversary A
and P0 , P1 . On the other hand, the simulator should be
able to extract the adversaries inputs (using the values for the inputs of the honest parties in the internal
run and the fact that each honest party has one component of the replicated secret sharing). These inputs
are fed to the functionality to generate correct output
distributions, thus achieving security against malicious
adversaries. Theorems 1-6 gives the indistinguishabilityof these two interactions.
Theorem 1. ΠPC securely realizes FPC with abort,in the presence of one malicious party in the(FMult , FReconst , FPrep )-hybrid model.
Proof. We first set up some detail on the proof strategy
that is essential for other proofs as well. For the easeof exposition, we describe it in the context of ΠPC . The
goal of designing a simulator is to be able to demonstrate the ability to produce transcripts that are indistinguishable from the transcripts in the real world. The
joint distribution of the inputs and outputs is a part ofthese transcripts and hence has to be indistinguishable
in the two interactions. However, since the honest parties simply forward their inputs to the functionality, thesimulator must be able to extract the inputs of the malicious parties to be able to generate the correct sharesfor the honest parties.
The usual technique to achieve this is to have thesimulator run a simulated version of the protocol internally, i.e., emulating the roles of the honest parties
and interacting with the adversary. This is what we callan internal run. This internal run can then be used to
extract the inputs of the adversarial party (which canthen be forwarded to the functionality in the ideal interaction). In the hybrid argument, the subroutines usedin the protocol can be replaced by their corresponding
ideal interactions, the simulator can emulate the rolesof these trusted functionalities in its internal run.

Falcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning

In the specific context of ΠPC , the simulator S for
adversary A works by playing the role of the trusted
party for FMult , FReconst and FPrep . To be able to simulate, we need to show that:(1) Real interaction transcripts can be simulated.
(2) Honest parties receive their outputs correctly.
Simulation follows easily from the protocol and the hybrid argument. The simulator for ΠMult (along with thesimulator for ΠReconst ) can be used to simulate the transcripts from Steps 2, 6 (from Algorithm 1). Note thatthe distributions of these transcripts are all uniformly
random values (β is required to make the transcript forβ 0 uniformly random, the various bits u[i], w[i], and c[i]are random because x is random) and hence achieve perfect security. Steps 3, 4, 7, and 8 on the other hand are
all local and do not need simulation.
To extract the inputs of the malicious party, thesimulator uses the fact that it has access to r and β(though FPrep ) and all the internal values for the honest
parties (in the internal run) and hence can extract theshares of x[i] from the corrupt party P2 . Finally, if the
protocol aborts at any time in the internal run, then thesimulator sends Abort to FPC otherwise, it inputs theextracted shares of x[i] to FPC and the honest parties
receive their outputs.
Theorem 2. ΠWA securely realizes FWA with abort,in the presence of one malicious party in the(FMult , FPC , FReconst , FPrep )-hybrid model.
Proof. We use a similar set-up as the proof of Theorem 1. Step 1 is local computation and does not need
simulation. Steps 2, 4 can be simulated using the simulators for FReconst , FPC respectively. Input extraction
follows from having access to ri (through FPrep ) and output x if the protocol does not abort. If the protocol does
abort at any time in the internal run, then the simulator
sends Abort to FWA . Otherwise, it simply passes on theextracted shares of a[i] to FWA and the honest parties
receive their outputs. Note that ΠDReLU is not formallydefined. However, this is simply local computation overΠWA and the proofs can be extended analogously.
Theorem 3. ΠReLU securely realizes FReLU with abort,in the presence of one malicious party in the(FMult , FWA , FPrep )-hybrid model.
Proof. Simulation is done using the hybrid argument.
The protocol simply composes FWA and FMult and henceis simulated using the corresponding simulators.

198

Theorem 4. ΠMaxpool securely realizes FMaxpool withabort, in the presence of one malicious party in the(FMult , FReLU , FPrep )-hybrid model.
Proof. Similar to the proof of Theorem 3, simulation
works by sequentially composing the simulators for
FReLU and FMult .
Theorem 5. ΠPow securely realizes FPow with abort,in the presence of one malicious party in the(FMult , FReLU , FReconst , FPrep )-hybrid model.
Proof. The simulator for A works by playing the roleof the trusted party for FMult , FReLU , and FReconst . The
protocol sequentially reveals bits of the scale α. It is
important to note the functionality that it emulates (seein Fig. 8). The simulator runs the first iteration of theloop and in the process extracts the adversaries inputs.
Then it proceeds to complete all the iterations of theloop. If the protocol proceeds without aborting till theend, then the simulator sends the extracted shares ofb along with k = 0 to the functionality FPow . If the
protocol aborts at iteration k, then the simulator sends
the extracted shares of b along with k to FPow .
Theorem 6. ΠDiv , ΠBN securely realize FDiv , FBN respectively, with abort, in the presence of one malicious
party in the (FMult , FPow , FPrep )-hybrid model.
Proof. ΠDiv , ΠBN are sequential combinations of local
computations and invocations of FMult . Simulation follows directly from composing the simulators and input
extraction follows from the simulator of ΠPow .
4.1.1 Protocol Overheads
We theoretically estimate the overheads of our protocols in Table 9 in Appendix B. The dominant roundcomplexity for private compare comes from the string
multiplication in Step 6. wrap3 requires one additionalround and one additional ring element (two in malicious
security) over private compare. Computing derivativeof ReLU is a local computation over the wrap3 function. Computing ReLU requires two additional rounds
and one ring element (two for malicious). Maxpool andderivative of require rounds proportional to the areaof the filter. Finally, pow, division, and batch-norm requires a quadratic number of rounds in `.

5 Experimental Evaluation
We evaluate the performance of training and inference with Falcon on 6 networks of varying parameterFalcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning

sizes trained using MNIST, CIFAR-10 and Tiny ImageNet datasets (cf. Appendix C). A number of prior
works such as SecureML [4], DeepSecure [45], MiniONN [6], Gazelle [8], SecureNN [12], ABY3 [11], andChameleon [5] evaluate over these networks and wemimic their evaluation set-up for comparison.

5.1 Experimental Setup
We implement Falcon framework in about 14.6k
LOC in C++ using the communication backend of SecureNN and will be open-sourced at https://github.
com/snwagh/falcon-public. We run our experimentson Amazon EC2 machines over Ubuntu 18.04 LTS
with Intel-Core i7 processor and 64GB of RAM. Ourevaluation set-up uses similar as compared to priorwork [4, 5, 8, 11, 12]. We perform extensive evaluationof our framework in both the LAN and WAN setting.
For the LAN setting, our bandwidth is about 625 MBps
and ping time is about 0.2ms. For WAN experiments,
we run servers in different geographic regions with 70ms
ping time and 40 MBps bandwidth.
Optimizations: All data-independent computation, i.e., pre-computation, is parallelized using 16 cores
to reduce the run-time. When a ReLU layer is followed
by a Maxpool layer, we swap the order of these twolayers for optimized runtimes. We use the Eigen library for faster matrix multiplication and parallelize theprivate compare computation. We optimize across theforward and backward pass for Maxpool, ReLU, andBatch-Normalization layers, i.e., we compute the relevant derivatives while computing the functions. We use
32-bit integer range with 16 bits of fixed-point precision. As the entire codebase is parallelizable, significant
improvement is possible by implementing Falcon using
TensorFlow or PyTorch which support easy parallelization as well as computations over GPUs.
Networks and Datasets: For comparison withdifferent networks as well as plaintext computations, we select 3 standard benchmarking datasets —MNIST [27], CIFAR-10 [28], and Tiny ImageNet [29]and 6 standard network architectures – 3 from theprivacy-preserving ML community and 3 from the ML
community. For more details refer to Appendix C, D.

5.2 Results for Private Inference
Tables 2, 3 report the end-to-end latency time (inseconds) and number of bytes (in MB) communicatedfor performing a single inference query with Falcon.
We execute the queries in both LAN and WAN as well
as semi-honest and malicious settings and compare withprior work wherever applicable.

199

Comparison to Prior Work. We compare the inference time of a single query and the communication
bytes of Falcon with prior work on networks A, B and
C. None of the prior works evaluate the remaining networks and hence we do not compare the performance of
Falcon for the networks in Table 3. Depending on the
network architecture, our results are between 3×-120×
faster than existing work. In particular, we are up to
18× faster than XONN [9] (11× on average) and 32×
faster than Gazelle (23× on average), 8× faster thanSecureNN (3× on average), and comparable to ABY3
on small networks. We are also 40× more communication efficient than ABY3 [11], 200× more communication efficient than SecureNN [12], and over 760× morecommunication efficient compared to XONN [9]. Notethat it is hard to compare frameworks without actuallyrunning benchmarks as different protocols scale differently for different architectures. For instance, GC based
protocols scale better when run over WAN settings andlarger networks change the fraction of the total overhead
from linear layers for reasons described in Section 5.4
and thus affect different protocols differently.
Inference Time and Communication with
Falcon. For both the adversarial settings, the inference
latency for Falcon over LAN is within 25ms for smaller
networks (A and B) and around 100ms for Network-C
and LeNet. For AlexNet and VGG16, the inference time
ranges from 0.5 to 12s depending on the model and the
input dataset. The inference time increases with the sizeof the input image. Hence, queries over Tiny ImageNet
are slower than CIFAR-10 for the same model architecture. The inference time over the WAN setting ranges
from 1 to 3s for the networks A, B and C and from 3
to 37s for the larger networks. However, we emphasizethat the inference time with semi-honest adversarial setting is around 3× faster than that for the malicious adversary. Hence, a faster deployment protocol is possible
depending on the trust assumptions of the application.
In addition to efficient response times, our results
show that Falcon requires small amounts of communication. Parties exchange less than 4MB of data forsmaller networks (Table 2) and 5-400MB for larger networks (Table 3) (same for both LAN, WAN). However,similar to the inference time, malicious setting requires
a higher communication and thus higher run-time.

5.3 Results for Private Training
Tables 4, 5 report the execution time and the communication required for training the 6 networks.

200

Falcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning

Framework

2PC

3PC

Threat Model

Network-B

Network-C

Time

Comm.

Time

Comm.

Time

Comm.

SecureML [4]
DeepSecure [45]EzPC [7]Gazelle [8]MiniONN [6]
XONN [9]Semi-honest
Semi-honest
Semi-honest
Semi-honest
Semi-honest
Semi-honest

LAN
LAN
LAN
LAN
LAN
LAN

4.88
0.7
0.09
1.04
0.13

76
0.5
15.8
4.29

9.67
0.6
0.29
1.28
0.16

791
70
0.8
47.6
38.3

5.1
1.16
9.32
0.15

501
70
657.5
32.1

Chameleon [5]ABY3 [11]SecureNN [12]Semi-honest
Semi-honest
Semi-honest
Semi-honest
Malicious
Semi-honest
Semi-honest
Malicious

LAN
LAN
LAN
LAN
LAN
WAN
WAN
WAN

0.008
0.043
0.011
0.021
2.43
0.99
2.33

0.5
2.1
0.012
0.31
2.1
0.012
0.31

2.7
0.01
0.076
0.009
0.022
3.06
0.76
1.7

12.9
5.2
4.05
0.049
0.52
4.05
0.049
0.52

0.13
0.042
0.089
3.93
3.0
7.8

8.86
0.51
3.37
8.86
0.5
3.37

Malicious
Malicious

LAN
WAN

0.029
12.6

-

-

-

-

-

FalconSecureNN [12]Falcon4PC

Network-A

LAN/ WAN

FLASH [17]FLASH [17]Table 2. Comparison of inference time of various frameworks for different networks using MNIST dataset. All runtimes are reported inseconds and communication in MB. ABY3 and XONN do no implement their maliciously secure versions. 2-party (2PC) protocols arepresented here solely for the sake of comprehensive evaluation of the literature.
Framework

FalconThreat Model
Semi-honest
Malicious
Semi-honest
Malicious

LAN/WAN
LAN
LAN
WAN
WAN

LeNet (MNIST)AlexNet (CIFAR-10)

VGG16 (CIFAR-10)

AlexNet (ImageNet)

VGG16 (ImageNet)

Time

Comm.

Time

Comm.

Time

Comm.

Time

Comm.

Time

Comm.

0.047
0.12
3.06
7.87

0.74
5.69
0.74
5.69

0.043
0.14
0.13
0.41

1.35
8.85
1.35
8.85

0.79
2.89
1.27
4.7

13.51
90.1
13.51
90.1

1.81
6.7
2.43
8.68

19.21
130.0
19.21
130.0

3.15
12.04*
4.67
37.6*

52.56
395.7*
52.56
395.7*

Table 3. Comparison of inference time of various frameworks over popular benchmarking network architectures from the machine learning domain. All runtimes are reported in seconds and communication in MB. * indicate non-amortized numbers.

Comparison to Prior Work. For private training, Falcon is up to 6× faster than SecureNN [12] (4×on average), 4.4× faster than ABY3 and 70× faster thanSecureML [4]. We highlight that Falcon achieves these
speedups due to improved protocols (both round complexity and communication as described in Section 2.3).
Table 4 shows that the communication overhead is 10×to 100× as compared to other solutions.
Execution Time for Falcon. The time to privately train networks A, B and C with Falcon is around
3 to 40 hrs. For larger networks, we extrapolate timefrom a single iteration of a forward and a backward pass.
The training time ranges from a few weeks to hundredsof weeks. Although these values seem to be quite large,
high capacity machine learning models are known totake from a few days to weeks to achieve high accuracy
when trained (both on CPU as well as GPU). Such networks can also benefit from transfer learning techniques,
where a public pre-trained model is fine-tuned with a
private dataset. This fine-tuning requires fewer epochs
and hence speed up the overall runtime considerably.

5.4 Compute vs. Communication Cost
Figure 1 shows the computation time as comparedto the communication time for the inference of a single
input over different network sizes. We observe that thecomputation cost increases with the network size andbecomes the dominant reason for the performance overhead in private deep learning with Falcon. The reason
for this is because the complexity of matrix multiplication is “super-quadratic” i.e., to multiply two n × n matrices, the computation overhead is strictly larger thanO(n2 ). Note that the communication of the matrix multiplication protocol in this work is only linear in the sizeof the matrices and has a round complexity of a single
round. On the other hand, the non-linear operations,though more communication expensive in MPC, are applied on vectors of size equal to the output of the matrix
product and thus are “quadratic.” In other words, thenon-linear operations such as ReLU are applied on the
output of the matrix multiplication (FC/Conv layers)
and are applied on vectors of size O(n2 ) assuming they
are applied on the output of the multiplication of two

201

Falcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning

Framework

Threat Model

SecureML [4]*SecureML [4]ABY3 [11]SecureNN [12]Semi-honest
Semi-honest
Semi-honest
Semi-honest
Semi-honest
Malicious
Semi-honest
Semi-honest
Semi-honest
Malicious

FalconSecureML [4]*SecureNN [12]FalconNetwork-A

LAN/ WAN
LAN
LAN
LAN
LAN
LAN
LAN
WAN
WAN
WAN
WAN

Network-B

Network-C

Time

Comm.

Time

Comm.

Time

Comm.

81.7
7.02
0.75
1.03
0.17
0.56
4336
7.83
3.76
8.01

0.031
0.11
0.016
0.088
0.11
0.016
0.088

0.42
1.17
3.4
7.5

0.056
0.32
56.14
0.32

17.4
3.71
11.9
53.98
14.8
39.32

30.6
0.54
3.29
30.6
0.54
3.29

Batch Size, Epochs

128, 15

128, 15

128, 15

Table 4. Comparison of training time of various frameworks over popular benchmarking network architectures from the security domain. All runtimes are reported in hours and communication in TB. * correspond to 2PC numbers. ABY3 does not implement theirmaliciously secure protocols.
Framework

Threat Model

LAN/ WAN

LeNet
Time

Semi-honest
Malicious
Semi-honest
Malicious

Falcon

LAN
LAN
WAN
WAN

Batch Size, Epochs

AlexNet (CIFAR-10)
Comm.

Time

0.81
4.82
0.81
4.82

7.89 × 101

6.05 × 100
1.22 × 101
1.85 × 101
5.20 × 101
128, 15

VGG16 (CIFAR-10)

Comm.

Time

7.24
43.4
7.24
43.4

8.43 × 102

2.82 × 102
2.33 × 102
7.24 × 102
128, 90

AlexNet (ImageNet)

Comm.

Time

45.9
185.3
45.9
185.3

1.23 × 104

3.05 × 103
2.09 × 103
5.26 × 103
128, 25

VGG16 (ImageNet)

Comm.

Time

Comm.

222.9
1598
222.9
1598

5.19 × 103

156.0
1012
156.0
1012

4.63 × 104
1.54 × 104
5.71 × 104
128, 90

1.95 × 104
6.89 × 103
2.47 × 104
128, 25

Table 5. Comparison of training time of various frameworks over popular benchmarking network architectures from the machine learning domain. All runtimes are reported in hours and communication in TB.
Network

Training
Accuracy

Inference
Accuracy

Falcon Inference
Accuracy

Relative
Error

Network-A
Network-B
Network-C
LeNet

98.18%
98.93%
99.16%
99.76%

97.42%
97.81%
98.64%
99.15%

97.42%
97.81%
98.64%
96.85%

0.471%
0.635%
0.415%
0.965%

Table 6. Summary of experiments involving accuracy of neuralnetworks using secure computation. The first two columns referto the plaintext accuracies and relative error refers to the averagerelative error of one forward pass computation using Falcon.

n × n matrices. Hence, for large network architectures,the time required for the matrix-multiplication dominates the overall cost.
This observation is against the conventional wisdom that MPC protocols are communication bound andnot computation bound. When running larger networks
such as AlexNet and VGG16, and especially for Tiny
ImageNet, the computation time starts becoming a significant fraction of the total time. Hence, we claim that
Falcon is optimized for communication rounds, specifically when operating over large networks. With our results, we motivate the community to focus on designing faster compute solutions using accelerators such as
GPUs, parallelization, efficient matrix multiplications
and caching, along with the conventional goals of reducing communication and round complexity.

Fig. 1. Compute vs. communication cost for private inference using Falcon over WAN for the malicious adversary. We show thatas the network size increases, computation becomes a dominantfactor in the overall end-to-end runtime.

5.5 Comparison vs. Plaintext Computation
Given the surprising insights from Figure 1, we also
compare the execution of privacy-preserving computations with plaintext computations. These results are
summarized in Table 7. We use standard PyTorch libraries for the plaintext code, similar hardware as thatof privacy-preserving benchmarks for CPU-CPU comparison, and use a single Nvidia P100 GPU for the
GPU-CPU comparison. Our findings indicate that private deep learning (over CPU) is within a factor of 40×-

Falcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning

(a)

(b)

202

(c)

Fig. 2. In Figs. 2a, 2b, we study the model accuracy with and without batch normalization layers as a function of epochs for AlexNet
network. As can be seen, batch normalization not only helps train the network faster but also train better networks. In Fig. 2c, westudy the performance overhead of running the network (using Falcon) with and without batch normalization layers.

1200× of plaintext execution of the same network overCPU and within 50×-four orders of magnitude that ofplaintext execution over GPU (using PyTorch) when
performed over LAN. The overhead further increases by
1.2×-2.4× when comparing against WAN evaluations.
This indicates the importance of supporting GPUs andoptimizers for private deep learning and showcases theneed for further reducing the overhead of MPC protocols. We believe that it is beneficial for the broader
research community to have an estimate of the gap between plaintext and privacy-preserving techniques forrealistic size networks and datasets.

5.6 Batch Normalization and Accuracy
We study the benefits of batch normalization for
privacy-preserving training of neural networks. We compute the accuracy of partially trained models after eachepoch with and without the batch normalization layers.
As seen in Figs. 2a, 2b, batch normalization layers not
only help train the network faster but also train better
networks. Fig. 2c demonstrates the overhead of MPC
protocols with and without batch normalization layers.
Given the high round complexity of batch normalization, the gap is significant only in the WAN setting.
We also study the effect of our approximations andsmaller datatype on the accuracy of the computation.
We compare the evaluation of the networks with 64-bit
float datatypes over PyTorch against a 32-bit datatypeuint32_t using fixed-point arithmetic for Falcon. The
final layer outputs differ by small amounts (less than1%) in comparison with the high precision 64-bit computation. As a consequence, as seen in Table 6, most
networks show no/low loss in the overall neural network
accuracy when the computation is performed as fixedpoint integers over 32-bit datatype. This is because thefinal prediction is robust to small relative error in individual values at the output. This also makes the fi-

nal prediction vector inherently noisy and may provide
some defense against model inversion attacks.

6 Related Work
Privacy-preserving Training. In a seminal paperon private machine learning, Mohassel et al. [4] show
protocols for a variety of machine learning algorithms
such as linear regression, logistic regression and neuralnetworks. Their approach is based on a 2-party computation model and rely on techniques such as oblivious transfer [46] and garbled circuits [19]. Following
that, Mohassel et al. [11] proposed a new framework
called ABY3 which generalizes and optimizes switching back and forth between arithmetic, binary, andYao garbled circuits in a 3-party computation model.
Wagh et al. [12] proposed SecureNN that considers asimilar 3-party model with semi-honest security andeliminate expensive cryptographic operations to demonstrate privacy-preserving training and inference of neural networks. SecureNN also provides malicious privacy,
a notion formalized by Araki et al. [30] but not correctness under malicious corruption. Falcon provides
a holistic framework for both training and inference ofneural networks while improving computation and communication overhead as compared to prior work.
Privacy-preserving
Inference.
Privacypreserving inference has received considerable attention
over the last few years. Recall that we have summarizedsome of these works in Table 1. Private inference typically relies on one or more of the following techniques:
secret sharing [11, 12], garbled circuits [7, 9], homomorphic encryption [4, 6, 47] or Goldreich-Micali-Wigderson(GMW) [5, 42], each with its own advantages and disadvantages. CryptoNets [48] was one of the earliest works
to demonstrate the use of homomorphic encryption to
perform private inference. CryptoDL [49] developed
techniques that use approximate, low-degree polynomi-

203

Falcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning

CIFAR-10
Run-type

Training

Tiny ImageNet
Inference

Training

Inference

AlexNet

VGG-16

AlexNet

VGG-16

AlexNet

VGG-16

AlexNet

VGG-16

1.6 × 102

7.3 × 102

7.2 × 101

3.4 × 102

5.0 × 102

3.1 × 103

2.5 × 102

Plaintext

CPU-only
GPU-assisted

localhost
localhost

2.8 × 101

6.4 × 101

3.8 × 101

5.8 × 101

3.6 × 101

1.2 × 102

3.8 × 101

1.3 × 103
5.7 × 101

PrivateCPU-onlyCPU-onlyLAN
WAN

6.4 × 103
2.4 × 104

2.5 × 105
6.2 × 105

5.6 × 103
1.7 × 104

1.0 × 105
1.6 × 105

6.3 × 105
7.8 × 105

9.5 × 105
1.2 × 106

2.3 × 105
3.1 × 105

4.0 × 105
5.9 × 105

6.4 × 103

2.5 × 105

5.6 × 103

1.0 × 105

6.3 × 105

9.5 × 105

2.3 × 105

4.0 × 105

PrivateBandwidth

Table 7. Comparison of private computation (for semi-honest protocols, cf Section 5.1 for network parameters) with plaintext over thesame hardware using PyTorch and a single NVIDIA P100 GPU. Numbers are for a 128 size batch in milliseconds.

als to implement non-linear functions and improve on
CryptoNets. DeepSecure [45] uses garbled circuits todevelop a privacy-preserving deep learning framework.
Chameleon [5] is another mixed protocol framework that uses the Goldreich-Micali-Wigderson (GMW)
protocol [42] for low-depth non-linear functions, garbled circuits for high-depth functions and secret sharing for linear operations to achieve high performancegains. The above three [4, 5, 11] demonstrate private
machine learning for other machine learning algorithms
such as SVMs, linear and logistic regression as well.
Gazelle [8] combines techniques from homomorphic encryption with MPC and optimally balances the useof a specially designed linear algebra kernel with garbled circuits to achieve fast private inference. EzPC [7]is a ABY-based [50] secure computation frameworkthat translates high-level programs into Boolean andarithmetic circuits. Riazi et al. propose a framework
XONN [9] and showcase compelling performance for inference on large binarized neural networks and uses garbled circuits to provide constant round private inference. The work also provides a simple easy-to-use API
with a translator from Keras [51] to XONN. EPIC [52]demonstrates the use of transfer learning in the space ofprivacy-preserving machine learning while Quotient [53]takes the first steps in developing two party securecomputation protocols for optimizers and normalizations. CrypTFlow [13] builds on SecureNN and uses
trusted hardware to achieve maliciously secure protocols in a 3PC model. Delphi [10] builds on Gazelle tofurther improve performance and proposes a novel planner that automatically generates neural network architecture configurations that navigate the performanceaccuracy trade-offs. Astra [15] is a 3PC protocol withsemi-honest security and forms the foundation for a few
follow-up works. BLAZE [16] builds on Astra to achieve
malicious security and fairness in a 3PC honest majority
corruption model and uses an adder circuit approach for
non-linear function computation. Trident achieves thesame result in a 4PC model with further performance
improvements. FLASH [17] also proposes a 4PC modelthat achieves malicious security with guaranteed output
delivery. QuantizedNN [14] proposes an efficient PPML
framework using the quantization scheme of Jacob et
al. [54] and provides protocols in all combinations ofsemi-honest/malicious security and honest majority vsdishonest majority corruptions.

7 Conclusion
Falcon supports new protocols for private training and inference in a honest-majority 3-party setting.
Theoretically, we propose novel protocols that improve
the round and communication complexity and provide
security against maliciously corrupt adversaries with anhonest majority. Falcon thus provides malicious security and provides several orders of magnitude performance improvements over prior work. Experimentally,
Falcon is the first secure deep learning framework to
examine performance over large-scale networks such as
AlexNet and VGG16 and over large-scale datasets suchas Tiny ImageNet. We also are the first work to demonstrate efficient protocols for batch-normalization which
is a critical component of present day machine learning.

Acknowledgments
We thank Vikash Sehwag for his help with the experiments, the anonymous reviews, and our Shepherd
Melek Önen. We also thank the following grant/awards
for supporting this work: Facebook Systems for ML
award, Qualcomm Innovation Fellowship, Princeton
CSML DataX award, Princeton E-ffiliates Partnershipaward, Army Research Office YIP award, Office ofNaval Research YIP Award, and National Science Foundation’s CNS-1553437 and CNS-1704105, ISF grant2774/20, BSF grant 2018393, NSF-BSF grant 2015782,
and a grant from the Ministry of Science and Technology, Israel, and the Dept. of Science and Technology,
Government of India.

Falcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning

References[1]

E. Bursztein, E. Clarke, M. DeLaune, D. M. Elifff, N. Hsu,
L. Olson, J. Shehan, M. Thakur, K. Thomas, and T. Bright,“Rethinking the detection of child sexual abuse imagery on
the internet,” in The World Wide Web Conference. ACM,
2019, pp. 2601–2607.
[2] “Child Abusers Run Rampant as Tech Companies Look the
Other Way,” https://www.nytimes.com/interactive/2019/11/09/us/internet-child-sex-abuse.html, 2019.
[3] H. Cho, D. J. Wu, and B. Berger, “Secure genome-wide association analysis using multiparty computation,” in Naturebiotechnology, vol. 36, no. 6, 2018, p. 547.
[4] P. Mohassel and Y. Zhang, “SecureML: A system for scalable privacy-preserving machine learning,” in IEEE Symposium on Security and Privacy (S&P), 2017.
[5] M. S. Riazi, C. Weinert, O. Tkachenko, E. M. Songhori,
T. Schneider, and F. Koushanfar, “Chameleon: A hybrid
secure computation framework for machine learning applications,” in ACM Symposium on Information, Computer andCommunications Security (ASIACCS), 2018.
[6] J. Liu, M. Juuti, Y. Lu, and N. Asokan, “Oblivious neuralnetwork predictions via MiniONN transformations,” in ACM
Conference on Computer and Communications Security(CCS), 2017.
[7] N. Chandran, D. Gupta, A. Rastogi, R. Sharma, and S. Tripathi, “EzPC: programmable, efficient, and scalable secure
two-party computation for machine learning,” in IEEE European Symposium on Security and Privacy (S&P), 2019.
[8] C. Juvekar, V. Vaikuntanathan, and A. Chandrakasan,“Gazelle: A low latency framework for secure neural network
inference,” in USENIX Security Symposium, 2018.
[9] M. S. Riazi, M. Samragh, H. Chen, K. Laine, K. Lauter, andF. Koushanfar, “XONN: XNOR-based oblivious deep neuralnetwork inference,” in USENIX Security Symposium, 2019.
[10] P. Mishra, R. Lehmkuhl, A. Srinivasan, W. Zheng, and R. A.
Popa, “Delphi: A cryptographic inference service for neuralnetworks,” in USENIX Security Symposium, 2020.
[11] P. Mohassel and P. Rindal, “ABY3 : A mixed protocol framework for machine learning,” in ACM Conference on Computer and Communications Security (CCS), 2018.
[12] S. Wagh, D. Gupta, and N. Chandran, “SecureNN: 3-Party
secure computation for neural network training,” in Privacy
Enhancing Technologies Symposium (PETS), 2019.
[13] N. Kumar, M. Rathee, N. Chandran, D. Gupta, A. Rastogi,
and R. Sharma, “Cryptflow: Secure tensorflow inference,” inIEEE Symposium on Security and Privacy (S&P), 2020.
[14] A. Dalskov, D. Escudero, and M. Keller, “Secure evaluationof quantized neural networks,” https://eprint.iacr.org/2019/131, 2019.
[15] H. Chaudhari, A. Choudhury, A. Patra, and A. Suresh, “Astra: High throughput 3pc over rings with application tosecure prediction,” in ACM SIGSAC Conference on Cloud
Computing Security Workshop, 2019.
[16] A. Patra and A. Suresh, “Blaze: Blazing fast privacypreserving machine learning,” in Symposium on Network
and Distributed System Security (NDSS), 2020.
[17] M. Byali, H. Chaudhari, A. Patra, and A. Suresh, “FLASH:
Fast and robust framework for privacy-preserving machine

204

learning,” in Privacy Enhancing Technologies Symposium(PETS), 2020.
[18] R. Rachuri and A. Suresh, “Trident: Efficient 4pc frameworkfor privacy preserving machine learning,” in Symposium on
Network and Distributed System Security (NDSS), 2019.
[19] A. C. Yao, “Protocols for secure computations,” in IEEE
Symposium on Foundations of Computer Science (FOCS),
1982.
[20] A. Shamir, “How to share a secret,” Communications of theACM, vol. 22, no. 11, pp. 612–613, 1979.
[21] J. Furukawa, Y. Lindell, A. Nof, and O. Weinstein, “Highthroughput secure three-party computation for malicious adversaries and an honest majority,” in Advances in
Cryptology—EUROCRYPT, 2017.
[22] H. Chabanne, A. de Wargny, J. Milgram, C. Morel, andE. Prouff, “Privacy-preserving classification on deep neural network.” IACR Cryptol. ePrint Arch., vol. 2017, p. 35,
2017.
[23] A. Ibarrondo and M. Önen, “Fhe-compatible batch normalization for privacy preserving deep learning,” in Data Privacy
Management, Cryptocurrencies and Blockchain Technology.
Springer, 2018, pp. 389–404.
[24] E. Chou, J. Beal, D. Levy, S. Yeung, A. Haque, and L. FeiFei, “Faster cryptonets: Leveraging sparsity for real-world
encrypted inference,” arXiv preprint arXiv:1811.09953, 2018.
[25] K. Simonyan and A. Zisserman, “Very deep convolutional
networks for large-scale image recognition,” https://arxiv.
org/abs/1409.1556, 2014.
[26] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet
classification with deep convolutional neural networks,”
2012.
[27] “MNIST database,” http://yann.lecun.com/exdb/mnist/,
accessed: 2017-09-24.
[28] A. Krizhevsky, V. Nair, and G. Hinton, “The CIFAR-10
dataset,” 2014.
[29] J. Wu, Q. Zhang, and G. Xu, “Tiny ImageNet Challenge,”
http://cs231n.stanford.edu/reports/2017/pdfs/930.pdf.
[30] T. Araki, J. Furukawa, Y. Lindell, A. Nof, and K. Ohara,“High-throughput semi-honest secure three-party computation with an honest majority,” in ACM Conference on
Computer and Communications Security (CCS), 2016.
[31] D. Bogdanov, S. Laur, and J. Willemson, “Sharemind: A
framework for fast privacy-preserving computations,” inEuropean Symposium on Research in Computer Security(ESORICS), 2008, pp. 192–206.
[32] “Announcing securenn in tf-encrypted,” https://mc.ai/
announcing-securenn-in-tf-encrypted/, 2018.
[33] PySyft, “Implement securenn within pysyft #1990,” https://github.com/OpenMined/PySyft/issues/1990, 2019.
[34] “Microsoft photodna cloud service,” 2018. [Online]. Available:
https://www.microsoft.com/en-us/photodna[35] R. Shokri, M. Stronati, C. Song, and V. Shmatikov, “Membership inference attacks against machine learning models,”in IEEE Symposium on Security and Privacy (S&P), 2017.
[36] M. Fredrikson, S. Jha, and T. Ristenpart, “Model inversion
attacks that exploit confidence information and basic
countermeasures,” in ACM Conference on Computer andCommunications Security (CCS). ACM, 2015.
[37] F. Tramèr, F. Zhang, A. Juels, M. K. Reiter, and T. Ristenpart,“Stealing machine learning models via prediction APIs,” inFalcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning

USENIX Security Symposium, 2016.
[38] E. Kushilevitz, Y. Lindell, and T. Rabin, “Informationtheoretically secure protocols and security under composition,” SIAM Journal on Computing, vol. 39, no. 5, pp.
2090–2112, 2010.
[39] S. Ioffe and C. Szegedy, “Batch normalization: Accelerating
deep network training by reducing internal covariate shift,”in International Conference on Machine Learning, 2015, pp.
448–456.
[40] O. Catrina and A. Saxena, “Secure computation with fixedpoint numbers,” in International Conference on Financial
Cryptography and Data Security, 2010, pp. 35–50.
[41] M. Aliasgari, M. Blanton, Y. Zhang, and A. Steele, “Securecomputation on floating point numbers,” in Symposium on
Network and Distributed System Security (NDSS), 2013.
[42] O. Goldreich, S. Micali, and A. Wigderson, “How to play
any mental game or a completeness theorem for protocols
with honest majority,” in ACM Symposium on Theory ofComputing (STOC), 1987.
[43] R. Canetti, “Security and composition of multiparty cryptographic protocols,” in Journal of CRYPTOLOGY, vol. 13,
no. 1, 2000, pp. 143–202.
[44] ——, “Universally composable security: A new paradigm for
cryptographic protocols,” in IEEE Symposium on Foundations of Computer Science (FOCS), 2001, pp. 136–.
[45] B. D. Rouhani, M. S. Riazi, and F. Koushanfar, “DeepSecure:
Scalable provably-secure deep learning,” in Annual Design
Automation Conference, 2018.
[46] C. Peikert, V. Vaikuntanathan, and B. Waters, “A framework
for efficient and composable oblivious transfer.” in Advancesin Cryptology—CRYPTO, 2008.
[47] W. Zheng, R. A. Popa, J. E. Gonzalez, and I. Stoica, “Helen:
Maliciously secure coopetitive learning for linear models,” inIEEE Symposium on Security and Privacy (S&P), 2019.
[48] R. Gilad-Bachrach, N. Dowlin, K. Laine, K. E. Lauter,
M. Naehrig, and J. Wernsing, “CryptoNets: Applying neuralnetworks to encrypted data with high throughput andaccuracy,” in International Conference on Machine Learning,
2016.
[49] E. Hesamifard, H. Takabi, and M. Ghasemi, “CryptoDL: Deep
Neural Networks over Encrypted Data,” in Privacy Enhancing
Technologies Symposium (PETS), 2018.
[50] D. Demmler, T. Schneider, and M. Zohner, “ABY – A
framework for efficient mixed-protocol secure two-party
computation.” in Symposium on Network and Distributed
System Security (NDSS), 2015.
[51] F. Chollet et al., “Keras,” https://github.com/fchollet/keras,
2015.
[52] E. Makri, D. Rotaru, N. P. Smart, and F. Vercauteren, “EPIC:
efficient private image classification (or: learning from themasters),” in Cryptographers’ Track at the RSA Conference.
Springer, 2019, pp. 473–492.
[53] N. Agrawal, A. Shahin Shamsabadi, M. J. Kusner, and
A. Gascón, “Quotient: Two-party secure neural network
training and prediction,” in ACM Conference on Computerand Communications Security (CCS). ACM, 2019, pp.
1231–1247.
[54] B. Jacob, S. Kligys, B. Chen, M. Zhu, M. Tang, A. Howard,
H. Adam, and D. Kalenichenko, “Quantization and trainingof neural networks for efficient integer-arithmetic-only205

inference,” in IEEE Conference on Computer Vision and
Pattern Recognition, 2018.
[55] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradientbased learning applied to document recognition,” Proceedingsof the IEEE, vol. 86, no. 11, pp. 2278–2324, 1998.
[56] Y. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E.
Howard, W. Hubbard, and L. D. Jackel, “Backpropagation applied to handwritten zip code recognition,” NeuralComputation, vol. 1, no. 4, pp. 541–551, 1989.

A Recent Related Work
We compare the theoretical complexities of protocols in Astra, BLAZE, FLASH, and Trident with protocols in Falcon. Since the approach for computing nonlinear operations is fundamentally different, we compare
the end-to-end overhead of the ReLU protocol in eachof these frameworks. Table 8 shows a comparison of thetheoretical complexities. Note that BLAZE and Astraare 3PC protocols and FLASH and Trident are 4PC protocols. In terms of evaluation of neural networks, mostof these works evaluate their approach only over DNNs.
None of these frameworks evaluate their approaches fortraining of neural networks. Comparison of concrete efficiency of these protocols is documented in Table 2.

B Theoretical Complexity
We theoretically estimate the overheads of our protocols in Table 9. The dominant round complexity for
private compare comes from the string multiplicationin Step 6. wrap3 requires one additional round and one
additional ring element (two in malicious security) overprivate compare. Computing derivative of ReLU is alocal computation over the wrap3 function. Computing
ReLU requires two additional rounds and one ring element (two for malicious). Maxpool and derivative of
require rounds proportional to the area of the filter. Finally, pow, division, and batch-norm require a quadratic
number of rounds in `.

C Datasets
We select 3 datasets popularly used for training image classification models — MNIST [27], CIFAR-10 [28],and Tiny ImageNet [29]. We describe these below:(A) MNIST [27]: MNIST is a collection of handwritten digits dataset. It consists of 60,000 images in the training set and 10,000 in the test set.
Each image is a 28 × 28 pixel image of a handwritten digit along with a label between 0 and
9. We evaluate Network-A, B, C, and the LeNet

206

Falcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning

3PC
Astra

ProtocolMultiplication
ReLU

4PC

BLAZE

FLASH

FalconTrident

Round

Comm.

Round

Comm.

Round

Comm.

Round

Comm.

Round

Comm.

1
3 + log `

4`
45`

1
4

3`
(κ + 7)`1
5 + log `

4`
32`

1
log ` + 10

3`
46`

1
4

3`
8` + 2

Table 8. Comparison of theoretical complexities of privacy-preserving protocols for Multiplication and ReLU with Astra, BLAZE,FLASH, Trident, and Falcon. ` is the bit-size of the datatype and κ is the security parameter (usually set to 40).

Basic
Protocols

MatMulPrivate Compare
wrap3

CompoundProtocols

ProtocolReLU andDerivative of ReLU
MaxPool and
Derivative of Maxpool
Pow
Division
Batch Norm

Semi-Honest

Dependence

Malicious

RoundsComm

RoundsComm(x × y)(y × z)nn

1
2 + log2 `3 + log2 `

kxz
2kn
3kn

1
2 + log2 `3 + log2 `

2kxz
4kn
6kn

n

5 + log2 `4kn

5 + log2 `8kn

n, {w, h}(wh − 1)(7 + log2 `)5k + wh(wh − 1)(7 + log2 `)10k + 2wh

n
n
r, n

5` + ` · log2 `7 + 5` + ` · log2 `15 + 5` + ` · log2 `4kn`
4kn` + 7kn
kr + 4kr` + 14krn

5` + ` · log2 `7 + 5` + ` · log2 `15 + 5` + ` · log2 `8kn`
8kn` + 14kn
2kr + 8kr` + 28krn

Table 9. Theoretical overheads of basic and compound protocols. Communication is in Bytes where ` is the logarithm of the ring size
and k is its Byte size. We use n to denote the size of the vector in vectorized implementations. Malicious protocols suffer from higher
communication complexity compared to semi-honest protocols that results in poor concrete efficiency when implemented.

network on this dataset in both the semi-honest
and maliciously secure variants.
(B) CIFAR-10 [28]: CIFAR-10 consists of 60,000
images (50,000 training and 10,000 test images)of 10 different classes (such as airplanes, dogs,
horses etc.). There are 6,000 images of each classwith each image consisting of a colored 32 × 32
image. We perform private training and inferenceof AlexNet and VGG16 on this dataset.
(C) Tiny ImageNet [29]: Tiny ImageNet dataset
consists of 100,000 training samples and 10,000
test samples with 200 different classes [29]. Eachsample is cropped to a size of 64 × 64 × 3. We
perform private training and inference of AlexNet
and VGG16 on this dataset.

D Networks
We evaluate Falcon on the following popular deeplearning networks. We select these networks based on
the varied range of model parameters and different typesof layers used in the network architecture. The first three
networks are purposely selected to perform performancecomparison of Falcon with prior work that evaluatedon these models. The number of layers that we report
include only convolutional and fully connected layers.

We also note that we enable the exact same functionality as prior work with no further approximations. Our
networks achieve an accuracy of 97.42% on NetworkA, 97.81% on Network-B, 98.64% on Network-C, and99.15% on LeNet – similar to the accuracy obtained by
SecureNN, SecureML, and ABY3 [4, 11, 12].
(A) Network-A: This is a 3 layer fully-connected network with ReLU activation after each layer as wasevaluated in SecureML [4]. This is the smallest network with around 118K parameters.
(B) Network-B: This network is a 3 layer networkwith a single convolution layer followed by 2 fullyconnected layers and ReLU activations. This architecture is chosen from Chameleon [5] with approximately 100K parameters.
(C) Network-C: This is a 4 layer network with 2
convolutional and 2 fully-connected layers selectedfrom prior work MiniONN [6]. This network uses
Max Pooling in addition to ReLU layer and hasaround 10,500 parameters in total.
(D) LeNet: This network, first proposed by LeCunet al. [55] was used in automated detection of zip
codes and digit recognition [56]. The network contains 2 convolutional layers and 2 fully connected
layers with 431K parameters.

Falcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning(E) AlexNet: AlexNet is the famous winner of the2012 ImageNet ILSVRC-2012 competition [26]. It
has 5 convolutional layers and 3 fully connected
layers and uses batch norm layer for stability, efficient training and has about 60 million parameters.
Falcon is the first private deep learning framework that evaluates AlexNet because of the support for batch norm layer in our system.
(F) VGG16: The last network which we implement
is called VGG16, the runner-up of the ILSVRC2014 competition [25]. VGG16 has 16 layers andhas about 138 million parameters.

E Functionality Descriptions
FPC
Input: The functionality receives inputs {Jxi Kp }`i=1 , r
Output: Compute the followingP
1. Reconstruct bits xi and x =xi · 2 i
2. Compute b = (x ≥ r)
3. Generate random shares of b and send back to thepartiesFig. 3. Ideal functionality for ΠPC

FWA
Input: The functionality receives inputs JaKL .
Output: Compute the following
1. Compute b = wrap3 (a1 , a2 , a3 , L)
2. Generate random shares of b and send back to thepartiesFig. 4. Ideal functionality for ΠWA

FReLU
Input: The functionality receives inputs JaKL .
Output: Compute the following
1. Compute b = ReLU(a1 + a2 + a3 (mod L))
2. Generate random shares of b and send back to thepartiesFig. 5. Ideal functionality for ΠReLU

207

ΠPrep
Usage: This is used to generate pre-processing material required for the online protocol.
Setup: This step will have to be done only once.
1. Each party Pi chooses a random seed ki
2. Send this random seed to party Pi+1
Common randomness: Let F be any seeded PNRG. Then
3-out-of-3 and 2-out-of-3 common randomness describedin Section 3.2 can be generated as follows:
1. αi = Fki (cnt) − Fki−1 (cnt) and cnt++
2. (αi , αi−1 ) = (Fki (cnt), Fki−1 (cnt)) and cnt++
Truncation Pair: Generate truncation pair JrK, Jr0 K =Jr/2d K.
1. Run protocol Πtrunc2 from [11] (Figure 3)
Correlated randomness for Private Compare:
Generate correlated randomness required for ΠPC
1. Sample random bit JbK2
2. Use bit injection from [11] JbK2 → JbKp
3. Sample random values m1 , . . . mk ∈ Zp .
4. Compute and open mp−1
, . . . , mp−1.
1k5. Remove openings that equal 0 and queue openings that equal 1. Note that this computation takes
dlog2 pe rounds and can be amortized for efficiency(by setting a large value of k).
Correlated randomness for Wrap3 : Generatecorrelated randomness required for ΠWA
1. Sample random bits Jri K2 for i ∈ [`]2. Perform bit composition from [11] to get Jri KL
3. Use bit injection from [11] Jri K2 → Jri Kp
4. Use the optimized full adder FA to compute the final
carry bit. Note that this bit is precisely wrap3 (·)
Correlated randomness for ReLU: Generatecorrelated randomness required for ΠReLU
1. Sample random bit JbK2
2. Use bit injection from [11] JbK2 → JbKLCorrelated randomness for Maxpool and Division:
No additional correlated randomness necessary other thanthat used in their subroutines.
Fig. 6. Protocols for generating various pre-processing materialFalcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning

208

FMaxpool

FBN

Input: The functionality receives inputs Ja1 KL , . . . Jan KL .
Output: Compute the following
1. Reconstruct a1 , . . . an and compute k=
argmax{a1 , . . . an }.
2. Set ek = {e1 , e2 , . . . en } with ei = 0 ∀i 6= k andek = 1.
3. Generate random shares of ak and ek and send backto the parties.

Input: The functionality receives inputs Ja1 KL , . . . Jan KL
and JγKL , JβKL and an index k ∈ {0, 1, . . . ` − 1}.
Output: Compute the following
1. Reconstruct a1 , . . . an and compute µ and σ 2 as given
in Step 1,2 of Algorithm 7
2. Set b = σ 2 +  and compute α such that 2α ≤ b <2α+1
3. If k = 0 send α[i] for i ∈ {` − 1, . . . , 0} to all parties.
4. If k 6= 0 send α[i] for i ∈ {` − 1, . . . , k} to all parties
and then Abort.
5. Complete steps 4-8 of Algorithm 7 and return random
shares of the output.

Fig. 7. Ideal functionality for ΠMaxpool

Fig. 10. Ideal functionality for ΠBN

FPowInput: The functionality receives inputs JbKL and an indexk ∈ {0, 1, . . . ` − 1}.
Output: Compute each bit of α sequentially as follows:
1. Reconstruct b.
2. Compute α such that 2α−1 < b ≤ 2α
3. If k = 0 send α[i] for i ∈ {` − 1, . . . , 0} to all parties.
4. If k 6= 0 send α[i] for i ∈ {` − 1, . . . , k} to all parties
and then Abort.
Fig. 8. Functionality for ΠPow

FDiv
Input: The functionality receives inputs JaKL , JbKL and anindex k ∈ {0, 1, . . . ` − 1}.
Output: Compute the following
1. Reconstruct a, b.
2. Compute α such that 2α ≤ b < 2α+1
3. If k = 0 send α[i] for i ∈ {` − 1, . . . , 0} to all parties.
4. If k 6= 0 send α[i] for i ∈ {` − 1, . . . , k} to all parties
and then Abort.
5. Generate random shares of a · AppDiv(b) and sendback to the parties
Fig. 9. Ideal functionality for ΠDiv