#  PEOPL: Characterizing Privately Encoded Open Datasets with Public Labels

Homa Esfahanizadeh, Adam Yala, Rafael G. L. D’Oliveira, Andrea J. D. Jaba,
Victor Quach, Ken R. Duffy, Tommi S. Jaakkola, Vinod Vaikuntanathan, Manya
Ghobadi, Regina Barzilay, Muriel Médard H. Esfahanizadeh, A. Jaba, V. Quach,
T. Jaakkola, V. Vaikuntanathan, M. Ghobadi, R. Barzilay, and M Médard are with
the Electrical Engineering and Computer Science Department, Massachusetts
Institute of Technology (MIT), Cambridge, MA USA (emails: {homaesf@, adjaba@,
quach@, tommi@, vinodv<EMAIL_ADDRESS><EMAIL_ADDRESS>medard@}mit.edu). A.
Yala is with University of California, Berkeley and University of California,
San Francisco, CA USA (email: yala@berkeley.edu). R. D’Oliveira is with School
of Mathematical and Statistical Sciences, Clemson University, SC USA. K. Duffy
is with Maynooth University, Ireland (email: Ken.Duffy@mu.ie). Research
supported in part by the National Science Foundation under grant no.
CNS-2008624, and in part by Wellcome Trust Fellowship and MIT J-Clinic.

###### Abstract

Allowing organizations to share their data for training of machine learning
(ML) models without unintended information leakage is an open problem in
practice. A promising technique for this still-open problem is to train models
on the encoded data. Our approach, called Privately Encoded Open Datasets with
Public Labels (PEOPL), uses a certain class of randomly constructed transforms
to encode sensitive data. Organizations publish their randomly encoded data
and associated raw labels for ML training, where training is done without
knowledge of the encoding realization. We investigate several important
aspects of this problem: We introduce information-theoretic scores for privacy
and utility, which quantify the average performance of an unfaithful user
(e.g., adversary) and a faithful user (e.g., model developer) that have access
to the published encoded data. We then theoretically characterize primitives
in building families of encoding schemes that motivate the use of random deep
neural networks. Empirically, we compare the performance of our randomized
encoding scheme and a linear scheme to a suite of computational attacks, and
we also show that our scheme achieves competitive prediction accuracy to raw-
sample baselines. Moreover, we demonstrate that multiple institutions, using
independent random encoders, can collaborate to train improved ML models.

###### Index Terms:

random encoding, outsourced training, sensitive data release, collaborative
learning.

##  I Introduction

For many applications, training Machine Learning (ML) models requires advanced
and expensive computational resources and a large set of labeled data with
sufficient diversity. An attractive approach is to enable co-operation across
organizations by outsourcing the training data from several centers to the
cloud where the model is trained. However, privacy concerns have complicated
the construction of multi-institution cohorts and limited the utilization of
external ML resources. For example, to protect patient privacy, regulations
such as HIPPA [1] and GDPR [2] prohibits sharing patients’ identifiable
information. Similarly, companies may be reluctant to share data that is part
of their intellectual property and provides them a competitive edge. It is
well-understood now that merely removing metadata, e.g., patient’s name, is
not enough for hiding sensitive information [3]. Characterizing and mitigating
this challenge is the main focus of this paper. We are interested in
developing a computationally effective mechanism to encode sensitive date in
order to facilitate outsourcing of training for ML. Inherent in our model is
the notion that labels will be perforce public but that we wish to reduce the
information leakage beyond the release of labels.

|
---|---
(a) Federated learning [4] | (b) Instahide [5]
(c) This paper: PEOPL
Figure 1: Three approaches for mitigating privacy concerns in outsourced
training and collaborative learning. (a) Federated learning [4]: There exists
a copy of global model at each data-owner. The local models are updated using
data of their data-owner, and the model updates are exchanged with the server,
rather than the sensitive data. (b) Instahide [5]: The sensitive samples are
linearly mixed with each other and with some public samples. The mixed samples
and mixed labels are transferred to the server for training. (c) PEOPL: Each
sample is encoded by a nonlinear transform dedicated to the data-owner. The
encoders of data-owners are sampled from a random distribution independently
from each other, and they do not need to be shared with other data-owners or
with the server. The encoded samples and raw labels are transferred to the
server for training.

There are a number of solutions that have been developed for different notions
of privacy. For instance, federated learning [4] trains models in a
distributed fashion, and in conjunction with adding noise during training [6],
it can obtain the theoretical notion of differential privacy [7], see Fig. 1
(a). However federated learning frameworks require a tight coordination across
data-owners and model developers to jointly perform the training. Thereby,
such approaches are not suitable for enabling data-owners to deposit their
datasets publicly. As another instance, cryptographic methods such as secure
multi-party computation, fully homomorphic encryption, and functional
encryption [8, 9, 10, 11] enable public sharing and offer extremely strong
security guarantees by hiding everything about the data. However, these
security guarantees come at the cost of extremely high computational and
communication overheads for training today’s advanced ML models [12, 13].
Moreover, the cryptographic methods do not accommodate the collaborative
setting, i.e., training a single classifier using data of multiple data-
owners, unless the data-owners trust each other and share the same key.

We argue that common ML training tasks do not require a strong level of
security to hide everything about the data. An example is the training task of
an ML model for diagnosing medical complications from chest x-ray images. The
training task already implies the information that most images in the dataset
contain human 24 ribs without looking into individual ones. Consequently, the
notion of security adopted by the cryptographic methods is an overkill for the
outsourced ML training task, where labels are public. Instead, we seek an
efficient encoding scheme to protect the information that is not already
implied by the general information about the training task and the samples’
labels.

Random encoders were recently considered in the literature to train models
directly on encoded data [5, 14, 15]. Instahide [5] used random linear mixing
of images in the private dataset and some public dataset to generate the
encoded samples and encoded labels. It demonstrated the feasibility of
training models on the randomly transformed data and its potentials, see Fig.
1 (b). However, as we show in this paper, the linearity of this scheme renders
it vulnerable to adversarial distribution attacks. DauntLess [14] used random
dense neural networks for encoding the samples and random mixing for encoding
the labels. The authors proved perfect privacy is feasible when the encoding
scheme is data-dependent, which is costly and not aligned with the philosophy
of the outsourced training and collaborative learning.

In this paper, we characterize randomized encoding schemes used by data-owners
to publish their encoded data, with associated uncoded labels, from both
privacy and utility perspectives. While developing practical schemes that
guarantee that the encoded data cannot be used for any purpose other than the
the designated training task (i.e., perfect schemes) remains an open
challenge, our theoretical results offer primitives for improving scheme
privacy. Building on these insights, we present PEOPL, an encoding scheme
based on the random selection of an encoder from a rich family of neural
networks. We empirically demonstrate that PEOPL obtains improved privacy over
linear baselines while obtaining competitive accuracy to raw-sample baselines.
When applied in the multi-institutional setting, each site uses independent,
uncoordinated random encoders to encode their data. With the help of label
information, models trained in this setting can map these independently
constructed encodings into a shared feature space, see Fig. 1 (c). Our
empirical results do not guarantee privacy against all possible attackers and
PEOPL should not be used in real-world sensitive settings today. However,
these results do reflect improved privacy-utility trade-offs compared to
common baselines and our analysis demonstrates a promising new direction for
scheme design.

The organization of this paper are as follows: In Section II, we formulate the
problem of hiding sensitive data via a random transform. We propose the
notions of privacy score and utility score, using the Shannon entropy [16],
that quantify the performance of the probability distribution, according to
which the random transform is chosen. In Section III, we propose how to
improve the private key distribution to obtain a better privacy score. In
particular, we show that function composition maintains or increases the
privacy score. Furthermore, we study two types of attacks on the encoder that
is chosen by a data-owner, given the available information to the adversary:
The optimal attack which is based on the actual probability distribution, and
a sub-optimal attack which is based on a mismatched distribution.

In Section IV, motivated by our theoretical results, we implement the family
of possible encoding functions as random convolutional neural networks and
random recurrent neural networks, for encoding the images and the texts,
respectively. Our implemented schemes are designed for the cases where
sensitive data does not have overlap with the relevant publicly-available
datasets. We hypothesized that these schemes offer improved privacy over
linear approaches. In Section V, we empirically compare our method to linear
baselines on two chest x-ray image datasets MIMIC-CXR [17], CheXpert [18], and
one text dataset SMS spam collection [19]. Section VI and VII are dedicated to
discussion and conclusions, respectively.

##  II Problem Setting and Performance Scores

We first introduce necessary notations and definitions. We denote a set of
elements with Calligraphic letters, e.g., $\mathcal{X}$. A transformation
(encoder) is denoted with $T:\mathcal{X}\rightarrow\mathcal{Z}$. The
cardinality (the number of elements) of a set and the factorial function are
denoted by $|.|$ and $(.)!$, respectively. For notation purposes, we
occasionally impose a total order $\preceq$ on $\mathcal{X}$ to represent it
by a vector $(x_{1},\ldots,x_{|\mathcal{X}|})$ such that $x_{i}\preceq x_{j}$
if $i\leq j$. We then can represent an encoder by a vector with size
$|\mathcal{X}|$ whose $i$-th element is $T(x_{i})$. Without loss of
generality, we assume all logarithms are in base $2$ in this paper. The
mathematical derivations used rely on both stochastic (random) and
deterministic variables. All stochastic variables are denoted with bold font,
e.g., x, while deterministic variables are denoted with non-bold italic font,
e.g., $x$. All proofs appear in the appendix.

We start with description of the sensitive data release problem. We then
define privacy and utility scores for the problem, which are two possibly
competing targets.

###  II-A Problem Description

Figure 2: Alice (data-owner) transmits her labeled encoded data to Bob (ML
developer). Eve (adversary) attempts to identify information about Alice’s raw
data beyond their labels.

