# ppAURORA: Privacy Preserving Area Under Receiver Operating Characteristic
and Precision-Recall Curves with Secure 3-Party Computation

Ali Burak Ünal
Methods in Medical Informatics
Department of Computer Science
University of Tuebingen
Germany
<EMAIL_ADDRESS>
Nico Pfeifer
Methods in Medical Informatics
Department of Computer Science
University of Tuebingen
Germany
<EMAIL_ADDRESS>
&Mete Akgün
Methods in Medical Informatics
Department of Computer Science
University of Tuebingen
Germany
<EMAIL_ADDRESS>
Also associated with Statistical Learning in Computational Biology, Max Planck
Institute for Informatics, Saarbrücken, GermanyAlso associated with
Translational Bioinformatics, University Hospital Tuebingen, Tuebingen,
Germany

###### Abstract

Computing an AUC as a performance measure to compare the quality of different
machine learning models is one of the final steps of many research projects.
Many of these methods are trained on privacy-sensitive data and there are
several different approaches like $\epsilon$-differential privacy, federated
machine learning and methods based on cryptographic approaches if the datasets
cannot be shared or evaluated jointly at one place. In this setting, it can
also be a problem to compute the global performance measure like an AUC, since
the labels might also contain privacy-sensitive information. There have been
approaches based on $\epsilon$-differential privacy to deal with this problem,
but to the best of our knowledge, no exact privacy preserving solution has
been introduced. In this paper, we propose an MPC-based framework, called
ppAURORA, with private merging of sorted lists and novel methods for comparing
two secret-shared values, selecting between two secret-shared values,
converting the modulus, and performing division to compute the exact AUC as
one could obtain on the pooled original test samples. With ppAURORA
computation of the exact area under precision-recall curve and receiver
operating characteristic curve is even possible when ties between prediction
confidence values exist. To show the applicability of ppAURORA, we use it to
evaluate a model trained to predict acute myeloid leukemia therapy response
and we also assess its scalability via experiments on synthetic data. The
experiments show that we efficiently compute exactly the same AUC with both
evaluation metrics in a privacy preserving manner as one can obtain on the
pooled test samples in the plaintext domain. Our solution provides security
against semi-honest corruption of at most one of the servers performing the
secure computation.

##  1 Introduction

Recently, privacy preserving machine learning studies aimed at protecting
sensitive information during training and/or testing of a model in scenarios
where data is distributed between different sources and cannot be shared in
plaintext (Mohassel and Zhang, 2017; Wagh et al., 2018; Juvekar et al., 2018;
Mohassel and Rindal, 2018; Ünal et al., 2019; Damgård et al., 2019; Byali et
al., 2020; Patra and Suresh, 2020). However, privacy protection in the
computation of the area under curve (AUC), which is one of the most preferred
methods to compare different machine learning models with binary outcome, has
not been addressed sufficiently. Even though there are no studies in the
literature enabling such a computation for the precision-recall (PR) curve,
there are several differential privacy based approaches in the literature for
the receiver operating characteristic (ROC) curve (Chaudhuri and Vinterbo,
2013; Boyd et al., 2015; Chen et al., 2016). Briefly, they protect the privacy
of the data by introducing noise into the computation so that one cannot
obtain the original data employed in the computation. However, due to the
nature of differential privacy, the resulting AUC is different from the one
which could be obtained by using non-perturbed prediction confidence values
(PCVs). For private computation of the exact AUC, there exists no approach in
the literature to the best of our knowledge.

In this paper, we propose the privacy preserving area under receiver operating
characteristic and precision-recall curves (ppAURORA) based on a secure
3-party computation framework to address the necessity of an efficient,
private and secure computation of the exact AUC. We compute the area under the
PR curve (AUPR) and ROC curve (AUROC) with ppAURORA. We address two different
cases of ROC curve in ppAURORA by two different versions of AUROC computation.
The first one is designed for the computation of the exact AUC by using PCVs
with no tie. In case of a tie of PCVs of samples from different classes, it
just approximates the metric based on the order of the samples, having a
problem when values of both axes change at the same time. In order to compute
the exact AUC even in case of a tie, we introduce the second version with a
slightly higher communication cost than the first approach. Along with the
AUC, both are capable of protecting the information of the number of samples
belonging to the classes from all participants of the computation, which could
be used to obtain the order of the labels of the PCVs (Whitehill, 2019).
Furthermore, since we do not provide the data sources with the ROC curve, they
cannot regenerate the underlying true data. Therefore, both versions are
secure against such attacks (Matthews and Harel, 2013). We utilized the with-
tie version of AUROC computation to compute the AUPR since the values of both
axes can change at the same time even if there is no tie.

We introduce a novel 3-party computation framework to achieve privacy
preserving AUC computation with ppAURORA. The framework consists of privacy
preserving sorting and four operations with novel and efficient versions,
which are select share ($\mathsf{MUX}$), modulus conversion ($\mathsf{MC}$),
compare ($\mathsf{CMP}$) and division ($\mathsf{DIV}$). $\mathsf{MUX}$ is
designed to select one of two secret shares based on a secret shared bit
value. $\mathsf{MC}$ privately converts the ring of a secret shared value from
$2^{\ell-1}$ to $2^{\ell}$. $\mathsf{CMP}$ compares two secret shared values,
determines if the first argument is larger than the second one without
revealing values and splits the result in a secret shared way. $\mathsf{DIV}$
performs the division of two secret shared values without sacrificing the
privacy of the values. Note that our new $\mathsf{DIV}$ is specifically
customized for efficient and secure AUC computation.

##  2 Scenarios

In this section, we describe the scenarios at which ppAURORA is applicable.
Note that it is not limited to these scenarios.

End-to-end MPC-based Collaborative Learning: Recently, researchers proposed
multi-party computation (MPC) based training and testing of several machine
learning algorithms (Mohassel and Zhang, 2017; Wagh et al., 2018; Damgård et
al., 2019). Their approaches can train the model privately and
collaboratively, and make predictions on the test data of the data sources
involved in the computation. However, the privacy preserving collaborative
evaluation of the model is lacking. To fulfill such a gap, one can integrate
ppAURORA at the end of the process once the PCVs are secret shared among two
computing parties. One possible scenario would be that one wants to build a
model for predicting hospitalization times for COVID-19 patients. Usually, the
personal data cannot be shared easily, due to the private nature of the data,
but even sharing the hospitalization times might be problematic in case the
hospitals do not want to allow competitors to learn about this piece of
information. Nevertheless, one can assume that a model built on data from many
hospitals will perform much better than models built on individual datasets
and that the global AUC will allow for a better model selection than an
average of locally computed AUCs. This privacy preserving global AUC
computation can be performed with our ppAURORA.

Evaluation of Models Trained by Federated Learning: In some cases, the data is
not allowed to be shared at all. For such cases, federated learning has been
widely utilized to train a collaborative machine learning model without
gathering the data in one place. Each data source updates the model by its own
data in an online learning process and passes the model to the next data
source until the model converges or the iteration limit is reached. Once the
data sources obtain the trained model, they make the predictions of their own
test data. In order to collaboratively evaluate the performance of the model,
they can utilize ppAURORA.

##  3 Preliminaries

Security Model: In this study, we prove the full security of our solution
(i.e., privacy and correctness) in the presence of semi-honest adversaries
that follow the protocol specification, but try to learn information from the
execution of the protocol. We consider a scenario where a semi-honest
adversary corrupts a single server and an arbitrary number of data owners in
the simulation paradigm (Lindell, 2017; Canetti, 2001) where two worlds are
defined: the real world where parties run the protocol without any trusted
party, and the ideal world where parties make the computation through a
trusted party. Security is modeled as the view of an adversary called a
simulator $\mathcal{S}$ in the ideal world, who cannot be distinguished from
the view of an adversary $\mathcal{A}$ in the real world. The universal
composability framework (Canetti, 2001) introduces an adversarial entity
called environment $\mathcal{Z}$, which gives inputs to all parties and reads
outputs from them. The environment is used in modeling the security of end-to-
end protocols where several secure protocols are used arbitrarily. Security
here is modeled as no environment can distinguish if it interacts with the
real world and the adversary $\mathcal{A}$ or the ideal world and the
simulator $\mathcal{S}$. We also provide privacy in the presence of a
malicious adversary corrupting any single server, which is formalized by Araki
et al. (2016). The privacy is formalized by saying that a malicious party,
which arbitrarily deviates from the protocol description, cannot learn
anything about the inputs and outputs of the honest parties.

Notations: In our secure protocols, we use additive secret sharing over three
different rings $\mathbb{Z}_{L}$, $\mathbb{Z}_{K}$ and $\mathbb{Z}_{P}$ where
$L=2^{\ell}$, $K=2^{\ell-1}$, $P=67$ and $\ell=64$. We denote two shares of
$x$ over $\mathbb{Z}_{L}$, $\mathbb{Z}_{K}$ and $\mathbb{Z}_{P}$ with
($\langle x\rangle_{0}$, $\langle x\rangle_{1}$), ($\langle x\rangle_{0}^{K}$,
$\langle x\rangle_{1}^{K}$) and ($\langle x\rangle_{0}^{P}$, $\langle
x\rangle_{1}^{P}$), respectively. If a value $x$ is shared over the ring
$\mathbb{Z}_{P}$, each bit of $x$ is additively shared in $\mathbb{Z}_{P}$.
This means $x$ is shared as a vector of $64$ shares where each share takes a
value between $0$ and $66$. We also use boolean sharing of a single bit which
is denoted with ($\langle x\rangle_{0}^{B}$, $\langle x\rangle_{1}^{B}$).

###  3.1 Secure Multi-party Computation

Secure multi-party computation was proposed in the 1980s (Yao, 1986; Goldreich
et al., 1987). These studies showed that multiple parties can compute any
function on inputs without learning anything about the inputs of the other
parties. Let us assume that there are $n$ parties $I_{1},\cdots,I_{n}$ and
$I_{i}$ has a private input $x_{i}$ for $i\in\\{1,\ldots,n\\}$. All parties
want to compute the arbitrary function
$(y_{1},\ldots,y_{n})=f(x_{1},\ldots,x_{n})$ and get the result $y_{i}$. MPC
allows the parties to compute the function through an interactive protocol and
$I_{i}$ to learn only $y_{i}$.

We first explain the 2-out-of-2 additive secret sharing and how addition (ADD)
and multiplication (MUL) are computed. In additive secret sharing, an
$\ell$-bit value $x$ is shared additively in the ring $\mathbb{Z}_{L}$ as the
sum of two values. For $\ell$-bit secret sharing of $x$, we have $\langle
x\rangle_{0}+\langle x\rangle_{1}\equiv x\mod L$ where $I_{i}$ knows only
$\langle x\rangle_{i}$ and $i\in\\{0,1\\}$. All arithmetic operations are
performed in the ring $\mathbb{Z}_{L}$. For additive secret sharing, we use
protocols based on Beaver’s multiplication triples (Beaver, 1991).

Addition: $\langle z\rangle=\langle x\rangle+\langle y\rangle$. $I_{i}$
locally computes $\langle z\rangle_{i}=\langle x\rangle_{i}+\langle
y\rangle_{i}$. In order to compute the addition of a shared value $\langle
x\rangle$ and a constant $c$, $I_{i}$ locally computes $\langle
z\rangle_{i}=\langle x\rangle_{i}+c$ and $I_{1-i}$ locally computes $\langle
z\rangle_{1-i}=\langle x\rangle_{1-i}$.

Multiplication: $\langle z\rangle=\langle x\rangle\cdot\langle y\rangle$.
Multiplication is performed using a pre-computed multiplication triple
$\langle c\rangle_{i}=\langle a\rangle_{i}\cdot\langle b\rangle_{i}$ (Beaver,
1991). $I_{i}$ computes $\langle e\rangle_{i}=\langle x\rangle_{i}-\langle
a\rangle_{i}$ and $\langle f\rangle_{i}=\langle y\rangle_{i}-\langle
b\rangle_{i}$. $I_{i}$ sends $\langle e\rangle_{i}$ and $\langle f\rangle_{i}$
to $I_{1-i}$. $I_{i}$ reconstructs $e$ and $f$, and then computes $\langle
z\rangle_{i}=i\cdot e\cdot f+f\cdot\langle a\rangle_{i}+e\cdot\langle
b\rangle_{i}+\langle c\rangle_{i}$. The computation of the multiplication
triple is performed via homomorphic encryption or oblivious transfer. $I_{i}$
cannot perform multiplication locally.

###  3.2 Area Under Curve

One of the most common ways to summarize the plot-based model evaluation
metrics is area under curve (AUC) which measures the area under the curve. It
is applicable to various different evaluation metrics. In this study, we
employ AUC to measure the area under the ROC curve and the PR curve.

####  3.2.1 Area Under ROC Curve (AUROC)

