.pdf

# Private Retrieval, Computing and Learning: Recent Progress and Future
Challenges 111Sennur Ulukus is with University of Maryland (email:
ulukus@umd.edu). Salman Avestimehr is with University of Southern California
(email: avestimehr@ee.usc.edu). Michael Gastpar is with EPFL (email:
michael.gastpar@epfl.ch). Syed Jafar is with University of California Irvine
(email: syed@ece.uci.edu). Ravi Tandon is with University of Arizona (email:
tandonr@email.arizona.edu). Chao Tian is with Texas A&M University (email:
chao.tian@tamu.edu).

Sennur Ulukus  Salman Avestimehr  Michael Gastpar  Syed Jafar
Ravi Tandon  Chao Tian

###### Abstract

Most of our lives are conducted in the cyberspace. The human notion of privacy
translates into a cyber notion of privacy on many functions that take place in
the cyberspace. This article focuses on three such functions: how to privately
retrieve information from cyberspace (privacy in information retrieval), how
to privately leverage large-scale distributed/parallel processing (privacy in
distributed computing), and how to learn/train machine learning models from
private data spread across multiple users (privacy in distributed (federated)
learning). The article motivates each privacy setting, describes the problem
formulation, summarizes breakthrough results in the history of each problem,
and gives recent results and discusses some of the major ideas that emerged in
each field. In addition, the cross-cutting techniques and interconnections
between the three topics are discussed along with a set of open problems and
challenges.

##  I Introduction

Privacy is an important part of human life. This article considers privacy in
the context of three distinct but related engineering applications, namely,
privacy in retrieving information, privacy in computing functions, and privacy
in learning. In the first sub-topic of private information retrieval, a user
wishes to download a content from publicly accessible databases in such a way
that the databases do not learn which particular content the user has
downloaded. Towards that goal, the user creates ambiguity by its actions
during the download. This strategy prevents databases from guessing which
content the user has downloaded. This in turn preserves the user’s privacy
because what is downloaded leaks information about interest and intent on the
part of the user. In the second sub-topic of private computing, a user wishes
to compute a function but does not have resources to perform the computation
on its own. Thus, the user outsources the computation to many distributed
servers. This necessitates the user send its data, which is private, to the
distributed servers. The goal of the user is to utilize the servers for
computation while preserving the privacy of its own data. To achieve that
goal, the user introduces randomness in its data so that the servers cannot
decipher the data while they are able to perform the computation successfully.
In the third sub-topic of privacy in learning, a centralized unit (parameter
server) wishes to train a learning model by utilizing distributed users
(clients). The parameter server needs labeled training data to train the
model. The data resides at the users, and the users prefer to keep their data
at their site, i.e., not send it to the parameter server, to preserve the
privacy of their data. Thus, such distributed (federated) learning has built-
in privacy advantages. However, even then, the computations (e.g., gradients
calculated on the data) may leak some information about the raw data. To
prevent that, the users may want to add randomness to the calculation they
send to the parameter server in order to further preserve their privacy.

The underlying threat model common to all three settings is the undesired leak
of information that is considered private by the respective entities. In the
case of private information retrieval, the leak is about the identity (index)
of the content being downloaded/accessed. In the case of private computation,
the leak is about the user data on which computation needs to performed by
distributed servers. In the case of private learning, the leak is user
(client) data that is used to train the learning model. A common aspect of the
solution approach to these problems is to randomize the information/actions in
such a way to hide the private information. In private information retrieval,
this corresponds to randomizing the downloads such that a certain download may
happen equally likely for all possible user content requirements. In private
computation, randomization is achieved by adding appropriate noise to the data
whose effect can be nullified during the computation. In private learning,
privacy of clients is achieved by keeping the data at the client side, and
also my randomizing the transmitted calculations so that leaks are prevented.

We present private information retrieval in Section II, private distributed
computation in Section III and private distributed machine learning in Section
IV. We conclude this article in Section Section V by listing a few challenges
and open problems.

##  II Private Information Retrieval

The private information retrieval (PIR) problem was introduced by Chor et al.
[1] as a privacy-preserving primitive for retrieving information in a private
manner. In the canonical PIR setting, a user wishes to retrieve one of $K$
available messages, from $N$ non-communicating servers, each of which has a
copy of these $K$ messages. User request privacy needs to be preserved during
the retrieval process, i.e., the identity of the desired message remains
unknown to any single server. A generic protocol to retrieve, e.g., message
$k$, is as follows in this setting:

  1. 1.

The user generates $N$ queries with a private random key and the message index
$k$, one query per server, which are sent to the respective servers;

  2. 2.

Each server, based on the query it receives and the content it stores, sends
back an answer to the user;

  3. 3.

The user collects the answers from $N$ databases, and reconstructs the message
based on the answers, the private key, and the requested message index $k$.

The privacy requirement can be either information-theoretic (e.g., [2]) or
computational (e.g., [3]). The former requires that each server cannot infer
any information on the identity of the requested message, even if assuming the
server has infinite computation power; in contrast, the latter assumes that
each server has only limited computation power, and under such computational
constraint, it is required that the server cannot learn anything on the
identity of the requested message. In this article, we only consider
information-theoretic privacy.

Figure 1: The PIR scheme of Chor et al. [1] for $N=2$ databases which achieves
a rate of $1/2$ for any number of messages $K$ (for the case shown in the
figure, i.e., for $K=3$ messages, the capacity is $4/7$ [4]). The main idea is
to use the fact that since the databases cannot collude, one can send
correlated queries across databases, allowing the user to leverage information
retrieved across databases to increase the rate (download efficiency).

Since the introduction of the PIR problem by Chor et al., tremendous advances
have been made using the computer science theoretic approach, including on the
canonical form and many variations; see the survey article [5] and references
therein. Within the context of this approach, the effort usually focuses on
the scaling behavior of the communication costs, including both the query
communication (upload) cost and the answer communication (download) cost, with
respect to $N$ and $K$. Moreover, the messages are usually assumed to be very
short, the most common of which is in fact a single bit per message. There
have been many variations on the canonical setting, and it has been recognized
that the PIR problem has deep connections to other coding or security
primitives, such as locally decodable codes and oblivious transfer [6, 7, 8].

It was shown in Chor et al. that for a single database, perfect information-
theoretic privacy can only be achieved by downloading the entire database (of
$K$ messages), i.e., the optimal rate defined as the ratio of the amount of
desired information (one message) and the total downloaded amount ($K$
messages) in this case is $1/K$. Thus, a natural question that was first
explored by Chor et. al is the following: can one achieve a better rate than
$1/K$ by exploiting $N>1$ databases? This question was answered in the
affirmative, and it was shown that even with $N=2$ databases, one can achieve
a rate of $1/2$ for any number of messages. We explain the main idea through a
simple example as shown in Fig. 1 for $K=3$ messages. The main idea behind the
scheme is as follows: assuming each message $W_{k}$ is one-bit, the user
generates $K$ random bits $\\{h_{1},\ldots,h_{K}\\}$ and requests the linear
combination (denoted by $\sum_{k=1}^{K}h_{k}W_{k}$) of the $K$ messages from
database $1$, whereas requests $\sum_{k=1}^{K}h_{k}W_{k}+W_{\theta}$ from the
other database whenever the user wants to retrieve $W_{\theta}$. Since
$\\{h_{k}\\}$’s are uniformly generated bits, the distribution of
$\sum_{k=1}^{K}h_{k}W_{k}+W_{\theta}$ is identical for every
$\theta\in\\{1,2,\ldots,K\\}$, ensuring perfect privacy.

Figure 2: The PIR scheme of Shah et al. [9] for $N=3$ databases and $K=2$
messages which achieves a rate of $2/3$ (the capacity for this setting is
$3/4$ [4]). More generally, the scheme achieves a rate of $1-1/N$,
irrespective of $K$. The new ingredient beyond Chor et al. [1] involved
message sub-packetization.

The PIR problem was recently reintroduced to the information theory and coding
community [9, 10, 11], with initial effort focused on using advanced coding
technique to improve the storage, upload, and download efficiency.
Specifically, Shah et al. [9] generalized the Chor et al. scheme to any
arbitrary number $(N>1)$ of databases. The key new idea herein was to
subpacketize each message into $(N-1)$ parts, and then follow an approach
similar to Chor et al. In Fig. 2, we highlight this through an example when
$N=3$ and for $K=2$ messages. Each message is partitioned into $(N-1)=2$
parts, following which the user then requests a random linear combination
($A_{1}$ from database $1$), followed by requesting $A_{1}$ XORed with the
$(N-1)$ subpackets individually from the remaining $(N-1)$ databases. This
leads to a rate of $\frac{N-1}{N}=1-\frac{1}{N}$, which is independent of $K$.

A significant milestone of this renewed effort on the PIR problem is the
result obtained in [4], where the optimal download cost of the PIR capacity of
the canonical setting was fully characterized. A key new ingredient that leads
to this breakthrough is the information-theoretic reformulation of the
problem. In contrast to typical computer science theoretical formulation, here
the number of bits in each message is allowed to approach infinity, and the
capacity is defined as the supremum of the number of useful message bits that
can be retrieved per total downloaded bits.

Figure 3: The capacity-achieving PIR scheme of Sun and Jafar [4] for $N=2$
databases and $K=2$ messages which achieves a rate of $2/3$. The optimal
scheme requires a combination of the following ideas: a) message sub-
packetization, b) maintaining message symmetry for privacy and c) fully
exploiting side information (from other databases) at each database.

A code construction was provided which relies on a few key code design
principles. The scheme by Sun and Jafar for $N=2$ databases and $K=2$ messages
is illustrated in Fig. 3. The key design principles behind the scheme include
the following: a) sub-packetization of each message into $L=N^{K}$ symbols,
followed by b) downloading parts of each message from every database (i.e.,
maintaining message symmetry) for maintaining privacy of the desired message
index, and c) fully exploiting side information at every database (from
remaining $(N-1)$ databases). For the example in Fig. 3, this amounts to
breaking the two messages into $L=4$ symbols. If the user wants to download
message $W_{1}=(a_{1},a_{2},a_{3},a_{4})$, it downloads one symbol from each
message from both databases (namely, $(a_{1},b_{1})$ from database 1 and
$(a_{2},b_{2})$ from database 2). Subsequently it downloads $a_{3}+b_{2}$ from
database 1 and $a_{4}+b_{1}$ from database 2 (i.e., the remaining desired
symbols together with the undesired symbols downloaded from the other
database). A matching converse is proved using the conventional information
theoretic approach.

The surprising result inspired many subsequent works using such a capacity
formulation and led to many new discoveries which will be surveyed in this
part of the article.

###  II-A The Canonical PIR System

For the canonical PIR setting, shown in Fig. 4, a rigorous computer science
theoretic problem definition of the problem was given in the seminal paper
[1], and a more explicit information theoretic translation was given in [12].
The breakthrough work of Sun and Jafar [4] instead directly represented the
coding function relations using information measure relations, which we
explain next.

The random query $Q^{[k]}_{n}$ intended for server-$n$ when requesting message
$k$ is determined by the private random key $\mathsf{F}$, i.e.,
$H(Q^{[k]}_{n}|\mathsf{F})=0$, for $n=1,2,\ldots,N,\,k=1,2,\ldots,K$. The
answers $A^{[k]}_{n}$ from server-$n$, in response to the query $Q^{[k]}_{n}$,
is determined by the stored messages and the query, i.e.,
$H(A^{[k]}_{n}|W_{1:K},Q^{[k]}_{n})=0$, for $n=1,2,\ldots,N,\,k=1,2,\ldots,K$.
Given the above, there are two key constraints/requirements from a PIR scheme:

  1. 1.

Decodability Constraint: The reconstructed message $\hat{W}_{k}$, by the user
for the requested message $k$, is determined from the answers $A^{[k]}_{1:N}$
and the random key $\mathsf{F}$, i.e.,

$\displaystyle H(\hat{W}_{k}|A^{[k]}_{1:N},\mathsf{F})=0,\,\text{for
}k\in\\{1,2,\ldots,K\\}.$ (1)

  2. 2.

Privacy Constraint: The privacy requirement is that the queries for any
message pairs $k$ and $k^{\prime}$ have an identical distribution

$\displaystyle\mathbf{Pr}(Q^{[k]}_{n}=q)=\mathbf{Pr}(Q^{[k^{\prime}]}_{n}=q),$
(2)

which can be represented as
$I(\theta;Q^{[\theta]}_{n},A^{[\theta]}_{n},W_{1:K})=0$, for
$n\in\\{1,2,\ldots,N\\}$, where $\theta$ is the random variable representing
the index of the requested message.

In the information-theoretic setting, the download cost $D$ dominates the
upload cost. The definition of the download cost $D$ requires some
elaboration. Two obvious information-theoretic measures directly related to
the download cost are $\sum_{i=1}^{N}H(A^{[k]}_{n})$ and
$\sum_{i=1}^{N}H(A^{[k]}_{n}|\mathsf{F})$. The latter is a lower bound of the
expected number of total download bits, which is how we usually measure the
download cost. The former is an upper bound of the latter, and can be viewed
as a surrogate, particularly in asymptotic (large number of information bits
in each message) settings.

Figure 4: (a) The canonical PIR system; (b) extensions of the canonical
system.

The efficiency of the download is then measured by the number of requested
message bits obtained per downloaded bit, which leads to the following
capacity notion, when error is not allowed. More precisely, a rate $R$ is said
to be achievable for zero-error PIR, if there exists a PIR code of download
cost $D$ such that $R=\frac{L}{D}$ with no decoding errors. The supremum of
achievable rates for zero-error PIR is called the (zero-error) PIR capacity
$C_{0}$.

For zero-error PIR code, there is no need to explicitly specify the
probability distribution for each message, and also no need to specify the
message retrieval probability. However, when a more general capacity notion,
the $\epsilon$-error capacity, is adopted, this is no longer the case, since
the error probability is not strictly zero. In this case, the convention is to
assume that each message is distributed in its range uniformly at random, and
the message is also being requested uniformly at random [4]. Correspondingly,
a rate $R$ is said to be $\epsilon$-error achievable if there exists a
sequence of PIR codes, each of rate greater than or equal to $R$, for which
$\frac{1}{K}\sum_{k=1}^{K}\mathbf{Pr}(\hat{W}_{k}\neq W_{k})\rightarrow 0$ as
$L\rightarrow\infty$. The supremum of $\epsilon$-error achievable rates is
called the $\epsilon$-error capacity $C_{\epsilon}$.