We denote the set of all samples by $\mathcal{X}$ and assume it is a finite
set. Each sample $x\in\mathcal{X}$ is labeled by a labeling function
$L:\mathcal{X}\rightarrow\mathcal{Y}$, where the set of labels $\mathcal{Y}$
is finite. We consider a model with three participants, Alice, Bob and Eve, to
be consistent with the common terminology of privacy (see Fig. 2). We consider
a setting where a data-owner (Alice) has some sensitive set of samples
$\mathcal{X}_{A}\subset\mathcal{X}$. Alice needs to train a classifier on her
sensitive data to estimate the labeling function $L(\cdot)$. To do so, she
wishes to communicate her labeled data $\\{(x,L(x))\\}_{x\in\mathcal{X}_{A}}$
with an ML developer (Bob) for learning. However, we assume an adversary (Eve)
is also able to observe all communication that take place between Alice and
Bob. In general, we consider the information revealed about Alice’s data
beyond their labels is privacy leakage and must be limited.

######  Assumption 1.

For the ease of theoretical derivations, we assume Alice’s samples given their
cardinality are chosen uniformly and independently from $\mathcal{X}$. Thus,
$\Pr[\bm{\mathcal{X}_{A}}=\mathcal{X}_{A}]=\mathbb{C}$, where $\mathbb{C}$ is
independent of the realization of $\bm{\mathcal{X}_{A}}$.

Occasionally, we attempt to protect some sensitive features about Alice’s data
(other than the published labels). For this purpose, let
$S:\mathcal{X}\rightarrow\tilde{\mathcal{Y}}$ be another labeling function
that describes sensitive features of samples in $\mathcal{X}$, where the set
$\tilde{\mathcal{Y}}$ is finite. We assume that Eve has prior knowledge as a
public dataset with identical distribution as Alice’s data, denoted with
$\mathcal{P}\subset\mathcal{X}$. Each public sample is associated with some
labels, including $L(x)$ and $S(x)$ for every $x\in\mathcal{P}$.

We consider the following type of schemes: Alice chooses a one-to-one encoding
function $T_{A}:\mathcal{X}\rightarrow\mathcal{Z}$ at random, from a family of
functions $\mathcal{F}$ according to distribution $\Pr[\bm{T_{A}}=T_{A}]$.
Thus,

$\mathcal{F}=\\{T:\Pr[\bm{T_{A}}=T]\neq 0\\}.$

She then transmits
$\mathcal{O}_{T_{A}}(\mathcal{X}_{A})=\\{(T_{A}(x),L(x))\\}_{x\in\mathcal{X}_{A}}$
to Bob. Bob then trains an ML classifier on the encoded data, thus seeking to
learn $L_{A}=L\circ T^{-1}_{A}$ on the encoded space $T_{A}(\mathcal{X})$. In
this setting, a scheme is the distribution according to which Alice chooses
$T_{A}$. Eve also receives Alice’s labeled encoded data
$\mathcal{O}_{T_{A}}(\mathcal{X}_{A})=\\{(T_{A}(x),L(x))\\}_{x\in\mathcal{X}_{A}}$,
which we call Eve’s observation. We assume Eve also knows the scheme, so she
has access to $\Pr[\bm{T_{A}}=T_{A}]$, but not exactly the transform sampled
by Alice. Thus, we define Eve’s prior knowledge $\mathcal{K}_{e}$ as follows:

$\mathcal{K}_{e}=\\{\\{(x,L(x),S(x))\\}_{x\in\mathcal{P}},\Pr[\bm{T_{A}}=T_{A}]\\}.$

The Shannon entropy $\operatorname{H}[\bm{x}]$ of a random variable $\bm{x}$
quantifies the average level of uncertainty inherent in its possible outcomes
[16]. By definition, given the distribution of $\bm{x}$ and the space set
$\mathcal{X}$ (set of possible values that the random variable $\bm{x}$ can
take),

$\operatorname{H}[\bm{x}]=-\sum_{x\in\mathcal{X}}\Pr[\bm{x}=x]\log\Pr[\bm{x}=x].$

The conditional entropy $\operatorname{H}[\bm{x_{1}}|\bm{x_{2}}]$ quantifies
the average level of uncertainty inherent in the possible outcomes of a random
variable $\bm{x_{1}}$ when the outcome of another (possibly correlated) random
variable $\bm{x_{2}}$ is known, and
$\operatorname{H}[\bm{x_{1}}|\bm{x_{2}}]=\sum_{x}\operatorname{H}[\bm{x_{1}}|\bm{x_{2}}=x]\Pr[\bm{x_{2}}=x]$.

###  II-B Privacy Definition and Eve’s Attacks

Given Eve’s prior knowledge $\mathcal{K}_{e}$ and observation
$\mathcal{O}_{T_{A}}(\mathcal{X}_{A})$, in this paper, we are interested in
what she learns about Alice’s private encoder $\bm{T_{A}}$. Since each
$T_{A}\in\mathcal{F}$ is a one-to-one function from $\mathcal{X}$ to
$\mathcal{Z}$, if Eve identifies $T_{A}$, she can revert back Alice’s encoded
data into their sensitive original representation. Eve uses her probability
distribution on $T_{A}$ given her prior knowledge and her observations, i.e.,

$P(T)=\Pr[\bm{T_{A}}=T\mid\mathcal{O}_{T_{A}}(\mathcal{X}_{A}),\;\mathcal{K}_{e}],$
(1)

to break Alice’s encoding scheme.

Given Eve’s prior knowledge and observations, she chooses an encoder that has
the highest likelihood to be Alice’s encoder. Therefore the optimal attack of
Eve is defined as follows:

######  Definition 1 (Optimal attack).

The optimal attack outputs an encoder that maximizes $P(T)$:

$T_{A}^{\text{opt}}=\arg\max_{T\in\mathcal{F}}P(T).$ (2)

When the solution of (2) is not unique, Eve would randomly choose one of them.

The optimal attack is possible for Eve when she has access to the actual
probability distribution $P(T)$ in (1). The sub-optimal attack refers to the
case when Eve uses a mismatched distribution $Q(T)$ rather then $P(T)$ to
obtain the encoder that has the highest likelihood to be Alice’s encoder:

######  Definition 2 (Sub-optimal attack).

The sub-optimal attack outputs an encoder that maximizes the mismatched
distribution:

$T_{A}^{\text{sub-opt}}=\arg\max_{T\in\mathcal{F}}Q(T).$

There are several ways to measure the privacy of an encoding scheme. In this
paper, we use Shannon entropy to quantify Eve’s average uncertainty about
Alice’s encoder:

######  Definition 3 (Privacy score against optimal attack).

The privacy score of Alice’s scheme is defined as:

$\begin{split}S_{\text{privacy}}(\bm{T_{A}})=\operatorname{H}[\bm{T_{A}}\mid\bm{{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}},\;\mathcal{K}_{e}].\end{split}$

A higher privacy score is better as it is equivalent to a higher uncertainty
of Eve about Alice’s encoder, and consequently a more private encoding scheme.
By definition, we have

$\begin{split}&S_{\text{privacy}}(\bm{T_{A}})=\\\
&\sum_{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}\operatorname{H}[\bm{T_{A}}\mid{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})},\;\mathcal{K}_{e}]\Pr[{\bm{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}=\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}]{=}\\\
&-\sum_{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}\sum_{T\in\mathcal{F}}P(T)\log
P(T)\Pr[{\bm{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}=\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}].\end{split}$

If the privacy score is zero, there is a unique solution for the optimal
attack, which is indeed Alice’s encoder.

Later in Corollary 2, we show that if Alice’s encoder can be identified using
Alice’s original data and encoded data, the privacy score is equivalent to the
average uncertainty of Eve about Alice’s original data. In general, the
privacy score is a lower-bound on the expected number of guesses for an
adversary that sorts the encoders from most-likely to least-likely according
to (1), to correctly guess Alice’s encoder [20]. The expected number of
guesses can be more tightly bounded by Rényi entropy [21, 22]. As the
presented results can be readily extended to other definitions of entropy, in
this paper we use the notion of Shannon Entropy.

The privacy score $S_{\text{privacy}}(\bm{T_{A}})$ measures the average
uncertainty about Alice’s encoder when Eve has access to $P(T)$. The average
uncertainty about Alice’s encoder when Eve uses $Q(T)$ rather than $P(T)$ is
obtained using cross-entropy. The cross-entropy
$\operatorname{CE}(P,Q)=-\sum_{T\in\mathcal{F}}P(T)\log Q(T)$ is a non-
negative metric, lower-bounded by the entropy
$\operatorname{H}[\bm{T_{A}}\mid{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})},\;\mathcal{K}_{e}]=\sum_{T\in\mathcal{F}}P(T)\log
P(T)$.

######  Definition 4 (Privacy score against sub-optimal attack).

The privacy score of Alice’s scheme when Eve has access to a mismatched
distribution $Q(T)$ rather than $P(T)$ is:

$\begin{split}&\tilde{S}_{\text{privacy}}(\bm{T_{A}})=\\\
&-\sum_{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}\sum_{T\in\mathcal{F}}P(T)\log
Q(T)\Pr[{\bm{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}=\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}].\end{split}$

###  II-C Utility Definition

The utility goal is to increase how much Bob learns about the labeling of
Alice’s encoded data, i.e., learning $L_{A}=L\circ T^{-1}_{A}$ on the encoded
space $T_{A}(\mathcal{X})$. This can be quantified in a variety ways, and we
use Shannon entropy to measure Bob’s average uncertainty about the labeling
function $L_{A}:\mathcal{Z}\rightarrow\mathcal{Y}$ given the Alice’s labeled
encoded data.

######  Definition 5 (Utility score).

The utility score of Alice’s scheme is defined as:

$S_{\text{utility}}(\bm{T_{A}})=\operatorname{H}[\bm{L}]-\operatorname{H}[\bm{L\circ
T_{A}^{-1}}\mid\bm{\mathcal{O}_{T_{A}}({\mathcal{X}_{A}})}].$ (3)

A higher utility score is better as it is equivalent to a lower uncertainty of
Bob about the labeling function that acts on Alice’s encoded data.