In machine learning problems with binary outcome, the ROC curve is very
effective to take the sensitivity and the specificity of the classifier into
account by plotting the false positive rate (FPR) on the x-axis and the true
positive rate (TPR) on the y-axis. AUC summarizes this plot by measuring the
area between the line and the x-axis, which is the area under ROC curve
(AUROC). Let us assume that $M$ is the number of test samples, $V\in[0,1]^{M}$
contains the sorted PCVs of test samples in descending order, $T\in[0,1]^{M}$
and $F\in[0,1]^{M}$ contain the corresponding TPR and FPR values,
respectively, where the threshold for entry $i$ is set to $V[i]$, and
$T[0]=F[0]=0$. In case that there is no tie in $V$, the privacy-friendly AUROC
computation is as follows:

$\small AUROC=\sum_{i=1}^{M}\Big{(}T[i]\cdot(F[i]-F[i-1])\Big{)}$ (1)

This formula just approximates the exact AUROC in case of a tie in $V$
depending on the order of the samples. As an extreme example, let $V$ have
$10$ samples with the same PCV. The first $5$ samples have label $1$ and the
second $5$ samples have label $0$. Such a setting outputs $AUROC=1$. As a
contrary, if we have samples with $0$ at the beginning and samples with $1$
later, we obtain $AUROC=0$. In order to define an accurate formula for the
AUROC in case of such a tie condition, let $\xi$ be the vector of indices in
ascending order where the PCV of the sample at that index and the preceding
are different for $0\leq|\xi|\leq M$ where $|\xi|$ denotes the size of the
vector. Assuming that $\xi[0]=0$, the computation of AUROC can be done as
follows:

$\displaystyle AUROC=\sum_{i=1}^{|\xi|}$
$\displaystyle\Big{(}T[\xi[i-1]]\cdot(F[\xi[i]]-F[\xi[i-1]])+\dfrac{(T[\xi[i]]-T[\xi[i-1]])\cdot(F[\xi[i]]-F[\xi[i-1]])}{2}\Big{)}$
(2)

As Equation 2 indicates, one only needs TPR and FPR values on the points where
the PCV changes to obtain the exact AUROC. We will benefit from this
observation in the privacy preserving AUROC computation.

####  3.2.2 Area Under PR Curve (AUPR)

Another model evaluation metric for machine learning problems with binary
outcome is the PR curve which plots recall on the x-axis and precision on the
y-axis, and it is generally preferred over AUROC for scenarios with class
imbalances. The AUC summarizes this plot by measuring the area under the PR
curve (AUPR). Since both precision and recall can change at the same time even
without a tie, we measure the area by using the Equation 2 where $T$ being the
precision and $F$ being the recall.

##  4 Framework

In this section, we give the definitions of basic operations of the framework
that we use in ppAURORA. Note that we include only the operations with novelty
due to the page limit. One can refer to the Supplement for the other
operations.