The download cost used above is the expected number of downloaded bits, and
the capacities are defined accordingly, which is usually the notion adopted in
subsequent works. However another slightly different notion of the download
cost is the worst-case download cost, which was used in [13] (and later
adopted in [14, 15]). The worst-case download cost is the largest number of
downloaded bits over all query combinations that are used with non-zero
probability. Using this notion, we can similarly define the zero-error worst-
case PIR capacity $\bar{C}_{0}$, and $\epsilon$-error worst-case PIR capacity
$\bar{C}_{\epsilon}$. The breakthrough work [4] essentially established that

$\displaystyle
C_{0}=\bar{C}_{0}=C_{\epsilon}=\bar{C}_{\epsilon}=\left(1+\frac{1}{N}+\cdots+\frac{1}{N^{K-1}}\right)^{-1}.$
(3)

The capacity definition $C_{0}$ is the most straightforward, and often adopted
in the literature for generalized PIR settings. When the problem setting
deviates from the canonical setting, it is known that $C_{\epsilon}$ can be
different from $C_{0}$ in certain cases, but it is not well understood when
this is the case. It is not known whether $\bar{C}_{0}$ and
$\bar{C}_{\epsilon}$ can in fact be different for any generalized PIR systems.

Figure 5: Low-subpacketization schemes for PIR for $(N,K)=(2,2)$. The scheme
in (a) was given in [16, 12], and the scheme in (b) in [17, 18]. One achieves
the minimum possible subpacketization for each message while achieving an
expected download cost of $3/2$.

The general code construction for the canonical PIR system turns out to be
rather elegant, and plays an important role for subsequent works. The code
construction to obtain the capacity result in [4] relies on several important
design principles, which are illustrated using the example of $N=K=2$ case in
Fig. 3. This original construction required sub-packetization of each message
into $N^{K}$ parts (alternatively, a message length of $L=N^{K}$ symbols),
followed by invoking the design principles of server/message symmetry and
exploiting side information.

An alternative code construction was provided in [16, 12], which is
illustrated in Fig. 5(a). In this construction, the server symmetry and and
message symmetry are not used on the per retrieval basis, but across all the
retrieval patterns. The random key $F\in\\{0,1\\}$ is invoked with probability
$1/2$ each, and thus the expected retrieval download cost is still the same
$3/2$. The advantage of this alternative code construction is that it can be
shown to have the minimum message length ($L=1$ in this example and $L=N-1$ in
general), comparing to the exponential growth of message length for the code
given in [4]. A similar code construction was discovered by [17] for special
case of $N=2$, and was later extended to the case of more general number of
databases [18] as shown in Fig. 5(b). The difference from that in [16, 12] is
additional layer of symmetrization enforced across the databases. It is clear
that both code constructions have the same download cost, however, the upload
cost of the former is lower ($\log 2$ vs $\log 4$). The symmetry structure in
the canonical PIR setting is quite sophisticated and plays an important role
in constructing efficient code design. The overall symmetry is induced by the
database symmetry, the message symmetry, and the (retrieval) variety symmetry;
see [12] for a detailed discussion.

###  II-B Relation to Computer Science Theoretic PIR

For the canonical PIR system, the computer science theoretic description of
the coding operations is exactly equivalent to the information-theoretic
version we just provided. The main difference between them is in terms of the
performance measure, i.e., regarding the definition of $C_{0}$ and
$C_{\epsilon}$. Since in the computer science theoretic setting the messages
are short, usually only one bit each, the upload cost, i.e.,
$\sum_{i=1}^{N}\log|\mathcal{Q}_{n}|$, plays an important role in the overall
communication cost, and thus the total communication cost must consist of both
components. In contrast, in the information-theoretic setting, since the
message size is allowed to be very large, the download cost dominates and the
upload cost can be essentially ignored, and only the normalized cost is
meaningful, whose inverse is the PIR rate.

Since in the computer science theoretic setting, the message length is fixed
and not allowed to grow to infinity, it is not meaningful to consider the
ratio between the message length and the communication cost. In contrast, in
the information-theoretic setting, this ratio between the message length and
the download cost is the key metric to consider.

It is in fact rather difficult to fully characterize the sum of the upload
cost and the download cost (for any fixed message length), and thus the
optimal scaling laws are usually sought after in the computer science
theoretic setting. In contrast, in the information-theoretic setting, the
ratio between the message length and the download cost leads to the concept of
capacity, and the problem in fact becomes much more tractable. Instead of the
scaling law, the capacity of the PIR system can be fully identified.

###  II-C Extended PIR Systems

The canonical PIR system given in the previous sub-section can be viewed as
consisting of four key components: a single-round query-answer protocol, a set
of independent messages of the same length, an absolute privacy requirement,
and also inherently a star-shape communication network; see Fig. 4. The last
item regarding the communication network may require some elaboration, since
it is usually not explicitly introduced: the user communicates to each server
through a dedicated link, and each server answers through a dedicated link,
and as a consequence, the communication costs are measured in a
straightforward manner on each link.

Any of these components can be generalized:

  1. 1.

The query-answer protocol structure. The user sends a single round of queries,
and the servers answer in a single round; this protocol can be generalized to
allow multiple rounds.

  2. 2.

The message structure. In more general systems, the messages can be dependent;
in a less obvious variation, the user in fact requests a function of the
messages.

  3. 3.

The privacy (or security) requirement. The user may wish to enforce the
privacy requirements that even certain subsets of the servers collude, they
still will not be able to infer any knowledge on the request. The server may
place security constraint that the authors cannot learn about other messages
than the one being requested.

  4. 4.

The communication network structure. This communication models can be
generalized in various way, for example, to allow a more complex communication
network, or using additional communication module, such as caches, to
facilitate the communication. In such general settings, the communication
costs are measured in rather different manners.

In the next subsections, we survey various generalizations of the canonical
PIR problem.

####  II-C1 Multi-round and Multi-message PIR Systems

Sun and Jafar [19] considered the extended PIR system where the user and the
servers are allowed multiple rounds of queries and answers. It was shown that
the capacity of multiround PIR is in fact the same as single round PIR, when
there is no constraint placed on the storage cost. This equality continues to
hold even when $T$-colluding is allowed. However, when the storage is more
constrained, this equality would indeed break. Yao et al. [20] considered
using multiround communication in the settings with Byzantine databases, and
showed that multiround communication is also beneficial in this setting. In
multi-message PIR, the user wishes to download multiple messages privately.
The question that arises is whether downloading multiple messages one-by-one
sequentially is optimum. [21] shows that downloading multiple messages jointly
is more efficient and beats the sequential use of single-message PIR. [21]
determines the PIR capacity when the number of desired messages is at least
half of the total number of messages, while the multi-message PIR capacity in
other cases remains open.

####  II-C2 Cache or Side Information Aided PIR

Cache aided private information retrieval (PIR) (e.g., [22, 23, 24]) and side
information aided PIR (e.g., [25, 26, 27, 28, 29, 30, 31, 32, 33, 34]) are
both interesting extensions of the original information-theoretic PIR problem
[4] because they both lead to reduction in download costs due to the fact
that, under both settings, the user possesses cache or side information,
respectively. The PIR capacity and the corresponding PIR schemes with
cache/side-information vary, depending on a) if the databases are aware or
unaware of the side-information at the user; b) if the user wishes to only
keep the message index private or both the message index and side-information
private from the databases; and c) the type of side-information available at
the user (e.g., subset of messages or fraction of some/all messages).
Recently, the role of side information is investigated in the context of
symmetric PIR (SPIR) where the side information is a subset of shared database
common randomness; this work showed that with appropriate amount of user-side
side information the capacity of SPIR can be increased to the capacity PIR,
and single-database SPIR can be made possible [35].

####  II-C3 PIR from Databases with Limited Storage

The assumption of fully replicated databases (all $N$ databases storing all
$K$ messages) can be unrealistic in practice. However, the amount of
redundancy across the databases has an impact on the capacity of PIR.
Specifically, on one extreme for replicated databases, the capacity is the
highest, whereas on the other extreme, if there is no redundant storage across
databases, then the only feasible strategy is to download all $K$ messages.
There have been several recent works which have explored the trade-off between
the capacity and storage for PIR. The case when each message is encoded by a
maximum distance separable (MDS) code and stored across the databases,
referred to as the MDS-PIR code, was studied in [36, 37] and the capacity was
settled by Banawan and Ulukus [36]; also see recent results on MDS-PIR with
minimum message size [38]. The problem of MDS-PIR with colluding databases
turns out to be more challenging and the capacity remains unknown for general
parameters; see [39, 40]. Several other variants have been studied including
PIR from databases storing data using an arbitrary linear code [41, 42],
impact on capacity versus storage when using arbitrary (possibly, non-linear
codes) [43, 44, 45, 46, 47], when databases only store fraction of uncoded
messages [48, 49, 50], and when data is not perfectly replicated across the
databases, but rather partially replicated according to graph based structures
[51, 52, 53, 54].

####  II-C4 PIR Under Additional Abilities and Constraints for the Databases

The original setting in [4] considers privacy against individual databases. In
practice, a subset of databases may have the ability to collude; this may
happen, for instance, if the databases belong to the same entity. [55]
considers the case where up to $T$ out of $N$ databases may collude, and finds
the PIR capacity as a function of $T$. Further, [56] considers the case where
in addition to the $T$ colluding databases, up to $B$ databases may exhibit
Byzantine behavior, meaning that they can return arbitrarily random or
incorrect answers to the queries, and finds the PIR capacity as a function of
$T$ and $B$. In addition, databases may require _database privacy_. This means
that the user does not learn anything further than the message it wished to
download. The resulting setting is coined as symmetric PIR (SPIR) to emphasize
the symmetry of privacy requirements of the user and the databases. The
capacity of SPIR is found in [57]. The SPIR capacity is smaller than the PIR
capacity, as SPIR is a more constrained problem than PIR. SPIR achievable
scheme is similar to the schemes in [1, 9] but it requires a shared common
randomness among the databases. Recent paper [35] explores making some of that
common randomness available (randomly) to the user to increase SPIR capacity.
Further, SPIR proves to be an important privacy primitive that is a building
block in many problems that involve symmetric privacy requirements among
participating parties, such as in private set intersection [58, 59].

Databases may be subject to a set of practical limitations due to the way that
the databases are accessed or the way they need to return their answers. For
instance, if the databases need to return their answers via noisy and/or
multiple-access wireless channels, then the PIR schemes should be designed
together with channel coding techniques to deal with the uncertainty in the
channels as in [60]. In another example setting, if the rate at which the user
can download information from the databases is different for each database,
then the user access to the databases and the PIR schemes across the databases
may need to be asymmetric. This may happen, for instance, if the databases
have different distances to the user (with a more distant database having a
smaller bit-rate) or if they have different channel qualities (some channels
from the databases being in deep fades). In this case, asymmetric access
conditions need to be taken into consideration [61]. An interesting
observation in [61] is that if the asymmetry is mild, the full unconstrained
PIR capacity may still be maintained. Another set of practical constraints
arise if the database-to-user channels are being eavesdropped by an external
entity. This gives rise to a problem formulation at the intersection of
information-theoretic privacy and information-theoretic security [62, 63, 64,
65]. Yet another practical constraint is that the messages stored at the
databases do not have to be of equal length, and their apriori probabilities
of retrieval (popularities) do not have to be the same. These give rise to
message semantics that need to be taken into account during a PIR code design
[66]. An interesting observation in [66] is that if longer messages have
higher popularities then the semantic PIR capacity may be larger than
classical PIR capacity.

####  II-C5 Relaxed Privacy Notions

Perfect information-theoretic privacy requirements (either for the user as in
PIR or for both the user and the databases as in SPIR) usually come at the
expense of high download cost and do not allow tuning the PIR efficiency and
privacy according to the application requirements. In applications which may
require frequently retrieving messages, trading user or database privacy for
communication efficiency could be desirable. Ideally, one would select a
desired leakage level and then design a leakage-constrained retrieval scheme
that guarantees such privacy while maximizing the download efficiency. Asonov
et al. introduced the concept of repudiative information retrieval [67]. The
repudiation property is achieved if the probability that the desired message
index was $i$ given the query is non-zero for every index $i$, i.e., there is
always some remaining uncertainty at the database about the desired message
index. Recently, Toledo et al. [68] adopted a game-based differential privacy
definition to increase the PIR capacity at the expense of bounded privacy
loss. With the goal of allowing bounded leakage for the information-theoretic
PIR/SPIR formulations (as initiated in [69]), there have been a series of
recent works. In [17], the perfect privacy constraint was relaxed by requiring
that the log likelihood of the posterior distribution for any two message
indices given the query is bounded by $\epsilon$. When $\epsilon=0$, this
recovers perfect privacy, and allows leakage for $\epsilon>0$. Lin et al. [70,
71] relaxed user privacy by allowing bounded mutual information between the
queries and the corresponding requested message index. Unlike [70, 71], which
deal with the average leakage measured by mutual information, the model
studied in [17] provides stronger privacy guarantees. Zhou et al. [72]
measured the leakage using the maximal leakage metric and argued this leakage
measure is more applicable. Guo et al. [73] considered the problem of SPIR
with perfect user privacy and relaxed database privacy. Database privacy was
relaxed by allowing a bounded mutual information (no more than $\delta$)
between the undesired messages, the queries, and the answers received by the
user. Similar to the original work on SPIR in [74], SPIR with relaxed database
privacy in [73] requires sharing common randomness among databases and comes
at the expense of a loss in the PIR capacity. Asymmetric leaky PIR was
explored in [18] where bounded leakage is allowed in both directions.
Recently, the model of latent-variable PIR was introduced and studied, where
instead of requiring privacy for the message index, one may require privacy of
data correlated with the message [75].