In our experiments, to evaluate the utility of an encoding scheme, we compare
the prediction utility of two classifiers that are trained with Alice’s
labeled original data and Alice’s labeled encoded data, respectively. We
denote the two classifiers with $L^{\text{emp}}$ and $L^{\text{emp}}_{A}$. The
classifier $L^{\text{emp}}$ approximates the function $L$ and is obtained by
training an ML model using Alice’s un-encoded data
$\mathcal{O}({\mathcal{X}_{A}})=\\{(x,L(x))\\}_{x\in\mathcal{X}_{A}}$. The
classifier $L^{\text{emp}}_{A}$ approximates the function $L_{A}=L\circ
T^{-1}_{A}$ and is obtained by training a similar ML model using Alice’s
encoded data
$\mathcal{O}_{T_{A}}({\mathcal{X}_{A}})=\\{(T_{A}(x),L(x))\\}_{x\in\mathcal{X}_{A}}$.
The performance of a classifier is quantified by comparing the output of the
original function and the approximated function for some held-out data
$\mathcal{Q}\subset\mathcal{X}$ (i.e., generalization accuracy):

$\\{(L^{\text{emp}}(x),L(x))\\}_{x\in\mathcal{Q}},\quad\\{(L_{A}^{\text{emp}}(T_{A}(x)),L(x))\\}_{x\in\mathcal{Q}}.$

The comparison can be formulated in several ways such as success rate (ratio
of pairs with identical values to the total number of pairs) or area under ROC
curve (AUC) for two-class classification problems.

##  III Main Theoretical Results

In this section, we first present some theoretical results to explore the
described privacy-utility problem, in Section III-A. In Section III-B, we
propose architectural lines to improve the privacy score of an encoding
scheme. In Section III-C, we study a tractable approximation of Eve’s optimal
attack, and the privacy score of an encoding scheme against this sub-optimal
attack. Finally, in Section III-D, we demonstrate how protecting the private
encoder, selected by Alice, is connected to protecting her sensitive data.

###  III-A On Privacy of Randomly Encoded Data

Here, we identify the set of possible values for Alice’s encoder
$\operatorname{Pos}[{T_{A}}]\subseteq\mathcal{F}$, from Eve’s point of view.
We then use this notion to investigate Eve’s probability distribution $P(T)$
and her optimal attack on Alice’s encoder.

######  Definition 6.

The set of possible values for Alice’s encoder given Eve’s observations is:

$\begin{split}\operatorname{Pos}[{T_{A}}]&\triangleq\\{T\in\mathcal{F}:\exists\bar{X}_{T}\subset\mathcal{X}\text{
with }\\\
&\\{(T(x),L(x))\\}_{x\in\bar{X}_{T}}=\mathcal{O}_{T_{A}}({\mathcal{X}_{A}})\\}.\end{split}$

The distribution of Eve on Alice’s encoder given her observations and
knowledge can be described in terms of $\operatorname{Pos}[{T_{A}}]$:

######  Theorem 1.

The probability distribution $P(T)$ can be stated as

$P(T)=\Pr[\bm{T_{A}}=T\mid\mathcal{O}_{T_{A}}({\mathcal{X}_{A}}),\mathcal{K}_{e}]=\frac{\Pr[\bm{T_{A}}=T]}{\Pr[\bm{T_{A}}\in\operatorname{Pos}[{T_{A}}]]},$

if $T\in\operatorname{Pos}[{T_{A}}]$. $P(T)=0$, otherwise.

######  Corollary 1.

The optimal attack can also be characterized in terms of
$\operatorname{Pos}[T_{A}]$ as follows:

$T_{A}^{\emph{\text{opt}}}=\arg\max_{T\in\operatorname{Pos}[T_{A}]}\Pr[\bm{T_{A}}=T].\vspace{-0.17cm}$

###  III-B Architectural Lines to Improve Privacy

We start from a family of functions $\mathcal{F}$ from which Alice chooses her
encoder according to $\Pr[\bm{T_{A}}=T]$. We wish to understand what kind of
operations Alice can perform to improve the privacy of her encoding scheme. To
this end, we explore several ways to grow $\mathcal{F}$. In our next
proposition, we show that adding arbitrary functions to $\mathcal{F}$ might
actually worsen the privacy score.

######  Proposition 1.

There exists cases where growing the family of functions that Alice randomly
chooses her encoder from lowers the privacy score.

However, as we now show, composing families of functions can only preserve or
increase the privacy score.

######  Theorem 2.

Let $\mathcal{F}$ and $\mathcal{F}^{\prime}$ be two families of encoders from
which Alice samples her encoder from according to $\Pr[\bm{T_{A}}=T_{A}]$ and
$\Pr[\bm{T^{\prime}_{A}}=T^{\prime}_{A}]$, respectively. Consider a new family
of encoders
$\mathcal{F}^{\prime\prime}=\mathcal{F}^{\prime}\circ\mathcal{F}=\\{T^{\prime}\circ
T:T^{\prime}\in\mathcal{F}^{\prime},T\in\mathcal{F}\\}$, and the associated
distribution

$\Pr[\bm{T^{\prime\prime}_{A}}=T^{\prime\prime}_{A}]=\sum_{T^{\prime}\circ
T=T^{\prime\prime}_{A}}\Pr[\bm{T^{\prime}_{A}}=T^{\prime}]\Pr[\bm{T_{A}}=T].$

Then, the privacy score of the new encoding scheme is at least equal to the
privacy score of each initial one, i.e.,

$S_{\text{privacy}}(\bm{T_{A}})\leq
S_{\text{privacy}}(\bm{T^{\prime\prime}_{A}}),\quad
S_{\text{privacy}}(\bm{T^{\prime}_{A}})\leq
S_{\text{privacy}}(\bm{T^{\prime\prime}_{A}}).$

Theorem 2 shows that composing families of encoders cannot reduce the privacy
score. Indeed, as we show in the following example, it can potentially
increase it.

######  Example 1.

Let consider the universe of all samples is
$\\{(x,L(x))\\}_{x\in\mathcal{X}}=\\{(1,+),(2,+),(3,-),(4,-)\\}$, and consider
these two families of encoders, from which Alice uniformly chooses her
encoder:

$\mathcal{F}=\begin{cases}T_{1}:&(1,2,3,4)\\\
T_{2}:&(2,1,3,4)\end{cases},\quad\text{and}\quad\mathcal{F}^{\prime}=\begin{cases}T^{\prime}_{1}:&(1,2,3,4)\\\
T^{\prime}_{2}:&(1,2,4,3)\end{cases}.$

Now, we consider the composition of these two families of encoders:

$\mathcal{F^{\prime}}\circ\mathcal{F}=\begin{cases}T^{\prime}_{1}\circ
T_{1}:&(1,2,3,4)\\\ T^{\prime}_{1}\circ T_{2}:&(2,1,3,4)\\\
T^{\prime}_{2}\circ T_{1}:&(1,2,4,3)\\\ T^{\prime}_{2}\circ
T_{2}:&(2,1,4,3)\end{cases}$

We can verify that

$\operatorname{H}[\bm{T_{A}}\mid\bm{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})},\mathcal{K}_{e}]=\operatorname{H}[\bm{T^{\prime}_{A}}\mid\bm{\mathcal{O}_{e}(T^{\prime}_{A})},\mathcal{K}_{e}]=1.$

However, $\operatorname{H}[\bm{T^{\prime}_{A}\circ
T_{A}}|\bm{\mathcal{O}_{T^{\prime}_{A}\circ
T_{A}}(\mathcal{X}_{A})},\mathcal{K}_{e}]=2$, which is a higher privacy score
than the one for the individual schemes.

We leverage our theoretical results on function composition to guide the
design of our encoding scheme. Starting with a weak encoder, a random linear
transform, we iteratively enrich the privacy of our scheme through function
composition (e.g by adding with additional non-linear and linear layers), to
build a random deep neural network. The non-linearity is a necessary component
to happen between the composed layers, otherwise the composed linear layers
reduce to just a one-layer linear encoder that is weak. More details on the
encoding scheme are presented in Section IV.

###  III-C Approximating the Optimal Attack

The probability distribution used by the optimal attack is given in (1) and is
revisited here,

$P(T)=\Pr[\bm{T_{A}}=T\mid\mathcal{O}_{T_{A}}(\mathcal{X}_{A}),\;\mathcal{K}_{e}].$

In practice, Eve does not have access to $P(T)$ to perform the optimal attack.
However, it has access to public dataset $\mathcal{P}\subset\mathcal{X}$ with
samples with the same distribution as Alice’s samples. The public samples and
Alice’s samples have the same distribution even after the transformation via
$T_{A}$. Thus, a tractable solution to approximate the optimal attack, i.e., a
sub-optimal attack, is to identify an encoder that results in a similar
distribution to distribution of Alice’s encoded data when applied to an
available public dataset $\mathcal{P}\subset\mathcal{X}$.

There are a variety of ways to quantify the mismatch between two
distributions, e.g., Kullback–Leibler (KL) divergence and Kolmogorov-Smirnov
distance (K-S) [23, 24]. Here, we use the generic form
$\operatorname{dist}[\mathcal{Z},\mathcal{Z}^{\prime}]$, where samples of
$\mathcal{Z}$ and $\mathcal{Z}^{\prime}$ are drawn from distributions $p$ and
$q$, to represent the mismatch between two distributions $p$ and $q$. Thus,
the sub-optimal attack is,

$T_{A}^{\text{sub-
opt}}\triangleq\arg\min_{T\in\mathcal{F}}\operatorname{dist}[T_{A}(\mathcal{X}_{A}),T(\mathcal{P})].$
(4)

In fact, the mismatch between distributions of Alice’s encoded data
$T_{A}(\mathcal{X}_{A})$ and public encoded data via the current estimated
encoder, can be used as a loss function for training an ML model that
approximates $T_{A}$. Let assume $T_{\theta}$ represents all possible choices
that can be obtained by the attack model of Eve, where each realization of
$\theta$ corresponds to one possible choice for the weights of the model.
Thus,

$\begin{split}&T_{A}^{\text{sub-opt}}=T_{\theta^{\star}},\\\
&\theta^{\star}=\arg\min_{\theta}\operatorname{dist}[T_{A}(\mathcal{X}_{A}),T_{\theta}(\mathcal{P})].\end{split}$