Selecting One of Two Secret Shared Values: Algorithm 1 performs 3-party
computation to select one of two secret shared values based on the secret
shared bit value (functionality $\mathcal{F}_{\mathsf{MUX}}$). At the
beginning of the protocol, $S_{0}$ and $S_{1}$ hold ($\langle x\rangle_{0}$,
$\langle y\rangle_{0}$, $\langle b\rangle_{0}$) and ($\langle x\rangle_{1}$,
$\langle y\rangle_{1}$, $\langle b\rangle_{1}$), respectively. At the end of
the secure computation, $S_{0}$ and $S_{1}$ hold the fresh shares of
$z=x-b(x-y)$. We utilize the randomized encoding of multiplication (Applebaum,
2017). As shown in Equation 3, we need to multiply two values owned by
different parties in the computation of $\langle b\rangle_{0}(\langle
x\rangle_{1}-\langle y\rangle_{1})$ and $\langle b\rangle_{1}(\langle
x\rangle_{0}-\langle y\rangle_{0}$. We assume that $S_{2}$ is the computation
party and performs these multiplications via the randomized encoding.

$\small\begin{split}z={}&x-b(x-y)\\\ ={}&\langle x\rangle_{0}+\langle
x\rangle_{1}-\langle b\rangle_{0}(\langle x\rangle_{0}-\langle
y\rangle_{0})-\langle b\rangle_{1}(\langle x\rangle_{1}-\langle
y\rangle_{1})-\langle b\rangle_{0}(\langle x\rangle_{1}-\langle
y\rangle_{1})-\langle b\rangle_{1}(\langle x\rangle_{0}-\langle
y\rangle_{0})\end{split}$ (3)

Modulus Conversion: Algorithm 2 describes our 3-party protocol realizing the
functionality $\mathcal{F}_{\mathsf{MC}}$ that converts shares over
$\mathbb{Z}_{K}$ to fresh shares over $\mathbb{Z}_{L}$ where $L=2K$. Assuming
that $S_{0}$ and $S_{1}$ have the shares $\langle x\rangle_{0}^{K}$ and
$\langle x\rangle_{1}^{K}$, respectively, the first step for $S_{0}$ and
$S_{1}$ is to mask their shares by using the shares of the random value
$r\in\mathbb{Z}_{K}$ sent by $S_{2}$. Afterwards, they reconstruct
$(x+r)\in\mathbb{Z}_{K}$, by first computing $\langle y\rangle_{i}^{K}=\langle
x\rangle_{i}^{K}+\langle r\rangle_{i}^{K}$ for $i\in\\{0,1\\}$ and sending
these values to each other. Along with the shares of $r\in\mathbb{Z}_{K}$,
$S_{2}$ also sends the information in boolean shares telling whether the
summation of the shares of $r$ wraps so that $S_{0}$ and $S_{1}$ can convert
$r$ from the ring $\mathbb{Z}_{K}$ to the ring $\mathbb{Z}_{L}$. Once they
reconstruct $y\in\mathbb{Z}_{K}$, $S_{0}$ and $S_{1}$ can change the ring of
$y$ to $\mathbb{Z}_{L}$ by adding $K$ to one of the shares of $y$ if $\langle
y\rangle_{0}^{K}+\langle y\rangle_{1}^{K}$ wraps. After conversion, the
important detail regarding $y\in\mathbb{Z}_{L}$ is to fix the value of it. In
case $(x+r)\in\mathbb{Z}_{K}$ wraps, which we identify by using $\mathsf{PC}$,
depending on the boolean share of the outcome of $\mathsf{PC}$, $S_{0}$ or
$S_{1}$ or both add $K$ to their shares. If both adds, this means that there
is no addition to the value of $y\in\mathbb{Z}_{L}$. At the end, $S_{i}$
subtracts $r_{i}\in\mathbb{Z}_{L}$ from $y_{i}\in\mathbb{Z}_{L}$ and obtains
$x_{i}\in\mathbb{Z}_{L}$ for $i\in\\{0,1\\}$.

SecureNN Wagh et al. (2018) | Our Framework
---|---
Protocol |  Rounds |  Communication |  Protocol |  Rounds |  Communication
$\mathsf{SelectShare}$ |  $2$ |  $5\ell$ |  $\mathsf{MUX}$ |  $2$ |  $6\ell$
$\mathsf{ShareConvert}$ |  4 |  $4\ell\log P+6\ell$ |  $\mathsf{ModulusConversion}$ |  3 |  $4\ell\log P+6\ell$
$\mathsf{ComputeMSB}$ |  5 |  $4\ell\log P+13\ell$ |  $\mathsf{Compare}$ |  5 |  $4\ell\log P+11\ell$
$\mathsf{DIV}$ |  $10\ell_{D}$ |  $(8\ell\log P+24\ell)\ell_{D}$ |  $\mathsf{DIV}$ |  2 |  $6\ell$
Table 1: Complexity comparison of distinguishing protocols of ppAURORA with
SecureNN Wagh et al. (2018)

Comparison of Two Secret Shared Values: Algorithm 3 gives the definition of
the 3-party protocol for the functionality $\mathcal{F}_{\mathsf{CMP}}$ that
compares two secret shared values $x$ and $y$, and outputs zero if $x\geq y$,
$1$ otherwise. In Algorithm 3, we find the value of $(x-y)\wedge 2^{L-1}$ that
indicates the most significant bit (MSB) of $(x-y)$. First, $S_{i}$ where
$i\in\\{0,1\\}$ computes $\langle d\rangle_{i}^{K}=(\langle
x\rangle_{i}^{L}-\langle y\rangle_{i}^{L})\mod K$. $S_{i}$ converts the ring
of $d$ from $\mathbb{Z}_{K}$ to $\mathbb{Z}_{L}$ by calling $\mathsf{MC}$.
Finally, $S_{0}$ and $S_{1}$ subtract the shares of $d$ over $\mathbb{Z}_{L}$
from the shares of $x-y$ and map the result to $1$ if it equals $K$, otherwise
$0$.

Division: Algorithm 4 gives the definition of the 3-party protocol realizing
the functionality $\mathcal{F}_{\mathsf{DIV}}$ that computes $x/y$. $S_{0}$
and $S_{1}$ hold shares of $x$ and $y$, and $\mathsf{DIV}$ outputs fresh
shares of $x/y$. $\mathsf{DIV}$ computes $x/y$ correctly when $S_{0}$ and
$S_{1}$ know the upper bound for $x$ and $y$. Thus, it is not a general
purpose method over $\mathbb{Z}_{L}$. We rather specifically designed it for
ppAURORA since $S_{0}$ and $S_{1}$ know the upper bound of inputs to
$\mathsf{DIV}$ in the computation of the AUC.

###  4.1 Complexities of Our Protocols

There are some frameworks in the literature that also perform 3-party secure
computation. The recently published SecureNN Wagh et al. (2018) has shown
successful results in terms of performance in private CNN training. We
compared our secure protocols with the corresponding building blocks from
SecureNN that one needs to use for computing AUC. Table 1 summarizes the
comparison. It is clear that our protocols have lower costs. Therefore, we can
deduce that our framework outperforms SecureNN in AUC computation. Our novel
protocols ($\mathsf{MUX}$, $\mathsf{MC}$, $\mathsf{CMP}$, $\mathsf{DIV}$)
require at most 5 communication rounds, which is the most important factor
affecting the performance of secure computing protocols. Our new protocols
show an improvement in terms of round complexities.

1 Algorithm  _$\mathsf{MUX}$(__)_

input : $S_{0}$ and $S_{1}$ hold ($\langle x\rangle_{0}$, $\langle
y\rangle_{0}$, $\langle b\rangle_{0}$) and ($\langle x\rangle_{1}$, $\langle
y\rangle_{1}$, $\langle b\rangle_{1}$), respectively.

output : $S_{0}$ and $S_{1}$ get $\langle z\rangle_{0}$ and $\langle
z\rangle_{1}$, respectively, where $z=x-b(x-y)$.

2 $S_{0}$ and $S_{1}$ hold four common random values $r_{i}$ where
$i\in\\{0,1,2,3\\}$

3 $S_{0}$ computes $M_{1}=\langle x\rangle_{0}-\langle b\rangle_{0}(\langle
x\rangle_{0}-\langle y\rangle_{0})+r_{1}\langle b\rangle_{0}+r_{2}(\langle
x\rangle_{0}-\langle y\rangle_{0})+r_{2}r_{3}$, $M_{2}=\langle
b\rangle_{0}+r_{0}$, $M_{3}=\langle x\rangle_{0}-\langle y\rangle_{0}+r_{3}$

4 $S_{0}$ sends $M_{2}$ and $M_{3}$ to $S_{2}$

5 $S_{1}$ computes $M_{4}=\langle x\rangle_{1}-\langle b\rangle_{1}(\langle
x\rangle_{1}-\langle y\rangle_{1})+r_{0}(\langle x\rangle_{1}-\langle
y\rangle_{1})+r_{0}r_{1}+r_{3}\langle b\rangle_{1}$, $M_{5}=(\langle
x\rangle_{1}-\langle y\rangle_{1})+r_{1}$, $M_{6}=\langle b\rangle_{1}+r_{2}$

6 $S_{1}$ sends $M_{5}$ and $M_{6}$ to $S_{2}$

7 $S_{2}$ computes $M_{2}M_{5}+M_{3}M_{6}$ $=z$

8 $S_{2}$ divides $z$ into two shares $(\langle z\rangle_{0}+\langle
z\rangle_{1})$ and sends $\langle z\rangle_{0}$ and $\langle z\rangle_{1}$ to
$S_{0}$ and $S_{1}$, respectively

9 $S_{0}$ computes $\langle z\rangle_{0}=M_{1}-\langle z\rangle_{0}$

10 $S_{1}$ computes $\langle z\rangle_{1}=M_{4}-\langle z\rangle_{1}$

11

Algorithm 1 Select Share ($\mathsf{MUX}$)

1 Algorithm  _$\mathsf{MC}$(__)_

input : $S_{0}$ and $S_{1}$ hold $\langle x\rangle_{0}^{K}$ and $\langle
x\rangle_{1}^{K}$, respectively

output : $S_{0}$ and $S_{1}$ get $\langle x\rangle_{0}$ and $\langle
x\rangle_{1}$, respectively

2 $S_{0}$ and $S_{1}$ hold a common random bit $n^{\prime}$

3 $S_{2}$ picks a random numbers $r\in\mathbb{Z}_{2^{L-1}}$ and generates
$\langle r\rangle_{0}^{K}$, $\langle r\rangle_{1}^{K}$, $\\{\langle
r[j]\rangle_{0}^{p}\\}_{j\in[\ell]}$ and $\\{\langle
r[j]\rangle_{1}^{p}\\}_{j\in[\ell]}$.

4 $S_{2}$ computes $w=\text{isWrap}(\langle r\rangle_{0}^{K},\langle
r\rangle_{1}^{K},K)$ and divides $w$ into two boolean shares $w_{0}^{B}$ and
$w_{1}^{B}$

5 $S_{2}$ sends $\langle r\rangle_{i}^{K}$, $\\{\langle
r[j]\rangle_{i}^{p}\\}_{j\in[\ell]}$ and $w_{i}^{B}$ to $S_{i}$, for each
$i\in\\{0,1\\}$

6 For each $i\in\\{0,1\\}$, $S_{i}$ executes Steps $7$-$8$

7 $\langle y\rangle_{i}^{K}=\langle x\rangle_{i}^{K}+\langle r\rangle_{i}^{K}$

8 $S_{i}$ reconstructs $y$ by exchanging shares with $S_{1-i}$

9 $n_{i}^{B}=\mathsf{PC}(\\{\langle
r[j]\rangle_{i}^{p}\\}_{j\in[\ell]},y,n^{\prime})$

10 $S_{0}$ computes $n_{i}^{B}=n_{i}^{B}\oplus n^{\prime}$

11 For each $i\in\\{0,1\\}$, $S_{i}$ computes $c_{i}^{B}=w_{i}^{B}\oplus
n_{i}^{B}$

12 $S_{0}$ computes $\langle y\rangle_{0}=\langle
y\rangle_{0}^{K}+\text{isWrap}(\langle y\rangle_{0}^{K},\langle
y\rangle_{1}^{K},K)\cdot K$

13 $S_{1}$ sets $\langle y\rangle_{1}=\langle y\rangle_{1}^{K}$

14 For each $i\in\\{0,1\\}$, $S_{i}$ computes $\langle x\rangle_{i}=\langle
y\rangle_{i}-(\langle r\rangle_{i}^{K}+c_{i}^{B}\cdot K)$

15

Algorithm 2 Modulus Conversion ($\mathsf{MC}$)

##  5 ppAURORA Computation

In this section, we give the description of our protocol for ppAURORA
computation. In ppAURORA, we have data owners that outsource their PCVs and
the ground truth labels in secret shared form and three non-colluding servers
that perform 3-party computation on secret shared PCVs to compute AUC. The
protocol starts with outsourcing by the data sources. Afterward, the servers
perform the desired calculation privately. Finally, they send the shares of
the result back to the data sources. The communication between all parties is
performed over a secure channel (e.g., TLS).

1 Algorithm  _$\mathsf{CMP}$(__)_

input : $S_{0}$ and $S_{1}$ hold ($\langle x\rangle_{0}$, $\langle
y\rangle_{0}$) and ($\langle x\rangle_{1}$, $\langle y\rangle_{1}$),
respectively

output : $S_{0}$ and $S_{1}$ get $\langle z\rangle_{0}$ and $\langle
z\rangle_{1}$, respectively, where $z$ is equal to zero if $x>=y$ and $K$
otherwise

2 $S_{0}$ and $S_{1}$ hold a common random bit $f$

3 For each $i\in\\{0,1\\}$, $S_{i}$ executes Steps $4$-$9$.

4 $\langle d\rangle_{i}^{K}=(\langle x\rangle_{i}-\langle y\rangle_{i})\mod K$

5 $\langle d\rangle_{i}=\mathsf{MC}(\langle d\rangle_{i}^{K})$.

6 $\langle z\rangle_{i}=\langle x\rangle_{i}-\langle y\rangle_{i}-\langle
d\rangle_{i}$.

7 $\langle a[0]\rangle_{i}=ifK-\langle z\rangle_{i}$

8 $\langle a[1]\rangle_{i}=i(1-f)K-\langle z\rangle_{i}$

9 $S_{i}$ sends $\langle a\rangle_{i}$ to $S_{2}$

10 $S_{2}$ reconstructs $a[j]$ where $j\in\\{0,1\\}$ and computes
$a[j]=a[j]/K$

11 $S_{2}$ creates two fresh shares of $a[j]$ where $j\in\\{0,1\\}$ sends them
to $S_{0}$ and $S_{1}$

12 For each $i\in\\{0,1\\}$, $S_{i}$ executes Step $13$

13 $\langle z\rangle_{i}=\langle a[f]\rangle_{i}$

14

Algorithm 3 Comparison of two secret shared values ($\mathsf{CMP}$)

1 Algorithm  _$\mathsf{DIV}$(__)_

input : $S_{0}$ and $S_{1}$ hold ($\langle x\rangle_{0}$, $\langle
y\rangle_{0}$) and ($\langle x\rangle_{1}$, $\langle y\rangle_{1}$),
respectively.

output : $S_{0}$ and $S_{1}$ get $\langle z\rangle_{0}$ and $\langle
z\rangle_{1}$, respectively, where $z=x/y$.

2 $S_{0}$, $S_{1}$ and $S_{2}$ know the common scaling factor $F$

3 $S_{0}$ and $S_{1}$ know the upper limit of $x$ and $y$, which is denoted by
$U$

4 $S_{0}$ and $S_{1}$ hold two common random values $r_{0}$ and $r_{1}$, where
$r_{0}<\lfloor L/2U\rfloor$ and $r_{1}<\lfloor L/2U\rfloor$

5 For each $i\in\\{0,1\\}$, $S_{i}$ executes Steps $4$-$5$.

6 $S_{i}$ computes $\langle a\rangle_{i}=r_{1}\langle
x\rangle_{i}+r_{0}\langle y\rangle_{i}$ and $\langle b\rangle_{i}=r_{1}\langle
y\rangle_{i}$

7 $S_{i}$ sends $\langle a\rangle_{i}$ and $\langle b\rangle_{i}$ to $S_{2}$

8 $S_{2}$ reconstructs $a$ and $b$ and computes $c=aF/b$

9 $S_{2}$ creates two shares of $c$ denoted by $\langle c\rangle_{0}$ and
$\langle c\rangle_{1}$, and sends them to $S_{0}$ and $S_{1}$, respectively

10 $S_{0}$ computes $\langle z\rangle_{0}=\langle c\rangle_{0}$

11 $S_{1}$ computes $\langle z\rangle_{1}=\langle c\rangle_{1}-r_{0}F/r_{1}$

12

Algorithm 4 Division ($\mathsf{DIV}$)

Outsourcing: At the start of ppAURORA, each data owner $H_{i}$ has a list of
PCVs and corresponding ground truth labels for $i\in\\{1,\ldots,n\\}$. Then,
each data owner $H_{i}$ sorts its whole list $T_{i}$ according to PCVs in
descending order and divides it into two additive shares $T_{i_{0}}$ and
$T_{i_{1}}$, and sends $T_{i_{0}}$ and $T_{i_{1}}$ to $S_{0}$ and $S_{1}$,
respectively. We refer to $S_{0}$ and $S_{1}$ as proxies.

Sorting: After the outsourcing phase, $S_{0}$ and $S_{1}$ obtain the shares of
individually sorted lists of PCVs of the data owners. Afterwards, the proxies
need to perform a merging operation on each pair of individually sorted lists
and continue with the merged lists until they obtain the global sorted list of
PCVs. This can be considered as the leaves of a binary tree merging into the
root node, which is, in our case, the global sorted list. Due to the high
complexity of privacy preserving sorting, we decided to make the sorting
parametric to adjust the trade-off between privacy and practicality. Let
$\delta=2a+1$ be this parameter that determines the number of PCVs that will
be added to the global sorted list in each iteration for $a\in\mathbb{N}$,
$T_{i_{k}}$ and $T_{j_{k}}$ be the shares of two individually sorted lists of
PCVs in $S_{k}$s for $k\in\\{0,1\\}$ and $|T_{i}|\geq|T_{j}|$ where $|.|$ is
size operator. At the beginning, the proxies privately compare the lists
elementwise. They utilize the results of the comparison in $\mathsf{MUX}$s to
privately exchange the shares of PCVs in each pair if the PCV in $T_{j}$ is
larger than the PCV in $T_{i}$. In the first $\mathsf{MUX}$, they input the
share in $T_{i_{k}}$ to $\mathsf{MUX}$ first and then the share in $T_{j_{k}}$
along with the share of the result of the comparison to select the larger of
the PCVs and move it to $T_{i_{k}}$. In the second $\mathsf{MUX}$, they
reverse the order to select the smaller of the PCVs and move it to
$T_{j_{k}}$. We call this stage shuffling. Then, they move the top PCV of
$T_{i_{k}}$ to the merged list of PCVs. If $\delta\neq 1$, then they continue
comparing the top PCVs in the lists and moving the largest of them to the
merged list. Once they move $\delta$ PCVs to the merged list, they shuffle the
lists again. Until finishing up the PCVs in $T_{i_{k}}$, the proxies follows
shuffling-moving cycle.

The purpose of the shuffling is to increase the number of candidates for a
specific position and, naturally, lower the chance of matching a PCV in the
individually sorted lists to a PCV in the merged list. The highest possible
chance of a matching is $50\%$. This results in a very low chance of guessing
the matching of whole PCVs in the list. Regarding the effect of $\delta$ on
the privacy, it is important to note that $\delta$ needs to be an odd number
to make sure that shuffling always leads to increment in the number of
candidates. Even value of $\delta$ may cause ineffective shuffling during the
sorting. Furthermore, $\delta=1$ provides the utmost privacy, which means that
the chance of guessing the matching of the whole PCVs is 1 over the number of
all possible merging of those two individually sorted lists. However, the
execution time of sorting with $\delta=1$ can be relatively high. For
$\delta\neq 1$, the execution time can be low but the number of possible
matching of PCVs in the individually sorted list to the merged list decreases
in parallel to the increment of $\delta$. As a guideline on the choice of
$\delta$, one can decide it based on how much privacy loss any matching could
cause on the specific task. In case of $\delta\neq 1$ and $|T_{j_{k}}|=1$ at
some point in the sorting, the sorting continues as if it had just started
with $\delta=1$ to make sure that the worst case scenario for guessing the
matching can be secured. More details of the sorting phase are in the
Supplement.

###  5.1 Secure Computation of AUROC

Once $S_{0}$ and $S_{1}$ obtain the global sorted list of PCVs, they calculate
the AUROC based on this list by employing one of the versions of AUROC
depending on whether there exists tie in the list.

input : $\langle T\rangle_{i}=(\\{\langle con_{1}\rangle_{i},\langle
label_{1}\rangle_{i}\\},...,$ $\\{\langle con_{M}\rangle_{i},\langle
label_{M}\rangle_{i}\\})$, $\langle T\rangle_{i}$ is a share of the global
sorted list of PCVs, and labels

1 For each $i\in\\{0,1\\}$, $S_{i}$ executes Steps $2$-$11$

2 $\langle TP\rangle_{i}\leftarrow 0$, $\langle P\rangle_{i}\leftarrow 0$,
$\langle pFP\rangle_{i}\leftarrow 0$, $\langle N\rangle_{i}\leftarrow 0$

3 foreach  _item $\langle t\rangle\in\langle T\rangle$_ do

4 $\langle TP\rangle_{i}\leftarrow\langle TP\rangle_{i}+\langle
t.label\rangle_{i}$

5 $\langle P\rangle_{i}\leftarrow\langle P\rangle_{i}+i$

6 $\langle FP\rangle_{i}\leftarrow\langle P\rangle_{i}-\langle TP\rangle_{i}$

7 $\langle A\rangle_{i}\leftarrow\mathsf{MUL}(\langle TP\rangle_{i},\langle
FP\rangle_{i}-\langle pFP\rangle_{i})$

8 $\langle N\rangle_{i}\leftarrow\langle N\rangle_{i}+\langle A\rangle_{i}$

9 $\langle pFP\rangle_{i}\leftarrow\langle FP\rangle_{i}$

10

11$\langle D\rangle_{i}\leftarrow\mathsf{MUL}(\langle TP\rangle_{i},\langle
FP\rangle_{i})$

12 $\langle ROC\rangle_{i}\leftarrow\mathsf{DIV}(\langle N\rangle_{i},\langle
D\rangle_{i})$

Algorithm 5 Secure AUROC computation without ties

input : $\langle T\rangle_{i}=(\\{\langle con_{1}\rangle_{i},\langle
label_{1}\rangle_{i}\\},$ $,...,$ $\\{\langle con_{M}\rangle_{i},\langle
label_{M}\rangle_{i}\\})$, $\langle T\rangle_{i}$ is a share of the global
sorted list of PCVs, and labels

1 For each $i\in\\{0,1\\}$, $S_{i}$ executes Steps $2$-$18$

2 $\langle TP\rangle_{i}\leftarrow 0$, $\langle P\rangle_{i}\leftarrow 0$,
$\langle pFP\rangle_{i}\leftarrow 0$, $\langle pTP\rangle_{i}\leftarrow 0$,
$\langle N_{1}\rangle_{i}\leftarrow 0$, $\langle N_{2}\rangle_{i}\leftarrow 0$

3 foreach  _item $\langle t\rangle_{i}\in\langle T\rangle_{i}$_ do

4 $\langle TP\rangle_{i}\leftarrow\langle TP\rangle_{i}+\langle
t.label\rangle_{i}$

5 $\langle P\rangle_{i}\leftarrow\langle P\rangle_{i}+i$

6 $\langle FP\rangle_{i}\leftarrow\langle P\rangle_{i}-\langle TP\rangle_{i}$

7

8 $\langle A\rangle_{i}\leftarrow\mathsf{MUL}(\langle pTP\rangle_{i},\langle
FP\rangle_{i}-\langle pFP\rangle_{i})$

9 $\langle A\rangle_{i}\leftarrow\mathsf{MUL}(\langle A\rangle_{i},\langle
t.con\rangle_{i})$

10 $\langle N_{1}\rangle_{i}\leftarrow\langle N_{1}\rangle_{i}+\langle
A\rangle_{i}$

11

12 $\langle A\rangle_{i}\leftarrow\mathsf{MUL}(\langle TP\rangle_{i}-\langle
pTP\rangle_{i},\langle FP\rangle_{i}-\langle pFP\rangle_{i})$

13 $\langle A\rangle_{i}\leftarrow\mathsf{MUL}(\langle A\rangle_{i},\langle
t.con\rangle_{i})$

14 $\langle N_{2}\rangle_{i}\leftarrow\langle N_{2}\rangle_{i}+\langle
A\rangle_{i}$

15 $\langle pre\\_FP\rangle_{i}\leftarrow\mathsf{MUX}(\langle
pFP\rangle_{i},\langle FP\rangle_{i},\langle t.con\rangle_{i})$

16 $\langle pre\\_TP\rangle_{i}\leftarrow\mathsf{MUX}(\langle
pTP\rangle_{i},\langle TP\rangle_{i},\langle t.con\rangle_{i})$

17

18$\langle N\rangle_{i}\leftarrow 2\cdot\langle N_{1}\rangle_{i}+\langle
N_{2}\rangle_{i}$

19 $\langle D\rangle_{i}\leftarrow 2\cdot\mathsf{MUL}(\langle
TP\rangle_{i},\langle FP\rangle_{i})$

20 $\langle ROC\rangle_{i}\leftarrow\mathsf{DIV}(\langle N\rangle_{i},\langle
D\rangle_{i})$

Algorithm 6 Secure AUROC computation with tie

####  5.1.1 Secure AUROC Computation without Ties

In Algorithm 5, we compute the AUROC as shown in Equation 1 because we assume
that there is no tie in the sorted list of PCVs. At the end of the secure
computation, the shares of numerator $N$ and denominator $D$ are computed
where $AUROC=N/D$. $S_{i}$ for $i\in\\{0,1\\}$ knows the number of test
samples $M$. Thus $S_{i}$ can determine the upper bound for $N$ and $D$ and
$\mathsf{DIV}$ can be used to calculate $AUROC=N/D$. With the help of high
numeric value precision of the results, most of the machine learning
algorithms yield different PCVs for samples. Therefore, such an approach to
compute the AUROC is applicable to most of the machine learning tasks.
However, in case of a tie between samples from two classes in the PCVs, it
does not guarantee that it gives the exact AUROC. Depending on the order of
the samples, it approximates the score. To have a more accurate AUROC, we will
propose another version with a slightly higher communication cost in the next
section.

####  5.1.2 Secure AUROC Computation with Ties

To detect ties in the list of PCVs, $S_{0}$ and $S_{1}$ compute the difference
between each PCV and its following PCV. $S_{0}$ computes the modular additive
inverse of its shares. The proxies apply a common random permutation to the
bits of each share in the list to prevent $S_{3}$ from learning the non-zero
relative differences. They also permute the list of shares using a common
random permutation to shuffle the order of the real test samples. Then, they
send the list of shares to $S_{2}$. $S_{2}$ XORes two shares and maps the
result to one if it is greater than zero and zero otherwise. Then, proxies
privately map PCVs to zero if they equal to their previous PCV and one
otherwise. This phase is depicted in Algorithm 7. In Algorithm 6, $S_{0}$ and
$S_{1}$ use these mappings to take only the PCVs which are different from
their subsequent PCV into account in the computation of the AUROC based on the
Equation 2. In Algorithm 6, $\mathsf{DIV}$ method is used because the upper
limit for the numerator and denominator is known, as in the AUROC computation
described in Section 5.1.1.

###  5.2 Secure AUPR Computation

As in the AUROC computation described in Section 5.1.2, $S_{0}$ and $S_{1}$
map a PCV in the global sorted list to zero if it equals to the previous PCV
and one otherwise by running the Algorithm 7. Then, we use Equation 2 to
calculate AUPR as shown in Algorithm 8. In the AUPR calculation, the
denominator of each precision value is different. Therefore, we need to
perform division in each iteration. Since the proxy servers can determine the
upper bound for numerators and denominators we can use the $\mathsf{DIV}$
operation to perform divisions.

input : $\langle C\rangle_{i}=(\langle con_{1}\rangle_{i},...,$ $\langle
con_{M}\rangle_{i})$, $\langle C\rangle_{i}$ is a share of the global sorted
list of PCVs, $M$ is the number of PCVs

1 $S_{0}$ and $S_{1}$ hold a common random permutation $\pi$ for $M$ items

2 $S_{0}$ and $S_{1}$ hold a list of common random values $R$

3 $S_{0}$ and $S_{1}$ hold a list of common random permutation $\sigma$ for
$\ell$ items

4 For each $i\in\\{0,1\\}$, $S_{i}$ executes Steps $5$-$13$

5 for  _$j\leftarrow 1$ to $M-1$_ do

6 $\langle C[j]\rangle_{i}\leftarrow(\langle C[j]\rangle_{i}-\langle
C[j+1]\rangle_{i})$

7 if  _$i=0$_ then

8 $\langle C[j]\rangle_{i}=L-\langle C[j]\rangle_{i}$

9

10 $\langle C[j]\rangle_{i}=\langle C[j]\rangle_{i}\oplus R[j]$

11 $\langle C[j]\rangle_{i}=\sigma_{j}(\langle C[j]\rangle_{i})$

12

13$\langle D\rangle_{i}=\pi(\langle C\rangle_{i})$

14 Insert arbitrary number of dummy zero and non-zero values to randomly
chosen locations in $\langle D\rangle_{i}$

15 $S_{i}$ sends $\langle D\rangle_{i}$ to $P_{2}$

16 $S_{2}$ reconstructs $D$ by computing $\langle D\rangle_{0}\oplus\langle
D\rangle_{1}$

17 foreach  _item $\langle d\rangle\in\langle D\rangle$_ do

18 if  _$d >0$_ then

19 $d\leftarrow 1$

20

21

22$S_{2}$ creates new shares of $D$, denoted by $\langle D\rangle_{0}$ and
$\langle D\rangle_{1}$, and sends them to $S_{0}$ and $S_{1}$, respectively.

23 For each $i\in\\{0,1\\}$, $S_{i}$ executes Steps $18$-$21$

24 Remove dummy zero and non-zero values from $\langle D\rangle_{i}$

25 $\langle C\rangle_{i}=\pi(\langle D\rangle_{i})$

26 for  _$j\leftarrow 1$ to $M-1$_ do

27 $\langle T[j].con\rangle_{i}\leftarrow\langle C[j]\rangle_{i}$

28

29$\langle T[M].con\rangle_{i}\leftarrow i$

Algorithm 7 Secure detection of ties

input : $\langle T\rangle_{i}=(\\{\langle con_{1}\rangle_{i},\langle
label_{1}\rangle_{i}\\},...,$ $\\{\langle con_{M}\rangle_{i},\langle
label_{M}\rangle_{i}\\})$, $\langle T\rangle_{i}$ is a share of the global
sorted list of PCVs, and labels

1 $S_{0}$ and $S_{1}$ hold a common random permutation $\pi$ for $M$ items

2 For each $i\in\\{0,1\\}$, $S_{i}$ executes Steps $3$-$24$

3 $\langle TP[0]\rangle_{i}\leftarrow 0$, $\langle RC[0]\rangle_{i}\leftarrow
0$, $\langle pPC\rangle_{i}\leftarrow i$, $\langle pRC\rangle_{i}\leftarrow
0$, $\langle N_{1}\rangle_{i}\leftarrow 0$, $\langle
N_{2}\rangle_{i}\leftarrow 0$

4 for  _$j\leftarrow 1$ to $M$_ do

5 $\langle TP[j]\rangle_{i}\leftarrow\langle TP[j-1]\rangle_{i}+\langle
T[j].label\rangle_{i}$

6 $\langle RC[j]\rangle_{i}\leftarrow\langle RC[j-1]\rangle_{i}+i$

7

8$\langle T\\_TP\rangle_{i}=\pi(\langle TP\rangle_{i})$

9 $\langle T\\_RC\rangle_{i}=\pi(\langle RC\rangle_{i})$

10 for  _$j\leftarrow 1$ to $M$_ do

11 $\langle T\\_PC[j]\rangle_{i}\leftarrow\mathsf{DIV}(\langle
T\\_TP[j]\rangle_{i},\langle T\\_RC[j]\rangle_{i})$

12

13$\langle PC\rangle_{i}=\pi^{\prime}(\langle T\\_PC\rangle_{i})$

14 for  _$j\leftarrow 1$ to $M$_ do

15 $\langle A\rangle_{i}\leftarrow\mathsf{MUL}(\langle pPC\rangle_{i},\langle
RC[j]\rangle_{i}-\langle pRC\rangle_{i})$

16 $\langle A\rangle_{i}\leftarrow\mathsf{MUL}(\langle A\rangle_{i},\langle
T[j].con\rangle_{i})$

17 $\langle N_{1}\rangle_{i}\leftarrow\langle N_{1}\rangle_{i}+\langle
A\rangle_{i}$

18 $\langle A\rangle_{i}\leftarrow\mathsf{MUL}(\langle
RC[j]\rangle_{i}-\langle pRC\rangle_{i},\langle PC[j]\rangle_{i}-\langle
pPC\rangle_{i})$

19 $\langle A\rangle_{i}\leftarrow\mathsf{MUL}(\langle A\rangle_{i},\langle
T[j].con\rangle_{i})$

20 $\langle N_{2}\rangle_{i}\leftarrow\langle N_{2}\rangle_{i}+\langle
A\rangle_{i}$

21 $\langle pPC\rangle_{i}\leftarrow\mathsf{MUX}(\langle
pPC\rangle_{i},\langle PC[j]\rangle_{i},\langle T[j].con\rangle_{i})$

22 $\langle pRC\rangle_{i}\leftarrow\mathsf{MUX}(\langle
pRC\rangle_{i},\langle RC[j]\rangle_{i},\langle T[j].con\rangle_{i})$

23

24

25$\langle N\rangle_{i}\leftarrow 2\cdot\langle N_{1}\rangle_{i}+\langle
N_{2}\rangle_{i}$

26 $\langle D\rangle_{i}\leftarrow 2\cdot\langle TP[M]\rangle_{i}$

27 $\langle PRC\rangle_{i}\leftarrow\mathsf{DIV}(\langle N\rangle_{i},\langle
D\rangle_{i})$

Algorithm 8 Secure AUPR computation with tie

##  6 Security Analysis

We provide all semi-honest simulation-based security proofs for the
$\mathsf{MUX}$, $\mathsf{MC}$, $\mathsf{CMP}$ and $\mathsf{DIV}$ functions
defined in our framework as well as the computations of ppAURORA in the
Supplement.

##  7 Dataset

DREAM Challenge Dataset: To demonstrate the correctness of ppAURORA and its
applicability to a real-life problem, we utilized data from the first
subchallenge of the Acute Myeloid Leukemia (AML) outcome prediction challenge
from the DREAM Challenges (Noren et al., 2016). We chose the submission of the
team with the lowest score in the leaderboard with accessible files, which is
the team Snail. The training dataset has $191$ samples, among which $136$
patients have complete remission. The ground truth labels of the training
samples can be reached at https://www.synapse.org/#!Synapse:syn2501858 and the
submission of team Snail can be found at
https://www.synapse.org/#!Synapse:syn2700200.

Synthetic Dataset: Since we aimed to analyze the scalability of ppAURORA at
different settings, we generated a synthetic dataset with no restriction other
than having the PCVs between $0$ and $1$.

(a)

(b)

(c)

Figure 1: (a) The execution time of various settings to evaluate the
scalability of ppAURORA to the number of samples for a fixed number of parties
and (b) to the number of parties for a fixed number of samples in each party.
(c) The effect of $\delta$ on the execution time is shown.

##  8 Results

Experimental Setup: We conducted our experiments on Amazon EC2 t2.xlarge
instances. For the LAN setting, we utilized only the instances in the
Frankfurt region. For the WAN setting, we additionaly selected one instance
from both London and Paris.

Experiments on DREAM Challenge Dataset: We conducted the experiments on LAN
setting. We assume that the result needs to be precise in the first three
decimal places. Thus, we set the precision of the division operation to cover
up to the fourth decimal place. To assess the correctness, we computed the
AUROC by ppAURORA and compared it to the result obtained without privacy. Both
settings gave $AUROC=0.693$. To check the correctness of AUROC with no-tie of
ppAURORA, we randomly picked one of the samples in tie condition and generated
a subset of the samples with no tie. We obtained the same AUROC with no-tie
version of AUROC of ppAURORA as the non-private computation. Additionally, we
computed AUPR by employing ppAURORA and verified that both private and non-
private gave $AUPR=0.844$. These results indicate that without sacrificing the
privacy of the data, ppAURORA can compute the exact same AUC as one could
obtain on the pooled test samples. To justify the collaborative evaluation, we
performed $1000$ repetitions of the non-private AUROC computation with
$N\in\\{5,10,20,40,80,160\\}$ samples, which are randomly drawn from the whole
data. The AUC starts to become more and more stable when we increase the size
of the samples.

Experiments on Synthetic Dataset: We evaluated no-tie and with-tie versions of
AUROC and AUPR of ppAURORA with $\delta=1$ on the settings in which the number
of data sources is $16$ and the number of samples is
$N\in\\{64,125,250,500,1000\\}$. The results showed that ppAURORA scales
almost quadratically in terms of both communication costs among all parties
and the execution time of the computation. Figure 1(a) displays the results.
We also analyzed the performance of all computations of ppAURORA on a varying
number of data sources. We fixed $\delta=1$, the number of samples in each
data sources to $1000$ and experimented with $D$ data sources where
$D\in\\{2,4,8,16\\}$. Similar to the previous analysis, ppAURORA scales around
quadratically to the number of data sources and Figure 1(b) summarizes the
results. We also analyzed the effect of $\delta\in\\{1,3,5,11,25,51,101\\}$ by
fixing the number of data sources to $8$ and the number of samples in each
data source to $1000$. The execution time shown in Figure 1(c) displays
logarithmic decrease for increasing $\delta$. In all analyses, since the
dominating factor is sorting, the execution times of the computations are
close to each other. Additionally, our analysis showed that LAN is $12$ to
$14$ times faster than WAN on average due to the high round trip time of WAN,
which is approximately $13.2$ ms. However, even with such a scaling factor,
ppAURORA can be deployed in real life scenarios if the alternative is a more
time-consuming approval process required for gathering all data in one place
still protecting the privacy of data. We provided the detailed results as
tables in the Supplement.

##  9 Conclusion

In this work, we presented a novel secure 3-party computation framework and
its application, ppAURORA, to compute AUC of the ROC and PR curves privately
even when there exist ties in the PCVs. We proposed four novel protocols in
the framework, which are $\mathsf{MUX}$ to select one of two secret shared
values, $\mathsf{MC}$ to convert the ring of a secret value from $2^{\ell-1}$
to $2^{\ell}$, $\mathsf{CMP}$ to compare two secret shared values and
$\mathsf{DIV}$ to divide two secret shared values. They have low round and
communication complexities. The framework and its application ppAURORA are
secure against passive adversaries in the honest majority setting. We
implemented ppAURORA in C++ and demonstrated that ppAURORA can both compute
correctly and privately, and scales quadratically to the number of parties and
the number of samples. To the best of our knowledge, ppAURORA is the first
method that enables computing the exact AUC (AUROC and AUPR) privately and
securely.

##  10 Supplementary Material

###  10.1 Framework

In this section, we give the definitions of basic operations that we utilized
in addition to the novel operations given in the main paper.

####  10.1.1 Multiplication

In two-party setting, multiplication is performed using a multiplication
triple (Beaver, 1991) which is generated via homomorphic encryption or
oblivious transfer. In our 3-party setting, $S_{2}$ generates the
multiplication triple and sends the shares of it to $S_{0}$ and $S_{1}$.
$S_{0}$ and $S_{1}$ hold $(\langle x\rangle_{0},\langle y\rangle_{0})$ and
$(\langle x\rangle_{1},\langle y\rangle_{1})$, respectively, and secure
multiplication outputs fresh shares of $xy$ (functionality
$\mathcal{F}_{\mathsf{MUL}}$).

1 Algorithm  _$\mathsf{MUL}$(__)_

input : $S_{0}$ and $S_{1}$ hold ($\langle x\rangle_{0}$, $\langle
y\rangle_{0}$) and ($\langle x\rangle_{1}$, $\langle y\rangle_{1}$),
respectively.

output : $S_{0}$ and $S_{1}$ get $\langle z\rangle_{0}$ and $\langle
z\rangle_{1}$, respectively, where $z=x\cdot y$.

2 $S_{2}$ picks three random numbers $a$, $b$ and $c$ where $c=a\cdot b$

3 $S_{2}$ generates $\langle a\rangle_{i}$, $\langle b\rangle_{i}$ and
$\langle c\rangle_{i}$, and sends them to $S_{i}$ for $i\in\\{0,1\\}$

4 For each $i\in\\{0,1\\}$, $S_{i}$ executes Steps $5$-$7$

5 $S_{i}$ computes $\langle e\rangle_{i}=\langle x\rangle_{i}-\langle
a\rangle_{i}$ and $\langle f\rangle_{i}=\langle y\rangle_{i}-\langle
b\rangle_{i}$

6 $S_{i}$ reconstructs $e$ and $f$ by exchanging the shares with $S_{1-i}$

7 $S_{i}$ computes $\langle z\rangle_{i}=i\cdot e\cdot f+f\cdot\langle
x\rangle_{i}+e\cdot\langle y\rangle_{i}+\langle c\rangle_{i}$

8

Algorithm 9 Multiplication

####  10.1.2 Comparison of a Secret Shared Value and a Plain Value

In this function, a value $r$ in the ring $\mathbb{Z}_{K}$ whose bits are
secret shared to $S_{0}$ and $S_{1}$ in the ring $P$ where $P=67$ is compared
with a common value $y$. At the end of the secure computation, $S_{2}$ learns
a bit $n^{\prime}=n\oplus(r>y)$. We get the definition of this functionality
$\mathcal{F}_{\mathsf{PC}}$ from Wagh et al. (2018) where it is called as
Private Compare ($\mathsf{PC}$). The only change that we made is $S_{2}$ sends
the fresh boolean shares of $n^{\prime}$ to $S_{1}$ and $S_{2}$. $\mathsf{PC}$
is described in Algorithm 10 in the Supplement.

1 Algorithm  _$\mathsf{PC}$(__)_

input : $S_{0},S_{1}$ hold $\left\\{\langle
r[j]\rangle_{0}^{p}\right\\}_{j\in[\ell]}$ and $\\{\langle
r[j]\rangle_{1}^{p}\\}_{j\in[\ell]}$, respectively, a common input $y$ and a
common random bit $n$.

output : $S_{0}$ and $S_{1}$ get $n^{\prime}=n\oplus(r>y)$, $\langle
n^{\prime}\rangle_{0}^{B}$ and $\langle n^{\prime}\rangle_{1}^{B}$,
respectively.

2 $S_{0},S_{1}$ hold $\ell$ common random values $s_{j}\in\mathbb{Z}_{p}^{*}$
for all $j\in[\ell]$ and a random permutation $\pi$ for $\ell$ elements.
$S_{0}$ and $S_{1}$ additionally hold $\ell$ common random values
$u_{j}\in\mathbb{Z}_{p}^{*}$.

3 Let $t=y+1\bmod 2^{\ell}$

4 $P_{i}$ executes Steps $5-17$:

5 for  _$j=\ell;\ j >0;\ j=j-1$_ do

6 if  _$n=0$_ then

7 $\left\langle w_{j}\right\rangle_{i}^{p}=\langle
r[j]\rangle_{i}^{p}+iy[j]-2y[j]\langle r[j]\rangle_{i}^{p}$

8 $\left\langle c_{j}\right\rangle_{i}^{p}=iy[j]-\langle
r[j]\rangle_{i}^{p}+j+\sum_{k=j+1}^{\ell}\left\langle
w_{k}\right\rangle_{i}^{p}$

9

10 else if  _$n=1$ AND $r\neq 2^{\ell}-1$_ then

11 $\left\langle w_{j}\right\rangle_{i}^{p}=\langle
r[j]\rangle_{i}^{p}+it[j]-2t[j]\langle r[j]\rangle_{i}^{p}$

12 $\left\langle c_{j}\right\rangle_{i}^{p}=-it[j]+\langle
r[j]\rangle_{i}^{p}+i+\sum_{k=j+1}^{\ell}\left\langle
w_{k}\right\rangle_{i}^{p}$;

13 else

14 if  _$i\neq 1$_ then

15 $\left\langle c_{j}\right\rangle_{i}^{p}=(1-i)\left(u_{j}+1\right)-iu_{j}$

16

17 else

18 $\left\langle c_{j}\right\rangle_{i}^{p}=(-1)^{j}\cdot u_{j}$

19

20

21

22

23 Send $\left\\{\left\langle
d_{j}\right\rangle_{i}^{p}\right\\}_{j}=\pi\left(\left\\{s_{j}\left\langle
c_{j}\right\rangle_{i}^{p}\right\\}_{j}\right)$ to $P_{2}$

24 For all $j\in{[\ell]}$, $P_{2}$ computes $d_{j}=\mathsf{Reconst}(\langle
d_{j}\rangle_{0}^{p},\langle d_{j}\rangle_{1}^{p})$ and sets $n^{\prime}=1$
iff $\exists j\in[\ell]$ such that $d_{j}=0$.

25 $P_{2}$ sends $\langle n^{\prime}\rangle_{i}^{B}$ to $S_{i}$ for
$i\in\\{0,1\\}$

Algorithm 10 Private Compare Wagh et al. (2018)

###  10.2 Result Tables

In this section, we provide the detailed results of the experiments with
ppAURORA to compute AUROC and AUPR in Tables 2 and 3, respectively.

|  | Communication Costs (MB) |
---|---|---|---
M $\times$ N |  $\delta$ |  $P_{1}$ |  $P_{2}$ |  Helper |  Total |  Time (sec)
$16\times 64$ |  $1$ |  $73.51/73.76$ |  $73.48/73.73$ |  $139.36/139.64$ |  $286.36/287.13$ |  $10.1/14.55$
$16\times 125$ |  $1$ |  $279.71/280.20$ |  $279.65/280.12$ |  $530.35/530.90$ |  $1089.71/1091.22$ |  $29.18/38.43$
$16\times 250$ |  $1$ |  $1117.32/1118.30$ |  $1117.20/1118.15$ |  $2116.65/2120.23$ |  $4351.17/4356.68$ |  $144.24/157.01$
$16\times 500$ |  $1$ |  $4466.23/4468.19$ |  $4466.00/4467.90$ |  $8469.41/8470.51$ |  $17401.65/17406.60$ |  $627.19/655.78$
$16\times 10^{3}$ |  $1$ |  $17858.86/17862.78$ |  $17858.4/17862.18$ |  $33863.45/33876.00$ |  $69580.71/69600.96$ |  $2578.46/2556.93$
$2\times 10^{3}$ |  $1$ |  $149.04/149.53$ |  $149.03/149.50$ |  $282.17/282.98$ |  $580.24/582.02$ |  $13.68/23.07$
$4\times 10^{3}$ |  $1$ |  $893.51/894.49$ |  $893.45/894.39$ |  $1693.99/1694.75$ |  $3480.94/3483.63$ |  $116.24/134.42$
$8\times 10^{3}$ |  $1$ |  $4168.03/4169.99$ |  $4167.86/4169.75$ |  $7903.60/7907.26$ |  $16239.49/16247.01$ |  $597.8/626.66$
$8\times 10^{3}$ |  $3$ |  $2068.78/2070.74$ |  $2068.66/2070.55$ |  $3921.74/3923.83$ |  $8059.18/8065.11$ |  $307.49/334.96$
$8\times 10^{3}$ |  $5$ |  $1383.59/1385.56$ |  $1383.49/1385.38$ |  $2622.98/2625.59$ |  $5390.06/5396.53$ |  $210.13/248.72$
$8\times 10^{3}$ |  $11$ |  $693.62/695.58$ |  $693.53/695.42$ |  $1313.98/1316.86$ |  $2701.13/2707.87$ |  $114.93/151.21$
$8\times 10^{3}$ |  $25$ |  $322.52/324.49$ |  $322.45/324.34$ |  $610.66/612.96$ |  $1255.63/1261.79$ |  $64.16/99.35$
$8\times 10^{3}$ |  $51$ |  $162.59/164.56$ |  $162.52/164.41$ |  $306.88/309.43$ |  $631.99/638.40$ |  $43.98/78.24$
$8\times 10^{3}$ |  $101$ |  $85.58/87.54$ |  $85.50/87.39$ |  $161.12/163.50$ |  $332.21/338.43$ |  $34.56/70.19$
$8\times 250$ |  $1$ |  $260.95/261.44$ |  $260.91/261.38$ |  $494.57/495.27$ |  $1016.43/1018.08$ |  $26.35/34.43$
$8\times UNB$ |  $1$ |  $331.49/331.98$ |  $331.42/331.9$ |  $628.7/629.15$ |  $1291.61/1293.03$ |  $34.4/43.81$
Table 2: The summary of the results of the experiments with ppAURORA to compute AUROC with and without tie on synthetic data. The left side of ”/´´ represents without-tie results and the right side of it represents with-tie results. $M$ represents the number of data sources and $N$ represents the number of samples in one data sources. $UNB$ represents the unbalanced sample distribution, which is $\\{12,18,32,58,107,258,507,1008\\}$. |  | Communication Costs (MB) |
---|---|---|---
M $\times$ N |  $\delta$ |  $P_{1}$ |  $P_{2}$ |  Helper |  Total |  Time (sec)
$16\times 64$ |  $1$ |  $73.79$ |  $73.75$ |  $139.70$ |  $287.24$ |  $15.49$
$16\times 125$ |  $1$ |  $280.25$ |  $280.17$ |  $530.90$ |  $1091.32$ |  $39.50$
$16\times 250$ |  $1$ |  $1118.39$ |  $1118.24$ |  $2120.17$ |  $4356.80$ |  $160.25$
$16\times 500$ |  $1$ |  $4468.38$ |  $4468.08$ |  $8470.66$ |  $17407.12$ |  $666.28$
$16\times 10^{3}$ |  $1$ |  $17863.16$ |  $17862.55$ |  $33874.20$ |  $69599.90$ |  $2639.34$
$2\times 10^{3}$ |  $1$ |  $149.58$ |  $149.55$ |  $283.02$ |  $582.14$ |  $23.09$
$4\times 10^{3}$ |  $1$ |  $894.58$ |  $894.49$ |  $1695.60$ |  $3484.67$ |  $137.44$
$8\times 10^{3}$ |  $1$ |  $4170.19$ |  $4169.94$ |  $7905.92$ |  $16246.05$ |  $635.72$
$8\times 10^{3}$ |  $3$ |  $2070.93$ |  $2070.73$ |  $3924.48$ |  $8066.14$ |  $346.11$
$8\times 10^{3}$ |  $5$ |  $1385.75$ |  $1385.57$ |  $2624.46$ |  $5395.77$ |  $249.01$
$8\times 10^{3}$ |  $11$ |  $695.77$ |  $695.61$ |  $1316.72$ |  $2708.10$ |  $152.96$
$8\times 10^{3}$ |  $25$ |  $324.68$ |  $324.52$ |  $613.25$ |  $1262.45$ |  $104.86$
$8\times 10^{3}$ |  $51$ |  $164.75$ |  $164.59$ |  $309.92$ |  $639.25$ |  $85.14$
$8\times 10^{3}$ |  $101$ |  $87.73$ |  $87.58$ |  $163.67$ |  $338.98$ |  $75.98$
$8\times 250$ |  $1$ |  $261.49$ |  $261.43$ |  $495.38$ |  $1018.29$ |  $35.95$
$8\times UNB$ |  $1$ |  $332.03$ |  $331.94$ |  $629.20$ |  $1293.17$ |  $46.00$
Table 3: The summary of the results of the experiments of AUPR computation
with ppAURORA on synthetic data. $M$ represents the number of data sources and
$N$ represents the number of samples in one data sources. $UNB$ represents the
unbalanced sample distribution, which is $\\{12,18,32,58,107,258,507,1008\\}$.

###  10.3 AUC Stability Analysis

We analyzed the stability of the AUROC based on the number of test samples to
justify the collaborative evaluation. We experimented with
$N\in\\{5,10,20,40,80,160\\}$ test samples which are randomly chosen from the
DREAM Challenge Dataset. In order to have a fair evaluation, we repeated these
experiments $1000$ times. The experiments showed that the AUROC becomes more
reliable and stable if we increase the number of test samples. In case a data
source has no more additional test samples, the collaborative evaluation can
be a best option. Figure 2 summarizes the results of the analysis.

Figure 2: AUROC for varying number of test samples randomly chosen from the
whole dataset

###  10.4 Privacy Preserving Merging

We include some sorting examples to demonstrate the process. In Figure 3, we
show the merging of two lists of PCVs with the same size. In this example,
$\delta=1$. By this setting, we do not decrease the number of possible merging
of two individually sorted lists, which can be computed as:

$\sum_{i=0}^{|L_{2}|-1}{|L_{1}|+1\choose i+1}{|L_{2}|-1\choose i}$ (4)

where $L_{1}$ and $L_{2}$ are the individually sorted lists and $|.|$ denotes
the size operation.

Figure 3: The merging of two same size lists with $\delta=1$. The red arrows
represent shuffling, the black ones denote moving the larger of the first list
to the global sorted list. The progress of the global sorted list is shown by
the grey arrows. Each color in the boxes represents different number of
candidate PCVs. The coding of the colors are shown on the right most side of
the figure. For each red arrow, i.e. for each shuffling, we utilize
$\mathsf{PC}$ operation on PCVs from two lists which are on the same index to
select the larger of them and employ the result of this comparison along with
$\mathsf{MUX}$s put the larger one into the $L_{1}$ and the other into
$L_{2}$. Afterward, we move the top of the first list to the global sorted
list. Since $\delta=1$, we perform shuffling after we move the top element.

Since the cost of having fully private merging is high and may not necessary
for some applications, we can have an intermediate solution. By setting
$\delta$ to a higher odd value, we can speed up the merging process. Figure 4
and 5 demonstrates an example of such a merging with $\delta=3$. The total
number of shuffling is $5$ and $3$, respectively.

Figure 4: The merging of two same size lists with $\delta=3$. We again start
with shuffling and then move the top PCV of the first list into the global
sorted list. Afterward, we compare the second element of the first list and
the top element of the second list via $\mathsf{PC}$. The proxies reconstruct
the result of this comparison and move the share of the larger of the compared
PCVs to the global sorted list. They continue until they move $\delta$ PCVs to
the global sorted list. Then, they shuffle and repeat the same procedure until
there is no PCV in the first list. Figure 5: The merging of two same size
lists with $\delta=3$. This example shows how the merging happens in case all
the PCVs are taken from the first list.

In Figure 6, we show the sorting when the number of PCVs in the second list is
$1$ to justify why we set $\delta=1$ regardless of the initial $\delta$ due to
the privacy reasons. By setting $\delta$, we secure that the number of
possible PCVs in each position of the global sorted list is the same as one
can see on such a merging without privacy. The beginning and the end of the
global sorted list have two possible matching, however, due to the nature of
the individual sorting, the number of possible PCVs for the other positions is
only $3$, which is lower than the ones in Figure 3.

Figure 6: The merging of two lists with $\delta=1$. The second list has only
one PCV. The red arrows represent shuffling, the black ones denote moving the
larger of the first list to the global sorted list. The progress of the global
sorted list is shown by the grey arrows. Each color in the boxes represents
different number of candidate PCVs. The coding of the colors are shown on the
right most side of the figure.

###  10.5 Security Analysis

Here, we provide semi-honest simulation-based security proofs for the
$\mathsf{MUX}$, $\mathsf{MC}$, $\mathsf{CMP}$ and $\mathsf{DIV}$ functions we
have defined in our framework. Since the protocols we propose for AUC
calculation use $\mathsf{MUX}$, $\mathsf{MC}$, $\mathsf{CMP}$, $\mathsf{DIV}$
and previously defined functions, we prove the security of the main protocols
in the F-hybrid model by proving the security of each function we call.

######  Lemma 10.1.

The protocol $\mathsf{MUL}$ in Algorithm 9 in the Supplement securely realizes
the functionality $\mathcal{F}_{\mathsf{MUL}}$.

###### Proof.

In order to prove the correctness of our protocol we show that $\langle
z\rangle_{0}+\langle z\rangle_{1}=xy$.

$\begin{split}\langle z\rangle_{0}+\langle z\rangle_{1}={}&f\cdot\langle
x\rangle_{0}+e\cdot\langle y\rangle_{0}+\langle c\rangle_{0}-e\cdot f\\\
&+f\cdot\langle x\rangle_{1}+e\cdot\langle y\rangle_{1}+\langle
c\rangle_{1}\\\ ={}&(fx+ey+c-ef)\\\ ={}&((y-b)x+(x-a)y+c-(x-a)(y-b))\\\
={}&xy-xb+xy-ya+c-xy+xb+ya-ab\\\ ={}&xy\end{split}$ (5)

We prove the security of our protocol. During the protocol execution, $S_{2}$
sends a multiplication triple to $S_{0}$ and $S_{1}$ and does not receive any
values. Thus the view of $S_{2}$ is empty and it is very easy to prove
security in case $S_{2}$ is corrupted. $S_{i}$ where $i\in\\{0,1\\}$ sees
$\langle a\rangle_{i},\langle b\rangle_{i},\langle c\rangle_{i},\langle
e\rangle_{i}$ and $\langle f\rangle_{i}$. These values are uniformly
distributed random values and hence can be perfectly simulated.

∎

######  Lemma 10.2.

The protocol $\mathsf{MUX}$ in Algorithm 1 in the main paper securely realizes
the functionality $\mathcal{F}_{\mathsf{MUX}}$.

###### Proof.

We first prove the correctness of our protocol. $\langle z\rangle_{i}$ is the
output of $S_{i}$ where $i\in\\{0,1\\}$. We need to prove that
$\mathsf{Reconstruct(\langle z\rangle_{i})}=(1-b)x+by$.

$\begin{split}\langle z\rangle_{0}+\langle z\rangle_{1}={}&\langle
x\rangle_{0}+s-\langle b\rangle_{0}(\langle x\rangle_{0}-\langle
y\rangle_{0})+r_{1}\langle b\rangle_{0}\\\ &+r_{2}(\langle
x\rangle_{0}-\langle y\rangle_{0})+r_{2}r_{3}+\langle x\rangle_{1}+t\\\
&-\langle b\rangle_{1}(\langle x\rangle_{1}-\langle
y\rangle_{1})+r_{0}(\langle x\rangle_{1}-\langle y\rangle_{1})\\\
&+r_{0}r_{1}+r_{3}\langle b\rangle_{1}-\langle b\rangle_{0}\langle
x\rangle_{1}+\langle b\rangle_{0}\langle y\rangle_{1}\\\ &-\langle
b\rangle_{0}r_{1}-r_{0}\langle x\rangle_{1}+r_{0}\langle
y\rangle_{1}-r_{0}r_{1}\\\ &-\langle x\rangle_{0}\langle b\rangle_{1}-\langle
x\rangle_{0}r_{2}+\langle y\rangle_{0}\langle b\rangle_{1}+\langle
y\rangle_{0}r_{2}\\\ &-r_{3}\langle b\rangle_{1}-r_{3}r_{2}-s-t\\\
={}&(1-\langle b\rangle_{0}-\langle b\rangle_{1})(\langle x\rangle_{0}+\langle
x\rangle_{1})\\\ &+(\langle b\rangle_{0}+\langle b\rangle_{1})(\langle
y\rangle_{0}+\langle y\rangle_{1})\\\ ={}&(1-b)x+by\end{split}$ (6)

Next we prove the security of our protocol. $S_{2}$ gets $M_{2},M_{3},M_{5}$
and $M_{6}$. All these values are uniformly random values because they are
generated using uniformly random values $r_{0},r_{1},r_{2},r_{4}$. $S_{2}$
computes $M_{2}M_{5}+M_{3}M_{6}$. The computed value is still uniformly random
because it contains uniformly random values $r_{0},r_{1},r_{2},r_{4}$. As a
result, any value learned by $S_{2}$ is perfectly simulated. For each
$i\in\\{0,1\\}$, $S_{i}$ learns a fresh share of the output. Thus $S_{i}$
cannot associate the share of the output with the shares of the inputs and any
value learned by $S_{i}$ is perfectly simulatable. ∎

######  Lemma 10.3.

The protocol $\mathsf{PC}$ in Algorithm 10 in the Supplement securely realizes
the functionality $\mathcal{F}_{PC}$.

###### Proof.

The proof of $\mathsf{PC}$ is given in Wagh et al. (2018). ∎

######  Lemma 10.4.

The protocol $\mathsf{MC}$ in Algorithm 2 in the main paper securely realizes
the functionality $\mathcal{F}_{MC}$ in $\mathcal{F}_{\mathsf{PC}}$ hybrid
model.

###### Proof.

First, we prove the correctness of our protocol by showing $(\langle
x\rangle_{0}^{K}+\langle x\rangle_{1}^{K})\mod K=(\langle x\rangle_{0}+\langle
x\rangle_{1})\mod L$. In the protocol, $y=(x+r)\mod K$ and
$\mathsf{isWrap}(x,r,K)=r\overset{?}{>}y$, that is, $\mathsf{isWrap}(x,r,K)=1$
if $r>y$, $0$ otherwise. At the beginning, $S_{0},S_{1}$ and $S_{2}$ call
$\mathcal{F}_{PC}$ to compute $c=r\overset{?}{>}y$ and $S_{0}$ and $S_{1}$
obtain the boolean shares $c_{0}$ and $c_{1}$, respectively. Besides, $S_{2}$
sends also the boolean shares $w_{0}$ and $w_{1}$ of
$w=\mathsf{isWrap}(\langle r\rangle_{0},\langle r\rangle_{1},K)$ to $S_{0}$
and $S_{1}$, respectively. If $\mathsf{isWrap}(\langle y\rangle_{0},\langle
y\rangle_{1},K)$ is $1$ then $S_{0}$ adds $K$ to $\langle y\rangle_{0}$ to
change the ring of $y$ from $K$ to $L$. To convert $r$ from ring $K$ to ring
$L$, $S_{0}$ and $S_{1}$ add $K$ to their shares of $r$ based on their boolean
shares $w_{0}$ and $w_{1}$, respectively. If $w_{0}=1$, then $S_{0}$ adds $K$
to its $r_{1}$ and $S_{1}$ does the similar with its shares. Later, we need to
fix is the summation of $x$ and $r$, that is the value $y$. In case of
$x+r\geq K$, we cannot fix the summation value $y$ in ring $L$ by simply
converting it from ring $K$ to ring $L$. This summation should be $x+r$ in
ring $L$ rather than $(x+r)$ $mod$ $K$. To handle this problem, $S_{0}$ and
$S_{1}$ add $K$ to their shares of $y$ based on their shares $c_{0}$ and
$c_{1}$. As a result, we convert the values $y$ and $r$ to ring $L$ and fix
the value of $y$ if necessary. The final step to obtain $x_{i}$ for party
$S_{i}$ is simply subtract $r_{i}$ from $y_{i}$ where $i\in\\{0,1\\}$.

Next, we prove the security of our protocol. $S_{2}$ involves this protocol in
execution of $\mathcal{F}_{PC}$. We give the proof $\mathcal{F}_{PC}$ above.
At the end of the execution of $\mathcal{F}_{PC}$, $S_{2}$ learns
$n^{\prime}$. However, $n^{\prime}=n\oplus(x>r)$ and $S_{2}$ does not know
$n$. Thus $n^{\prime}$ is uniformly distributed and can be perfectly simulated
with randomly generated values. $S_{i}$ where $i\in\\{0,1\\}$ sees fresh
shares of $\langle r\rangle_{i}^{K}$, $\\{\langle
r[j]\rangle_{i}^{p}\\}_{j\in[\ell]}$, $w_{i}^{B}$ and $n_{i}^{B}$. These
values can be perfectly simulated with randomly generated values. ∎

######  Lemma 10.5.

The protocol $\mathsf{CMP}$ in Algorithm 3 in the main paper securely realizes
the functionality $\mathcal{F}_{CMP}$ in $\mathcal{F}_{\mathsf{MC}}$ hybrid
model.

###### Proof.

First, we prove the correctness of our protocol. Assume that we have
$\ell$-bit number $u$. $v=u-(u\mod 2^{\ell-1})$ is either $0$ or $2^{\ell-1}$.
$v$ is only represented with the most significant bit (MSB) of $u$. In our
protocol, $\langle z\rangle_{i}$ is the output of $S_{i}$ where
$i\in\\{0,1\\}$. We need to prove that $\mathsf{Reconstruct(\langle
z\rangle_{i})}$ is $1$ if $x<y$ and $0$ otherwise. $S_{i}$ where
$i\in\\{0,1\\}$ computes $d_{i}^{K}=(x_{i}-y_{i})\mod K$ which is a share of
$d$ over $K$. $S_{i}$ computes $d_{i}$ which is a share of $d$ over $L$ by
invoking $\mathsf{MC}$. Note that $z=x-y-\mathsf{Reconstruct(\langle
d\rangle_{i})}$ and all bits of $z$ are $0$ except MSB of $z$ which is equal
to MSB of $(x-y)$. Now we need to map $z$ to $1$ if it’s equal to $K$ and 0 if
it’s equal to $0$. $S_{0}$ sends the $z_{0}$ and $z_{0}+K$ in random order to
$S_{2}$ and $S_{1}$ sends the $z_{1}$ to $S_{2}$. $S_{2}$ reconstructs two
different values, divides these values by $K$, creates two additive shares of
them, and sends these shares to $S_{0}$ and $S_{1}$. Since $S_{0}$ and $S_{1}$
know the order of the real MSB value, they correctly select the shares of its
mapped value.

Second, we prove the security of our protocol. $S_{i}$ where $i\in\\{0,1\\}$
sees $\langle d\rangle_{i}$ which is a fresh share of $d$ and $\langle
a[0]\rangle_{i}$ and $\langle a[1]\rangle_{i}$ one of them is a fresh share of
the MSB of $x-y$ and the other is a fresh share of the complement of the MSB
of $x-y$. Thus the view of $S_{i}$ can be perfectly simulated with randomly
generated values. ∎

######  Lemma 10.6.

The protocol $\mathsf{DIV}$ in Algorithm 4 in the main paper securely realizes
the functionality $\mathcal{F}_{\mathsf{DIV}}$.

###### Proof.

We first prove the correctness of our protocol. $\langle z\rangle_{i}$ is the
output of $S_{i}$ where $i\in\\{0,1\\}$. We prove that
$\mathsf{Reconstruct(\langle z\rangle_{i})}=\frac{xF}{y}$.

$\begin{split}\langle z\rangle_{0}+\langle z\rangle_{1}={}&\frac{(r_{1}\langle
x\rangle_{0}+r_{0}\langle y\rangle_{0}+r_{1}\langle x\rangle_{1}+r_{0}\langle
y\rangle_{1})F}{r_{1}\langle y\rangle_{0}+r_{1}\langle
y\rangle_{1}}-\frac{r_{0}F}{r_{1}}\\\
={}&\frac{(r_{1}x+r_{0}y)F}{r_{1}y}-\frac{r_{0}F}{r_{1}}\\\
={}&\frac{xF}{y}+\frac{r_{0}F}{r_{1}}-\frac{r_{0}F}{r_{1}}\\\
={}&\frac{xF}{y}\\\ \end{split}$ (7)

$\mathsf{DIV}$ method produces correct results when $S_{0}$ and $S_{1}$ know
the upper limit of $x$ and $y$ values. In this case, the values of $r_{0}$ and
$r_{1}$ are chosen in such a way that the values $r_{1}\langle
x\rangle_{0}+r_{0}\langle y\rangle_{0}+r_{1}\langle x\rangle_{1}+r_{0}\langle
y\rangle_{1}$ and $r_{1}\langle y\rangle_{0}+r_{1}\langle y\rangle_{1}$ do not
wrap around $\mathbb{Z}_{L}$. If wrapping occurs around $\mathbb{Z}_{L}$,
$\mathsf{DIV}$ method produces the wrong result.

Next we prove the security of our protocol. $S_{2}$ gets $a_{0},a_{1},b_{0}$
and $b_{1}$. All these values are uniformly random values because they are
generated using uniformly random values $r_{0}$ and $r_{1}$. As a result, any
value learned by $S_{2}$ is perfectly simulated. For each $i\in\\{0,1\\}$,
$S_{i}$ learns a fresh share of the output. Thus $S_{i}$ cannot associate the
share of the output with the shares of the inputs and any value learned by
$S_{i}$ is perfectly simulatable. ∎

######  Lemma 10.7.

The protocol in Algorithm 5 in the main paper securely computes AUROC in
$(\mathcal{F}_{\mathsf{MUL}},\mathcal{F}_{\mathsf{DIV}})$ hybrid model.

###### Proof.

In the protocol, we separately calculate the numerator $N$ and the denominator
$D$ of the AUROC, which can be expressed as $AUROC=\frac{N}{D}$. Let us first
focus on the computation of $D$. It is equal to the multiplication of the
number of samples with label $1$ by the number of samples with label $0$. In
the end, we have the number of samples with label $1$ in $TP$ and calculate
the number of samples with label $0$ by $P-TP$. Then, the computation of $D$
is simply the multiplication of these two values. In order to compute $N$, we
employed Equation 1 in the main paper. We have already shown the denominator
part of it. For the numerator part, we need to multiply the current $TP$ by
the change in $FP$ and sum up these multiplication results. $\langle
A\rangle\leftarrow\mathsf{MUL}(\langle TP\rangle,\langle FP\rangle-\langle
pFP\rangle)$ computes the contribution of the current sample on the
denominator and we accumulate all the contributions in $N$, which is the
numerator part of Equation 1 in the main paper. Therefore, we can conclude
that we correctly compute the AUROC.

Next, we prove the security of our protocol. $S_{i}$ where $i\in\\{0,1\\}$
sees $\\{\langle RL\rangle\\}_{j\in M}$, $\\{\langle A\rangle\\}_{j\in M}$,
$\langle D\rangle$ and $\langle ROC\rangle$ which are fresh shares of these
values. Thus the view of $S_{i}$ is perfectly simulatable with uniformly
random values. ∎

######  Lemma 10.8.

The protocol in Algorithm 7 in the main paper securely marks the location of
ties in the list of prediction confidences.

###### Proof.

For the correctness of our protocol, we need to prove that for each index $j$
in $T$, $t[j].con=0$ if $(C[j]-C[j+1])=0$, $t[j].con=1$, otherwise. We first
calculate the difference of successive items in $C$. Let assume we have two
additive shares $(\langle a\rangle_{0},\langle a\rangle_{1})$ of a over the
ring $\mathbb{Z}_{L}$. If $a=0$, then $(L-\langle a\rangle_{0})\oplus\langle
a\rangle_{1}=0$ and if $a\neq 0$, then $(L-\langle a\rangle_{0})\oplus\langle
a\rangle_{1}\neq 0$ where $L-\langle a\rangle_{0}$ is the additive modular
inverse of $\langle a\rangle_{0}$. We use this fact in our protocol. $S_{0}$
computes the additive inverse of each item $\langle c\rangle_{0}$ in $\langle
C\rangle_{0}$ which is denoted by $\langle c\rangle_{0}^{\prime}$, XORes
$\langle c\rangle_{0}^{\prime}$ with a common random number in $R$, which is
denoted by $\langle c\rangle_{0}^{\prime\prime}$ and permutes the bits of
$\langle c\rangle_{0}^{\prime\prime}$ with a common permutation $\sigma$ which
is denoted by $\langle c\rangle_{0}^{\prime\prime\prime}$. $S_{1}$ XORes each
item $\langle c\rangle_{1}$ in $\langle C\rangle_{1}$ with a common random
number in $R$ which is denoted by $\langle c\rangle_{1}^{\prime\prime}$ and
permutes the bits of $\langle c\rangle_{1}^{\prime\prime}$ with a common
permutation $\sigma$ which is denoted by $\langle
c\rangle_{1}^{\prime\prime\prime}$. $S_{i}$ $i\in\\{0,1\\}$ permutes values in
$\langle C\rangle_{i}^{\prime\prime\prime}$ by a common random permutation
$\pi$ which is denoted by $\langle D\rangle_{i}$. After receiving $\langle
D\rangle_{0}$ and $\langle D\rangle_{1}$, $S_{2}$ maps each item $d$ of $D$ to
$0$ if $\langle d\rangle_{0}^{\prime}\oplus\langle d\rangle_{1}=0$ which means
$\langle d\rangle_{0}+\langle d\rangle_{1}=0$ and maps $1$ if $\langle
d\rangle_{0}^{\prime}\oplus\langle d\rangle_{1}\neq 0$ which means $\langle
d\rangle_{0}+\langle d\rangle_{1}\neq 0$. After receiving a new share of $D$
from $S_{2}$, $S_{i}$ $i\in\\{0,1\\}$ removes dummy values and permutes
remaining values by $\pi^{\prime}$. Therefore, our protocol correctly maps
items of $C$ to $0$ or $1$.

We next prove the security of our protocol. $S_{i}$ where $i\in\\{0,1\\}$
calculates the difference of successive prediction values. The view of $S_{2}$
is $D$ which includes real and dummy zero values. $S_{i}$ XORes each item of
$\langle C\rangle_{i}$ with fresh boolean shares of zero, applies a random
permutation to bits of each item of $\langle C\rangle_{i}$, applies a random
permutation $\pi$ to $\langle C\rangle_{i}$ and add dummy zero and non-zero
values. Thus differences, the index $j$ where $D[j]=0$, the index $j$ where
$D[j]\neq 0$ are uniformly random. The number of zero and non-zero values are
not known to $S_{2}$ due to dummy values. With common random permutations
$\sigma_{j\in M}$ and common random values $R[j],j\in M$, each item in $C$ are
hidden. Thus $S_{2}$ can not infer anything about real values in $C$.
Furthermore, the number of repeating predictions is not known to $S_{2}$ due
to a random permutation $\pi$. ∎

######  Lemma 10.9.

The protocol in Algorithm 6 in the main paper securely computes AUROC in
($\mathcal{F}_{\mathsf{MUL}}$,$\mathcal{F}_{\mathsf{MUX}}$,$\mathcal{F}_{\mathsf{DIV}}$)
hybrid model.

###### Proof.

In order to compute the AUROC in case of tie, we utilize Equation 2 in the
main paper, of which we calculate the numerator and the denominator
separately. The calculation of the denominator $D$ is the same as Lemma 10.7.
The computation of the numerator $N$ has two different components, which are
$N_{1}$ and $N_{2}$. $N_{1}$, more precisely the numerator of
$T[i-1]*(F[i]-F[i-1])$, is similar to no-tie version of privacy preserving
AUROC computation. This part corresponds to the rectangle areas in ROC curve.
The decision of adding this area $A$ to the cumulative area $N_{1}$ is made
based on the result of the multiplication of $A$ by $t.con$. $t.con=1$
indicates if the sample is one of the points of prediction confidence change,
$0$ otherwise. If it is $0$, then $A$ becomes $0$ and there is no contribution
into $N_{1}$. If it is $1$, then we add $A$ to $N_{1}$. On the other hand,
$N_{2}$, which is the numerator of $(T[i]-T[i-1])*(F[i]-F[i-1])$, accumulates
the triangular areas. We compute the possible contribution of the current
sample to $N_{2}$. In case this sample is not one of the points that the
prediction confidence changes, which is determined by $t.con$, then the value
of $A$ is set to $0$. If it is, then $A$ remains the same. Finally, $A$ is
added to $N_{2}$. Since there is a division by $2$ in the second part of
Equation 2 in the main paper, we multiply $N_{1}$ by $2$ to make them have
common denominator. Afterwards, we sum $N_{1}$ and $N_{2}$ to obtain $N$ In
order to have the term $2$ in the common denominator, we multiply $D$ by $2$.
As a result, we correctly compute the denominator and the nominator of the
AUROC.

Next, we prove the security of our protocol. $S_{i}$ where $i\in\\{0,1\\}$
sees $\\{\langle RL\rangle\\}_{j\in M}$, $\\{\langle A\rangle\\}_{j\in M}$,
$\\{\langle pFP\rangle\\}_{j\in M}$, $\\{\langle pTP\rangle\\}_{j\in M}$,
$\langle D\rangle$ and $\langle ROC\rangle$ which are fresh shares of these
values. Thus the view of $S_{i}$ is perfectly simulatable with uniformly
random values. ∎

######  Lemma 10.10.

The protocol in Algorithm 8 in the main paper securely computes AUPR in
($\mathcal{F}_{\mathsf{MUL}}$,$\mathcal{F}_{\mathsf{MUX}}$,$\mathcal{F}_{\mathsf{DIV}}$)
hybrid model.

###### Proof.

In order to compute the AUPR , we utilize Equation 2 in the main paper of
which we calculate the numerator and the denominator separately. We nearly
perform the same computation with the AUROC computation in case of tie. The
main difference is that we need perform division to calculate each precision
value because denominators of each precision value are different. The rest of
the computation is the same with the computation in Algorithm 6 in the main
paper. The readers can follow the proof of Lemma 10.9.

Next, we prove the security of our protocol. $S_{i}$ where $i\in\\{0,1\\}$
sees $\\{\langle RL\rangle\\}_{j\in M}$, $\\{\langle T\\_PC\rangle\\}_{j\in
M}$, $\\{\langle A\rangle\\}_{j\in M}$, $\\{\langle pPC\rangle\\}_{j\in M}$,
$\\{\langle pRC\rangle\\}_{j\in M}$, $\langle D\rangle$ and $\langle
ROC\rangle$ which are fresh shares of these values. Thus the view of $S_{i}$
is perfectly simulatable with uniformly random values. ∎

######  Lemma 10.11.

The sorting protocol in Section 5 in the main paper securely merges two sorted
lists in ($\mathcal{F}_{\mathsf{CMP}}$,$\mathcal{F}_{\mathsf{MUX}}$) hybrid
model.

###### Proof.

First, we prove the correctness of our merge sort algorithm. $L_{1}$ and
$L_{2}$ are two sorted lists. In the merging of $L_{1}$ and $L_{2}$, the
corresponding values are first compared using the secure $\mathsf{CMP}$
operation. The larger values are placed in $L_{1}$ and the smaller values are
placed in $L_{2}$, after the secure $\mathsf{MUX}$ operation is called twice.
This process is called shuffling because it shuffles the corresponding values
in the two lists. After the shuffling process, we know that the largest
element of the two lists is the top element of $L_{1}$. Therefore, it is
removed and added to the global sorted list $L_{3}$. On the next step, the top
elements of $L_{1}$ and $L_{2}$ are compared with the $\mathsf{CMP}$ method.
The comparison result is reconstructed by $S_{0}$ and $S_{1}$ and the top
element of $L_{1}$ or $L_{2}$ is removed based on the result of $\mathsf{CMP}$
and added to $L_{3}$. The selection operation also gives the largest element
of $L_{1}$ and $L_{2}$ because $L_{1}$ and $L_{2}$ are sorted and the
selection operation selects the larger of the top elements of $L_{1}$ and
$L_{2}$. We show that shuffling and selection operations give the largest
element of two sorted lists. This ensures that our merge sort algorithm that
only uses these operations correctly merges two sorted lists in ordered
manner.

Next, we prove the security of our merge sort algorithm. In the shuffling
operation, $\mathsf{CMP}$ and $\mathsf{MUX}$ operations are called.
$\mathsf{CMP}$ outputs fresh shares of comparison of corresponding values in
$L_{1}$ and $L_{2}$. Shares of these comparison results are used in
$\mathsf{MUX}$ operations and $\mathsf{MUX}$ operation generates fresh shares
of the corresponding values. Therefore, $S_{0}$ and $S_{1}$ cannot precisely
map these values to the values in $L_{1}$ and $L_{2}$. In the selection
operation, $\mathsf{CMP}$ is called and the selection is performed based on
the reconstructed output of $\mathsf{CMP}$. $S_{0}$ and $S_{1}$ are still
unable to map the values added to $L_{3}$ to the values in $L_{1}$ and $L_{2}$
precisely because at least one shuffling operation took place before these
repeated selection operations. Shuffling and $\delta-1$ selection operations
are performed repeatedly until the $L_{1}$ is empty. After each shuffling
operation, the fresh share of the larger corresponding values in $L_{1}$ and
the fresh share of the smaller corresponding values in $L_{2}$ are stored. The
view of $S_{0}$ and $S_{1}$ are perfectly simulatable with random values due
to the shuffling process performed at regular intervals.

It is possible in some cases to use unshuffled values in selection operations.
To prevent this, the following rules are followed in the execution of the
merge protocol. If there are two lists that do not have the same length, the
longer list is chosen as $L_{1}$. If the $\delta$ is greater than the length
of the $L_{2}$ list, it is set to the largest odd value smaller or equal to
the length of $L_{2}$ so that the unshuffled values that $L_{1}$ may have are
not used in selection processes. If the length of $L_{2}$ is reduced to $1$ at
some point in the sorting, the $\delta$ is set to $1$. Thus $L_{2}$ will have
$1$ element until the end of the merge and shuffling is done before each
selection. ∎

####  10.5.1 Privacy against Malicious Adversaries

Araki et al. (2016) defined the notion of privacy against malicious
adversaries in the client-server setting. In this setting, the servers
performing secure computation on the shares of the inputs to produce the
shares of the outputs do not see the plain inputs and outputs of the clients.
This notion of privacy says that a malicious party cannot break the privacy of
input and output of the honest parties. This setting is very similar to our
setting. In our framework, two parties exchange a seed which is used to
generate common randoms between them. Two parties randomize their shares using
these random values which are not known to the third party. It is very easy to
add fresh shares of zero to outputs of two parties with common random values
shared between them. In our algorithms, we do not state the randomization of
outputs with fresh shares of zero. Thus, our framework provides privacy
against a malicious party by relying on the security of a seed shared between
two honest parties.

## References

  * Mohassel and Zhang [2017] Payman Mohassel and Yupeng Zhang.  Secureml: A system for scalable privacy-preserving machine learning.  In _2017 IEEE Symposium on Security and Privacy (SP)_ , pages 19–38. IEEE, 2017.
  * Wagh et al. [2018] Sameer Wagh, Divya Gupta, and Nishanth Chandran.  Securenn: Efficient and private neural network training.  _IACR Cryptol. ePrint Arch._ , 2018:442, 2018.
  * Juvekar et al. [2018] Chiraag Juvekar, Vinod Vaikuntanathan, and Anantha Chandrakasan.  $\\{$GAZELLE$\\}$: A low latency framework for secure neural network inference.  In _27th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 18)_, pages 1651–1669, 2018.
  * Mohassel and Rindal [2018] Payman Mohassel and Peter Rindal.  Aby3: A mixed protocol framework for machine learning.  In _Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security_ , pages 35–52, 2018.
  * Ünal et al. [2019] Ali Burak Ünal, Mete Akgün, and Nico Pfeifer.  A framework with randomized encoding for a fast privacy preserving calculation of non-linear kernels for machine learning applications in precision medicine.  In _International Conference on Cryptology and Network Security_ , pages 493–511. Springer, 2019.
  * Damgård et al. [2019] Ivan Damgård, Daniel Escudero, Tore Frederiksen, Marcel Keller, Peter Scholl, and Nikolaj Volgushev.  New primitives for actively-secure mpc over rings with applications to private machine learning.  In _2019 IEEE Symposium on Security and Privacy (SP)_ , pages 1102–1120. IEEE, 2019.
  * Byali et al. [2020] Megha Byali, Harsh Chaudhari, Arpita Patra, and Ajith Suresh.  Flash: fast and robust framework for privacy-preserving machine learning.  _Proceedings on Privacy Enhancing Technologies_ , 2020(2):459–480, 2020.
  * Patra and Suresh [2020] Arpita Patra and Ajith Suresh.  BLAZE: blazing fast privacy-preserving machine learning.  In _27th Annual Network and Distributed System Security Symposium, NDSS 2020, San Diego, California, USA, February 23-26, 2020_. The Internet Society, 2020.
  * Chaudhuri and Vinterbo [2013] Kamalika Chaudhuri and Staal A Vinterbo.  A stability-based validation procedure for differentially private machine learning.  In _Advances in Neural Information Processing Systems_ , pages 2652–2660, 2013.
  * Boyd et al. [2015] Kendrick Boyd, Eric Lantz, and David Page.  Differential privacy for classifier evaluation.  In _Proceedings of the 8th ACM Workshop on Artificial Intelligence and Security_ , pages 15–23, 2015.
  * Chen et al. [2016] Yan Chen, Ashwin Machanavajjhala, Jerome P Reiter, and Andrés F Barrientos.  Differentially private regression diagnostics.  In _ICDM_ , pages 81–90, 2016.
  * Whitehill [2019] Jacob Whitehill.  How does knowledge of the auc constrain the set of possible ground-truth labelings?  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 5425–5432, 2019.
  * Matthews and Harel [2013] Gregory J Matthews and Ofer Harel.  An examination of data confidentiality and disclosure issues related to publication of empirical roc curves.  _Academic radiology_ , 20(7):889–896, 2013.
  * Lindell [2017] Yehuda Lindell.  How to simulate it - A tutorial on the simulation proof technique.  In Yehuda Lindell, editor, _Tutorials on the Foundations of Cryptography_ , pages 277–346. Springer International Publishing, 2017.  doi: 10.1007/978-3-319-57048-8\\_6.  URL https://doi.org/10.1007/978-3-319-57048-8_6.
  * Canetti [2001] Ran Canetti.  Universally composable security: A new paradigm for cryptographic protocols.  In _42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA_ , pages 136–145. IEEE Computer Society, 2001.  doi: 10.1109/SFCS.2001.959888.  URL https://doi.org/10.1109/SFCS.2001.959888.
  * Araki et al. [2016] Toshinori Araki, Jun Furukawa, Yehuda Lindell, Ariel Nof, and Kazuma Ohara.  High-throughput semi-honest secure three-party computation with an honest majority.  In _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ , pages 805–817, 2016.
  * Yao [1986] Andrew Chi-Chih Yao.  How to generate and exchange secrets.  In _Proceedings of the 27th Annual Symposium on Foundations of Computer Science_ , SFCS ’86, pages 162–167, Washington, DC, USA, 1986. IEEE Computer Society.  ISBN 0-8186-0740-8.  doi: 10.1109/SFCS.1986.25.  URL https://doi.org/10.1109/SFCS.1986.25.
  * Goldreich et al. [1987] O. Goldreich, S. Micali, and A. Wigderson.  How to play any mental game.  In _Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing_ , STOC ’87, pages 218–229, New York, NY, USA, 1987. ACM.  ISBN 0-89791-221-7.  doi: 10.1145/28395.28420.  URL http://doi.acm.org/10.1145/28395.28420.
  * Beaver [1991] Donald Beaver.  Efficient multiparty protocols using circuit randomization.  In _Advances in Cryptology - CRYPTO ’91, 11th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11-15, 1991, Proceedings_ , pages 420–432, 1991.  doi: 10.1007/3-540-46766-1\\_34.  URL https://doi.org/10.1007/3-540-46766-1_34.
  * Applebaum [2017] Benny Applebaum.  Garbled circuits as randomized encodings of functions: a primer.  In Yehuda Lindell, editor, _Tutorials on the Foundations of Cryptography_ , pages 1–44. Springer International Publishing, 2017.  doi: 10.1007/978-3-319-57048-8\\_1.  URL https://doi.org/10.1007/978-3-319-57048-8_1.
  * Noren et al. [2016] David P Noren, Byron L Long, Raquel Norel, Kahn Rrhissorrakrai, Kenneth Hess, Chenyue Wendy Hu, Alex J Bisberg, Andre Schultz, Erik Engquist, Li Liu, et al.  A crowdsourcing approach to developing and assessing prediction algorithms for aml prognosis.  _PLoS computational biology_ , 12(6):e1004890, 2016.