Full capacity characterization |
---|---
PIR[4] Multiround[19] Computation[76, 77] |  $C=\Psi(N,K)$ |  Multiround: allows sequential queries Computation: retrieves arbitrary linear combinations of messages |  ✓
TPIR[55] |  $C=\Psi((N-U)/T,K)$ |  $U$ unresponsive servers |  ✓
PIR[78] with  arbitrary collusion pattern |  $C=\Psi(S^{*},K)$ |  Arbitrary collusion pattern $P$, $S^{*}=\max_{y}1_{N}^{T}y$, s.t. $B_{P}^{T}y\leq 1_{M},y\geq 0_{N}$ $B_{P}$: incidence matrix of $P$ |  ✓
Cache-aided PIR[79] |  $C=\Psi(N,K)/(1-S/K)$ |  PIR aided by local cache at user of size $S\times$ message size |  ✓
PIR-SI[80, 81] |  $C=\Psi(N,\lceil\frac{K}{M+1}\rceil)$ |  Side Information of $M$ messages at User, Privacy of SI not required |  ✓
PIR-PSI[80, 82, 28] |  $C=\Psi(N/T,K-M)$ |  Side Information of $M$ messages at User, $\theta$ and SI jointly $T$-private |  ✓
SPIR[57, 83] |  $C=(1-\frac{2B+\max(T,E)}{N})$ $\qquad\qquad\cdot\mathbb{I}_{\left(\rho\geq\frac{2B+\max(T,E)}{N-2B-\max(T,E)}\right)}$ |  Symmetric security,  $B$-Byzantine servers, $E$-Eavesdroppers, Common randomness $\rho$ shared among servers |  ✓
Q-PIR, Q-STPIR[84] |  ${C}=\min\left\\{1,\frac{2(N-T)}{N}\right\\}$ |  Quantum PIR,  allows symmetric security, Servers share an entangled state |  ✓
B-TPIR[56] |  $C=\left(1-\frac{2B}{N}\right)\Psi(\frac{T}{N-2B},K)$, $\footnotesize{N>2B+T}$ $C=\frac{1}{(2B+1)K}\mathbb{I}_{(N>2B)}$, $N\leq 2B+T$ |  $B$-Byzantine servers |  ✓
MDS-PIR[36] |  $C=\Psi(N/K_{c},K)$ |  $(N,K_{c})$ MDS Coded Storage
PIR with limited  storage [48, 49, 50] |  $C=\Psi(\mu N,K)$, $\mu=\frac{t}{N},t\in[N]$ |  Each server stores no more than $\mu$ fraction of  database; heterogeneous sizes $\mu_{i}$; decentralized. |

Partial capacity characterization |
---|---
Multimessage PIR[21] |  ${C}=\Psi(N,\frac{K}{M})$ if $K/M\in\mathbb{N}$ $C=\frac{MN}{MN+K-M}$ if $M\geq\frac{K}{2}$ |  Multi-message Retrieval Retrieves $M$ out of $K$ messages |  ✓
MDS-TPIR[40, 39] |  ${C}_{l}=1-(K_{c}+T-1)/N$ $C=\frac{N^{2}-N}{2N^{2}-3N+T}$ if $K_{c}=N-1$ |  $(N,K_{c})$ MDS Coded Storage
XS-TPIR[85] |  ${C}_{l}=\left(1-\frac{X+T}{N}\right)^{+}=C_{\infty}$ ${C}^{u}=\left(1-\frac{X}{N}\right)\Psi(\frac{N-X}{T},K)$ $=C$ if $N\leq X+T$ or $(N,X,T)=(3,1,1)$ |  $X$-secure storage  |
U-B-XS-MDS-TPIR[86, 87] |  ${C}_{l}=\left(1-\frac{K_{c}+X+T+2B-1}{N-U}\right)$ $=C_{\infty}$ if $K_{c}=1,X=0$ |  $X$-secure, $(N,K_{c}+X)$ MDS coded storage, $U$-unresponsive, $B$-Byzantine servers  |

Figure 6: A sampling of capacity results for various forms of PIR, where $N$
is the number of servers, $K$ is the number of messages, and $T$ is the
privacy parameter with default value being $1$. For the rows with a check
mark, the storage on server is simple message replication. $C$ represents
capacity, $C_{\infty}$ is the asymptotic capacity for large number of messages
$(K\rightarrow\infty)$, ${C}^{u}$ and ${C}_{l}$ are upper and lower bounds on
$C$, respectively.
$\Psi(A,B)\triangleq(1+1/A+1/A^{2}+\cdots+1/A^{(B-1)})^{-1}$.

###  II-D Connections to Other Security Primitives

PIR holds particular significance as a point of convergence of complementary
perspectives. It is well known that PIR shares intimate connections to
prominent problems in theoretical computer science and cryptography,
communication and information theory, and coding and signal processing. PIR
protocols are often used as essential ingredients of oblivious transfer [88],
instance hiding [89, 90, 91], multiparty computation [92], secret sharing
schemes [93, 94] and locally decodable codes [7]. Through the topics of
locally decodable, recoverable, repairable and correctable codes [95], PIR
connects to distributed data storage repair [96], index coding [97] and the
entire umbrella of network coding [98] in general. PIR schemes are essentially
interference alignment schemes [99] as the downloads comprise a mix of desired
messages with undesired messages (interference). Efficient retrieval requires
the alignment of interference dimensions across the downloads from different
servers while keeping desired signals resolvable. It is not surprising then
that interference alignment has been used implicitly in PIR and index coding
long before its applications in wireless networks [99]. Various equivalence
results have been established between PIR and blind interference alignment
(BIA) [100, 101]; BIA and topological interference management (TIM) [102]; TIM
and index coding [102]; index coding and locally repairable codes [103, 104];
locally repairable and locally decodable codes [95]; and between locally
decodable codes and PIR [7]. Add to this the equivalence between index coding
and network coding [105, 106], storage capacity and index coding [107], index
coding and hat guessing [108], or the application of asymptotic interference
alignment schemes originally developed for wireless interference networks
[109] to distributed storage exact repair [110], and it becomes evident that
discoveries in PIR have the potential for a ripple effect in their impact on a
number of related problems.

The remainder of this article explores in greater depth the topics of secure
distributed computing and private federated learning.

##  III Private Distributed Computing

###  III-A Formulation

We consider a general distributed computing framework, where the goal is to
compute a function $g$ using $N$ distributed workers, while keeping the input
dataset $\boldsymbol{X}$ secure (illustrated in Fig. 7). The $N$ workers are
assigned encrypted versions of the input using $N$ encoding functions
$\boldsymbol{c}\triangleq(c_{1},...,c_{N})$, then each worker computes a
function $f$ over the assigned share, which can be viewed as building blocks
of computing $g$.

Figure 7: An illustration of private computation.

This framework captures many commonly used operations. One example is _block
matrix multiplication_ , where the goal is to compute the product
$A^{\intercal}B$ given two large matrices $A\in\mathbb{F}^{s\times t}$ and
$B\in\mathbb{F}^{s\times r}$. Here the input dataset is $X=(A,B)$, and the
computation task is $g(A,B)=A^{\intercal}B$. Given some partitioning
parameters $p$, $m$, and $n$, the input matrices are partitioned block-wise
into $p$-by-$m$ and $p$-by-$n$ sub-blocks of equal sizes, respectively. Then
each worker is assigned a pair of sub-blocks and computes their product, i.e.,
the function $f$ is the multiplication of two matrices of sizes
$\mathbb{F}^{\frac{t}{m}\times\frac{s}{p}}$ and
$\mathbb{F}^{\frac{s}{p}\times\frac{r}{n}}$. If there are no security
requirements, the final result can be recovered using $N=pmn$ workers, by
having each worker compute a product of certain uncoded submatrices.

Another example is to compute _multivariate polynomials_ on a dataset $X$.
Particularly, given a general polynomial $f$, the input dataset is partitioned
into $K$ subsets $X_{1},\ldots,X_{K}$, and the goal is to compute
$g(\boldsymbol{X})=(f(X_{1}),\ldots,f(X_{K}))$. If each worker can compute a
single evaluation of $f$, then a computing design using $N=K$ workers can be
obtained by assigning each worker a disjoint uncoded subset of the input.

However, in secure computing, we aim to carry out the computation with an
additional requirement that the entire input dataset is information-
theoretically secure from the workers, even if up to a certain number of them
can collude. In particular, a set of encoding functions
$\boldsymbol{c}\triangleq(c_{1},\ldots,c_{N})$ is $T$-secure, if
$I(\\{c_{i}(X)\\}_{i\in\mathcal{T}};X)=0$ for any subset $\mathcal{T}$ with a
size of at most $T$, where $X$ is generated uniformly at random.

Tradeoffs in secure distributed computing: The goal is to design the encoding
functions to achieve a tradeoff between the resources/constraints while
ensuring the reliable recovery of the desired computation. Specifically, the
resources could correspond to the number of available workers, storage and
computation performed per worker. In addition to $T$-security, one may also be
interested in communication efficient designs to account for bandwidth
constraints (between master node and the workers). In the past few years,
there have been significant progress in using ideas from coding/information
theory to devise new schemes, and ultimately towards understanding these
fundamental tradeoffs. As an example, a large body of work [111, 112, 113,
114, 115] have focused on the problem of distributed computing in the presence
of stragglers. Here, since the overall latency of computation can be limited
by the slowest workers, the goal is to design schemes which minimize the
number of workers required to carry out the computation, while satisfying the
security requirement. More rigorously, let $\mathcal{C}_{T}$ denotes the set
of allowable222The set $\mathcal{C}_{T}$ also captures practical constraints
such as encoding complexities. encoding function designs that are $T$-secure.
Then, in a secure coded computing problem, given fixed parameters $f,g,$ and
$\mathcal{C}_{T}$, one aim could be to find computing schemes
$\boldsymbol{c}\in\mathcal{C}_{T}$ that use as small number of workers $N$ as
possible. Alternatively, when the total number of workers $N$ is fixed, one
may be interested in the design of $T$-secure schemes with minimum download
communication overhead. The capacity of secure distributed computation,
analogous to that of PIR, can then be defined as the supremum of the ratio of
the number of bits of desired information (the desired function,
$g(\mathbf{X})$), to the total number of bits downloaded from the $N$ servers.

###  III-B Schemes for Private Distributed Computing

Information-theoretically secure distributed computing has its origins in the
celebrated work of Ben-Or Goldwasser Micali (BGW protocol) on tasks involving
linear/bilinear computations. Specifically, the master node creates $N$ coded
shares with $T$-secure guarantees (using Shamir’s secret sharing scheme) which
are subsequently sent to the workers. The workers subsequently compute the
function on the coded shares. In a recent work [116], staircase codes,
presented originally for a PIR problem [117], were combined with the idea of
secret sharing to minimize the overall latency for secure distributed matrix
multiplication.

Lagrange coded computing (LCC) [118] has been proposed to provide a unified
solution for computing general multivariate polynomials. In comparison to the
classical BGW (or similar Shamir’s secret sharing based protocols), LCC
reduces the amount of storage, communication and randomness overhead. Given
any fixed parameter $T$, LCC encodes the input variables using the following
Lagrange interpolation polynomial

$\displaystyle
c(x)\triangleq\sum_{j\in[K]}X_{j}\cdot\prod_{k\in[K+T]\setminus\\{j\\}}\frac{x-x_{k}}{x_{j}-x_{k}}+\sum_{j=K+1}^{K+T}Z_{j}\cdot\prod_{k\in[K+T]\setminus\\{j\\}}\frac{x-x_{k}}{x_{j}-x_{k}},$

where $x_{1},\ldots,x_{K+T}$ are some arbitrary distinct elements from the
base field $\mathbb{F}$, and $Z_{i}$’s are some random cryptographic keys
generated uniformly333We assume that $\mathbb{F}$ is finite so that the
uniform distribution is well defined.  at random on the domain of $X_{i}$’s.
Each worker $i$ selects a distinct variable $y_{i}$ from the base field that
is not from $\\{x_{1},\ldots,x_{K}\\}$, and obtains $\tilde{X}_{i}\triangleq
c(y_{i})$ as the coded variable. LCC is $T$-secure, because the coded
variables sent to any subset of $T$ workers are padded by an invertible linear
transformation of $T$ random keys, which are jointly uniformly random.

After each worker $i$ applies function $f$ over the coded inputs, they
essentially evaluate the composed polynomial $f(c)$ at point $y_{i}$. On the
other hand, the evaluations of the same polynomial at $x_{1},\ldots,x_{K}$ are
exactly the $K$ needed final results. Hence, by polynomial interpolation, the
decoder can recover all final results by recovering $f(c)$, by receiving
results from any subset of workers with a size greater than the degree of
$f(c)$. More precisely, let $\textup{deg}f$ denote the total degree of
polynomial $f$, the degree of the composed polynomial equals
$(K-1)\textup{deg}f$. Thus, LCC computes any multivariate polynomial with at
most $N=(K-1)\textup{deg}f+1$ workers.

Secure coded computation has also been studied for different computation tasks
and settings. A majority of works are on matrix multiplication [119, 120, 121,
122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134], and it has
been shown in [135, 134] that for block-partition-based designs, the optimum
number of workers to enable secure computation can be within a constant factor
of a fundamental quantity called the bilinear complexity [136]. Private
gradient computation was studied in [137] and it was shown that the optimal
coding design is encoding the input variables using harmonic sequences. [138,
139] considered a setting where the workers send compressed versions of their
computing results to tradeoff the download communication cost and the required
number of workers.

LCC has also been widely leveraged to enable privacy-preserving machine
learning [140, 141]. In particular, authors in [140] have considered a
scenario in which a data-owner (e.g., a hospital) wishes to train a logistic
regression model by offloading the large volume of data (e.g., healthcare
records) and computationally-intensive training tasks (e.g., gradient
computations) to $N$ machines over a cloud platform, while ensuring that any
collusions between $T$ out of $N$ workers do not leak information about the
dataset. In this setting, CodedPrivateML [140] has been proposed, which
leverages LCC, to provide three salient features:

  1. 1.

it provides strong information-theoretic privacy guarantees for both the
training dataset and model parameters.

  2. 2.

it enables fast training by distributing the training computation load
effectively across several workers.

  3. 3.

it secret shares the dataset and model parameters using coding and information
theory principles, which significantly reduces the training time.

LCC has also been leveraged to break a fundamental “quadratic barrier” for
secure model aggregation in federated learning [142]. We defer the discussion
on this topic to the next section.