One popular practical method to measure the distribution mismatch
$\operatorname{dist}[T_{A}(\mathcal{X}_{A}),T_{\theta}(\mathcal{P})]$ is the
maximum mean discrepancy (MMD) which has recently received significant
attention [25, 26]. By definition,

$\text{MMD}[p,q]=\sup_{h\in\mathcal{H}}(E_{x\sim p}[h(x)]-E_{x\sim q}[h(x)]).$

If $\mathcal{H}$ is the space of bounded continuous functions on
$\mathcal{X}$, the MMD measure is zero if and only if $p=q$ [25]. An estimate
of the above measure is obtained by replacing the expectations with empirical
average. For having a rich family of functions $\mathcal{H}$, we use the
functions in the unit ball of a reproducing kernel Hilbert space (RKHS), as
suggested in [27, 28].

The attack (4) is a tractable approximation of optimal attack, and can be
considered as if Eve uses another distribution such as $Q$ rather than $P$ for
her attack. We remind that the privacy score against the optimal attack
$S_{\text{privacy}}(\bm{T_{A}})$ and the privacy score against the sub-optimal
attack $\tilde{S}_{\text{privacy}}(\bm{T_{A}})$ measure the average
uncertainty about Alice’s encoder when Eve has access to the actual
probability distribution $P$ and the approximated distribution $Q$,
respectively, see Section II-B. In fact,

$\begin{split}\operatorname{CE}(P,Q){-}&\operatorname{H}[\bm{T_{A}}\mid{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})},\;\mathcal{K}_{e}]{=}\sum_{T\in\mathcal{F}}P(T)\log\frac{P(T)}{Q(T)}\\\
&=D_{\text{KL}}(P||Q).\end{split}$

Here, $D_{\text{KL}}(P||Q)\geq 0$ is the KL divergence. Therefore,

$\begin{split}&\tilde{S}_{\text{privacy}}(\bm{T_{A}})-S_{\text{privacy}}(\bm{T_{A}})=\\\
&\sum_{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}D_{\text{KL}}(P||Q)\Pr[{\bm{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}=\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}]\geq
0.\end{split}$

The privacy score of a scheme against sub-optimal attack, who has $Q(T)$
rather than $P(T)$, is an upper-bound for the actual privacy score. The gap is
equivalent to the KL divergence between the actual distribution and the
approximated distribution that Eve uses, averaged over all possible
observations. In our experiments, Eve uses the practical MMD measure to close
the gap between the two distributions.

###  III-D Protecting the Encoder versus Protecting the Data

In this subsection, we show how the privacy score, which is the average
uncertainty of Eve about Alice’s encoder, is connected to her average
uncertainty about Alice’s original data. We then demonstrate for which
encoding schemes these two notions of uncertainty coincide.

######  Proposition 2.

The privacy score in Definition 3, can be written as

$\begin{split}S_{\text{privacy}}(\bm{T_{A}})&=\operatorname{H}[\bm{\mathcal{X}_{A}}\mid\bm{{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}},\;\mathcal{K}_{e}]\\\
&+\operatorname{H}[\bm{T_{A}}\mid\bm{\mathcal{X}_{A}},\bm{{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}},\;\mathcal{K}_{e}].\end{split}$

######  Corollary 2.

Eve has the same average uncertainty about Alice’s encoder and about Alice’s
sensitive data if

$\operatorname{H}[\bm{T_{A}}\mid\bm{\mathcal{X}_{A}},\bm{{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}},\;\mathcal{K}_{e}]=0$
(5)

According to Corollary 2, if the realization of encoder can be identified
given un-ordered sets of original data and encoded data, the privacy score of
the encoding scheme is equivalent to the average uncertainty of Eve about
Alice’s data. In Section V-A, we provide experimental results showing that (5)
holds for the version of PEOPL that will be presented in Section IV. We note
that (5) does not hold for the encoding schemes that are difficult to break,
without protecting the sensitive data. Examples of such useless encoding
schemes are those that append random data to each sensitive sample.

Lastly, we note that encoding schemes that satisfy (5) are vulnerable when the
adversary has access to un-ordered sets of original and encoded samples, e.g.,
the cases where $\mathcal{X}_{A}\cap\mathcal{P}\neq\emptyset$. In fact, having
non zero intersection between the public data and private data might lead to
zero privacy score for these schemes. Thus, if
$\mathcal{X}_{A}\cap\mathcal{P}\neq\emptyset$, the data-owner either needs to
exclude the public samples from her dataset before encoding, to use an
encoding scheme with
$\operatorname{H}[\bm{T_{A}}\mid\bm{\mathcal{X}_{A}},\bm{{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}},\;\mathcal{K}_{e}]>0$
such as [15], or to use non-invertible transforms as her encoding scheme.

##  IV Method: Random DNNs for Image and Text

In this section, we develop two encoding schemes inspired by our result that
functional composition can improve the privacy of encoding schemes. The
schemes will be presented in two separate subsections: one for encoding image
data and one for encoding text data. Later, in Section V, we provide an
empirical evaluation of the privacy and utility performance of the proposed
encoding schemes, and will show that our schemes offer improved privacy over
linear randomized encoding schemes when:

$\mathcal{X}_{A}\cap\mathcal{P}=\emptyset.$ (6)

###  IV-A Random CNN for Encoding Image Data

In this subsection, we focus on imaging tasks, and thus implement our encoders
as convolutional neural networks (CNNs). Our encoder architecture is
illustrated in Fig. 3, and consists of convolutional layers with non-
overlapping strides, batch normalization [29], and ReLu non-linearities. To
encode positional information into the feature space while hiding spatial
structure, we add a random positional embedding for each patch before the
final convolutional and ReLu layers and randomly permute the patches at the
output independently for each private sample. This results in an unordered set
of patch feature vectors for each image. We note that this architecture is
closely inspired by the design of patch-embedding modules in Vision
Transformer networks [30, 31].

Figure 3: Architecture of image encoder. The encoding task resembles an
inference task using an untrained CNN.

###  IV-B Random RNN for Encoding Text Data

In this subsection, we focus on natural language processing (NLP) tasks, and
thus implement our encoders as random recurrent neural networks (RNNs) [32].
As illustrated in Fig. 4, we first map the constituents words of the original
sample into vectors using a word embedding. Then, we feed the embedded vectors
into an RNN which includes a hidden state and a Tanh non-linearity. The
initial state of the RNN is randomly chosen and plays the role of the private
key. The encoded output can be either the sequence of RNN outputs, or the
final value of its hidden state. The first type of output results in a
sequence of encoded words per sample, and along with the labels, can be used
to train a downstream model with memory, e.g., another RNN or Long Term Short
Memory (LSTM) models. The second type of output results in a single vector
which is basically the encoded context, and can be used for training
memoryless models such as a dense neural network.

Figure 4: Architecture of text encoder. The encoding task resembles an
inference task using an untrained RNN.

We highlight that using a random RNN for encoding the text data is a benchmark
here, and one can use more sophisticated NLP models with randomly initialized
states for encoding. Besides, although only the initial value of the hidden
state is chosen randomly, the next values of the hidden state depend on the
previous states and the incoming words. This results in a sequence of pseudo
random values for the hidden state. This is similar to a self-synchronising
stream cipher [33] with the difference that the ciphertext does not need to be
decoded to be useful. The unfolded version of a randomly-initialized RNN can
be seen as a deep neural network with pseudo-random values for its weights.

###  IV-C Private Collaborative Learning

It is known that a richer training dataset results in better predictive
utility of ML models. In fact, the current bottleneck in training competent
predictive models in many sensitive applications, such as healthcare, is lack
of training data, e.g., [34, 35] among many others. Sufficient and diverse
data for training often does not belong to a single data-owner, and multiple
cohorts are encouraged to collaboratively provide data for the training job.

Let assume we have $D$ data-owners. We wish to enable each data-owner with
index $d$, $d\in\\{0,\dots,D-1\\}$, to publish their labeled dataset
$\mathcal{X}_{d}$ while hiding its sensitive information. Given the dataset
$\\{(x,L(x))\\}_{x\in\mathcal{X}_{d}}$, the data-owner randomly samples a
private encoder $T_{d}$ according to $\Pr[\bm{T_{A}}=T_{d}]$, and uses $T_{d}$
to produce labeled encoded samples
$\\{(T_{d}(x),L(x))\\}_{x\in\mathcal{X}_{d}}$. The data-owner can then deposit
the labeled encoded dataset publicly for untrusted third parties for
collaborative learning. In this section, we show that multiple data-owners can
seamlessly collaborate to develop joint models by publishing datasets on the
same task while using independently-sampled encoders, see Fig 1 (c).

From information theoretical view, the average uncertainty of Bob about the
labeling function goes down with enriching the training data, i.e., for
$d\in\\{0,\dots,D-1\\}$,

$\begin{split}\operatorname{H}[\bm{L}{\mid}\bm{\\{(x,L(x))\\}_{x\in\mathcal{X}_{0}}},&\dots,\bm{\\{(x,L(x))\\}_{x\in\mathcal{X}_{D-1}}}]\\\
&\leq\operatorname{H}[\bm{L}{\mid}\bm{\\{(x,L(x))\\}_{x\in\mathcal{X}_{d}}}],\end{split}$

and in fact, if the combined data is equivalent to the set of all samples,
i.e., $\mathcal{X}_{0}\cup\dots\cup\mathcal{X}_{D-1}=\mathcal{X}$, the entropy
of the labeling function given the combined labeled data is zero.

The same argument holds for training on combined encoded data of multiple
data-owners,

$\begin{split}\operatorname{H}[\bm{L\circ
T_{d}^{-1}}{\mid}&\cup_{d^{\prime}}\bm{\bm{\\{(T_{d^{\prime}}(x),L(x))\\}_{x\in\mathcal{X}_{d^{\prime}}}}}]\\\
&\leq\operatorname{H}[\bm{L\circ
T_{d}^{-1}}{\mid}\bm{\\{(T_{d}(x),L(x))\\}_{x\in\mathcal{X}_{d}}}],\end{split}$

Thus, the utility score obtained by the combined encoded data, is at least
equivalent to the utility score when the model is trained with the encoded
data of one data-owner. This is because the ML developer can just ignore the
data of other data-owners and treat them individually to train $D$ disjoint
classifiers. Next, we show as long as knowing the optimal classifier for one
data-owner contains useful information for classifying the data of other data-
owners, the utility score can theoretically increase by using combined encoded
data.

######  Proposition 3.

The utility score of a scheme that uses combined encoded data of multiple
data-owners for training is lower bounded by the utility score of the scheme
when only encoded data of one data-owner is used for training. The bound is
sharp if and only if

$\displaystyle\operatorname{H}[\cup_{d^{\prime}\neq
d}\bm{\bm{\\{(T_{d^{\prime}}(x),L(x))\\}_{x\in\mathcal{X}_{d^{\prime}}}}}{\mid}\bm{\\{T_{d}(x)\\}_{x\in\mathcal{X}_{d}},L\circ
T_{d}^{-1}}]$ $\displaystyle=\operatorname{H}[\cup_{d^{\prime}\neq
d}\bm{\bm{\\{(T_{d^{\prime}}(x),L(x))\\}_{x\in\mathcal{X}_{d^{\prime}}}}}{\mid}\bm{\\{T_{d}(x),L(x)\\}_{x\in\mathcal{X}_{d}}}].$

Our experiments in Section V also show improvements in the predictive utility
of an ML model when trained with combined individually-encoded data of two
data-owners (each one samples its encoder randomly and independently) compared
to the case where the model is trained only with encoded data of one data-
owner.

##  V Experimental Results

To evaluate the impact of our randomized encoding scheme on downstream
modeling performance, we compared models that are trained with our encoded
data to standard architectures trained on raw data. For each classification
task and training setting, we report the average AUC of such models. For the
case of multiple data-owners, we wished to evaluate the impact of leveraging
independently-sampled encoders on modeling accuracy. As a result, we evaluate
both model performance when leveraging a single encoder across both data-
owners (Combined-Clear), and model performance when leveraging two independent
encoders (Combined-Randomized). We note that prediction accuracy in the
Combined-Clear setting acts as an upper bound for the Combined-Randomized.

To compare the privacy of multiple encoding schemes, we considered a
computational attack that aims to estimate the encoder realization $T_{A}$. We
assumed that the attacker has access to a labeled public dataset
$\\{(x,L(x)),S(x)\\}_{x\in\mathcal{P}}$, and Alice’s labeled encoded samples
$\\{(T_{A}(x),L(x))\\}_{x\in\mathcal{X}_{A}}$. Given this information, the
attacker tries to learn a $T^{\text{sub-opt}}$ such that $T_{A}\approx
T^{\text{sub-opt}}$. To estimate $T_{A}$, we sampled an initial encoder
$T_{\theta}$ with the same architecture as $T_{A}$, and trained it to minimize
the MMD between $Z^{*}=T_{\theta}(\mathcal{P})$ (generated ciphertext) and
$Z=T_{A}(\mathcal{X}_{A})$ (real ciphertext).

We also consider a scenario where an attacker may try to learn a sensitive
attribute classifier on the encoded domain using the estimated encoder and the
public data. The attacker can use this classifier on Alice’s encoded data
$T_{A}(\mathcal{X}_{A})$ to obtain sensitive information that is not released
by Alice.

###  V-A Chest X-Ray Data

For these experiments, we utilized two benchmark datasets of chest x-rays,
MIMIC-CXR ([17]) and CheXpert ([18]) from Beth Israel Deaconess Medical Center
and Stanford, respectively. The MIMIC-CXR and CheXpert datasets are available
under the PhysioNet Credentialed Health Data License 1.5.0 license and
Stanford University School of Medicine CheXpert Dataset Research Use
Agreement, respectively. The samples of each dataset are labeled with up to
$5$ abnormalities, i.e., Edema, Pneumothorax, Consolidation, Cardiomegaly and
Atelectasis. For each medical condition as a classification task, we excluded
exams with an uncertain disease label, i.e., the clinical diagnosis did not
explicitly rule out or confirm the disease, and randomly split the remaining
data $60{-}20{-}20$ for training, development and testing, respectively. All
images were down sampled to $256{\times}256$ pixels. All experiments were
repeated $3$ times across different seeds.

#### Evaluating modeling utility

For each diagnosis task and training setting, we report the average AUC across
the MIMIC-CXR and CheXpert test sets. Our encoding split each image into
several patches with size $16{\times}16$, and leveraged a model with depth of
$7$ and a hidden dimension of $2048$. This model had $\sim 22.9M$ parameters
and mapped $256{\times}256$ pixel images to $256{\times}2048$ vectors. Because
of the patch-shuffling component of our encoding scheme, the encoded patches
are unordered. As a result, we trained Vision Transformers (ViT) [31], a self-
attention based architecture that is invariant to patch ordering. Across all
experiments, we used a one-layer ViT with a hidden dimension of $2048$ for the
utility evaluation, and we compared the classification performance with a raw-
sample baseline. We trained all models for $25$ epochs using the Adam
optimizer [36], an initial learning rate of $1\mathrm{e}{-04}$, weight decay
of $1\mathrm{e}{-03}$ and a batch size of $128$.

We report our results in predicting various medical diagnoses from chest x-ray
datasets in Table I. The models trained on encoded data obtained competitive
AUCs to our raw-sample baseline across all training settings. In the multi-
hospital setting, we found that trained on encoded data was effectively able
to leverage the larger training set to learn an improved classifier, despite
using separate encoders for each dataset. Our scheme obtained an average AUC
increase of 2 and 3 points compared to training only on the MIMIC-CXR and
CheXpert datasets, respectively. Moreover, our scheme demonstrated to achieve
equivalent performance in the Combined-Clear and Combined-Randomized settings,
showing that multiple institutions do not pay a significant performance cost
to collaborate via publishing their randomly-encoded data.

TABLE I: Chest x-ray prediction tasks across different training settings. All metrics are average ROC AUCs across the MIMIC-CXR and CheXpert test sets. Guides of abbreviations for medical diagnosis: (E)dema, (P)neumothorax, (Co)nsolidation, (Ca)rdiomegaly and (A)telectasis. Data | E | P | Co | Ca | A | Average
---|---|---|---|---|---|---
Train on MIMIC-CXR
orig | 85 $\pm$ 1 | 69 $\pm$ 3 | 74$\pm$ 2 | 87 $\pm$ 0 | 83 $\pm$ 1 | 80
enc | 85 $\pm$ 2 | 72 $\pm$ 1 | 72 $\pm$ 1 | 87 $\pm$ 0 | 83 $\pm$ 1 | 80
Train on CheXpert
orig | 82 $\pm$ 1 | 71 $\pm$ 1 | 72 $\pm$ 3 | 83 $\pm$ 1 | 80 $\pm$ 0 | 77
enc | 84 $\pm$ 1 | 71 $\pm$ 1 | 75 $\pm$ 2 | 82 $\pm$ 1 | 81 $\pm$ 0 | 79
Train on Combined-Clear
orig | 86 $\pm$ 0 | 77 $\pm$ 1 | 76 $\pm$ 2 | 87 $\pm$ 1 | 85 $\pm$ 0 | 82
enc | 87 $\pm$ 0 | 76 $\pm$ 3 | 78 $\pm$ 1 | 88 $\pm$ 0 | 85 $\pm$ 1 | 83
Train on Combined-Randomized
enc | 87 $\pm$ 1 | 77$\pm$ 3 | 77 $\pm$ 3 | 86 $\pm$ 1 | 84 $\pm$ 1 | 82

#### Evaluating modeling privacy

We performed the attack on convolutional architectures with a depth of $7$. As
a baseline, we also performed the attack when using a simple linear encoder,
implemented as single convolutional layer. Across all experiments, we used a
hidden dimension of $2048$ and trained $T^{\text{sub-opt}}$ for $25$ epochs.
We performed a grid search over different learning rates and weight decay
values for each attack. We recorded the validation MMD, as the loss of the MMD
attack, against linear encoding scheme and our encoding scheme. Moreovere, we
evaluated the attack by measuring the normalized MSE between generated
($Z^{*}$) and real ciphertext ($Z$) for some held-out plaintext images. For
normalization, we use the MSE of a naive estimation of Alice’s encoder that
maps every sample to the average of Alice’s encoded samples. We report the
performance of our adversarial attack in Table II.

TABLE II: Evaluation of an adversarial attack on two different encodings for held-out dataset $\mathcal{Q}$. Encoding | Validation MMD | Normalized MSE
---|---|---
Linear | 1.139 | $0.43\pm 0.01$
Depth-7 | 1.637 | $4.44\pm 0.12$

To compare the performance of multiple encoding schemes against the second
type of attack, we began with the best estimated $T^{\text{sub-opt}}$ from our
adversarial attack experiments, and built a new classifier to predict a
sensitive feature of an encoded sample. To build the training data, we use a
public data and $T^{\text{sub-opt}}$ to obtain $Z^{*}$. We report the ROC AUC
of this classifier on both $Z$ and $Z^{*}$. We performed this attack for both
an encoding with a depth of $7$ and a hidden dimension of $2048$, as leveraged
in the modeling utility experiments, and when using a linear encoding. For
each experiment, we trained a ViT for $25$ epochs using the Adam optimizer, an
initial learning rate of $1\mathrm{e}{-04}$ and a batch size of $128$. We
report the performance of our sensitive feature attack in Table III. As
expected, using a linear encoding is not robust to both attacks.

TABLE III: Performance of sensitive feature attack on Linear and our encodings. Encoding | AUC on $Z^{*}$ | AUC on $Z$
---|---|---
Linear | 89 $\pm$ 1 | 86 $\pm$ 1
Depth-7 | 84 $\pm$ 1 | 52 $\pm$ 4

#### Verification of Equality (5)