Within the scope of this article, the connection between PIR, secure
distributed computing, and private federated learning is exemplified by the
idea of cross-subspace alignment (CSA) which extends to all three domains. CSA
codes originated in [85] as a solution to XS-TPIR, i.e., the problem of
$T$-private information retrieval from $N$ servers that store $K$ messages in
an $X$-secure fashion. CSA codes then found applications in private secure
coded computation [143, 144, 87], and in particular secure distributed matrix
multiplication (SDMM) [145]. CSA codes were first applied to SDMM by Kakar et
al. in [146], and subsequently applied to secure distributed _batch_ matrix
multiplication (SDBMM) by Jia et al. in [147]. These works produced sharp
capacity444Analogous to PIR, the capacity of SDBMM is defined as the supremum
of the ratio of the number of bits of desired information (the desired matrix
products), to the total number of bits downloaded from the $N$ servers.
characterizations for various cases. For example, in [147] the capacity for
$X$-secure distributed computation by $N$ servers of a batch of outer products
of two vectors is shown to be $(1-X/N)^{+}$, the capacity for computing the
inner product of two length-$K$ vectors is $\frac{1}{K}(1-\frac{X}{N})^{+}$
when $N\leq 2X$, and for long vectors $(K\rightarrow\infty)$ the capacity of
computing inner products is shown to be $(1-2X/N)^{+}$. While LCC [118] codes
and CSA codes originated in seemingly unrelated contexts of distributed secure
computing and secure PIR, there are interesting connections between them. For
example, in a special case of secure multiparty/distributed batch matrix
multiplications, CSA codes yield LCC codes as a special case[148, 149]. The
generalization inherent in CSA codes is beneficial primarily in download-
limited settings, where CSA codes are able to strictly outperform LCC codes.
However, it is worth mentioning that to achieve order-optimal performances,
entangled polynomial codes [135, 134] should be applied, which enables coding
over bilinear-complexity-based algebraic structures, and achieving order-wise
improvements. Finally, in the domain of federated learning, CSA codes were
applied in [150] to find a solution to the problem of $X$-secure $T$-private
federated submodel learning. Fundamentally, this is a problem of privately
reading from and privately writing to a database comprising $K$ files
(messages/submodels) that are stored across $N$ distributed servers in an
$X$-secure fashion. The CSA read-write scheme of [150] is able to fully update
the storage at all $N$ servers after each write operation even if some of the
servers (up to a specified threshold value) are inaccessible, and achieves a
synergistic gain from the joint design of private-read and private-write
operations. Intuitively, the connection between these problems arises because
the operation required at each server for many (but not all) PIR (and private
write) schemes can be interpreted as a _matrix multiplication_ between a
threshold-$T$ secret-shared query vector/matrix (polynomial encoded for
$T$-privacy) and a threshold-$X$ secret-shared data vector/matrix (polynomial
encoded for $X$-security), which produces various desired and undesired
products. CSA codes are characterized by a Cauchy-Vandermonde structure that
facilitates interference alignment of undesired products along the Vandermonde
terms, while the desired products remain separable along the Cauchy terms.
This alignment structure allows efficient downloads by reducing interference
dimensions. Therefore, to the extent that a multiplication of polynomial
encoded matrices is involved, and download efficiency is of concern, the same
Cauchy-Vandermonde alignment structure facilitated by CSA codes turns out to
be useful across these problems. It is also noteworthy that applications of
CSA codes generalize naturally beyond matrix products, to tensor products, as
seen in Double Blind Private Information Retrieval ($M$-way blind PIR in
general) [151].

##  IV Private Federated Learning

###  IV-A Threat Models for Private Federated Learning

A typical federated learning (FL) system [152, 153] comprises users/workers, a
server/curator, and an analyst, where users are connected to the server, and
the server is subsequently connected to the analyst. Users wish to jointly
train a machine learning model using their local datasets with the help of the
server. The training is typically done using iterative algorithms such as
gradient descent and its variants, where users receive the global learning
model that needs to be trained from the server and compute gradients using
their local datasets, and subsequently send the gradients or the updated local
models back to the server for aggregation. The analyst may request for the
model at any given time. Depending on who the malicious party is, its
capability and intent, we can have several different threat models. For
example, the analyst can be assumed to be honest but curious who does not
actively attack the trustworthy server or users but tries to learn as much
information about users as possible through the output released to it.
Similarly, the server can also be assumed to be honest but curious. However,
different from the analyst, the server can also be an active attacker, who
alters the training process and/or baits users into revealing their
information. Another possible threat model is when a subset of users is
malicious, who try to tamper with the training process by sending altered
gradients or model updates. We refer the reader to a recent excellent
comprehensive survey on the subject of FL [153], which gives an in-depth
account of recent progress on various FL modalities, as well as challenges in
achieving efficiency, privacy, fairness, and system level implementation.

In this survey, we focus on the models where (a) the server is trustworthy and
the analyst is honest but curious; and (b) both the server and the analyst are
honest but curious. One may think that no information can be learned by the
curious party due to the fact that the local data never leave the users,
therefore, the local data is private. However, it has been shown that even
gradients or updated models can be used to recover the data used during
training for feed-forward neural networks [154, 155, 156] and convolutional
neural network [157, 158]. This type of attack is known as gradient/model
inversion attack.

Figure 8: Conventional federated learning system, where $\mathbf{w}_{t}$
denotes the model parameters at iteration $t$, and
$\mathbf{g}_{k}(\mathbf{w}_{t})$ denotes the gradient computed using
$\mathbf{w}_{t}$ by user $k$. After training, the model is released to an
analyst.

###  IV-B Differential Private Federated Learning

In private distributed computing, where the entire data is available at a
central location (user), as discussed in the previous section, it is indeed
possible to achieve perfect privacy (in an information-theoretic sense) when
performing computations over distributed cluster of nodes. The federated
learning paradigm, however, has several key distinctions as we briefly
highlight next: since the data is already locally spread at the users (and is
required to be kept private), perfect privacy against a single server can only
be achieved by completely sacrificing utility (in terms of the model learned
by perfectly private interactions with the user). Thus, in conventional
single-server FL, one seeks to relax the privacy requirements from perfect
privacy to allowing some leakage in a graceful manner. Indeed, as is shown in
[150], perfect privacy can be feasible with multiple servers, and when one may
be interested in training multiple sub-models at the servers, or when some
collaboration between the users is allowed (also see the discussion in Section
IV-C). For the remainder of this section, we will exclusively focus on the
single-server FL setting when the users cannot collaborate.

Differential privacy (DP) [159] is one of the most widely used privacy notions
and has been shown to be effective to mitigate not only inversion attacks, but
also differential attacks. The goal is to protect the private data by
perturbing the output before it is released to untrustworthy parties.
Depending on who performs the perturbation or who we wish to protect against,
differential privacy can be further categorized into local DP and central DP.
For a FL system with $K$ users, the local and central DP are formally defined
as follows.

######  Definition 1.

($(\epsilon_{\ell}^{(k)},\delta_{\ell})$-LDP) Let $\mathcal{X}_{k}$ be a set
of all possible data points at user $k$. For user $k$, a randomized mechanism
$\mathcal{M}_{k}:\mathcal{X}_{k}\rightarrow\mathds{R}^{d}$ is
$(\epsilon_{\ell}^{(k)},\delta_{\ell})$-LDP if for any $x,\leavevmode\nobreak\
x^{\prime}\in\mathcal{X}_{k}$, and any measurable subset
$\mathcal{O}_{k}\subseteq\text{Range}(\mathcal{M}_{k})$, we have

$\displaystyle\operatorname{Pr}(\mathcal{M}_{k}(x)\in\mathcal{O}_{k})\leq\exp{(\epsilon_{\ell}^{(k)})}\operatorname{Pr}(\mathcal{M}_{k}(x^{\prime})\in\mathcal{O}_{k})+\delta_{\ell}.$
(4)

The setting when $\delta_{\ell}=0$ is referred as pure
$\epsilon_{\ell}^{(k)}$-LDP.

######  Definition 2.

($(\epsilon_{c},\delta_{c})$-DP) Let
$\mathcal{D}\triangleq\mathcal{X}_{1}\times\mathcal{X}_{2}\times\dots\times\mathcal{X}_{K}$
be the collection of all possible datasets of all $K$ users. A randomized
mechanism $\mathcal{M}:\mathcal{D}\rightarrow\mathds{R}^{d}$ is
$(\epsilon_{c},\delta_{c})$-DP if for any two neighboring datasets
$D,D^{\prime}$ and any measurable subset
$\mathcal{O}\subseteq\text{Range}(\mathcal{M})$, we have

$\displaystyle\operatorname{Pr}(\mathcal{M}(D)\in\mathcal{O})$
$\displaystyle\leq\exp{(\epsilon_{c})}\operatorname{Pr}(\mathcal{M}(D^{\prime})\in\mathcal{O})+\delta_{c}.$
(5)

The setting when $\delta_{c}=0$ is referred as pure $\epsilon_{c}$-DP.

We refer $\epsilon_{c}$ ($\epsilon_{\ell}^{(k)}$) and $\delta_{c}$
($\delta_{\ell}$) as privacy parameters. These parameters are closely
associated with a quantity called sensitivity, which is defined as the largest
difference of a function over all available inputs. It is known that central
DP is a weaker guarantee than local DP. Therefore, local DP guarantee implies
central DP guarantee. Both central and local DP are first computed on a per-
iteration basis. Then, the total leakage is computed by summing up the
leakages over all iterations. However, simply summing up the leakages over all
iterations provides bound on the actual total leakage due to the fact that
data is often reused during training. It is known that the more a data point
is used, the more information it leaks. Therefore, to capture this phenomenon,
various of composition theorem/leakage accountant methods are used to tighten
the bound on the total leakage, such as advanced composition theorem, and
moment accountant [160].

| Noise Injection | Sampling | Shuffling | Others
---|---|---|---|---
Central DP | [161, 162] | [163, 164, 160, 165] | [166, 167, 168] | [169]
Local DP | [170, 171] | [172, 173] | [166, 174, 175, 176, 177] | [178, 179]
TABLE I: A quick reference of some of the key privacy preserving techniques
for providing central and local DP guarantees in Federated Learning.

  1. 1.

Basic privacy preserving mechanisms: Let us first look at the case where the
server is trustworthy, and the goal is to satisfy a desired central DP level
against the curious analyst. The outputs, e.g., learning model iterates or
gradients, have been shown to leak information about the local datasets.
Therefore, the goal is to perturb the outputs so that it becomes difficult for
the analyst to learn information about the local datasets. Typically, for
works that focus on central DP, the perturbation is done at the server. The
outputs can be perturbed by using random response, adding noise, or using
approximations. For example, in [160], Gaussian noise is added to the gradient
before the model update. However, gradients and model parameters often are
represented with finite precision, which make Gaussian noise injecting
mechanism impractical. Thus, other types of noise injecting mechanisms are
also considered, such as Laplace mechanism, and for discrete values, binomial
mechanism can be used [161]. Noise with custom density can also be used [162].
However, as mentioned earlier, the privacy guarantee degrades when the same
data is used for training repeatedly.

  2. 2.

Privacy amplification via sampling: To remedy this issue, another line of work
focuses on reducing the exposure of the data through user [163, 164] or data
point sampling [160, 165, 172, 173]. In [163], users are sampled i.i.d.
according to some probability, who will then compute and send the gradients to
the server for perturbation and model updates. In [165], exponential mechanism
is studied. In [172], various data sampling schemes, such as Poisson sampling,
sampling with/without replacement, are studied and analyzed. As a result of
sampling, the privacy level is amplified [172], i.e., less noise is needed to
achieve the same privacy level that is achieved by schemes without sampling.
Amplification can also be obtained through shuffling [166], where a trusted
shuffler shuffles the outputs from users before sending it to the server.
Works that consider shuffling as part of the pipeline include [167, 168].
Another way to control leakage is to ensure that the sensitivity is small by
carefully choosing the clipping norm [169].

Figure 9: Federated learning system with a shuffler, who shuffles the
gradients before sending them to the PS. The trained model is subsequently
released to the analyst.

  3. 3.

Private FL over new communication models: The above works rely on assumption
that the server (and the shuffler) is trustworthy. This assumption may not be
practical in certain scenarios. To remove this assumption, local DP was
proposed and studied, where each user is responsible for protecting their own
data. Similar to central DP, one can ask users to directly perturb the
information they want to send, e.g., in [170]. In addition to adding noise,
one can also perturb the information by using approximation. In [178], the
approximation is obtained by flipping a random bit in the input string of each
user. In [179], a random vector that is roughly in the same direction as the
original gradient is sampled and used as an approximation by each user.
However, it has been shown that techniques that let users perturb information
directly to achieve LDP may suffer greatly in terms of utility, i.e.,
accuracy. In order to satisfy LDP and provide reasonable utility, we can again
use the idea of privacy amplification using sampling and/or shuffling [166,
174, 175, 176, 177]. Since information is perturbed at the user, honest but
curious shuffler would not compromise the local DP. Intuitively, both sampling
and shuffling are able to further confuse the curious party without injecting
more noise. Therefore, one is able to inject less noise to maintain utility,
and still achieve the desired privacy level via sampling and/or shuffling.
Another line of work focuses on private FL over wireless channels [180, 181,
182, 183, 184, 185]. With superposition property of wireless channel, the
gradients can be naturally aggregated while being transmitted. It has been
shown in [182] and [183] that, by carefully designing the power control
factors, the channel noise can be used as perturbation and provides DP
guarantee. Amplification results are shown in [180], where perturbation added
by users that is aggregated over wireless channel enhances privacy guarantee,
and in [185], the privacy is amplified by aggregated perturbation and the
addition of user sampling in the FL pipeline. However, channel state
information (CSI) is obtained with the help of the server and is crucial in
these works. When the server is untrustworthy, CSI obtained from the server
can be tampered to lurk users to leak information. Therefore, [184] and [185]
study the case when CSI is not available.

  4. 4.

Other privacy notions and connections to DP: There are also works that use
different privacy notions, such as Concentrated DP [186, 187], Renyi DP [188],
Bayesian DP [189], communication-constrained DP [177] and information-
theoretic privacy [140]. Concentrated DP is a relaxed version of DP, where it
ensures that leakage is centered around the expected privacy level
$\epsilon_{c}$, and is subgaussian. The probability that leakage exceeds
$\epsilon_{c}$ by a small amount is bounded. Unlike the standard DP, where the
expected leakage is not bounded and could potentially go to infinity with
probability $\delta_{c}$, leakage of concentrated DP does not go to infinity.
Renyi DP is another relaxation of the standard DP that is based on the concept
of Renyi divergence. Renyi DP can be translated to standard DP and it was
shown to have better composition result in [188]. Bayesian DP is essentially
standard DP, however, the data distribution is taken into account when
quantifying privacy parameters. While one can show connection between DP and
information-theoretic privacy, the approaches that are used to secure data are
completely different. In [140], data is kept private by using error control
codes and the idea of secret sharing. The data is considered private when the
mutual information of the original data and encoded data is zero. Other works
such as [190] studies how to allocate the amount of noise added to the data by
each user in a decentralized setting (without the presence of a server) so
that the collective noise does not reduce the utility.

###  IV-C Secure Model Aggregation in Federated Learning