Here, we empirically validate that for the described encoding scheme, we have
$\operatorname{H}[\bm{T_{A}}\mid\bm{\mathcal{X}_{A}},\bm{{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}},\mathcal{K}_{e}]\approx
0,$ and thus Alice’s data and Alice’s encoder have the same average
uncertainty for the attacker. For this purpose, we show that an attacker who
has access to $\mathcal{X}_{A}$, $\mathcal{O}_{T_{A}}(\mathcal{X}_{A})$, and
$\mathcal{K}_{e}$ can recover $T_{A}$. We realize this goal in two steps.
Using the un-ordered datasets $\mathcal{X}_{A}$ and
$\mathcal{O}_{T_{A}}(\mathcal{X}_{A})$, we first demonstrate that an attacker
can use her knowledge $\mathcal{K}_{e}$ to recover the pairs
$\\{(x,T_{A}(x))\\}_{x\in\mathcal{X}_{A}}$. Then, using a sufficient number of
matching pairs $\\{(x,T_{A}(x))\\}_{x\in\mathcal{X}_{A}}$, we recover $T_{A}$.

For the first step, we leverage a model-based attacker $M$, trained using the
following procedure:

  1. 1.

Sample an encoder $T\in\mathcal{F}$ according to $\Pr[\bm{T_{A}}=T]$.

  2. 2.

Create an encoded dataset $T(\mathcal{X}_{A})$.

  3. 3.

Update the weights of the model $M$ such that for every
$x,y\in\mathcal{X}_{A}$, where $x\neq y$, $M(x,T(x))$ is high (high
similarity), while $M(y,T(x))$ is low (low similarity).

  4. 4.

Repeat from 1) until convergence.

We emphasize that at each iteration of the algorithm, a new encoding function
$T$ is sampled. Hence, $M$ learns to generalize across the family of encoding
functions for the fixed dataset $\mathcal{X}_{A}$. As a result, $M$ also
generalizes to Alice’s specific encoder $T_{A}$ and the attacker obtains pairs
of plaintexts and their corresponding ciphertexts.

For the second step, we utilize the corresponding pairs to carry a plaintext
attack using gradient descent on the weights of a candidate encoder $T$, to
minimize the loss between $T(x)$ and $T_{A}(x)$ for every
$x\in\mathcal{X}_{A}$.

For an encoder architecture with depth $7$, in the first step (the matching
game), we observed the re-identification AUC $99.93$ and re-identification
accuracy $89.44$, respectively. As for the second step, we measured the
success of recovering Alice’s encoder by mean square error (MSE) metric. We
observed a validation MSE of 0.0435 between pairs of samples in
$\\{T_{A}(x),T(x)\\}_{x\in\mathcal{X}_{A}}$. In comparison, the MSE between
$\\{T_{A}(x),T_{R}(x)\\}_{x\in\mathcal{X}_{A}}$, where $T_{R}$ is a random
encoder with the same architecture as $T_{A}$ is 0.780.

###  V-B SMS Text Data

The dataset contains labeled English SMS messages for spam classification
[19]. A word-level tokenizer was used to tokenize the samples (messages).
Then, samples with less than $5$ tokens were removed, in order to train only
on texts with discernible meaning. The filtered dataset is composed of $4916$
samples. Next, we used GloVe $200$ disctionary as the word embedding [37].
GloVe $200$ is trained on Wikipedia and GigaWord $5$ data to transform words
into a vector representations, such that some similarity metrics between the
words are preserved. We simulate two data-owners by equally splitting this
dataset into two - Spam Dataset 1 and Spam Dataset 2. We randomly split each
dataset $45{-}45{-}10$ for training, development and testing, respectively.
Our encoder is a randomly initialized RNN model with $200$ features in its
hidden state. The final value of the hidden state represents the encoded
sample we use for training a classifier as described next.

#### Evaluating modeling utility

The resulting encoded representations associated with their labels are sent to
a downstream densely connected neural network for spam classification. We
evaluate the utility of our encoder by computing the AUC of spam
classification trained on encoded data, compared to a raw-sample baseline that
is trained on original uncoded data. We train the models using early stopping
with a patience of $10$ points to avoid overfitting, and we use the Adam
optimizer and learning rate of $1\mathrm{e}{-03}$.

TABLE IV: Spam prediction tasks across different training settings. All metrics are average ROC AUCs across SMS Spam test sets. Data | AUC
---|---
Train on Spam Dataset 1
orig | 99.48
enc | 88.74
Train on Spam Dataset 2
orig | 97.96
enc | 89.55
Train on Combined-Clear
orig | 99.37
enc | 89.55
Train on Combined-Randomized
enc | 87.39

#### Evaluating modeling privacy

To test the privacy of the encoder, we conduct an adversarial MMD attack to
obtain an estimated encoder, and recorded the validation MMD as well as AUC of
obtaining sensitive feature from Alice’s encoded data using the estimated
encoder. For the sensitive feature attack, we used the same label (spam or
not) as both public label and private label since we did not have access to a
text dataset with two features suitable for our experiments. We trained a
classifier on public data encoded via the estimated encoder, and used the
trained classifier to estimate the label of Alice’s encoded data. The results
are given in Table V and show that linear encoding is notably weaker than our
RNN-based encoding, against both attacks.

TABLE V: Adversarial attacks on two different encodings. Left: MMD Between
$T_{A}(\mathcal{Q})$ and $T^{\text{sub-opt}}(\mathcal{Q})$ for held-out
dataset $\mathcal{Q}$. Right: Performance of sensitive feature attack.

Encoding | Validation MMD
---|---
Linear | 0.0472
R-RNN | 0.0512

Encoding | AUC
---|---
Linear | 66.14
R-RNN | 52.98

##  VI Discussion

Since the leading results of using a single (potentially randomized) transform
to encode samples of an ML training dataset, also known as instance encoding,
there were a couple of works that support or challenge its privacy promises.
We conclude our paper by briefly going through a subset of these works, and
argue how PEOPL stands in line of these theoretical and experimental
arguments.

From the information theoretical view, a scheme is perfectly private, if the
transformed and original datasets have zero mutual information. However,
perfect privacy is not helpful for data sharing, since the encoded data cannot
be used for training a classifier which is the authorized use. Recently, in
[38, 39], the notion of perfect sample privacy and perfect subset privacy were
considered, which are shown to be attainable using instance encoding. These
papers demonstrated the possibility of ensuring zero mutual information
between the encoded samples and any subset of original samples with a
constrained cardinality, while preserving the learnibility of the encoded
dataset. In this paper, we took an alternative approach and changed the focus
of privacy question from the original data to the random choice of the encoder
taken by the data-owner (i.e., the private key). Thus, the privacy was
evaluated against an adversary who is interested to break the encoder given
the sensitive encoded data and some relevant uncoded public data.

The arguments that discourage using instance randomized encoding schemes for
privacy purposes either targeted a specific encoding scheme, such as linear
schemes, or are based on assumptions that do not apply to the setting of this
paper. After the introduction of Instahide [5], where the sensitive samples
are randomly and linearly mixed together and with some public samples before
training, it was shown experimentally in [40] that this random mixing can be
un-done. Further, it was argued in [41] that it is theoretically impossible to
achieve a form of privacy (called distinguishing privacy) by means of mix-up
type encodings. This impossibility argument does not apply to PEOPL, as it is
neither a linear encoding nor a mix-up type scheme. The results in [41] do not
consider encoding schemes that use private keys, which are focus of this
paper.

Later in [42], an attack was proposed to re-identify correspondences of
transformed data (encoded via the scheme presented in Section V-A) and raw
data, from shuffled datasets [43]. The attacker in this task has access to
matching (un-ordered) original and encoded datasets, and intends to break the
encoder. This is explicitly not the setting we considered for the encoding
schemes we presented in Section IV, where there is no data overlap. In fact,
we proved in Proposition 2 that if such an assumption holds, the key and the
original data have the same average uncertainty in eyes of an adversary.

The theoretical impossibility result of [42] which argues the impossibility of
achieving ideal privacy for non-trivial encoding schemes is not valid for our
setting for two reasons: (i) It is assumed in [42] that the encoding scheme
has some auxiliary information about the labeling function, which does not
apply to our setting where the encoder is drawn from a distribution that is
independent of the data distribution. (ii) We do not target the perfect or
ideal privacy in this paper. Instead, we quantify the privacy obtained via a
key distribution, using the average uncertainty of the adversary about the
encoder chosen by the data-owner given observed encoded data and some public
un-encoded data.

Lastly, we note that this paper does not claim proposing an encoding scheme
that guarantees the encoded data cannot be used for an un-authorized task
(i.e., anything beyond the designated ML training task). Rather, it sheds
light on this important privacy-utility problem. In particular, we
theoretically showed why the random non-linear transforms, and especially the
random deep neural networks, are a viable candidate for this problem. We
provided empirical experiments to test the robustness of instances of our
encoding scheme against adversarial attacks, following standard practice in
security [44, 45]. While our empirical attacks are not sufficient to guarantee
any privacy, they are insightful to demonstrate trade-offs and measure
improvements in the scheme design. Our results validated our presented
theoretical argument that composing random functions can offer improved
privacy over linear approaches, while maintaining competitive accuracy to raw-
sample baselines. Moreover, we demonstrated that multiple independent random
encoders can be combined to achieve improved overall utility. While, PEOPL
should not be directly applied for private data sharing today, it’s promising
empirical properties show that randomized neural networks warrant further
study, as they offer a new direction of private encoding scheme design.

##  VII Conclusions and Future Work

This paper combined the idea of key-based encoding and training on the latent
representation of data. The encoded data does not need to be decoded to be
used for the downstream training task. Thus, effectively the key does not need
to be shared among parties. With the introduced notions of privacy and utility
scores of a random encoding scheme, we proposed how one can improve the
randomized scheme. While the proposed approach does not guarantee zero
information leakage beyond the labeling data, our analysis provided a useful
machinery for the design of competent encoding schemes.

On two benchmark chest x-ray datasets, MIMIC-CXR and CheXpert, and a spam text
dataset, we found that models trained on our encoded data obtained competitive
performance to our raw-sample baselines. In the multi-institutional setting,
where each site leverages an independently chosen encoder, we demonstrated
that models trained on combined data of multiple cohorts could effectively
leverage the larger training data to learn improved classifiers.