While data is kept at the user-side in FL, a user’s model still carries a
significant amount of information about the local dataset of this user.
Specifically, as shown recently, the private training data can be
reconstructed from the local models through inference or inversion attacks
(see e.g., [191, 192, 193, 194]). To prevent such information leakage, secure
aggregation protocols are proposed (e.g., [195, 142, 196, 197, 198]) to
protect the privacy of individual local models, both from the server and other
users, while still allowing the server to learn the aggregate model of the
users. More specifically, secure aggregation protocols ensure that, at any
given round, the server can only learn the aggregate model of the users, and
beyond that no further information is revealed about the individual local
model of a particular user. The key idea of the secure aggregation protocols
is that the users mask their models before sending them to the server. These
masks then cancel out when the server aggregates the masked models, which
allows the server to learn the aggregate of the local models without revealing
the individual models.

In the secure aggregation protocol of [195], known as SecAgg, pairwise secret
keys are generated between each pair of users. For handling user dropouts, the
pairwise keys in [195] are secret shared among all users, and can be
reconstructed by the server in case of dropouts. This protocol tolerates any
$D$ dropped users and ensures privacy guarantee against up to $T$ colluding
users, provided that $T+D<N$, where $N$ is the number of users. The
communication cost of constructing these masks, however, scales as $O(N^{2})$,
which limits the scalability of this approach. Several works have considered
designing communication-efficient secure aggregation protocol [142, 196, 197,
199, 198]. SecAgg+ [198] improves upon SecAgg [195] by limiting the secret
sharing according to a sparse random graph instead of the complete graph
considered in SecAgg [195]. TurboAgg [142] overcomes the quadratic aggregation
overhead of [195], achieving a secure aggregation overhead of $O(N\log N)$,
while simultaneously tolerating up to a user dropout rate of $50\%$ and
providing privacy against up to $N/2$ colluding users with high probability.
The key idea of Turbo-Aggregate that enables communication-efficient
aggregation is that it employs a multi-group circular strategy in which the
users are partitioned into groups. The dropout and the privacy guarantees of
TurboAgg, however, are not worst-case guarantees and it requires $\log N$
rounds. FastSecAgg [196] is a $3$-round secure aggregation interactive
communication-efficient protocol that is based on the Fast Fourier Transform
multi-secret sharing, but it provides lower dropout and privacy guarantees
compared to SecAgg [195]. While all of aforementioned works in secure
aggregation provide cryptographic security, the secure aggregation protocol
[197] provides information-theoretic security. In addition, unlike all
previous protocols that depend on the pairwise random-seed reconstruction of
the dropped users, this protocol departs from the previous protocols by
employing instead one-shot aggregate-mask reconstruction of the surviving
users. This feature can reduce the aggregation complexity significantly.
However, this protocol relies on a trusted-third party to distribute the masks
over the users. While all of the aforementioned works do not consider the
bandwidth heterogeneity among the different users in secure aggregation, an
adaptive secure aggregation protocol has been proposed in [199] which
quantizes the model of each user according to the available bandwidth to
improve the training accuracy.

While secure aggregation seeks to resolve the issue of preserving user data
privacy by masking the individual model updates, the learning protocol can be
adversarially affected by Byzantine users that may aim to break or perturb the
learning to their benefit [200, 201, 202, 203, 204]. As the local models are
protected by random masks, the server cannot observe the individual user
updates in the clear, which prevents the server from utilizing outlier
detection protocols to protect the model against Byzantine manipulations. This
problem has been recently addressed in [201], for the I.I.D. setting, where
the first single-server Byzantine-resilient secure aggregation protocol for
secure federated learning known as BREA has been developed. BREA is based on
distance based adversarial detection and leverages quantization and verifiable
secret sharing to provide robustness against malicious users, while preserving
the privacy of the individual user models.

All works on secure aggregation only guarantee the privacy of the individual
users over a single aggregation round [195, 142, 196, 197, 198]. While the
privacy of the users is protected in each single round, the server can
reconstruct an individual model from the aggregated models over multiple
rounds of aggregation. Specifically, as a result of the client sampling
strategy and the users dropouts, the server may be able to recover an
individual model by exploiting the history of the aggregate models [205, 206].
This problem was studied for the first time in [206] which developed a client
selection strategy known as Multi-RoundSecAgg that ensures the privacy of the
individual users over all aggregation rounds while taking into account other
important factors such as the aggregation fairness among the users and average
number of users participating at each round (average aggregation cardinality)
which control the convergence rate.

##  V Discussion: Challenges and Open Problems

In this article, we have surveyed the privacy issues in information retrieval,
distributed computation, and distributed (federated) learning. We conclude
this article with the following incomplete list of remaining challenges and
open problems in these areas.

_Challenges and open problems in private information retrieval:_

  * •

Coded colluding databases: The PIR problem is completely solved when the
database content is coded for the case when the databases do not collude, and
is also completely solved when the databases collude for the case when the
database content is replicated (uncoded). However, the problem is open when
database content is coded, potentially secured and the databases may collude.
Remarkably, even the asymptotic capacity (for large number of messages)
remains open. While the lower bound for U-B-XS-MDS-TPIR in Table II-C5 is
conjectured to be aymptotically optimal, the asymptotic capacity $C_{\infty}$
remains unknown in almost all cases.

  * •

Non-replicated databases: The basic form of PIR assumes that the databases
contain exactly the same set of files. In reality, the databases will have
some overlap in content and will also have distinct items. When the databases
have arbitrary contents, the PIR capacity problem is open, with a few notable
exceptions[51, 52, 53, 54]. The challenge here is to be able exploit the
replication to reduce the download cost, while at the same time deal with non-
replication as efficiently as possible.

  * •

Upload cost and message size: In the capacity formulation, the upload cost is
largely ignored. However, when the message sizes are not very large, the
consideration on the upload cost becomes important. The problem then becomes
how to construct codes for small message sizes to achieve a smaller upload
cost. In general, PIR schemes should be designed to minimize a combined
measure of upload and download costs.

  * •

Weakly private (leaky) information retrieval: In some practical applications
of PIR, it may not be absolutely necessary to require perfect privacy, and a
small leakage may be tolerable. In this setting, two questions stand out: What
are good metric(s) to measure the leakage, and how to characterize the
capacity as a function of these metrics.

  * •

More complex message structure: The messages are usually required to be
independent (and of the same length). What is the optimal coding strategy when
the messages are dependent, either as overlapping parts, or are dependent
following a general probability law?

  * •

Privacy, stragglers and timeliness of retrieval: While PIR focuses mainly only
on the privacy of downloaded information, it assumes that the servers are
ideal, which respond to queries immediately and with no delays. Robust PIR
problem considers the case of servers being completely unresponsive [55, 117].
However, most servers respond eventually, albeit slowly in many cases.
Therefore, there is a need to design systems where information may be
downloaded privately but also in a timely manner. An initial consideration of
this issue is presented in a recent paper in [207], but the problem remains
largely open.

_Challenges and open problems in private distributed computing:_

  * •

Optimal coding for block matrix multiplication: In a standard coded computing
setup, we aim to find coding designs to minimize the recovery threshold [208]
(or the number of workers when no straggler is present) given fixed
constraints on computation, security, and privacy. While the optimal recovery
thresholds have been characterized within a factor of $2$ for block matrix
multiplication [135, 134], its exact characterization is not known except for
some boundary cases. In particular, a remaining interesting open problem is to
show whether the factor-of-$2$ penalty in the state-of-the-art upper bound is
necessary when all partition parameters are large.

  * •

Analog coded computing: Most works in coded computing such as [208, 118, 134,
209, 135] rely on quantizing the data into finite fields and then leveraging
coding-theoretic techniques to mitigate stragglers and Byzantine workers, and
to provide data privacy. This approach, however, degrades the accuracy of the
computations [210, 211]. In fact, this is a limitation of many other problems
such as verifiable computing and machine learning [212, 213]. Recently,
several works have extended LCC to the analog domain to address these
challenges [214, 215, 210, 211], but they either focus only on straggler-
mitigation [215], privacy [210, 211] or Byzantine-robustness [214]. An
interesting open problem is to design a framework that jointly tackles these
three challenges in the analog domain.

_Challenges and open problems in private federated learning:_

  * •

Secure and Byzantine-robust aggregation in federated learning: While BREA
[201] has considered secure aggregation and mitigating Byzantine users
jointly, it has only focused on the i.i.d. setting. Extending BREA to the
non-i.i.d. setting is an interesting future direction. The main challenge in
this direction is to determine whether the updates that may seem deviating are
due to the users having non-i.i.d. data or because of Byzantine users sending
erroneous updates.

  * •

Secure aggregation and multi-round secure aggregation: There are many open
problems related to the multi-round secure aggregation problem introduced in
[206]. While the secure aggregation protocols are believed to protect the
privacy the of the individual users, it is not clear whether such protocols
ensure privacy in the information-theoretic sense. Specifically, the secure
aggregation protocols ensure that the server only learns the aggregate model
of the users. However, the aggregate model of the users may still reveal
information about the individual users and characterizing such a leakage is an
important problem. While Multi-RoundSecAgg provides a trade-off between
between the multi-round privacy, the average aggregation cardinality, and the
aggregation fairness, investigating the optimality of Multi-RoundSecAgg
remains an open problem.