Developing randomized coding schemes which facilitate collaborative training
among data-owners with different types of data is a promising future direction
to pursue. Another future direction is to develop hybrid collaborative
schemes, which allow data-owners to share either their raw data, randomly
encoded data, or their model updates. Last but not least, investigating other
information measures for quantifying the privacy and utility performance of an
encoding scheme remains for the future research.

## References

  * [1] HIPAA, _Health Insurance Portability and Accountability Act of 1996_.
  * [2] GDPR, _EU General Data Protection Regulation of 2016_.
  * [3] L. Rocher, J. M. Hendrickx, and Y. de Montjoye, “Estimating the success of re-identifications in incomplete datasets using generative models,” _Nature Communications_ , vol. 10, no. 3069, 2019.
  * [4] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Artificial Intelligence and Statistics_. PMLR, 2017, pp. 1273–1282.
  * [5] Y. Huang, Z. Song, K. Li, and S. Arora, “InstaHide: Instance-hiding schemes for private distributed learning,” in _Proceedings of the 37th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, H. D. III and A. Singh, Eds., vol. 119. PMLR, 13–18 Jul 2020, pp. 4507–4518.
  * [6] M. Adnan, S. Kalra, J. C. Cresswell, G. W. Taylorand, and H. R. Tizhoosh, “Federated learning and differential privacy for medical image analysis.” _Nature Scientific Report_ , vol. 12, no. 1953, 2022.
  * [7] C. Dwork, A. Roth _et al._ , “The algorithmic foundations of differential privacy,” _Foundations and Trends in Theoretical Computer Science_ , vol. 9, no. 3-4, pp. 211–407, 2014.
  * [8] C. Gentry, “Fully homomorphic encryption using ideal lattices,” in _Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009_ , M. Mitzenmacher, Ed. ACM, 2009, pp. 169–178. [Online]. Available: https://doi.org/10.1145/1536414.1536440
  * [9] Z. Brakerski and V. Vaikuntanathan, “Efficient fully homomorphic encryption from (standard) LWE,” in _IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011_ , R. Ostrovsky, Ed. IEEE Computer Society, 2011, pp. 97–106. [Online]. Available: https://doi.org/10.1109/FOCS.2011.12
  * [10] D. Boneh, A. Sahai, and B. Waters, “Functional encryption: a new vision for public-key cryptography,” _Commun. ACM_ , vol. 55, no. 11, pp. 56–64, 2012\. [Online]. Available: https://doi.org/10.1145/2366316.2366333
  * [11] H. Cho, D. J. Wu, and B. Berger, “Secure genome-wide association analysis using multiparty computation,” _Nature biotechnology_ , vol. 36, no. 6, pp. 547–551, 2018.
  * [12] C. Gentry, S. Halevi, and N. P. Smart, “Fully homomorphic encryption with polylog overhead,” Cryptology ePrint Archive, Paper 2011/566, 2011, https://eprint.iacr.org/2011/566. [Online]. Available: https://eprint.iacr.org/2011/566
  * [13] B. Reagen, W.-S. Choi, Y. Ko, V. T. Lee, H.-H. S. Lee, G.-Y. Wei, and D. Brooks, “Cheetah: Optimizing and accelerating homomorphic encryption for private inference,” in _IEEE International Symposium on High-Performance Computer Architecture (HPCA)_ , 2021, pp. 26–39.
  * [14] H. Xiao and S. Devadas, “Dauntless: Data augmentation and uniform transformation for learning with scalability and security,” Cryptology ePrint Archive, Paper 2021/201, 2021, https://eprint.iacr.org/2021/201. [Online]. Available: https://eprint.iacr.org/2021/201
  * [15] A. Yala, V. Quach, H. Esfahanizadeh, R. G. L. D’Oliveira, K. R. Duffy, M. Médard, T. S. Jaakkola, and R. Barzilay, “Syfer: Neural obfuscation for private data release,” 2022. [Online]. Available: https://arxiv.org/abs/2201.12406
  * [16] C. E. Shannon, “A mathematical theory of communication.” _Bell Syst. Tech. J._ , vol. 27, no. 3, pp. 379–423, 1948.
  * [17] A. E. Johnson, T. J. Pollard, N. R. Greenbaum, M. P. Lungren, C.-y. Deng, Y. Peng, Z. Lu, R. G. Mark, S. J. Berkowitz, and S. Horng, “Mimic-cxr-jpg, a large publicly available database of labeled chest radiographs,” _arXiv preprint arXiv:1901.07042_ , 2019.
  * [18] J. Irvin, P. Rajpurkar, M. Ko, Y. Yu, S. Ciurea-Ilcus, C. Chute, H. Marklund, B. Haghgoo, R. Ball, K. Shpanskaya _et al._ , “Chexpert: A large chest radiograph dataset with uncertainty labels and expert comparison,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 33, no. 01, 2019, pp. 590–597.
  * [19] “Sms spam collection v. 1.” [Online]. Available: http://www.dt.fee.unicamp.br/~tiago/smsspamcollection/
  * [20] J. Massey, “Guessing and entropy,” in _Proceedings of 1994 IEEE International Symposium on Information Theory_ , 1994, pp. 204–.
  * [21] E. Arikan, “An inequality on guessing and its application to sequential decoding,” _IEEE Transactions on Information Theory_ , vol. 42, no. 1, pp. 99–105, 1996.
  * [22] S. BOZTAS, “On renyi entropies and their applications to guessing attacks in cryptography,” _IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences_ , vol. E97.A, no. 12, pp. 2542–2548, 2014\.
  * [23] S. Kullback, _Information Theory and Statistics_. New York: Wiley, 1959.
  * [24] M. Karson, “Handbook of methods of applied statistics. volume i: Techniques of computation descriptive methods, and statistical inference. volume ii: Planning of surveys and experiments. i. m. chakravarti, r. g. laha, and j. roy, new york, john wiley; 1967, $9.00.” _Journal of the American Statistical Association_ , vol. 63, no. 323, pp. 1047–1049, 1968. [Online]. Available: https://doi.org/10.1080/01621459.1968.11009335
  * [25] A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Schölkopf, and A. Smola, “A kernel two-sample test,” _The Journal of Machine Learning Research_ , vol. 13, no. 1, pp. 723–773, 2012.
  * [26] I. O. Tolstikhin, B. K. Sriperumbudur, and B. Schölkopf, “Minimax estimation of maximum mean discrepancy with radial kernels,” in _Advances in Neural Information Processing Systems_ , D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, Eds., vol. 29. Curran Associates, Inc., 2016. [Online]. Available: https://proceedings.neurips.cc/paper/2016/file/5055cbf43fac3f7e2336b27310f0b9ef-Paper.pdf
  * [27] K. Fukumizu, A. Gretton, X. Sun, and B. Schölkopf, “Kernel measures of conditional dependence,” in _Advances in neural information processing systems 20_ , Max-Planck-Gesellschaft. Red Hook, NY, USA: Curran, Sep. 2008, pp. 489–496.
  * [28] B. K. Sriperumbudur, A. Gretton, K. Fukumizu, B. Schölkopf, and G. R. Lanckriet, “Hilbert space embeddings and metrics on probability measures,” _J. Mach. Learn. Res._ , vol. 11, p. 1517–1561, aug 2010.
  * [29] S. Ioffe and C. Szegedy, “Batch normalization: Accelerating deep network training by reducing internal covariate shift,” in _International conference on machine learning_. PMLR, 2015, pp. 448–456.
  * [30] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly _et al._ , “An image is worth 16x16 words: Transformers for image recognition at scale,” _arXiv preprint arXiv:2010.11929_ , 2020.
  * [31] D. Zhou, B. Kang, X. Jin, L. Yang, X. Lian, Z. Jiang, Q. Hou, and J. Feng, “Deepvit: Towards deeper vision transformer,” _arXiv preprint arXiv:2103.11886_ , 2021.
  * [32] S. Hochreiter and J. Schmidhuber, “Long short-term memory,” _Neural Comput._ , vol. 9, no. 8, p. 1735–1780, nov 1997. [Online]. Available: https://doi.org/10.1162/neco.1997.9.8.1735
  * [33] D. Stinson, _Cryptography: Theory and Practice,Second Edition_. London, UK: Chapman & Hall, CRC, 2002, pp. 117–154.
  * [34] T. Panch, H. Mattie, and L. A. Celi, “The “inconvenient truth”about ai in healthcare,” _npj Digital Medicine_ , vol. 2, no. 1, p. 77, 2019.
  * [35] M. V. Bak M, F. MC, M. MT, and M. S, “You can’t have ai both ways: Balancing health data privacy and access fairly,” _Frontiers in Genetics_ , June 2022\.
  * [36] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.
  * [37] J. Pennington, R. Socher, and C. D. Manning, “Glove: Global vectors for word representation.” in _EMNLP_ , vol. 14, 2014, pp. 1532–1543.
  * [38] B. Rassouli, F. E. Rosas, and D. Gündüz, “Data disclosure under perfect sample privacy,” _IEEE Transactions on Information Forensics and Security_ , vol. 15, pp. 2012–2025, 2020.
  * [39] N. Raviv and Z. Goldfeld, “Perfect subset privacy for data sharing and learning,” in _2022 IEEE International Symposium on Information Theory (ISIT)_ , 2022, pp. 1850–1855.
  * [40] N. Carlini, S. Deng, S. Garg, S. Jha, S. Mahloujifar, M. Mahmoody, S. Song, A. Thakurta, and F. Tramer, “An attack on instahide: Is private learning possible with instance encoding?” 2020.
  * [41] N. Carlini, S. Deng, S. Garg, S. Jha, S. Mahloujifar, M. Mahmoody, A. Thakurta, and F. Tramèr, “Is private learning possible with instance encoding?” in _42nd IEEE Symposium on Security and Privacy, SP 2021, San Francisco, CA, USA, 24-27 May 2021_. IEEE, 2021, pp. 410–427. [Online]. Available: https://doi.org/10.1109/SP40001.2021.00099
  * [42] N. Carlini, S. Garg, S. Jha, S. Mahloujifar, M. Mahmoody, and F. Tramer, “Neuracrypt is not private,” 2021. [Online]. Available: https://arxiv.org/abs/2108.07256
  * [43] A. Yala, H. Esfahanizadeh, R. G. L. D’Oliveira, K. R. Duffy, M. Ghobadi, T. S. Jaakkola, V. Vaikuntanathan, R. Barzilay, and M. Medard. [Online]. Available: https://github.com/yala/NeuraCrypt-Challenge
  * [44] N.-F. Standard, “Announcing the advanced encryption standard (AES),” _Federal Information Processing Standards Publication_ , vol. 197, no. 1-51, pp. 3–3, 2001.
  * [45] M. J. Dworkin, “SHA-3 standard: Permutation-based hash and extendable-output functions,” 2015.