## References

  * [1] B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan, “Private information retrieval,” in _Proceedings of the 36th Annual Symposium on Foundations of Computer Science_ , Oct. 1995, pp. 41–50.
  * [2] A. Beimel and Y. Ishai, “Information-theoretic private information retrieval: A unified construction,” in _Automata, Languages and Programming_. Springer, 2001, pp. 912–926.
  * [3] C. Cachin, S. Micali, and M. Stadler, “Computationally private information retrieval with polylogarithmic communication,” in _International Conference on the Theory and Applications of Cryptographic Techniques_. Springer, 1999, pp. 402–414.
  * [4] H. Sun and S. A. Jafar, “The capacity of private information retrieval,” _IEEE Transactions on Information Theory_ , vol. 63, no. 7, pp. 4075–4088, Jul. 2017.
  * [5] W. Gasarch, “A survey on private information retrieval,” in _Bulletin of the EATCS_ , vol. 82, Feb. 2004, pp. 72–107.
  * [6] O. Goldreich, H. Karloff, L. J. Schulman, and L. Trevisan, “Lower bounds for linear locally decodable codes and private information retrieval,” in _Proceedings 17th IEEE Annual Conference on Computational Complexity_ , 2002, pp. 175–183.
  * [7] S. Yekhanin, “Locally decodable codes and private information retrieval schemes,” Ph.D. dissertation, Department of EECS, Massachusetts Institute of Technology, 2007.
  * [8] G. Di Crescenzo, T. Malkin, and R. Ostrovsky, “Single database private information retrieval implies oblivious transfer,” in _International Conference on the Theory and Applications of Cryptographic Techniques_. Springer, 2000, pp. 122–138.
  * [9] N. Shah, K. Rashmi, and K. Ramchandran, “One extra bit of download ensures perfectly private information retrieval,” in _Proceedings of 2014 IEEE International Symposium on Information Theory (ISIT)_ , Jun.-Jul. 2014, pp. 856–860.
  * [10] T. H. Chan, S.-W. Ho, and H. Yamamoto, “Private information retrieval for coded storage,” _Proceedings of 2015 IEEE International Symposium on Information Theory (ISIT)_ , pp. 2842–2846, Jun. 2015.
  * [11] A. Fazeli, A. Vardy, and E. Yaakobi, “Codes for distributed PIR with low storage overhead,” in _2015 Proceedings of IEEE International Symposium on Information Theory (ISIT)_ , Jun. 2015, pp. 2852–2856.
  * [12] C. Tian, H. Sun, and J. Chen, “Capacity-achieving private information retrieval codes with optimal message size and upload cost,” _IEEE Transactions on Information Theory_ , vol. 65, no. 11, pp. 7613–7627, Nov. 2019\.
  * [13] H. Sun and S. A. Jafar, “Optimal download cost of private information retrieval for arbitrary message length,” _IEEE Transactions on Information Forensics and Security_ , vol. 12, no. 12, pp. 2920–2932, Dec. 2017\.
  * [14] Z. Zhang and J. Xu, “The optimal sub-packetization of linear capacity-achieving PIR schemes with colluding servers,” _IEEE Transactions on Information Theory_ , vol. 65, no. 5, pp. 2723–2735, 2018.
  * [15] J. Xu and Z. Zhang, “On sub-packetization and access number of capacity-achieving PIR schemes for MDS coded non-colluding databases,” _SCIENCE CHINA Information Sciences_ , vol. 61, no. 7, pp. 100 306:1––100 306:16, 2018.
  * [16] C. Tian, H. Sun, and J. Chen, “Capacity-achieving private information retrieval codes with optimal message size and upload cost,” in _ICC 2019-2019 IEEE International Conference on Communications (ICC)_. IEEE, 2019, pp. 1–6.
  * [17] I. Samy, R. Tandon, and L. Lazos, “On the capacity of leaky private information retrieval,” in _2019 IEEE International Symposium on Information Theory (ISIT)_ , 2019, pp. 1262–1266.
  * [18] I. Samy, M. Attia, R. Tandon, and L. Lazos, “Asymmetric leaky private information retrieval,” _IEEE Transactions on Information Theory_ , pp. 1–1, 2021.
  * [19] H. Sun and S. A. Jafar, “Multiround private information retrieval: Capacity and storage overhead,” _IEEE Transactions on Information Theory_ , vol. 64, no. 8, pp. 5743–5754, Aug. 2018.
  * [20] X. Yao, N. Liu, and W. Kang, “The capacity of multi-round private information retrieval from byzantine databases,” _arXiv preprint arXiv:1901.06907_ , 2019\.
  * [21] K. Banawan and S. Ulukus, “Multi-message private information retrieval: Capacity results and near-optimal schemes,” _IEEE Trans. on Info. Theory_ , vol. 64, no. 10, pp. 6842–6862, October 2018.
  * [22] R. Tandon, “The capacity of cache aided private information retrieval,” in _2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_. IEEE, 2017, pp. 1078–1082.
  * [23] Y.-P. Wei, K. Banawan, and S. Ulukus, “Fundamental limits of cache-aided private information retrieval with unknown and uncoded prefetching,” _IEEE Trans. on Info. Theory_ , vol. 65, no. 5, pp. 3215–3232, May 2019.
  * [24] ——, “Cache-aided private information retrieval with partially known uncoded prefetching: Fundamental limits,” _IEEE JSAC_ , vol. 36, no. 6, pp. 1126–1139, June 2018.
  * [25] A. Heidarzadeh, B. Garcia, S. Kadhe, S. El Rouayheb, and A. Sprintson, “On the capacity of single-server multi-message private information retrieval with side information,” in _2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_. IEEE, 2018, pp. 180–187.
  * [26] S. Kadhe, B. Garcia, A. Heidarzadeh, S. El Rouayheb, and A. Sprintson, “Private information retrieval with side information,” _IEEE Transactions on Information Theory_ , vol. 66, no. 4, pp. 2032–2043, 2020.
  * [27] Z. Chen, Z. Wang, and S. A. Jafar, “The capacity of ${T}$-private information retrieval with private side information,” _IEEE Transactions on Information Theory_ , vol. 66, no. 8, pp. 4761–4773, 2020.
  * [28] Y.-P. Wei, K. Banawan, and S. Ulukus, “The capacity of private information retrieval with partially known private side information,” _IEEE Trans. on Info. Theory_ , vol. 65, no. 12, pp. 8222–8231, December 2019.
  * [29] Y.-P. Wei and S. Ulukus, “The capacity of private information retrieval with private side information under storage constraints,” _IEEE Trans. on Info. Theory_ , vol. 66, no. 4, pp. 2023–2031, April 2020.
  * [30] S. P. Shariatpanahi, M. J. Siavoshani, and M. A. Maddah-Ali, “Multi-message private information retrieval with private side information,” in _2018 IEEE Information Theory Workshop (ITW)_. IEEE, 2018, pp. 1–5.
  * [31] A. Heidarzadeh, S. Kadhe, S. El Rouayheb, and A. Sprintson, “Single-server multi-message individually-private information retrieval with side information,” in _2019 IEEE International Symposium on Information Theory (ISIT)_ , 2019, pp. 1042–1046.
  * [32] S. Li and M. Gastpar, “Single-server multi-message private information retrieval with side information,” in _2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_. IEEE, 2018, pp. 173–179.
  * [33] ——, “Single-server multi-message private information retrieval with side information: the general cases,” in _2020 IEEE International Symposium on Information Theory_. IEEE, 2020, pp. 1083–1088.
  * [34] A. Heidarzadeh, F. Kazemi, and A. Sprintson, “Capacity of single-server single-message private information retrieval with private coded side information,” in _2019 IEEE International Symposium on Information Theory (ISIT)_ , 2019, pp. 1662–1666.
  * [35] Z. Wang and S. Ulukus, “Symmetric private information retrieval with user-side common randomness,” in _IEEE ISIT_ , July 2021.
  * [36] K. Banawan and S. Ulukus, “The capacity of private information retrieval from coded databases,” _IEEE Trans. on Info. Theory_ , vol. 64, no. 3, pp. 1945–1956, March 2018.
  * [37] R. Tajeddine, O. W. Gnilke, and S. El Rouayheb, “Private information retrieval from MDS coded data in distributed storage systems,” _IEEE Transactions on Information Theory_ , vol. 64, no. 11, pp. 7081 – 7093, 2018.
  * [38] R. Zhou, C. Tian, H. Sun, and T. Liu, “Capacity-achieving private information retrieval codes from MDS-coded databases with minimum message size,” _IEEE Transactions on Information Theory_ , vol. 66, no. 8, pp. 4904–4916, 2020.
  * [39] R. Freij-Hollanti, O. W. Gnilke, C. Hollanti, and D. A. Karpuk, “Private information retrieval from coded databases with colluding servers,” _SIAM Journal on Applied Algebra and Geometry_ , vol. 1, no. 1, pp. 647–664, Nov. 2017.
  * [40] H. Sun and S. A. Jafar, “Private information retrieval from MDS coded data with colluding servers: Settling a conjecture by Freij-Hollanti et al.” _IEEE Transactions on Information Theory_ , vol. 64, no. 2, pp. 1000–1022, Feb. 2018.
  * [41] S. Kumar, H.-Y. Lin, E. Rosnes, and A. G. i Amat, “Achieving maximum distance separable private information retrieval capacity with linear codes,” _IEEE Transactions on Information Theory_ , vol. 65, no. 7, pp. 4243–4273, Jul. 2019.
  * [42] H.-Y. Lin, S. Kumar, E. Rosnes, and A. G. i Amat, “A capacity-achieving PIR protocol for distributed storage using an arbitrary linear code,” _arXiv preprint arXiv:1801.04923_ , Jan. 2018.
  * [43] T. Guo, R. Zhou, and C. Tian, “New results on the storage-retrieval tradeoff in private information retrieval systems,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 2, no. 1, pp. 403–414, 2021.
  * [44] K. Banawan, B. Arasli, and S. Ulukus, “Improved storage for efficient private information retrieval,” in _IEEE ITW_ , August 2019, pp. 1–5.
  * [45] C. Tian, “On the storage cost of private information retrieval,” _IEEE Transactions on Information Theory_ , vol. 66, no. 12, pp. 7539–7549, 2020.
  * [46] C. Tian, H. Sun, and J. Chen, “A shannon-theoretic approach to the storage-retrieval tradeoff in pir systems,” in _2018 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2018, pp. 1904–1908.
  * [47] H. Sun and C. Tian, “Breaking the MDS-PIR capacity barrier via joint storage coding,” _Information_ , vol. 10, no. 9, p. 265, 2019.
  * [48] M. A. Attia, D. Kumar, and R. Tandon, “The capacity of private information retrieval from uncoded storage constrained databases,” _arXiv preprint arXiv:1805.04104_ , 2018.
  * [49] K. Banawan, B. Arasli, Y.-P. Wei, and S. Ulukus, “The capacity of private information retrieval from heterogeneous uncoded caching databases,” _IEEE Trans. on Info. Theory_ , vol. 66, no. 6, pp. 3407–3416, June 2020\.
  * [50] Y.-P. Wei, B. Arasli, K. Banawan, and S. Ulukus, “The capacity of private information retrieval from decentralized uncoded caching databases,” _Information_ , vol. 10, December 2019.
  * [51] N. Raviv, I. Tamo, and E. Yaakobi, “Private information retrieval in graph-based replication systems,” _IEEE Transactions on Information Theory_ , vol. 66, no. 6, pp. 3590–3602, June 2020.
  * [52] K. Banawan and S. Ulukus, “Private information retrieval from non-replicated databases,” in _IEEE ISIT_ , July 2019, pp. 1272–1276.
  * [53] Z. Jia and S. A. Jafar, “On the asymptotic capacity of $x$-secure $t$-private information retrieval with graph based replicated storage,” _IEEE Transactions on Information Theory_ , vol. 66, no. 10, pp. 6280–6296, October 2020.
  * [54] B. Sadeh, Y. Gu, and I. Tamo, “Bounds on the capacity of pir over graphs,” _arXiv preprint arXiv:2105.07704_ , 2021.
  * [55] H. Sun and S. A. Jafar, “The capacity of robust private information retrieval with colluding databases,” _IEEE Transactions on Information Theory_ , vol. 64, no. 4, pp. 2361–2370, 2018.
  * [56] K. Banawan and S. Ulukus, “The capacity of private information retrieval from Byzantine and colluding databases,” _IEEE Trans. on Info. Theory_ , vol. 65, no. 2, pp. 1206–1219, February 2019.
  * [57] H. Sun and S. A. Jafar, “The capacity of symmetric private information retrieval,” _IEEE Transactions on Information Theory_ , 2018.
  * [58] Z. Wang, K. Banawan, and S. Ulukus, “Private set intersection: A multi-message symmetric private information retrieval perspective,” available at arXiv:1912.13501.
  * [59] ——, “Multi-party private set intersection: An information-theoretic approach,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 2, no. 1, pp. 366–379, 2021.
  * [60] K. Banawan and S. Ulukus, “Noisy private information retrieval: On separability of channel coding and information retrieval,” _IEEE Trans. on Info. Theory_ , vol. 65, no. 12, pp. 8232–8249, December 2019.
  * [61] ——, “Asymmetry hurts: Private information retrieval under asymmetric traffic constraints,” _IEEE Trans. on Info. Theory_ , vol. 65, no. 11, pp. 7628–7645, November 2019.
  * [62] Q. Wang and M. Skoglund, “On PIR and symmetric PIR from colluding databases with adversaries and eavesdroppers,” _IEEE Trans. on Info. Theory_ , vol. 65, no. 5, pp. 3183–3197, May 2019.
  * [63] Q. Wang, H. Sun, and M. Skoglund, “The capacity of private information retrieval with eavesdroppers,” _IEEE Trans. on Info. Theory_ , vol. 65, no. 5, pp. 3198–3214, May 2019.
  * [64] K. Banawan and S. Ulukus, “Private information retrieval through wiretap channel II: Privacy meets security,” _IEEE Trans. on Info. Theory_ , vol. 66, no. 7, pp. 4129–4149, July 2020.
  * [65] H. Yang, W. Shin, and J. Lee, “Private information retrieval for secure distributed storage systems,” _IEEE Trans. on Info. Forensics and Security_ , vol. 13, no. 12, pp. 2953–2964, December 2018.
  * [66] S. Vithana, K. Banawan, and S. Ulukus, “Semantic private information retrieval,” available at arXiv:2003.13667.
  * [67] D. Asonov and J.-C. Freytag, “Repudiative information retrieval,” in _Proceedings of the ACM workshop on Privacy in the Electronic Society_ , 2002, pp. 32–40.
  * [68] R. R. Toledo, G. Danezis, and I. Goldberg, “Lower-cost-private information retrieval,” _Proceedings on Privacy Enhancing Technologies_ , no. 4, pp. 184–201, 2016.
  * [69] B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan, “Private information retrieval,” _Journal of the ACM (JACM)_ , vol. 45, no. 6, pp. 965–981, Nov. 1998.
  * [70] H.-Y. Lin, S. Kumar, E. Rosnes, A. G. i Amat, and E. Yaakobi, “Weakly-private information retrieval,” in _Proceedings of the IEEE International Symposium on Information Theory (ISIT)_ , 2019, pp. 1257–1261.
  * [71] ——, “The capacity of single-server weakly-private information retrieval,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 2, no. 1, pp. 415–427, 2021.
  * [72] R. Zhou, T. Guo, and C. Tian, “Weakly private information retrieval under the maximal leakage metric,” in _2020 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2020, pp. 1089–1094.
  * [73] T. Guo, R. Zhou, and C. Tian, “On the information leakage in private information retrieval systems,” _arXiv preprint arXiv:1909.11605_ , 2019\.
  * [74] H. Sun and S. A. Jafar, “The capacity of symmetric private information retrieval,” _IEEE Transactions on Information Theory_ , vol. 65, no. 1, pp. 322–329, 2018.
  * [75] I. Samy, M. A. Attia, R. Tandon, and L. Lazos, “Latent-variable private information retrieval,” in _2020 IEEE International Symposium on Information Theory (ISIT)_ , 2020, pp. 1071–1076.
  * [76] H. Sun and S. A. Jafar, “The capacity of private computation,” _IEEE Transactions on Information Theory_ , vol. 65, no. 6, pp. 3880–3897, 2018.
  * [77] M. Mirmohseni and M. A. Maddah-Ali, “Private function retrieval,” _arXiv preprint arXiv:1711.04677_ , 2017.
  * [78] X. Yao, N. Liu, and W. Kang, “The capacity of private information retrieval under arbitrary collusion patterns,” _IEEE International Symposium on Information Theory (ISIT)_ , July 2020.
  * [79] R. Tandon, “The capacity of cache aided private information retrieval,” _arXiv preprint arXiv:1706.07035_ , 2017.
  * [80] S. Kadhe, B. Garcia, A. Heidarzadeh, S. E. Rouayheb, and A. Sprintson, “Private information retrieval with side information,” _arXiv preprint arXiv:1709.00112_ , 2017.
  * [81] S. Li and M. Gastpar, “Converse for multi-server single-message pir with side information,” _2020 54th Annual Conference on Information Sciences and Systems (CISS), (arXiv:1809.09861)_ , 2020.
  * [82] Z. Chen, Z. Wang, and S. Jafar, “The capacity of $t$ private information retrieval with private side information,” _IEEE Transactions on Information Theory_ , vol. 66, no. 8, pp. 4761–4773, August 2020.
  * [83] Q. Wang and M. Skoglund, “Secure symmetric private information retrieval from colluding databases with adversaries,” _arXiv preprint arXiv:1707.02152_ , Jul. 2017.
  * [84] S. S. M. Hayashi, “Capacity of quantum private information retrieval with colluding servers,” _IEEE Transactions on Information Theory_ , May 2021\.
  * [85] Z. Jia, H. Sun, and S. A. Jafar, “Cross subspace alignment and the asymptotic capacity of $x$ -secure $t$ -private information retrieval,” _IEEE Transactions on Information Theory_ , vol. 65, no. 9, pp. 5783–5798, Sep. 2019.
  * [86] R. Tajeddine, O. W. Gnilke, D. Karpuk, R. Freij-Hollanti, and C. Hollanti, “Private information retrieval from coded storage systems with colluding, byzantine, and unresponsive servers,” _IEEE Transactions on Information Theory_ , vol. 65, no. 6, pp. 3898–3906, June 2019\.
  * [87] Z. Jia and S. A. Jafar, “$x$-secure $t$-private information retrieval from mds coded storage with byzantine and unresponsive servers,” _IEEE Transactions on Information Theory_ , vol. 66, no. 12, pp. 7427–7438, December 2020.
  * [88] Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin, “Protecting data privacy in private information retrieval schemes,” in _Proceedings of the thirtieth annual ACM symposium on Theory of computing_. ACM, 1998, pp. 151–160.
  * [89] J. Feigenbaum, “Encrypting problem instances,” in _Advances in Cryptology – CRYPTO ‘85 Proceedings_. Springer, 1985, pp. 477–488.
  * [90] M. Abadi, J. Feigenbaum, and J. Kilian, “On hiding information from an oracle,” in _Proceedings of the nineteenth annual ACM symposium on Theory of computing_. ACM, 1987, pp. 195–203.
  * [91] D. Beaver and J. Feigenbaum, “Hiding instances in multioracle queries,” in _STACS 90_. Springer, 1990, pp. 37–48.
  * [92] D. Beaver, J. Feigenbaum, J. Kilian, and P. Rogaway, “Locally random reductions: Improvements and applications,” _Journal of Cryptology_ , vol. 10, no. 1, pp. 17–36, 1997.
  * [93] A. Shamir, “How to share a secret,” _Communications of the ACM_ , vol. 22, pp. 612–613, 1979.
  * [94] A. Beimel, Y. Ishai, E. Kushilevitz, and I. Orlov, “Share conversion and private information retrieval,” in _Proceedings of the 27th Annual Conference on Computational Complexity_ , 2012, pp. 258–268.
  * [95] P. Gopalan, C.Huang, H. Simitci, and S. Yekhanin, “On the Locality of Codeword Symbols,” _IEEE Transactions on Information Theory_ , vol. 58, no. 11, pp. 6925–6934, Nov. 2012.
  * [96] A. G. Dimakis, K. Ramchandran, Y. Wu, and C. Suh, “A survey on network codes for distributed storage,” _Proceedings of the IEEE_ , vol. 99, pp. 476–489, 2011. [Online]. Available: http://arxiv.org/abs/1004.4438
  * [97] Y. Birk and T. Kol, “Coding on demand by an informed source (ISCOD) for efficient broadcast of different supplemental data to caching clients,” _IEEE Trans. on Information Theory_ , vol. 52, no. 6, pp. 2825–2830, June 2006.
  * [98] R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, “Network information flow,” _IEEE Trans. Inform. Theory_ , vol. 46, no. 4, pp. 1204–1216, Jul. 2000.
  * [99] S. Jafar, “Interference Alignment: A New Look at Signal Dimensions in a Communication Network,” in _Foundations and Trends in Communication and Information Theory_ , 2011, pp. 1–136.
  * [100] H. Sun and S. A. Jafar, “The Capacity of Private Information Retrieval,” _IEEE Transactions on Information Theory_ , vol. 63, no. 7, pp. 4075–4088, July 2017.
  * [101] ——, “Blind interference alignment for private information retrieval,” _arXiv preprint arXiv:1601.07885_ , 2016.
  * [102] S. A. Jafar, “Topological Interference Management through Index Coding,” _IEEE Trans. on Inf. Theory_ , vol. 60, no. 1, pp. ”529–568”, Jan. 2014.
  * [103] K. Shanmugam and A. Dimakis, “Bounding multiple unicasts through index coding and locally repairable codes,” in _Proceedings of International Symposium on Information Theory (ISIT)_ , 2014.
  * [104] A. Mazumdar, “A duality between recoverable distributed storage and index coding,” in _Proceedings of International Symposium on Information Theory (ISIT)_ , 2014.
  * [105] S. Rouayheb, A. Sprintson, and C. Georghiades, “On the Index Coding Problem and Its Relation to Network Coding and Matroid Theory,” _IEEE Trans. on Inf. Theory_ , vol. 56, no. 7, pp. 3187–3195, July 2010.
  * [106] M. Effros, S. El Rouayheb, and M. Langberg, “An Equivalence between Network Coding and Index Coding,” _ArXiv:1211.6660_ , Nov. 2012.
  * [107] A. Mazumdar, “Storage Capacity of Repairable Networks,” _IEEE Trans. on Inf. Theory_ , vol. 61, no. 11, Nov. 2015.
  * [108] S. Riis, “Information Flows, Graphs and their Guessing Numbers,” _The Electronic Journal of Combinatorics_ , vol. 14, no. 1, p. R44, 2007.
  * [109] V. Cadambe and S. Jafar, “Interference Alignment and the Degrees of Freedom of the $K$ user Interference Channel,” _IEEE Transactions on Information Theory_ , vol. 54, no. 8, pp. 3425–3441, Aug. 2008.
  * [110] V. Cadambe, S. Jafar, H. Maleki, K. Ramchandran, and C. Suh, “Asymptotic interference alignment for optimal repair of mds codes in distributed data storage,” _IEEE Trans. on Information Theory_ , vol. 59, no. 5, pp. 2974–2987, May 2013.
  * [111] K. Lee, M. Lam, R. Pedarsani, D. Papailiopoulos, and K. Ramchandran, “Speeding up distributed machine learning using codes,” _IEEE Transactions on Information Theory_ , vol. 64, no. 3, pp. 1514–1529, 2018.
  * [112] R. Tandon, Q. Lei, A. G. Dimakis, and N. Karampatziakis, “Gradient coding,” _arXiv preprint arXiv:1612.03301_ , 2016.
  * [113] Q. Yu, S. Li, M. A. Maddah-Ali, and A. S. Avestimehr, “How to optimally allocate resources for coded distributed computing?” _arXiv preprint arXiv:1702.07297_ , 2017.
  * [114] S. Dutta, V. Cadambe, and P. Grover, “Short-dot: Computing large linear transforms distributedly using coded short dot products,” in _Advances In Neural Information Processing Systems_ , 2016, pp. 2092–2100.
  * [115] Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “Straggler mitigation in distributed matrix multiplication: Fundamental limits and optimal coding,” _IEEE Transactions on Information Theory_ , vol. 66, no. 3, pp. 1920–1933, March 2020.
  * [116] R. Bitar, P. Parag, and S. El Rouayheb, “Minimizing latency for secure coded computing using secret sharing via staircase codes,” _IEEE Transactions on Communications_ , vol. 68, no. 8, pp. 4609–4619, 2020.
  * [117] R. Bitar and S. El Rouayheb, “Staircase-PIR: Universally robust private information retrieval,” in _2018 IEEE Information Theory Workshop (ITW)_. IEEE, 2018, pp. 1–5.
  * [118] Q. Yu, S. Li, N. Raviv, S. M. M. Kalan, M. Soltanolkotabi, and S. A. Avestimehr, “Lagrange coded computing: Optimal design for resiliency, security, and privacy,” in _Proceedings of Machine Learning Research_ , ser. Proceedings of Machine Learning Research, K. Chaudhuri and M. Sugiyama, Eds., vol. 89. PMLR, 16–18 Apr 2019, arXiv:1806.00939, 2018, pp. 1215–1225. [Online]. Available: http://proceedings.mlr.press/v89/yu19b.html
  * [119] W.-T. Chang and R. Tandon, “On the capacity of secure distributed matrix multiplication,” _arXiv preprint arXiv:1806.00469_ , 2018.
  * [120] H. Yang and J. Lee, “Secure distributed computing with straggling servers using polynomial codes,” _IEEE Transactions on Information Forensics and Security_ , vol. 14, no. 1, pp. 141–150, Jan 2019.
  * [121] J. Kakar, S. Ebadifar, and A. Sezgin, “Rate-efficiency and straggler-robustness through partition in distributed two-sided secure matrix computation,” _arXiv preprint arXiv:1810.13006_ , 2018.
  * [122] R. G. L. D’Oliveira, S. El Rouayheb, and D. Karpuk, “Gasp codes for secure distributed matrix multiplication,” in _2019 IEEE International Symposium on Information Theory (ISIT)_ , July 2019, pp. 1107–1111.
  * [123] H. A. Nodehi, S. R. H. Najarkolaei, and M. A. Maddah-Ali, “Entangled polynomial coding in limited-sharing multi-party computation,” in _2018 IEEE Information Theory Workshop (ITW)_ , Nov 2018, pp. 1–5.
  * [124] M. Aliasgari, O. Simeone, and J. Kliewer, “Distributed and private coded matrix computation with flexible communication load,” _arXiv preprint arXiv:1901.07705_ , 2019.
  * [125] M. Kim and J. Lee, “Private secure coded computation,” _arXiv preprint arXiv:1902.00167_ , 2019.
  * [126] J. Kakar, S. Ebadifar, and A. Sezgin, “On the capacity and straggler-robustness of distributed secure matrix multiplication,” _IEEE Access_ , vol. 7, pp. 45 783–45 799, 2019.
  * [127] W.-T. Chang and R. Tandon, “On the upload versus download cost for secure and private matrix multiplication,” _arXiv preprint arXiv:1906.10684_ , 2019\.
  * [128] S. Ebadifar, J. Kakar, and A. Sezgin, “The need for alignment in rate-efficient distributed two-sided secure matrix computation,” in _ICC 2019 - 2019 IEEE International Conference on Communications (ICC)_ , May 2019, pp. 1–6.
  * [129] H. A. Nodehi and M. A. Maddah-Ali, “Secure coded multi-party computation for massive matrix operations,” _arXiv preprint arXiv:1908.04255_ , 2019.
  * [130] Z. Jia and S. A. Jafar, “On the capacity of secure distributed matrix multiplication,” _arXiv preprint arXiv:1908.06957_ , 2019.
  * [131] J. Kakar, A. Khristoforov, S. Ebadifar, and A. Sezgin, “Uplink-downlink tradeoff in secure distributed matrix multiplication,” _arXiv preprint arXiv:1910.13849_ , 2019.
  * [132] M. Aliasgari, O. Simeone, and J. Kliewer, “Private and secure distributed matrix multiplication with flexible communication load,” _arXiv preprint arXiv:1909.00407_ , 2019.
  * [133] R. G. D’Oliveira, S. El Rouayheb, D. Heinlein, and D. Karpuk, “Degree tables for secure distributed matrix multiplication,” 2019.
  * [134] Q. Yu and A. S. Avestimehr, “Entangled polynomial codes for secure, private, and batch distributed matrix multiplication: Breaking the ”cubic” barrier,” in _2020 IEEE International Symposium on Information Theory (ISIT)_ , 2020, pp. 245–250.
  * [135] Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “Straggler mitigation in distributed matrxix multiplication: Fundamental limits and optimal coding,” in _2018 IEEE International Symposium on Information Theory (ISIT)_ , June 2018, arXiv:1801.07487v1, 2018, pp. 2022–2026.
  * [136] M. Bläser, _Fast Matrix Multiplication_ , ser. Graduate Surveys. Theory of Computing Library, 2013, no. 5. [Online]. Available: http://www.theoryofcomputing.org/library.html
  * [137] Q. Yu and A. S. Avestimehr, “Harmonic coding: An optimal linear code for privacy-preserving gradient-type computation,” in _2019 IEEE International Symposium on Information Theory (ISIT)_ , July 2019, pp. 1102–1106.
  * [138] Z. Chen, Z. Jia, Z. Wang, and S. A. Jafar, “Gcsa codes with noise alignment for secure coded multi-party batch matrix multiplication,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 2, no. 1, pp. 306–316, 2021.
  * [139] N. Raviv, Q. Yu, J. Bruck, and S. Avestimehr, “Download and access trade-offs in lagrange coded computing,” in _2019 IEEE International Symposium on Information Theory (ISIT)_ , 2019, pp. 1787–1791.
  * [140] J. So, B. Güler, and A. S. Avestimehr, “Codedprivateml: A fast and privacy-preserving framework for distributed machine learning,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 2, no. 1, pp. 441–451, 2021.
  * [141] J. So, B. Guler, and S. Avestimehr, “A scalable approach for privacy-preserving collaborative machine learning,” in _Advances in Neural Information Processing Systems_ , H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, Eds., vol. 33. Curran Associates, Inc., 2020, pp. 8054–8066. [Online]. Available: https://proceedings.neurips.cc/paper/2020/file/5bf8aaef51c6e0d363cbe554acaf3f20-Paper.pdf
  * [142] J. So, B. Güler, and A. S. Avestimehr, “Turbo-aggregate: Breaking the quadratic aggregation barrier in secure federated learning,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 2, no. 1, pp. 479–489, 2021.
  * [143] M. Kim and J. Lee, “Private secure coded computation,” _IEEE Communications Letters_ , pp. 1–1, 2019, doi: 10.1109/LCOMM.2019.2934436.
  * [144] W. Chang and R. Tandon, “On the upload versus download cost for secure and private matrix multiplication,” _IEEE Information Theory Workshop (ITW), Visby, Sweden_ , August 2019.
  * [145] W.-T. Chang and R. Tandon, “On the capacity of secure distributed matrix multiplication,” _IEEE Global Communications Conference (GLOBECOM)_ , December 2018.
  * [146] J. Kakar, S. Ebadifar, and A. Sezgin, “On the capacity and straggler-robustness of distributed secure matrix multiplication,” _IEEE Access_ , vol. 7, pp. 45 783–45 799, 2019.
  * [147] Z. Jia and S. Jafar, “On the capacity of secure distributed batch matrix multiplication,” _arXiv preprint arXiv:1908.06957_ , August 2019.
  * [148] Z. Jia and S. A. Jafar, “Cross subspace alignment codes for coded distributed batch computation,” _IEEE Transactions on Information Theory_ , vol. 67, no. 5, pp. 2821–2846, May 2021.
  * [149] Z. Chen, Z. Jia, Z. Wang, and S. A. Jafar, “Gcsa codes with noise alignment for secure coded multi-party batch matrix multiplication,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 2, no. 1, pp. 306–316, March 2021.
  * [150] Z. Jia and S. Jafar, “X-secure t-private federated submodel learning with elastic dropout resilience,” _arXiv preprint arXiv:2020.01059_ , October 2020\.
  * [151] Y. Lu, Z. Jia, and S. A. Jafar, “Double blind t-private information retrieval,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 2, no. 1, pp. 428–440, March 2021.
  * [152] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-Efficient Learning of Deep Networks from Decentralized Data,” in _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics_ , ser. Proceedings of Machine Learning Research, A. Singh and J. Zhu, Eds., vol. 54. Fort Lauderdale, FL, USA: PMLR, 20–22 Apr 2017, pp. 1273–1282. [Online]. Available: http://proceedings.mlr.press/v54/mcmahan17a.html
  * [153] P. Kairouz _et al._ , “Advances and open problems in federated learning,” in _Foundations and Trends in Machine Learning, NOW Publishers_ , vol. 1, no. 1-2, 2021, pp. 1–210.
  * [154] L. T. Phong, Y. Aono, T. Hayashi, L. Wang, and S. Moriai, “Privacy-preserving deep learning: Revisited and enhanced,” in _Applications and Techniques in Information Security_ , L. Batten, D. S. Kim, X. Zhang, and G. Li, Eds. Singapore: Springer Singapore, 2017, pp. 100–110.
  * [155] ——, “Privacy-preserving deep learning via additively homomorphic encryption,” _IEEE Transactions on Information Forensics and Security_ , vol. 13, no. 5, pp. 1333–1345, 2018.
  * [156] J. Geiping, H. Bauermeister, H. Dröge, and M. Moeller, “Inverting gradients - how easy is it to break privacy in federated learning?” in _Advances in Neural Information Processing Systems_ , H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, Eds., vol. 33. Curran Associates, Inc., 2020, pp. 16 937–16 947. [Online]. Available: https://proceedings.neurips.cc/paper/2020/file/c4ede56bbd98819ae6112b20ac6bf145-Paper.pdf
  * [157] L. Zhu, Z. Liu, and S. Han, “Deep leakage from gradients,” in _Advances in Neural Information Processing Systems_ , H. Wallach, H. Larochelle, A. Beygelzimer, F. Alché-Buc, E. Fox, and R. Garnett, Eds., vol. 32. Curran Associates, Inc., 2019. [Online]. Available: https://proceedings.neurips.cc/paper/2019/file/60a6c4002cc7b29142def8871531281a-Paper.pdf
  * [158] Z. Wang, M. Song, Z. Zhang, Y. Song, Q. Wang, and H. Qi, “Beyond inferring class representatives: User-level privacy leakage from federated learning,” in _IEEE INFOCOM 2019 - IEEE Conference on Computer Communications_ , 2019, pp. 2512–2520.
  * [159] C. Dwork and A. Roth, “The algorithmic foundations of differential privacy,” in _Foundations and Trends in Theoretical Computer Science, NOW Publishers_ , vol. 9, no. 3-4, 2014, pp. 211–407.
  * [160] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ , ser. CCS ’16. New York, NY, USA: Association for Computing Machinery, 2016, p. 308–318. [Online]. Available: https://doi.org/10.1145/2976749.2978318
  * [161] N. Agarwal, A. T. Suresh, F. X. X. Yu, S. Kumar, and B. McMahan, “cpsgd: Communication-efficient and differentially-private distributed sgd,” in _Advances in Neural Information Processing Systems_ , S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, Eds., vol. 31. Curran Associates, Inc., 2018\. [Online]. Available: https://proceedings.neurips.cc/paper/2018/file/21ce689121e39821d07d04faab328370-Paper.pdf
  * [162] S. Song, K. Chaudhuri, and A. D. Sarwate, “Stochastic gradient descent with differentially private updates,” in _2013 IEEE Global Conference on Signal and Information Processing_ , 2013, pp. 245–248.
  * [163] B. McMahan, D. Ramage, K. Talwar, and L. Zhang, “Learning differentially private recurrent language models,” in _International Conference on Learning Representations (ICLR)_ , 2018. [Online]. Available: https://openreview.net/pdf?id=BJ0hF1Z0b
  * [164] S. Asoodeh and F. Calmon, “Differentially private federated learning: An information-theoretic perspective,” in _ICML-FL_ , 2020. [Online]. Available: http://federated-learning.org/fl-icml-2020/
  * [165] R. Bassily, A. Smith, and A. Thakurta, “Private empirical risk minimization: Efficient algorithms and tight error bounds,” in _Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science_ , ser. FOCS ’14. USA: IEEE Computer Society, 2014, p. 464–473. [Online]. Available: https://doi.org/10.1109/FOCS.2014.56
  * [166] U. Erlingsson, V. Feldman, I. Mironov, A. Raghunathan, K. Talwar, and A. Thakurta, “Amplification by shuffling: From local to central differential privacy via anonymity,” in _Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms_ , ser. SODA ’19. USA: Society for Industrial and Applied Mathematics, 2019, p. 2468–2479.
  * [167] A. Bittau, Úlfar Erlingsson, P. Maniatis, I. Mironov, A. Raghunathan, D. Lie, M. Rudominer, U. Kode, J. Tinnes, and B. Seefeld, “Prochlo: Strong privacy for analytics in the crowd,” in _Proceedings of the Symposium on Operating Systems Principles (SOSP)_ , 2017, pp. 441–459. [Online]. Available: https://arxiv.org/abs/1710.00901
  * [168] A. Cheu, A. D. Smith, J. R. Ullman, D. Zeber, and M. Zhilyaev, “Distributed differential privacy via mixnets,” _CoRR_ , vol. abs/1808.01394, 2018. [Online]. Available: http://arxiv.org/abs/1808.01394
  * [169] O. Thakkar, G. Andrew, and H. B. McMahan, “Differentially private learning with adaptive clipping,” _CoRR_ , vol. abs/1905.03871, 2019. [Online]. Available: http://arxiv.org/abs/1905.03871
  * [170] H. Ono and T. Takahashi, “Locally private distributed reinforcement learning,” _CoRR_ , vol. abs/2001.11718, 2020. [Online]. Available: https://arxiv.org/abs/2001.11718
  * [171] Y. Li, T.-H. Chang, and C.-Y. Chi, “Secure federated averaging algorithm with differential privacy,” in _2020 IEEE 30th International Workshop on Machine Learning for Signal Processing (MLSP)_ , 2020, pp. 1–6.
  * [172] B. Balle, G. Barthe, and M. Gaboardi, “Privacy amplification by subsampling: Tight analyses via couplings and divergences,” in _Advances in Neural Information Processing Systems_ , S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, Eds., vol. 31. Curran Associates, Inc., 2018. [Online]. Available: https://proceedings.neurips.cc/paper/2018/file/3b5020bb891119b9f5130f1fea9bd773-Paper.pdf
  * [173] M. A. Heikkilä, A. Koskela, K. Shimizu, S. Kaski, and A. Honkela, “Differentially private cross-silo federated learning,” _CoRR_ , vol. abs/2007.05553, 2020. [Online]. Available: https://arxiv.org/abs/2007.05553
  * [174] B. Balle, J. Bell, A. Gascón, and K. Nissim, “The privacy blanket of the shuffle model,” in _Advances in Cryptology – CRYPTO 2019_ , A. Boldyreva and D. Micciancio, Eds. Cham: Springer International Publishing, 2019, pp. 638–667.
  * [175] B. Ghazi, R. Pagh, and A. Velingker, “Scalable and differentially private distributed aggregation in the shuffled model,” _CoRR_ , vol. abs/1906.08320, 2019. [Online]. Available: http://arxiv.org/abs/1906.08320
  * [176] B. Balle, P. Kairouz, B. McMahan, O. Thakkar, and A. Guha Thakurta, “Privacy amplification via random check-ins,” in _Advances in Neural Information Processing Systems_ , H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, Eds., vol. 33. Curran Associates, Inc., 2020, pp. 4623–4634. [Online]. Available: https://proceedings.neurips.cc/paper/2020/file/313f422ac583444ba6045cd122653b0e-Paper.pdf
  * [177] A. Girgis, D. Data, S. Diggavi, P. Kairouz, and A. Theertha Suresh, “Shuffled model of differential privacy in federated learning,” in _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics_ , ser. Proceedings of Machine Learning Research, A. Banerjee and K. Fukumizu, Eds., vol. 130. PMLR, 13–15 Apr 2021, pp. 2521–2529. [Online]. Available: http://proceedings.mlr.press/v130/girgis21a.html
  * [178] A. Smith, A. Thakurta, and J. Upadhyay, “Is interaction necessary for distributed private learning?” in _2017 IEEE Symposium on Security and Privacy (SP)_ , 2017, pp. 58–77.
  * [179] J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Local privacy and statistical minimax rates,” in _2013 IEEE 54th Annual Symposium on Foundations of Computer Science_ , 2013, pp. 429–438.
  * [180] M. Seif, R. Tandon, and M. Li, “Wireless federated learning with local differential privacy,” in _2020 IEEE International Symposium on Information Theory (ISIT)_ , 2020, pp. 2604–2609.
  * [181] A. Sonee and S. Rini, “Efficient federated learning over multiple access channel with differential privacy constraints,” _CoRR_ , vol. abs/2005.07776, 2020. [Online]. Available: https://arxiv.org/abs/2005.07776
  * [182] Y. Koda, K. Yamamoto, T. Nishio, and M. Morikura, “Differentially private aircomp federated learning with power adaptation harnessing receiver noise,” _CoRR_ , vol. abs/2004.06337, 2020. [Online]. Available: https://arxiv.org/abs/2004.06337
  * [183] D. Liu and O. Simeone, “Privacy for free: Wireless federated learning via uncoded transmission with adaptive power control,” _IEEE Journal on Selected Areas in Communications_ , vol. 39, no. 1, pp. 170–185, 2021.
  * [184] B. Hasırcıoğlu and D. Gündüz, “Private wireless federated learning with anonymous over-the-air computation,” in _ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2021, pp. 5195–5199.
  * [185] M. Seif, W. Chang, and R. Tandon, “Privacy amplification for federated learning via user sampling and wireless aggregation,” _CoRR_ , vol. abs/2103.01953, 2021. [Online]. Available: https://arxiv.org/abs/2103.01953
  * [186] C. Dwork and G. N. Rothblum, “Concentrated differential privacy,” _CoRR_ , vol. abs/1603.01887, 2016. [Online]. Available: http://arxiv.org/abs/1603.01887
  * [187] M. Bun and T. Steinke, “Concentrated differential privacy: Simplifications, extensions, and lower bounds,” in _Theory of Cryptography_ , M. Hirt and A. Smith, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2016, pp. 635–658.
  * [188] I. Mironov, “Renyi differential privacy,” _CoRR_ , vol. abs/1702.07476, 2017\. [Online]. Available: http://arxiv.org/abs/1702.07476
  * [189] A. Triastcyn and B. Faltings, “Federated learning with bayesian differential privacy,” in _2019 IEEE International Conference on Big Data (Big Data)_ , 2019, pp. 2587–2596.
  * [190] S. Guo, T. Zhang, T. Xiang, and Y. Liu, “Differentially private decentralized learning,” _CoRR_ , vol. abs/2006.07817, 2020. [Online]. Available: https://arxiv.org/abs/2006.07817
  * [191] M. Fredrikson, S. Jha, and T. Ristenpart, “Model inversion attacks that exploit confidence information and basic countermeasures,” in _Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security_ , 2015, pp. 1322–1333.
  * [192] M. Nasr, R. Shokri, and A. Houmansadr, “Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning,” in _2019 IEEE symposium on security and privacy (SP)_. IEEE, 2019, pp. 739–753.
  * [193] L. Zhu and S. Han, “Deep leakage from gradients,” in _Federated Learning_. Springer, 2020, pp. 17–31.
  * [194] J. Geiping, H. Bauermeister, H. Dröge, and M. Moeller, “Inverting gradients–how easy is it to break privacy in federated learning?” _arXiv preprint arXiv:2003.14053_ , 2020.
  * [195] K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth, “Practical secure aggregation for privacy-preserving machine learning,” in _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ , 2017, pp. 1175–1191.
  * [196] S. Kadhe, N. Rajaraman, O. O. Koyluoglu, and K. Ramchandran, “Fastsecagg: Scalable secure aggregation for privacy-preserving federated learning,” _arXiv preprint arXiv:2009.11248_ , 2020.
  * [197] Y. Zhao and H. Sun, “Information theoretic secure aggregation with user dropouts,” _arXiv preprint arXiv:2101.07750_ , 2021.
  * [198] J. H. Bell, K. A. Bonawitz, A. Gascón, T. Lepoint, and M. Raykova, “Secure single-server aggregation with (poly) logarithmic overhead,” in _Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security_ , 2020, pp. 1253–1269.
  * [199] A. R. Elkordy and A. S. Avestimehr, “Secure aggregation with heterogeneous quantization in federated learning,” 2020.
  * [200] P. Blanchard, E. M. El Mhamdi, R. Guerraoui, and J. Stainer, “Machine learning with adversaries: Byzantine tolerant gradient descent,” in _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , 2017, pp. 118–128.
  * [201] J. So, B. Guler, and A. S. Avestimehr, “Byzantine-resilient secure federated learning,” _IEEE Journal on Selected Areas in Communication, Series on Machine Learning for Communications and Networks_ , 2020.
  * [202] L. He, S. P. Karimireddy, and M. Jaggi, “Secure byzantine-robust machine learning,” _arXiv preprint arXiv:2006.04747_ , 2020.
  * [203] S. Prakash and A. S. Avestimehr, “Mitigating byzantine attacks in federated learning,” _arXiv preprint arXiv:2010.07541_ , 2020.
  * [204] Y. Khazbak, T. Tan, and G. Cao, “Mlguard: Mitigating poisoning attacks in privacy preserving distributed collaborative learning,” in _2020 29th International Conference on Computer Communications and Networks (ICCCN)_. IEEE, 2020, pp. 1–9.
  * [205] B. Pejó and G. Biczók, “Quality inference in federated learning with secure aggregation,” _arXiv preprint arXiv:2007.06236_ , 2020.
  * [206] J. So, R. E. Ali, B. Guler, J. Jiao, and S. Avestimehr, “Securing secure aggregation: Mitigating multi-round privacy leakage in federated learning,” _arXiv preprint arXiv:2106.03328_ , 2021.
  * [207] K. Banawan, A. Arafa, and S. Ulukus, “Timely private information retrieval,” in _IEEE ISIT_ , July 2021.
  * [208] Q. Yu, M. Maddah-Ali, and S. Avestimehr, “Polynomial codes: an optimal design for high-dimensional coded matrix multiplication,” in _Advances in Neural Information Processing Systems 30_. Curran Associates, Inc., 2017, arXiv:1705.10464, 2017, pp. 4406–4416. [Online]. Available: http://papers.nips.cc/paper/7027-polynomial-codes-an-optimal-design-for-high-dimensional-coded-matrix-multiplication.pdf
  * [209] M. Soleymani, R. E. Ali, H. Mahdavifar, and A. S. Avestimehr, “List-decodable coded computing: Breaking the adversarial toleration barrier,” _arXiv preprint arXiv:2101.11653_ , 2021.
  * [210] M. Soleymani, H. Mahdavifar, and A. S. Avestimehr, “Analog lagrange coded computing,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 2, no. 1, pp. 283–295, 2021.
  * [211] ——, “Privacy-preserving distributed learning in the analog domain,” _arXiv preprint arXiv:2007.08803_ , 2020.
  * [212] Z. Ghodsi, T. Gu, and S. Garg, “Safetynets: Verifiable execution of deep neural networks on an untrusted cloud,” _arXiv preprint arXiv:1706.10268_ , 2017.
  * [213] R. E. Ali, J. So, and A. S. Avestimehr, “On polynomial approximations for privacy-preserving and verifiable relu networks,” _arXiv preprint arXiv:2011.05530_ , 2020.
  * [214] A. M. Subramaniam, A. Heidarzadeh, and K. R. Narayanan, “Collaborative decoding of polynomial codes for distributed computation,” in _2019 IEEE Information Theory Workshop (ITW)_. IEEE, 2019, pp. 1–5.
  * [215] T. Jahani-Nezhad and M. A. Maddah-Ali, “Berrut approximated coded computing: Straggler resistance beyond polynomial computing,” _arXiv preprint arXiv:2009.08327_ , 2020.