This section belongs to the proofs of the theoretical results in this paper.

Proof of Theorem 1.
We first note that according to Definition 6, for any
$T\notin\operatorname{Pos}[{T_{A}}]$, we have
$\Pr[\bm{T_{A}}=T\mid\mathcal{O}_{T_{A}}({\mathcal{X}_{A}}),\;\mathcal{K}_{e}]=0$.
Next, we consider the case where $T\in\operatorname{Pos}[{T_{A}}]$:

$\displaystyle\Pr[\bm{T_{A}}=T\mid\mathcal{O}_{T_{A}}({\mathcal{X}_{A}}),\mathcal{K}_{e}]$
$\displaystyle{=}\frac{\Pr[\bm{\mathcal{O}_{T_{A}}({\mathcal{X}_{A}})}=\mathcal{O}_{T_{A}}({\mathcal{X}_{A}})\mid\bm{T_{A}}=T,\mathcal{K}_{e}]\Pr[\bm{T_{A}}=T]}{\hskip
5.69046pt\sum_{T^{\prime}}\Pr[\bm{\mathcal{O}_{T_{A}}({\mathcal{X}_{A}})}{=}\mathcal{O}_{T_{A}}({\mathcal{X}_{A}}){\mid}\bm{T_{A}}=T^{\prime},\mathcal{K}_{e}]\Pr[\bm{T_{A}}{=}T^{\prime}]}$
(7) $\displaystyle=\frac{\Pr[\bm{\mathcal{X}_{A}}=\bar{X}_{T}]}{\hskip
5.69046pt\sum_{T^{\prime}\in\operatorname{Pos}[T_{A}]}\Pr[\bm{\mathcal{X}_{A}}=\bar{X}_{T^{\prime}}]\Pr[\bm{T_{A}}=T^{\prime}]}\Pr[\bm{T_{A}}=T]$
(8)
$\displaystyle=\frac{1}{\sum_{T^{\prime}\in\operatorname{Pos}[T_{A}]}\Pr[\bm{T_{A}}=T^{\prime}]}\Pr[\bm{T_{A}}=T].$
(9)

Equation (7) is the application of the Bayes’ theorem, and that by
construction $\Pr[\bm{T_{A}}=T\mid\mathcal{K}_{e}]=\Pr[\bm{T_{A}}=T]$. For
(8), we use the fact that each transform in the family is a one-to-one
function. Thus given the encoder, the probability of observing a set of
encoded data is equivalent to the probability that the equivalent uncoded data
be Alice’s data. Finally, equation (9) is the result of the distribution of
Alice’s data described in Assumption 1, and the proof is concluded. ∎

Proof of Proposition 1.
Let $\\{(x,L(x))\\}_{x\in\mathcal{X}}=\\{(1,+),(2,+),(3,-),(4,-)\\}$, and
consider these two families of encoders, from which Alice uniformly chooses
her encoder:

$\mathcal{F}=\begin{cases}T_{1}:&(1,2,3,4)\\\ T_{2}:&(2,1,3,4)\\\
T_{3}:&(1,2,4,3)\\\
T_{4}:&(2,1,4,3)\end{cases},\quad\text{and}\quad\mathcal{F}^{\prime}=\begin{cases}T_{1}:&(1,2,3,4)\\\
T_{2}:&(2,1,3,4)\\\ T_{3}:&(1,2,4,3)\\\ T_{4}:&(2,1,4,3)\\\
T_{5}:&(3,4,1,2)\end{cases}$

We denote with $\bm{T_{A}}$ and $\bm{T^{\prime}_{A}}$ as two random variables
representing Alice’s encoder, when uniformly distributed over $\mathcal{F}$
and $\mathcal{F}^{\prime}$, respectively. Here,
$\operatorname{H}[\bm{T_{A}}\mid{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})},\mathcal{K}_{e}]=2$
regardless of Alice’s data or Eve’s observation, and thus
$\operatorname{H}[\bm{T_{A}}\mid\bm{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})},\mathcal{K}_{e}]=2$.
However,
$\operatorname{H}[\bm{T^{\prime}_{A}}\mid\mathcal{O}_{T_{A}}(\mathcal{X}_{A}),\mathcal{K}_{e}]=0$
if for example $(3,+)\in\mathcal{O}_{T_{A}}(\mathcal{X}_{A})$. In general,
when Alice’s data is non-empty,

$\operatorname{H}[\bm{T^{\prime}_{A}}\mid\bm{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})},\mathcal{K}_{e}]=2\times
4/5+0\times 1/5=8/5.$

∎

Proof of Theorem 2.
We show that if $T^{\prime}_{A}$ is given to Eve, then the scheme is as
private as if Alice had sampled her encoder from $\mathcal{F}$:

$\begin{split}\Pr&[\bm{T^{\prime}_{A}\circ
T_{A}}=T\mid\mathcal{O}_{T_{A}}(\mathcal{X}_{A}),\;\mathcal{K}_{e},\;T_{A}^{\prime}]\\\
&=\Pr[\bm{T_{A}}=(T^{\prime}_{A})^{-1}\circ
T\mid\mathcal{O}_{T_{A}}(\mathcal{X}_{A}),\;\mathcal{K}_{e}]\\\
&=\Pr[\bm{T_{A}}=T_{A}\mid\mathcal{O}_{T_{A}}(\mathcal{X}_{A}),\;\mathcal{K}_{e}].\end{split}$
(10)

Therefore, we also have

$\begin{split}\operatorname{H}&[\bm{T^{\prime}_{A}\circ
T_{A}}\mid\mathcal{O}_{T_{A}}(\mathcal{X}_{A}),\;\mathcal{K}_{e},\;T_{A}^{\prime}]=\operatorname{H}[\bm{T_{A}}\mid\mathcal{O}_{T_{A}}(\mathcal{X}_{A}),\;\mathcal{K}_{e}].\end{split}$

The above essentially shows the ambiguity about the encoder selected by Alice
from $\mathcal{F}^{\prime}\circ\mathcal{F}$ is at least equal to the ambiguity
when Alice selects her encoder from $\mathcal{F}$. Thus,
$\mathcal{F}^{\prime}\circ\mathcal{F}$ has a privacy score that is equal or
grater than the privacy score of $\mathcal{F}$. Analogous arguments show that
$\mathcal{F}^{\prime}\circ\mathcal{F}$ has a privacy score that is equal or
grater than the privacy score of $\mathcal{F}^{\prime}$. ∎

Proof of Proposition 2
By construction, the encoders that Alice can choose from are one-to-one
mappings, thus

$\begin{split}&\operatorname{H}[\bm{\mathcal{X}_{A}}\mid\bm{T_{A}},\bm{{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}},\;\mathcal{K}_{e}]=0.\end{split}$
(11)

Besides, because of the chain rule of the information entropy,

$\begin{split}&\operatorname{H}[\bm{\mathcal{X}_{A}},\bm{T_{A}}\mid\bm{{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}},\;\mathcal{K}_{e}]\\\
&=\operatorname{H}[\bm{\mathcal{X}_{A}}\mid\bm{{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}},\;\mathcal{K}_{e}]{+}\operatorname{H}[\bm{T_{A}}\mid\bm{\mathcal{X}_{A}},\bm{{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}},\;\mathcal{K}_{e}]\\\
&=\operatorname{H}[\bm{T_{A}}\mid\bm{{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}},\;\mathcal{K}_{e}]{+}\operatorname{H}[\bm{\mathcal{X}_{A}}\mid\bm{T_{A}},\bm{{\mathcal{O}_{T_{A}}(\mathcal{X}_{A})}},\;\mathcal{K}_{e}]\end{split}$
(12)

Using (11) and (12), we can conclude the proof.∎

Proof of Proposition 3.

$\displaystyle\operatorname{H}[\bm{L\circ
T_{d}^{-1}}{\mid}\cup_{d^{\prime}}\bm{\\{(T_{d^{\prime}}(x),L(x))\\}_{x\in\mathcal{X}_{d^{\prime}}}}]$
$\displaystyle{=}\operatorname{H}[\bm{L\circ
T_{d}^{-1}}{\mid}\bm{\\{(T_{d}(x),L(x))\\}_{x\in\mathcal{X}_{d}}}]$
$\displaystyle{+}\operatorname{H}[\cup_{d^{\prime}{\neq}d}\bm{\\{(T_{d^{\prime}}(x){,}L(x))\\}_{x\in\mathcal{X}_{d^{\prime}}}}{\mid}\bm{T_{d}(\mathcal{X}_{d}),L{\circ}T_{d}^{-1}}]$
$\displaystyle{-}\operatorname{H}[\cup_{d^{\prime}{\neq}d}\bm{\\{(T_{d^{\prime}}(x){,}L(x))\\}_{x\in\mathcal{X}_{d^{\prime}}}}{\mid}\bm{\\{T_{d}(x),L(x)\\}_{x\in\mathcal{X}_{d}}}],$

where we used Bayes’ theorem for information entropy and the fact that having
the function $L\circ T_{d}^{-1}$ and $T_{d}(\mathcal{X}_{d})$ subsumes the
information in $\\{(T_{d}(x),L(x))\\}_{x\in\mathcal{X}_{d}}$. ∎