PIR schemes with small download complexity
and low storage requirements∗
Simon R. Blackburn†

Tuvi Etzion‡

Maura B. Paterson§

November 15, 2017

arXiv:1609.07027v3 [] 13 Nov 2017

Abstract
In the classical model for (information theoretically secure) Private Information
Retrieval (PIR) due to Chor, Goldreich, Kushilevitz and Sudan, a user wishes to
retrieve one bit of a database that is stored on a set of n servers, in such a way that
no individual server gains information about which bit the user is interested in. The
aim is to design schemes that minimise the total communication between the user
and the servers. More recently, there have been moves to consider more realistic
models where the total storage of the set of servers, or the per server storage, should
be minimised (possibly using techniques from distributed storage), and where the
database is divided into R-bit records with R > 1, and the user wishes to retrieve
one record rather than one bit. When R is large, downloads from the servers to
the user dominate the communication complexity and so the aim is to minimise
the total number of downloaded bits. Work of Shah, Rashmi and Ramchandran
shows that at least R + 1 bits must be downloaded from servers in the worst case,
and provides PIR schemes meeting this bound. Sun and Jafar have considered the
download cost of a scheme, defined as the ratio of the message length R and the
total number of bits downloaded. They determine the best asymptotic download
cost of a PIR scheme (as R → ∞) when a database of k messages is stored by n
servers.
This paper provides various bounds on the download complexity of a PIR
scheme, generalising those of Shah et al. to the case when the number n of servers
is bounded, and providing links with classical techniques due to Chor et al. The
paper also provides a range of constructions for PIR schemes that are either simpler or perform better than previously known schemes. These constructions include
explicit schemes that achieve the best asymptotic download complexity of Sun and
Jafar with significantly lower upload complexity, and general techniques for constructing a scheme with good worst case download complexity from a scheme with
good download complexity on average.
∗

Parts of this paper were presented at the International Symposium on Information Theory, Aachen,
Germany, June 2017
†
Department of Mathematics, Royal Holloway University of London, Egham, Surrey TW20 0EX,
United Kingdom, e-mail: s.blackburn@rhul.ac.uk.
‡
Department
of
Computer
Science,
Technion,
Haifa
3200003,
Israel,
e-mail:
etzion@cs.technion.ac.il. Part of the research was performed while the second author visited
Royal Holloway University of London under EPSRC Grant EP/N022114/1. Part of the research was
supported by the NSF-BSF grant 2016692.
§
Department of Economics, Mathematics and Statistics, Birkbeck, University of London, Malet Street,
London WC1E 7HX, United Kingdom, e-mail: m.paterson@bbk.ac.uk.

1

1
1.1

Introduction
The PIR Model

In the classical model for private information retrieval (PIR) due to Chor, Goldreich,
Kushilevitz and Sudan [13], a database X is replicated across n servers S1 , S2 , . . . , Sn .
A user wishes to retrieve one bit of the database, so sends a query to each server and
downloads their reply. The user should be able to deduce the bit from the servers’ replies.
Moreover, no single server should gain any information on which bit the user wishes to
retrieve (without collusion). The resulting protocol is known as an (information-theoretic)
PIR scheme; there are also computational variants of the security model [28]. The goal
of PIR is to minimise the total communication between the user and the servers.
In practice, the assumption that the user only wishes to retrieve one bit of the
database, and the assumption that there is no shortage of server storage seem unrealistic. Because of this, many recent papers assume that the database X consists of k
records, each of which is R bits in length, so that the number of possible databases is 2kR .
We denote the value of Record i by Xi , and we write Xij for the jth bit of Xi . The aim
of the protocol is for the user to retrieve the whole of Xi , rather than a single bit. We
also, following Shah, Rashmi and Ramchandran [36], drop the assumption that the whole
database is replicated across the n servers S1 , S2 , . . . , Sn and so, for example, there is the
possibility of using techniques from coding theory in general and from distributed storage
codes in particular to reduce the total storage of the scheme. No restrictions are made on
the particular encoding used to distribute the database across the servers other than to
assume it is deterministic, i.e. that there is a unique way to encode each database. This
important generalisation of the model has led to very interesting recent work which we
discuss in Subsection 1.3 below.
More combinatorially, we define a private information retrieval scheme as follows.
Definition 1.1 (PIR scheme). Suppose a database X is distributed across n servers
S1 , S2 , . . . , Sn . A user who wishes to learn the value Xℓ of Record ℓ submits a query
(q1 , q2 , . . . , qn ). For each r ∈ {1, 2, . . . , n}, server Sr receives qr and responds with a
value cr that depends on qr and on the information stored by Sr . The user receives the
response (c1 , c2 , . . . , cn ). This system is a private information retrieval (PIR) scheme if
the following two properties are satisfied:
(Privacy) For r = 1, 2, . . . , n the value qr received by server Sr reveals no information
about which record is being sought.
(Correctness) Given a response (c1 , c2 , . . . , cn ) to a query (q1 , q2 , . . . , qn ) for Record ℓ,
the user is unambiguously able to recover the value Xℓ of this record.
Note that while the query is drawn randomly according a pre-specified distribution
on a set of potential queries, the response is assumed to be deterministic.
Example 1.1. In the case of a single server, a trivial method for achieving PIR is for
the user to download the entire kR-bit database.
Chor, Goldreich, Kushilevitz and Sudan showed that in the case of single-bit records
(R = 1), if there is a single server then PIR is only possible if the total communication is
2

at least k bits (i.e. the size of the entire database) [13], and so the solution above is best
possible. We are interested in finding solutions such as the scheme below, which transmit
significantly fewer than kR bits.
Example 1.2. [13] Suppose there are two servers, each storing the entire database.
Suppose R = 1.
• A user who requires Record ℓ chooses a k-bit string (α1 , α2 , . . . , αk ) uniformly at
random.
Lk
• Server 1 is requested
to
return
the
value
c
=
1
i=1 αi Xi , and Server 2 is requested

L
k
to return c2 =
i=1 βi Xi , where
(
αi ⊕ 1 when i = ℓ,
βi =
αi
otherwise.

• The user computes c1 ⊕ c2 to recover the value Xℓ of Record ℓ.
The strings (α1 , α2 , . . . , αk ) and (β1 , β2 , . . . , βk ) are both uniformly distributed, and
are independent of the choice of ℓ, hence neither server receives any information as to
which record is being recovered by the user.
We note that the scheme above works unchanged when the records are R-bit strings
rather than single bits. The download complexity of the scheme, in other words the total
number of bits downloaded from the servers, is 2R. The upload complexity is 2k, since
each server receives a k-bit string from the user. Thus the total communication of the
scheme is 2R + 2k bits, which is significantly less than kR bits for most parameters.
Note that the upload complexity of this scheme does not depend on R, and so is an
insignificant proportion of the total communication when R is large. This is a general
phenomenon: Chan, Ho and Yamamoto [12, Remark 2] observe the following. Let m > 1
be an integer. Suppose we have an n-server PIR scheme for a database of k records, each
R bits long. Suppose the scheme requires u upload bits and d download bits. Then we
can construct an n-server PIR scheme for a database of k records, each mR bits long,
which requires md bits of download but still needs just u bits to be uploaded. Note that
when m is large (so records are long) the communication complexity of the new scheme
is dominated by the download complexity of the given scheme.
Because of the observation of Chan et al., it is vital to find PIR schemes with low
download complexity. We formalise the download complexity as follows.
Definition 1.2. A PIR scheme uses binary channels if the response cj sent by server
Sj is a binary string of length dj , where dj depends only
Pn on the query qj it receives.
The download complexity is the maximum of the sum j=1 dj over all possible queries
(q1 , q2 , . . . , qn ).
So the download complexity is the number of bits downloaded in the worst case. We
emphasise that the length dj in the definition above does not depend on the database X,
but could depend on the query qj received by server Sj . We note that we allow for the
possibility that dj = 0, so the server does not reply to the query. Finally, we note that if
3

we know that there are more than 2x distinct possibilities for cj as the database varies,
we may deduce that dj ≥ x + 1. Although it is possible to use non-binary channels for
PIR, we restrict our exposition to PIR schemes using binary channels in this paper (as
is standard in the literature).
We should comment that, despite the observation of Chan et al., we should not ignore
upload complexity completely, as there are scenarios (for example, when R is not so large)
when it might be dominant. Moreover, we cannot compare 2k bits of download with 2R
bits of upload just by comparing k and R, since we know (at least currently) that in
practice it takes much more time to upload a bit than to download one. Of course, we
don’t know how the speed of downloading and uploading will change over time. But the
obvious consequence of the current situation and future developments is to consider both
upload and download complexities separately, and not to ignore one of them completely.
This is something that will be done in this paper, although the download complexity
will be the main target for optimisation since we generally assume that the size of the
database is (considerably) larger than the one bit of the classical PIR model.
We continue to another important measure that has motivated many papers in the
last three years, after being introduced by Shah et el.[36]:
Definition 1.3. Suppose server Sr stores sr bits of information about the database X.
• The per-server storage of the scheme is max{sr | r = 1, 2, . . . , n}.
P
• The total storage of the scheme is nr=1 sr .

• The storage overhead of the scheme is the ratio between the total storage and the
size of the database, i.e. kR.
The classical model of PIR ignored storage issues: it was assumed that there is enough
storage to allow the replication of the database at each server. But, with the quantity
of information stored today in data centres, storage is an issue today and might be an
important barrier in the future. Thus, it is important to reduce the storage overhead
as much as possible, while keeping reliability, fast access, fast upload and fast download
at reasonable levels. This is the perspective of the current paper, which is concerned
with schemes whose download complexity is as small as possible whilst keeping the total
storage at reasonable levels.

1.2

Our contributions

In Section 2, we provide combinatorial results on the structure of a PIR scheme with
small download complexity:
• We generalise (Theorem 2.2) a key theorem in the foundational paper of Chor et
al. [13], and use this result to generalise the lower bound of R + 1 on download
complexity in [36]. The results imply (Theorem 2.5) that an n-server PIR scheme
n
R when k > ⌈R/(n − 1)⌉. (This
must have download complexity at least n−1
last result can also be obtained as a corollary of a recent bound due to Sun and
Jafar [37].) These results provide a bridge between classical PIR and the new models
that are assuming the retrieval of long records.
4

• We provide (Corollary 2.6, Theorem 2.7) information on the structure of a PIR
scheme with minimal download complexity R + 1. In particular, Theorem 2.7
provides a rigorous statement of [36, Theorem 1].
In Section 3, we provide various constructions for PIR schemes with low download
complexity:
• In Subsection 3.1, we provide two simple (R+1)-server PIR schemes with download
complexity R + 1. Both schemes have total storage which is quadratic in R. The
first scheme is a natural generalisation of the scheme of Chor et al. given above.
The second scheme is a close variant of the quadratic total storage PIR scheme
in [36], which avoids having to design slightly different schemes depending on the
parity of R. This second scheme is to be preferred due to its lower upload complexity. (Another, more complex, PIR scheme with download complexity R + 1 is
considered in detail in [36]. This scheme has small per-server storage, but requires
an exponential (in R) number of servers, and so has exponential total storage.)
• In Subsection 3.2, we describe an n-server PIR scheme with download complexity
n
R. The total storage of the scheme is linear in R. This shows that for any ǫ > 0
n−1
there exists a PIR scheme with linear total storage and download complexity at
most (1 + ǫ)R. (Schemes with linear total storage, but with download complexity
between 2R and 4R, are given in [36].)
• We describe (Subsection 3.3) schemes that provide trade-offs between increasing
the number of servers and reducing the per-server storage of the scheme in Subsection 3.2.
• In Subsection 3.4, we provide explicit schemes that achieve optimal asymptotic
download cost. The performance of these schemes is equal to the inductively defined
schemes in Sun and Jafar [37], but the description of these schemes is more concise,
and the proof that they are indeed PIR schemes is much more straightforward.
• Finally, in Subsection 3.5, we explain an averaging technique that allows a PIR
scheme with good average download complexity to be transformed into a scheme
with good download complexity in the worst case.

1.3

Context

We end this introduction with a discussion of some of the related literature. (Many of
these papers appeared after the conference version of our paper [10] was posted.)
Private information retrieval was introduced in [13], and has been an active area ever
since. See, for example, Yekhanin [54] for a fairly recent survey.
The papers by Shah et al. [36] and (independently) by Augot, Levy-Dit-Vahel, and
Shikfa [2] are the first to consider PIR models where the information stored in the servers
could be coded using techniques from distributed storage. Whereas [36] is mainly concerned with download complexity, and also with total storage (with per-server storage,
and query size also relevant parameters), the authors of [2] emphasise measures of robustness against malicious servers, namely decoder locality and PIR locality.
5

More recently, the literature has addressed several parallel and related issues, which
can be categorised as follows:
1. Papers dealing with the download complexity, rate, and capacity of PIR schemes.
2. Research which attempts to reduce the storage overhead of PIR schemes.
3. Papers which present coding techniques, based on various error-correcting codes,
e.g. MDS codes, to store the database in a distributed fashion.
4. Papers which consider PIR schemes in the presence of unreliable servers. Servers
might be colluding (so they have access to more than one query qr ), they might
fail (and so do not reply with a value cr ), they might be adversarial (replying with
incorrect values cr ), they might be unsynchronised (storing slightly different copies
of the database) and so on.
5. Research which aims to build PIR schemes into previously known architectures for
distributed storage.
6. Papers dealing with other PIR models, for example allowing broadcasting of some
information, or allowing the user to possess side information such as the value of
some records.
Clearly, these issues are related, and a given paper might address aspects of more than
one of these topics.
In early papers, Fanti and Ramchandran [16, 17] considered unsynchronized databases;
the results are the same as for synchronized PIR at the expense of probabilistic success
for information retrieval, and the use of two rounds of communication. We are not aware
of recent work in this model, but we mention in this context the work of Tajeddine and
El Rouayheb [46] which considers PIR schemes in the presence of some servers which do
respond to a query.
In a sequence of papers, Sun and Jafar [37, 38, 39, 40, 41] consider the capacity of
the channels related to PIR codes in various models. (The rate of a PIR scheme is the
ratio of R and the download complexity, and the capacity is the supremum of achievable
rates.) In the model for PIR we consdier, they use information theoretic techniques to
show [37] that an n-server PIR scheme on a k message database has rate at most


 k !−1
1
1
1−
1−
.
n
n
(Their model is restricted to the special case of replication, but it is easy to see that
this restriction is not needed for this result to hold.) They also provide a scheme that
attains this rate. The messages in their scheme are extremely long for most values of n
and k: the message length must be a multiple of nk . Because of this, the scheme can
be thought of as being tailored for the situation when R → ∞. Their results show that
when R → ∞ with n and k fixed, there are schemes whose download complexity (and so
whose communication complexity) has a leading term of the form
 k !
n
1
1−
R,
n−1
n
6

and that this term is best possible. (We give an explicit scheme with the same download
complexity in Subsection 3.4.)
The results in [37] have been generalised to the case when some of the servers collude.
Sun and Jafar [38] find the capacity of the channel in this more general case. (The
results in [37] can be thought of as the special case where each server can collude only
with itself.) The capacity for the symmetric PIR model, where the user who retrieves a
message will get no information about the other messages in the database, is determined
in [39]. The optimal download complexity in the situation when the messages in the
database might be of different lengths is considered in [40]. The most recent in this
sequence of papers considers an interactive model, where a user can have several rounds
of queries, the queries in a given round are allowed to depend on answers from previous
rounds. Moreover, colluding servers are considered in this model. It is proved [41] that for
this case there is no change in the capacity, but that the storage overhead can sometimes
be improved.
Banawan and Ulukus [3] also generalise the results of Sun and Jafar [37], finding the
capacity of the PIR scheme when the database is encoded with a linear code. Another
generalisation due to Banawan and Ulukus [4, 5] is to the scenario that the user is allowed
to request a few records in one round of queries. They provide capacity computations
and schemes for this scenario. A similar case was also discussed in [58]. Finally, Banawan
and Ulukus [6] consider the capacity of PIR schemes in the scenario where servers might
not be synchronised, there might be adversarial errors, and some servers might collude.
They compute the capacity when some or all of these events might occur. Wang and
Skoglund [51] consider the capacity of a symmetric PIR scheme when the database is
stored in a distributed fashion using an MDS code.
Chan, Ho, and Yamamoto [11, 12] consider the trade-off between the total storage
and the download complexity when the size of a record is large; the trade-off depends on
the number of records in the system. They also consider the case where the database is
encoded with an MDS code.
Fazeli, Vardy, and Yaakobi [18, 19] give a method to reduce the storage overhead based
on any known PIR scheme which uses replication. Their method reduces the storage
overhead considerably, without affecting the order of the download complexity or upload
complexity of the overall scheme, by simulating the original scheme on a larger number
of servers. Their key concept is an object they call a κ-PIR code (more generally a κ-PIR
array code), where κ is the number of servers used in the originally known PIR scheme,
which controls how a database can be divided into parts and encoded within servers to
allow a trade-off between the number of servers and the storage overhead. In particular,
for all ǫ > 0, they show that there exist good schemes (in terms of communication
requirements) where the amount of information stored in a server is bounded but the
total storage is at most (1 + ǫ) times the database size. Rao and Vardy [30] study PIR
codes further, establishing the asymptotic behavior of κ-PIR codes. Vajha, Ramkumar,
and Kumar [49, 50] find the redundancy of such codes for κ = 3, 4 by using ReedMuller codes. Lin and Rosnes [29] show how to shorten and lengthen PIR codes, and
find the redundancy of such codes for κ = 5, 6. Blackburn and Etzion [8, 9] consider
the optimal ratios between κ-PIR array codes and the actual number of servers used in
the system. Zhang, Wang, Wei, and Ge [57] consider these ratios further, and improve
some of the results from [8, 9]. We remark that though it is possible to reduce the
7

storage overhead using the techniques of PIR array codes, it seems impossible to reduce
the download complexity of the resulting schemes below (3/2)R (and most codes give
download complexity close to 2R) because of restrictions on the PIR rate of such codes.
It is interesting to note that Augot, Levy-Dit-Vahel, and Shikfa [2] constructed PIR
schemes by partitioning the database into smaller parts, as done later in [18, 19], to
reduce the storage overhead. But they applied this technique only to a certain family of
multiplicity codes, and the parts of the partition were not encoded as in [18, 19].
Fazeli, Vardy, and Yaakobi [19] remark that the concept of a κ-PIR code is closely
related to codes with locality and availability. Such codes were studied first by Rawat,
Papailiopoulos, Dimakis, and Vishwanath [31, 32] and later also by others, for example [20, 23]. A new subspace approach for such codes was given recently in [34, 35].
Another family of related codes with similar properties are batch codes, which were first
defined by Ishai, Kushilevitz, Ostrovsky, and Sahai [24] and were recently studied by
many others, for example [1, 33]. It is important to note that all these codes are very important in the theory of distributed storage codes. This connection between the concepts
of locality and PIR codes are explored in [20].
Error-correcting codes, and in particular maximum distance separable (MDS) codes,
have been considered by many authors in various PIR models. It is natural to consider
MDS codes, as they are very often used in various types of distributed storage codes
(especially for locally repairable codes [22] and regenerating codes [14, 15]), and we expect
that the servers in our PIR scheme will be part of a distributed storage system. We will
now mention various examples.
Colluding or malicious servers in PIR have been much studied over the last two years.
Tajeddine and El Rouayheb [44, 45] consider PIR schemes where the information is stored
using MDS codes. They describe schemes which have optimal download complexity in
this model, as they attain the bounds in [11, 12], in the situation when one or two ‘spies’
(colluding and/or malicious servers) are present. In the case of one spy (no collusion)
a generalisation to any linear code with rate greater than half was given in [27]. FreijHollanti, Gnilke, Hollanti, and Karpuk [21] give a PIR scheme coded with an MDS code
which can be adjusted (by varying the rate of the MDS code) to combat against larger
numbers of colluding servers. This scheme also attains the asymptotic bound on the
related capacity of such a PIR scheme. This idea is generalised in [47]. The results
in the latter paper are analysed (and one conjecture disproved) by Sun and Jafar [42,
43]. Another scheme based on MDS codes which can combat large number of colluding
servers is given by Zhang and Ge [55]. A generalisation to the case where the user wants
to retrieve several files is given by the same authors in [56]. Wang and Skoglund [52]
consider a symmetric PIR scheme using an MDS code, in which the user can retrieve the
information about the file he wants, but can gain no information about the other files.
This scheme attains the bound on the capacity which they derive earlier in [51]. They
have extended their work to accommodate colluding servers in [53].
PIR can be combined with other applications in storage and communication in many
ways. One example is a related broadcasting scheme in [26]. Another example is cacheaided PIR, considered by Tandon [48]. In this setup the user is equipped with a local
cache which is formed from an arbitrary function on the whole set of messages, and this
local cache is known to the servers. The situation when this cache is not known to the
servers is considered by Kadhe, Garcia, Heidarzadeh, El Rouayheb, and Sprintson [25].
8

Since the user has side information in these models, the problem is closely related to
index coding [7] a topic which is also of great interest.

2

Optimal download complexity

In this section, we give structural results for PIR schemes with optimal download complexity, given that the database consists of k records of length R. For some of the results,
we also assume that the PIR scheme involves n servers, where n is fixed.
In Subsection 2.1 we generalise a classical result in Private Information Retrieval due
to Chor et al. We use this result to provide an alternative proof of the theorem of Shah,
Rashmi and Ramchandran [36] that a PIR scheme must have download complexity at
n
least R + 1 when k ≥ 2, and to prove a lower bound of n−1
R for the download complexity
of an n-server PIR scheme whenever k is sufficiently large. In Section 2.2 we present
more precise structural results when the download complexity of a PIR scheme attains
the optimal value of R + 1 bits.
Definition 2.1. We say that a response (c1 , c2 , . . . , cn ) is possible for a query (q1 , q2 , . . . , qn )
if there exists a database X for which (c1 , c2 , . . . , cn ) is returned as the response to the
query (q1 , q2 , . . . , qn ) when X is stored by the servers.

2.1

Lower bounds on the download complexity

We aim to generalise the following theorem, which was proved by Chor et al. in the very
first paper on PIR [13, Theorem 5.1]:
Theorem 2.1. A PIR scheme that uses a single server for a database with k records of
size one bit is not possible unless the number of possible responses from the server to any
given query is at least 2k .
Our generalisation shows a server must reply with at least k(R − d) bits of download,
if no more than at total of d bits (where 0 ≤ d ≤ R) are downloaded from the other
servers. We state our generalisation as follows. Without loss of generality we will focus
on server S1 , so for ease of notation we will denote the tuple (q1 , q2 , . . . , qn ) by (q1 , qother ),
and (c1 , c2 , . . . , cn ) by (c1 , cother ).
Theorem 2.2. Suppose 0 ≤ d ≤ R. Let q1 be fixed. Suppose we have a PIR scheme with
the property that for any query of the form (q1 , qother ), we have
|{cother | ∃c1 such that (c1 , cother ) is possible for (q1 , qother )}| ≤ 2d .
′
Then for any query (q1 , qother
) we have
′
|{c1 | ∃cother such that (c1 , cother ) is possible for (q1 , qother
)}| ≥ 2k(R−d) .

We remark that Theorem 2.1 is the case d = 0 and R = 1 of Theorem 2.2.

9

Proof. Let q1 be fixed, and suppose we have a PIR scheme with the property that for
any query (q1 , qother )
|{cother | ∃c1 such that (c1 , cother ) is possible for (q1 , qother )}| ≤ 2d .
∗
Assume, for a contradiction, that there exists a query (q1 , qother
) corresponding to the ith
record for which
∗
|{c1 | ∃cother such that (c1 , cother ) is possible for (q1 , qother
)}| < 2k(R−d) .

There are 2kR databases, and less than 2k(R−d) possibilities for the reply c1 of S1 to
∗
the (q1 , qother
). So by the pigeonhole principle, there is a value c∗1 for which there exists a
set T of databases with |T | > 2kR /2k(R−d) = 2kd having the property that for each X ∈ T ,
∗
the response of S1 to (q1 , qother
) when the servers store X is c∗1 . If server S1 receives the
query q1 , it will thus return c∗1 whenever a database in T is being stored.
Since the databases consist of k records, the fact that |T | > 2kd implies the existence
of a record, say Record ℓ, for which the number of distinct values Xℓ that appear among
the databases in T is greater than 2d . Thus we can choose a set of databases W ⊆ T
such that no two databases in W have the same value Xℓ .
∗
The requirement for privacy against server S1 implies that if (q1 , qother
) is a query for
ℓ
Record i, then there exists a query for Record ℓ of the form (q1 , qother ), since otherwise S1
ℓ
could distinguish between queries for Record i and Record ℓ. If query (q1 , qother
) is made
∗
when a database in T is stored, then server S1 receives q1 and responds c1 as before. Now
consider the databases in W . As there are 2d + 1 of them, yet at most 2d values for cother
ℓ
for which there is a possible response (c∗1 , cother ) to (q1 , qother
), it follows that there must
ℓ
be some value cother for which there are two databases X, Y ∈ W such that the response
ℓ
to (q1 , qother
) is (c∗1 , cℓother ) when either of those databases is stored. This contradicts the
correctness of our scheme, since the values of Record ℓ in X and Y are not equal yet the
ℓ
response (c∗1 , cℓother ) to the query (q1 , qother
) does not allow the user to distinguish between
them.
The following theorem is a key consequence of Theorem 2.2.
Theorem 2.3. Let x be non-negative, and suppose we have a PIR scheme that has
download complexity at most R + x. If the database contains k records, where k ≥ x + 2,
then the number of bits downloaded from any server is at most x.
Proof. Without loss of generality, consider the server S1 . Suppose for a contradiction
that there exists a query q1 so that at least x + 1 bits are downloaded from S1 (and so
at most (R + x) − (x + 1) = R − 1 bits are downloaded from the other servers). Suppose
that a total of d bits are downloaded from the other servers in the worst case when S1
receives q1 . So d ≤ R − 1. Theorem 2.2 implies that at least k(R − d) bits are downloaded
from S1 , and so at least k(R − d) + d bits are downloaded from the servers in the worst
case. But d ≤ R − 1 and k ≥ x + 2, so
k(R−d)+d = kR−(k−1)d ≥ kR−(k−1)(R−1) = R+k−1 ≥ R+(x+2)−1 = R+x+1,
which is impossible as the scheme has total download complexity R+x. This contradiction
establishes the theorem.
10

We are now in a position to provide a new short proof of the following corollary. The
corollary is due to Shah et al. [36].
Corollary 2.4. Let the database contain k records with k ≥ 2. Any PIR scheme requires
a total download of at least R + 1 bits.
Proof. Suppose we have a scheme with total download of R or fewer bits. Theorem 2.3
with x = 0 implies that 0 bits are downloaded from each server, and so the user receives
no information about the desired record. Hence such a scheme cannot exist.
The following theorem improves the bound of Corollary 2.4 when n < R + 1 and k is
sufficiently large.
Theorem 2.5. Suppose a PIR scheme involves n servers, where n ≥ 2. Suppose the
1
database contains k records, where k ≥ ⌈ n−1
R⌉ + 1. Then the download complexity of the
n
scheme is at least n−1 R bits.
Proof. Assume for a contradiction that the scheme has download complexity R+x, where
1
1
R. Since x ≤ ⌈ n−1
R⌉ − 1, we see that k ≥ x + 2 and
x is an integer such that x < n−1
so Theorem 2.3 implies that the number of bits downloaded by any server is at most x.
Since we have n servers, the total number of bits of download is always at most xn. Since
our scheme has download complexity R + x, there is a query where a total of R + x bits
are downloaded from servers. Hence we must have that nx ≥ R + x, which implies that
1
x ≥ n−1
R. This contradiction establishes the result.

2.2

Download complexity R + 1

The final two results of this section concentrate on the extreme case when the download
complexity is exactly R+1. Recall that the download complexity is a worst case measure,
so R + 1 is an upper bound on the number of bits downloaded for any query, and there
exists a query where R + 1 bits are downloaded.
Corollary 2.6. Let the database contain k records with k ≥ 3. Any PIR scheme with
a total download of exactly R + 1 bits requires 1 bit to be downloaded from each of R or
R + 1 different servers in response to any query.
Proof. The special case of Theorem 2.3 when x = 1 shows that no server replies with
more than 1 bit. For the download complexity to be R + 1, no more than R + 1 servers
can respond non-trivially. Since the user deduces the value of an R-bit record from the
bits it has downloaded, at least R servers must reply to any query.
One might hope that the Corollary 2.6 could be strengthened to the statement that
exactly R + 1 servers must respond non-trivially. However, examples show that this is
not always the case: see the comments after Construction 1 below.
Shah et al. state [36, Theorem 1] that, in the situation above, “for almost every PIR
operation” R + 1 servers must respond, and they provide a heuristic argument to support
this statement. The following result makes this rigorous, with a precise definition of
‘almost every’.

11

Theorem 2.7. Let the database contain k records with k ≥ 3. Suppose we have a PIR
scheme with a total download of exactly R + 1 bits (in the worst case). Suppose a user
chooses to retrieve a record chosen with a uniform probability distribution on {1, 2, . . . , k}.
Let α be the probability that only R bits are downloaded. Then
α≤

R+1
.
kR + 1

Proof. By Corollary 2.6, each server replies to any query with at most one bit. We may
assume, without loss of generality, that if a server replies with one bit then this bit must
depend on the database in some way (since otherwise we may modify the scheme so that
this server does not reply and the probability α will increase).
Let (q1 , q2 , . . . , qn ) be a query for the ℓth record where only R servers reply nontrivially. Since only R servers reply, there are at most 2R possible replies to the query
(over all databases). But the value Xℓ of the record is determined by the reply, and there
are 2R possible values of Xℓ . So in fact there must be exactly 2R possible replies, and
there is a bijection between possible replies and possible values Xℓ . We claim that the
replies of each of these R servers can only depend on Xℓ , not on the rest of the database.
To see this, suppose a server Sr replies non-trivially, and let f : {0, 1}kR → {0, 1} be
the function mapping each possible value of the database to the reply of Sr to query qr .
Suppose f is not a function of Xℓ alone, so there are two databases X and X′ whose ℓth
records are equal and such that f (X) 6= f (X′ ). Let ρ be the common value of the ℓth
record in both X and X′ . When Xℓ = ρ there are at least two possible replies to the
query, depending on the value of the remainder of the database. But this contradicts
the fact that we have a bijection between possible replies and possible values Xℓ . So our
claim follows.
Let A be the event that exactly R servers reply, and for r = 1, 2, . . . , n let Br be the
event that server Sr replies non-trivially. Let Dr be the indicator random variable for the
event Br . So Dr is equal to 1 when Sr responds non-trivially and 0 otherwise. Note that
Dr is always equal to the number of bits downloaded from Sr , thus the expected value of
the sum of these variables satisfies
!
n
X
E
Dr = αR + (1 − α)(R + 1) = R + 1 − α.
(1)
r=1

Let Dr′ be the indicator random variable for the event A ∧ Br . When A does not occur,
all the variables Dr′ are equal to 0. When A occurs, Dr′ is the number of bits downloaded
from server Sr and a total of R bits are downloaded. So
!
n
X
E
(2)
Dr′ = (1 − α)0 + αR = αR.
r=1

Suppose a server Sr uses the following strategy to guess the value of ℓ from the query
qr it receives. If the server replies non-trivially using a function f that depends on only
one record, say Record ℓ′ , it guesses that ℓ = ℓ′ . Otherwise, the server guesses a value
uniformly at random. The server guesses correctly with probability 1/k when it responds
trivially. The argument in the paragraph above shows the server always guesses correctly
12

if it responds non-trivially and only R servers reply. Thus the server is correct with
probability at least (1/k) Pr(Br ) + Pr(A ∧ Br ). The privacy requirement of the PIR
scheme implies that the server’s probability of success can be at most 1/k, and so we
must have that Pr(A ∧ Br ) ≤ (1/k) Pr(Br ). Hence
E(Dr′ ) ≤ (1/k)E(Dr ).
By linearity of expectation, we see that
!
!
n
n
n
n
X
X
X
X
1
1
E
Dr′ =
E(Dr′ ) ≤
E(Dr ) = E
Dr .
k r=1
k
r=1
r=1
r=1
So, using (1) and (2), we see that
1
(R + 1 − α).
k
Rearranging this inequality in terms of α, we see that the theorem follows.
αR ≤

3

Constructions

Recall the notation from the introduction: we are assuming that our database X consists
of k records, each of R bits, and we write Xij for the jth bit of the ith record.

3.1

Two schemes with download complexity R + 1

This section describes two schemes with download complexity R + 1. Recall that this
download complexity is optimal, by Corollary 2.4. The first scheme is included because
of its simplicity; it can be thought of as a variation of the scheme of Chor et al. described
in Example 1.2, and achieves optimal download complexity using only R + 1 servers. It
has a total storage requirement which is quadratic in R. But the scheme has high upload
complexity: kR(R + 1). The second scheme is very closely related to a scheme mentioned
in an aside in Shah et al. [36, Section IV]. This scheme has the same properties as the
first scheme, except the upload complexity is improved to just (R + 1)k⌈log(R + 1)⌉.
We note that the main scheme described in Shah et al. [36, Section IV] also has
optimal download complexity of R + 1. Each server stores just R bits, and so the storage
per server is low. However, their scheme uses an exponential (in R) number of servers,
and so has exponential total storage.
Construction 1. Suppose there are R + 1 servers, each storing the whole database.
• A user who requires Record ℓ creates a k × R array of bits by drawing its entries
αij uniformly and independently at random.
L L
• Server SR+1 is requested to return the bit cR+1 = ki=1 R
j=1 αij Xij .
L L
• For r = 1, 2, . . . , R, server Sr is requested to return the bit cr = ki=1 R
j=1 βij Xij ,
where
(
αij ⊕ 1 if i = ℓ and j = r,
βij =
αi,j
otherwise.
13

• To recover Xℓr , namely bit r of record Xℓ , the user computes cr ⊕ cR+1 .
Theorem 3.1. Construction 1 is a (R + 1)-server PIR scheme with download complexity
R + 1. The scheme has upload complexity kR(R + 1) and total storage (R + 1)Rk bits.
Proof. We note that
αij ⊕ βij =

(

1 if i = ℓ and j = r,
0 otherwise.

Hence
cr ⊕ cR+1 =

R
k M
M

(αij ⊕ βij )Xij

i=1 j=1

= Xℓr .

So the user recovers the bit Xℓr correctly for any r with 1 ≤ r ≤ R. This proves
correctness.
For privacy, we note that SR+1 receives a uniformly distributed vector qR+1 = (αij ) ∈
{0, 1}kR in all circumstances. Since the distribution of qR+1 does not depend on ℓ, no
information about ℓ is received by SR+1 . Similarly, for any 1 ≤ r ≤ R, the query
qr = (βij ) ∈ {0, 1}kR is uniformly distributed irrespective of the value of ℓ, and so no
information about ℓ is received by Sr .
We note that each query qr is kR bits long (for any r ∈ {1, 2, . . . , R + 1}) and so the
upload complexity of the scheme is kR(R + 1). Each server replies with a single bit, and
so the download complexity is R + 1. The database is kR bits long, and so (since each
server stores the whole database) the total storage is (R + 1)Rk bits.
We note that there are situations where one of the servers is asked for an all-zero
linear combination of bits from the database. In this case, that server need not reply.
So the number of bits of downloaded in Construction 1 is sometimes R (though usually
R + 1 bits are downloaded). See the comment following Corollary 2.6.
We now describe a second construction with improved upload complexity. The construction can be thought of as a variant of Construction 1 where the rows of the array α
are all taken from a restricted set {e0 , e1 , . . . , eR } of size R + 1. A similar idea is used in
the constructions in [36].
For i = 1, 2, . . . , R, let ei be the ith unit vector of length R. Let e0 be the all zero
vector. For binary vectors x and y of length R, write x · y be their inner product; so
x · y = ⊕R
j=1 xj yj .
Construction 2. Suppose there are R + 1 servers, each storing the whole database.
• A user who requires Record ℓ chooses k elements a1 , a2 , . . . , ak ∈ ZR+1 uniformly
and independently at random. For r = 1, . . . , R + 1, server Sr is sent the vector
qr = (b1r , b2r , . . . , bkr ) ∈ ZkR+1 , where
(
ai + r mod R + 1 if i = ℓ,
bir =
ai
otherwise.
14

• Server Sr returns the bit cr =

Lk

i=1 ebir

· Xi .

• To recover the j th bit of Xℓ , the user finds the integers r and r ′ such that bℓr = 0
and bℓr′ = j. The user then computes cr ⊕ cr′ .
Theorem 3.2. Construction 2 is an (R+1)-server PIR scheme with download complexity
R + 1. The scheme has upload complexity k(R + 1) log(R + 1) and total storage (R + 1)Rk
bits.
Proof. For correctness, we first note that r and r ′ exist since bℓr ∈ {0, 1, 2 . . . , R} takes
on each possible value once as r ∈ {0, 1, . . . , R} varies. Also note that
(
ej if i = ℓ,
ebir ⊕ ebir′ =
e0 otherwise.
So, since e0 = 0,
cr ⊕ cr ′ =

k
M

(ebir ⊕ ebir′ ) · Xi = ej · Xℓ = Xℓj .

i=1

So the user recovers the bit Xℓj correctly for any j with 1 ≤ j ≤ R.
For privacy, we note that Sr receives a uniformly distributed vector qr ∈ (ZR+1 )k in all
circumstances. Since the distribution of qr does not depend on ℓ, no information about ℓ
is received by Sr .
The calculations of the total storage and download complexity are identical to those
in the proof of Theorem 3.1. For the upload complexity, note that it takes just log(R + 1)
bits to specify an element of ZR+1 . Since each server receives k elements from ZR+1 , and
since there are R + 1 servers, the upload complexity of the scheme is k(R + 1) log(R + 1)
as claimed.

3.2

Optimal download complexity for a small number of servers

For an integer n such that (n − 1) | R, we now describe an n-server PIR scheme with
n
download complexity n−1
R bits. By Theorem 2.5, this construction provides schemes
with an optimal download complexity for n servers, provided the number k of records is
sufficiently large. This construction is closely related to Construction 2 above. Indeed,
the construction below is a generalisation of Construction 2 where we work with strings
rather than single bits.
We first define an analogue of the bits eb · Xi computed by servers in Construction 2. We divide an R-bit string X into n − 1 blocks, each of size R/(n − 1). For
b ∈ {1, 2, . . . , n − 1} we write πb (X) for the bth block (so πb (X) is an R/(n − 1)-bit
string). We write π0 (X) for the all-zero string 0R/(n−1) of length R/(n − 1).
Construction 3. Let n be an integer such that (n − 1) | R. Suppose there are n servers,
each storing the entire database.
• A user who requires Record ℓ chooses k elements a1 , a2 , . . . , ak ∈ Zn uniformly
and independently at random. For r = 1, . . . , n, server Sr is sent the vector qr =
(b1r , b2r , . . . , bkr ) ∈ Zkn , where
(
ai + r mod n if i = ℓ,
bir =
ai
otherwise.
15

• Server Sr returns the R/(n − 1)-bit string cr =

Lk

i=1

πbir (Xi ).

• To recover the j th block of Xℓ , the user finds the integers r and r ′ such that bℓr = 0
and bℓr′ = j. The user then computes cr ⊕ cr′ .
Theorem 3.3. Construction 3 is an n-server PIR scheme with download complexity
n
R. The scheme has upload complexity nk log n and total storage is nkR.
n−1
Proof. Exactly as in the proof of Theorem 3.2, we first note that r and r ′ exist since
bℓr ∈ {0, 1, 2 . . . , n − 1} takes on each possible value once as r ∈ {0, 1, . . . , n} varies. Also
note that when i 6= ℓ
πbir (Xi ) ⊕ πbir′ (Xi ) = πai (Xi ) ⊕ πai (Xi ) = 0R/(n−1) ,
but when i = ℓ
πbir (Xi ) ⊕ πbir′ (Xi ) = π0 (Xi ) ⊕ πj (Xi ) = πj (Xi ) = πj (Xℓ ).
Hence
cr ⊕ cr ′ =

k
M

(πbir (Xi ) ⊕ πbir′ (Xi )) = πj (Xℓ ).

i=1

So the user recovers the jth block of Xℓ correctly for any j with 1 ≤ j ≤ (n − 1).
For privacy, we note that Sr receives a uniformly distributed vector qr ∈ (Zn )k in all
circumstances. Since the distribution of qr does not depend on ℓ, no information about ℓ
is received by Sr .
The total storage is nkR, since each of n servers stores the entire kR-bit database.
Each query qr is k log n bits long, since an element of Zn may be specified using log n
bits. Hence the upload complexity is nk log n. Since each server returns an R/(n − 1)n
R.
bit string, the download complexity is n−1
Shah et al. [36, Section V] provide PIR schemes with linear (in R) total storage
and with download complexity between 2R and 4R. Their scheme requires a number of
servers which is independent of R (but is linear in k). The construction above (taking
n to be fixed but sufficiently large) shows that for any fixed positive ǫ a PIR scheme
with linear total storage exists with download complexity of (1 + ǫ)R: this is within an
arbitrarily close factor of optimality. Moreover, the number of servers in our construction
is independent of both k and R. However, note that in our scheme each server stores the
whole database, whereas the per server storage of the scheme of Shah et al. is a fixed
multiple of R. This issue is addressed in Construction 4 below.

3.3

Schemes with small per-server storage

We make the observation that the last construction may be used to give families of
schemes with lower per-server storage; see [36, Section V] for similar techniques. The
point here is that we never XOR the first bit (say) from one block with the second bit
(say) of any other block, so we can store these bits in separate servers without causing
problems.
16

More precisely, let s be a fixed integer such that s | R and let t be a fixed integer such
that (t − 1) | s. We divide each record Xi into R/s blocks π1 (Xi ), π2 (Xi ), . . . , πR/s (Xi ),
each s bits long. We then divide each block πj (Xi ) into (t − 1) sub-blocks πj,1 (Xi ),
πj,2 (Xi ), . . . , πj,t−1 (Xi ), each s/(t − 1) bits long. For any i ∈ {1, 2, . . . , k} and any j ∈
{1, 2, . . . , R/s}, we define πj,0 (Xi ) to be the all zero string 0s/(t−1) of length s/(t − 1).
Construction 4. Let s be a fixed integer such that s | R. Let t be a fixed integer such
that (t − 1) | s. Let n = t(R/s). Suppose there are n servers. Each server will store just
ks bits.
• Index the t(R/s) servers by pairs (u, r), where 1 ≤ r ≤ t and where 1 ≤ u ≤ R/s.
Server S(u,r) stores the uth sub-block of every block. So S(u,r) stores πu,j (Xi ) where
1 ≤ i ≤ k and 1 ≤ j ≤ t − 1. Note that each server stores k(t − 1)s/(t − 1) = ks
bits.
• A user who requires Record ℓ chooses k elements a1 , a2 , . . . , ak ∈ Zt uniformly and
independently at random. The server S(k,r) is sent the query qr = (b1r , b2r , . . . , bkr ) ∈
Zkt , where
(
ai + r mod n if i = ℓ,
bir =
ai
otherwise.
(Note that many servers receive the same query.)
• Server S(u,r) returns the s/(t − 1)-bit string c(u,r) = ⊕ki=1 πu,bir (Xi ).
• To recover the jth sub-block of the uth block of Xℓ , the user finds integers r and r ′
such that bℓr = 0 and bℓr′ = j and computes c(u,r) ⊕ c(u,r′ ) .
r
t
s = t−1
R.
Theorem 3.4. Construction 4 is a PIR scheme with download complexity Rs t−1
The scheme has upload complexity nk log t = (tkR/s) log t and total storage nks = tkR
bits.

Proof. As in the proofs of Theorems 3.2 and 3.3, privacy follows since Su,r always receives
a uniformly distributed vector qr ∈ Zkt as a query. For correctness, observe that when
i 6= ℓ
πu,bir (Xi ) ⊕ πu,bir′ (Xi ) = πu,ai (Xi ) ⊕ πu,ai (Xi ) = 0s/(t−1) ,
but when i = ℓ
πu,bir (Xi ) ⊕ πu,bir′ (Xi ) = πu,0 (Xi ) ⊕ πu,j (Xi ) = πu,j (Xi ) = πu,j (Xℓ ).
Hence
c(u,r) ⊕ c(u,r′ )

k
M
=
(πu,bir (Xi ) ⊕ πu,bir′ (Xi )) = πu,j (Xℓ ).
i=1

So the user can indeed compute the j-th sub-block of the u-th block as claimed.
It is easy to calculate the upload complexity, download complexity and total storage
complexity as before, remembering that each server stores ks bits rather than the entire
database.

17

By fixing t and s to be sufficiently large integers, we can see that for all positive ǫ we
have a family of schemes with download complexity at most (1 + ǫ)R, with total storage
linear in the database size, with a linear (in R) number of servers, and where the per
server storage is independent of R. So this family of schemes has a better download
complexity and per-server storage than Shah et al. [36, Section V], and is comparable in
terms of both the number of servers and total storage.
The servers may be divided into t classes S1 , S2 , . . . , St , where
Sr = {S(1,r) , S(2,r) , . . . , S(R/s,r) }.
Since servers in the same class receive the same query, the above construction still works if
some of the servers within a class are merged. If this is done, the storage requirements of
each merged server is increased, the download complexity and total storage are unaffected,
and the number of servers required and upload complexity are reduced. So various tradeoffs are possible using this technique.

3.4

An explicit asymptotically optimal scheme

Sun and Jafar [39] describe a PIR scheme that has the best possible asymptotic download
complexity, as R → ∞. Their scheme is constructed in a recursive fashion. In this
subsection, we describe an explicit, non-recursive, scheme with the same parameters as
the Sun and Jafar scheme. Our scheme has the advantages of a more compact description,
and (we believe) a proof that is significantly more transparent.
Our scheme is described in detail in Construction 5 below. But, to aid understanding,
we first provide an overview of the scheme.
Suppose that nk divides R. We split an R-bit string X into nk blocks, each of length
R/nk . For j ∈ {1, 2, . . . , nk } we write πj (X) for the j-th block of X, and we write π0 (X)
k
for the all zero block 0R/n .
k
Let
PkV be the set of all non-zero strings v = v1 v2 v3 . . . vk ∈ {0, 1, 2, . . . , n − 1} such
that i=1 vi ≡ 0 mod n − 1. (Note that our sum is taken modulo n − 1, not modulo n.)
Let W = {1, 2, . . . , n} × V.
There are n servers in the scheme, each storing the whole database. Server Sr receives
a query consisting of integers bi (r, v) ∈ {1, 2, . . . , nk } where i ∈ {1, 2, . . . , k} and v ∈
V. The server replies with |V| strings, each of length R/nk . Each string is a linear
combination of blocks, at most one block from each record (the choice of each block
being determined by an integer bi (r, v): see (3) below). From the perspective of Sr , the
distribution of the integers bi (r, v) does not depend on ℓ, enabling us to attain privacy.
However, the user chooses these integers so that bi (r, v) and bi (r ′ , v′) are sometimes
constrained to be equal when r 6= r ′ . This is done in such a way that the user can
reconstruct Record ℓ from the replies of the servers. To describe the constraints the user
imposes, which of course depend on ℓ, we define a graph Γ[ℓ] on the set W, and constrain
bi (r, v) and bi (r ′ , v′ ) to be equal when (r, v) and (r ′ , v′ ) lie in the same component of Γ[ℓ] .
We now give details of the scheme. We begin by describing the graph Γ[ℓ] (see Figure 1)
[ℓ]
and by detailing some of its structure. Let ℓ ∈ {1, 2, . . . , k}. Let W1 consist of those
[ℓ]
elements (r, v) ∈ W such that vℓ 6= 0, and let W2 consist of the elements such that
vℓ = 0. The graph Γ[ℓ] is defined on the vertex set W, and is bipartite with parts
18

[ℓ]

W1

[ℓ]

W2

(1, 200)
(3, 121)

(1, 011)

(2, 211)
(2, 121)

(3, 011)

(1, 211)
(3, 222)

(2, 022)

(1, 112)
(3, 220)

(2, 020)

(1, 110)
(3, 202)

(2, 002)
..
.

(1, 101)
..
.

Figure 1: Part of the graph Γ[ℓ] when n = k = 3 and ℓ = 1.

19

[ℓ]

[ℓ]

[ℓ]

[ℓ]

W1 and W2 . We draw at most one edge from each element (r, v) ∈ W1 into W2
as follows. If vℓ is the only non-zero component of v, we draw no edge from (r, vℓ ), so
we have an isolated vertex. Suppose two or more components of v are non-zero. We
define ℓ2 ∈ {1, 2, . . . , k} to be the next component in v after the ℓth that is non-zero,
taken cyclically. Let w ∈ {1, 2, . . . , n − 1} be such that w ≡ vℓ + vℓ2 mod n − 1. Define
v′ = v1′ v2′ · · · vk′ by

vi if i ∈ {1, 2, . . . , k} \ {ℓ, ℓ2 },

′
vi = 0 if i = ℓ,


w if i = ℓ2 .

Let r ′ ∈ {1, 2, . . . , n} be such that r ′ ≡ r + vℓ mod n. We join (r, v) to (r ′ , v′ ).
Let C [ℓ] be the set of components of Γ[ℓ] . We note that Γ[ℓ] has exactly n isolated
vertices, namely the vectors of the form (r, v) where r ∈ {1, 2, . . . , n} and where v is the
single vector defined by
(
0
if i 6= ℓ,
vi =
n − 1 if i = ℓ.
[ℓ]

The remaining components in C [ℓ] are stars consisting of a central vertex in W2 and n−1
[ℓ]
other vertices all lying in W1 . Moreover, we note that if (r, v) and (r ′ , v′ ) are distinct
vertices in the same component of Γ[ℓ] then r 6= r ′ .
[ℓ]
We claim that the number of vertices (r, v) ∈ W1 is nk . To see this, we note
that there are n choices for r, and then nk−1 choices for v1 , v2 , . . . , vℓ−1 , vℓ+1 , . . . , vk .
Once these choices are made vℓ ∈ {0, 1, . . . , n − 1} is determined, since vℓ 6= 0 and
P
k
i=1 vi ≡ 0 mod n − 1. This establishes our claim.
[ℓ]
[ℓ]
Since every component of Γ[ℓ] contains a vertex in W1 , we see that |C [ℓ] | ≤ |W1 | = nk .
Indeed, the number of components of Γ[ℓ] is:
[ℓ]

|C [ℓ] | = n + (|W1 | − n)/(n − 1) = n(1 + (nk−1 − 1)/(n − 1)).
Construction 5. Suppose that nk | R. Suppose there are n servers, each storing the
whole database.
• A user who requires Record ℓ proceeds as as follows. In the notation defined above,
for each i ∈ {1, 2, . . . , k} \ {ℓ} the user chooses (uniformly and independently) a
random injection fi : C [ℓ] → {1, 2, . . . , nk }. The user chooses (again uniformly and
[ℓ]
independently) a random bijection ψ : W1 → {1, 2, . . . , nk }.
Define integers bi (r, v) ∈ {0, 1, . . . , nk } for (r, v) ∈ W and i ∈ {1, 2, . . . , k} as
follows. If i 6= ℓ, define
(
0
if vi = 0,
bi (r, v) =
fi (C) if vi 6= 0 and (r, v) lies in the component C ∈ C.
[ℓ]

Note that when i = ℓ we have that vi 6= 0 if and only if (r, v) ∈ W1 . So when i = ℓ
we may define
(
0
if vi = 0,
bi (r, v) =
ψ((r, v)) if vi 6= 0.
20

For r = 1, 2, . . . , n, server Sr is sent the vector qr = (bi (r, v) : v ∈ V, i ∈
{1, 2, . . . , k}).
• The server Sr replies with the blocks
s(r,v) =

k
X

πbi (r,v) (Xi )

(3)

i=1

for all v ∈ V.
[ℓ]

• To recover block j of Xℓ , the user finds (r, v) = ψ −1 (j) ∈ W1 . Let C ∈ C [ℓ] be the
[ℓ]
component containing (r, v). If |C| > 1, let (r ′ , v′ ) ∈ C ∩ W2 . Then (see below for
justification)
(
s(r,v)
if |C| = 1, and
πj (Xℓ ) =
s(r,v) ⊕ s(r′ ,v′ ) if |C| > 1.
Theorem 3.5. Construction 5 is an n-server PIR scheme with download complexity
(1 − 1/nk )(n/(n − 1))R. The total storage of the scheme is nkR. The upload complexity
of the scheme is k 2 nk log n bits.
Proof. We begin by establishing correctness of the scheme. Let (r, v) = ψ −1 (j) and let
C ∈ C [ℓ] be the component containing (r, v). When |C| = 1 we have vi 6= 0 if and only if
i = ℓ and so
k
X
s(r,v) =
πbi (r,v) (Xi ) = πbℓ (r,v) (Xℓ ) = πj (Xℓ ),
i=1

the last equality following since bℓ (r, v) = j. Hence the user recovers the jth block πj (Xℓ )
of Xℓ correctly in this case. Suppose now that C contains two or more vertices, so there
[ℓ]
exists (r ′ , v′ ) ∈ C ∩ W2 . When i 6= ℓ, the values of bi (r, v) and bi (r ′ , v′ ) are equal, since
(r, v) and (r ′ , v′ ) lie in the same component C of Γ[ℓ] and since vi = 0 if and only if vi′ = 0.
Moreover, vℓ 6= 0 and vℓ′ = 0. Hence
s(r,v) ⊕ s(r′ ,v′ ) =

k
X

πbi (r,v) (Xi ) ⊕ πbi (r′ ,v′ ) (Xi )

i=1

= πbℓ (r,v) (Xℓ ) ⊕ πbℓ (r′ ,v′ ) (Xℓ ))
= πψ((r,v)) (Xℓ ) ⊕ π0 (Xℓ ))
= πj (Xℓ ).



So the user recovers the jth block πj (Xℓ ) of Xℓ correctly in this case also. We have
established correctness.
We now aim to establish the security of the scheme. Let A be the set of integer vectors
(ai (v) ∈ {0, 1, . . . , nk } : i ∈ {1, 2, . . . , k}, v ∈ V) with the restrictions that ai (v) = 0 if
and only if vi = 0, and that for any fixed i ∈ {1, 2, . . . , k} the integers ai (v) with vi 6= 0 are
distinct. Let r ∈ {1, 2, . . . , n} be fixed. The query qr = (bi (r, v) : v ∈ V, i ∈ {1, 2, . . . , k})
lies in A, since the functions fi and ψ are injective and since (whether or not i = ℓ) we
have bi (r, v) = 0 if and only if vi = 0. Indeed, the query is uniformly distributed in A.
21

To see this, first note that the functions fi (for i 6= ℓ) and ψ are chosen independently.
The values bℓ (r, v) for vℓ 6= 0 are uniform subject to being distinct since ψ is a randomly
chosen bijection. For i 6= ℓ, the values bi (r, v) for vℓ 6= 0 are uniform subject to being
distinct, since fi is a uniformly chosen injection from C [ℓ] , and since at most one vertex in
any component C ∈ C [ℓ] has its first entry equal to r. Hence the distribution of query qr
is uniform on A as claimed. Since this distribution does not depend on ℓ, privacy follows.
Each server replies with |V| strings, each string of length R/nk . Since there are n
servers, the download complexity is nR|V|/nk . So it remains to determine |V|. For
0 ≤ s ≤ k − 1, there are nk−s−1 elements v1 v2 · · · vk ∈ V that begin with exactly s zeros,
since we may choose vs+2 , vs+3, . . . , vk ∈ P
{0, 1, . . . , n − 1} arbitrarily and then vs+1 is
determined by the fact it is non-zero and kj=1 vj ≡ 0 mod n − 1. So
|V| =

k−1
X

nk−s−1 = (nk − 1)/(n − 1)

s=0

and the download complexity is (1 − 1/nk )(n/(n − 1))R, as required.
We may argue that the total upload complexity is k 2 nk log n as follows. Consider
Server Sr . The integers bi (r, v) with vi = 0 are zero, and so do not need to be sent.
There are exactly knk−1 integers bi (r, v) ∈ {1, 2, . . . , nk } with i ∈ {1, 2, . . . , k} and v ∈ V
with vi 6= 0. (To see this, note that there are k choices for i, and n choices for each
component
v except the ℓth. But then vℓ is determined by the fact that it is non-zero
Pk
and j=1 vj ≡ 0 mod n − 1.) Each integer can be specified using k log n bits, and so the
query qr is k 2 nk−1 log n bits long. Since there are n servers, the total upload complexity
is k 2 nk log n bits, as required.

3.5

An averaging technique

The download complexity of both the PIR scheme due to Sun and Jafar [39] and the
scheme in Construction 5 above is (1 − 1/nk )(n/(n − 1))R. This is only slightly smaller
than the more practical scheme in Construction 3, which has download complexity
(n/(n − 1))R. In fact, the expected number of bits downloaded in Construction 3 is
(1 − 1/nk )(n/(n − 1))R, since a server is asked for an all-zero linear combination of
blocks with probability 1/nk and need not reply in this case. This section describes an
‘averaging’ technique which transforms Construction 3 into a scheme with good (worst
case) download complexity, at the price of a much stronger divisibility constraint on
the length of blocks. This technique will work for a wide range of PIR schemes, but
in the case of Construction 3 it produces a scheme with optimal download complexity
(1 − 1/nk )(n/(n − 1))R. Moreover, the upload complexity is considerably smaller than
the schemes described in [39] and Construction 5.
Before giving the detail, we describe the general idea. Chan, Ho and Yamamoto [12,
Remark 2] observed that a PIR scheme with good upload complexity (but long record
lengths) can be constructed by dividing each record into blocks, then using copies of
a fixed PIR scheme for shorter records operating on each block in parallel. Crucially,
the same randomness (and so the same queries) can be used for each parallel copy of
the scheme, and so upload complexity is low. The ‘averaging’ construction operates in
a similar way. However, rather than using the same randomness we use different but
22

predictably varying randomness for each parallel copy. The server can calculate queries
for each copy of the scheme from just one query, so upload complexity remains low.
But (because queries vary over all possibilities) the resulting scheme has (worst case)
download complexity equal to the average number of bits of download in the Chan, Ho
and Yamamoto construction.
In more detail, we modify Construction 3 as follows. Suppose that nk (n − 1) | R. We
divide an R-bit string X into nk (n − 1) blocks, each of size R/(nk (n − 1)). We index these
blocks by pairs (b, x) where b ∈ {1, 2, . . . , n − 1} ⊆ Zn and x ∈ Zkn . We write π(b,x) (X)
for the block of X that is indexed by (b, x). For any x ∈ Zkn , we write π(0,x) (X) for the
k
all-zero string 0R/(n (n−1)) of length R/(nk (n − 1)).
Construction 6. Let n be an integer such that nk (n − 1) | R. Suppose there are n
servers, each storing the entire database.
• A user who requires Record ℓ chooses k elements a1 , a2 , . . . , ak ∈ Zn uniformly
and independently at random. For r = 1, . . . , n, server Sr is sent the vector qr =
(b1r , b2r , . . . , bkr ) ∈ Zkn , where
(
ai + r mod n if i = ℓ,
bir =
ai
otherwise.
• For r ∈ {1, 2, . . . , n} and x ∈ Zkn , define the string c(r,x) of length R/(nk (n − 1)) by
c(r,x) =

k
M

π(bir +xi ,x) (Xi ).

i=1

The server Sr returns the string c(r,x) , for all x = (x1 , x2 , . . . , xk ) ∈ Zkn such that
x + qr 6= 0. So Sr returns nk − 1 strings.
• To recover the block of Xℓ indexed by a pair (j, x), the user finds the integers r and
r ′ such that bℓr + xℓ = 0 and bℓr′ + xℓ = j. The user then computes c(r,x) ⊕ c(r′ ,x) .
Theorem 3.6. Construction 6 is an n-server PIR scheme with download complexity
n
(1 − 1/nk ) n−1
R. The scheme has upload complexity nk log n and total storage is nkR.
Proof. We begin with the correctness of the scheme. Exactly as in the proof of Theorem 3.3, we note that r and r ′ exist since bℓr + xℓ ∈ {0, 1, 2 . . . , n − 1} takes on each
possible value once as r ∈ {0, 1, . . . , n} varies. Moreover, we note that the string c(r,x) is
all zero if x + qr = 0 (and similarly the string c(r′ ,x) is all zero if x + qr′ = 0) and so the
user always receives enough information to calculate c(r,x) ⊕ c(r′ ,x) .
Let x = (x1 , x2 , . . . , xk ). When i 6= ℓ
π(bir +xi ,x) (Xi ) ⊕ π(bir′ +xi ,x) (Xi ) = π(ai +xi ,x) (Xi ) ⊕ π(ai +xi ,x) (Xi ) = 0R/(n−1) .
When i = ℓ
π(bir +xi ,x) (Xi ) ⊕ π(bir′ +xi ,x) (Xi ) = π(0,x) (Xi ) ⊕ π(j,x) (Xi ) = π(j,x) (Xi ) = π(j,x) (Xℓ ).
23

Hence
c(r,x) ⊕ c(r′ ,x) =

k
M

(π(bir +xi ,x) (Xi ) ⊕ π(bir′ +xi ,x) (Xi )) = π(j,x) (Xℓ ).

i=1

So the user recovers the block of Xℓ indexed by (j, x) correctly.
Privacy follows from the privacy of Construction 3, as the method for generating
queries is identical.
The total storage is nkR, since each of n servers stores the entire kR-bit database.
Each query qr is k⌈log n⌉ bits long, since an element of Zn may be specified using log n bits.
Hence the upload complexity is nk log n. Since there are n servers, and each server returns
n
R.
nk − 1 strings of length R/(nk (n − 1)), the download complexity is (1 − 1/nk ) n−1

4

Conclusions and future work

In this paper, we have used classical PIR techniques to prove bounds on the download
complexity of PIR schemes in modern models, and we have presented various constructions for PIR schemes which are either simpler or perform better than previously known
schemes.
Various interesting problems remain in this area. We first consider schemes with
optimal download complexity:
Question 1. Are there PIR schemes with fewer than R + 1 bits of download complexity?
Our paper, like the rest of the literature, only considers PIR schemes over binary
channels, and in this model the answer is ‘no’. But the proofs of this fact in this paper
and in Shah at el. [36] both use the fact that we are working over binary channels: more
than R bits of download implies that at least R + 1 bits are downloaded. So this problem
is still open if we extend the model to schemes that do not necessarily use binary channels.
We now return to the standard binary channel model.
Question 2. Are there PIR schemes with download complexity R + 1 and total storage
linear in R?
This result was claimed in Shah at el. [36], but we believe that a proof of this is still
not known. A proof of this result might depend on a more detailed structural analysis of
PIR schemes with R + 1 bits of download. As a first step, we believe the following to be
of interest:
Question 3. Theorem 2.7 bounds the probability that only R bits are downloaded in a
PIR scheme with (worst case) download complexity R + 1. Is this bound tight?
We conjecture that the bound could be significantly improved in some cases.
We now consider families of schemes that have good asymptotic complexity as R → ∞.
Question 4. Does there exist a family of schemes with download complexity (1 + o(R))R
and linear total storage?
Note that an affirmative solution to Question 2 will imply an affirmative solution to
this question.
24

Question 5. Are there practical PIR schemes that approach asymptotic capacity as R
grows?
The schemes by Sun and Jafar [37] and the schemes presented in this paper have the
strong restriction that nk must divide R. This makes the schemes impractical for many
parameters.
Question 6. Is there a combinatorial proof that provides a tight upper bound on the
asymptotic capacity as R → ∞?
We comment that the proof in Sun and Jafar [37] uses information theoretic techniques. A combinatorial proof might give extra structural information for schemes meeting the bound, and might improve the bound in non-asymptotic cases.
Finally, we turn to larger questions.
Question 7. Can we find better constructions for PIR schemes?
Schemes are of interest if they improve per server storage, total storage, upload or
download complexity, if the number of servers needed was reduced, or if the divisibility
conditions for parameters such as R are weakened.
Question 8. Can the techniques from this paper be applied to establish bounds or give
constructions in other models, such as those discussed in Subsection 1.3?
Acknowledgement The authors would like to thank Doug Stinson for comments on
an earlier draft.

References
[1] H. Asi and E. Yaakobi, Nearly optimal constructions of PIR and batch codes,
Proc. of IEEE Int. Symp. on Inform. Theory (ISIT), pp. 151–155, Aachen, Germany,
June 2017.
[2] D. Augot, F. Levy-Dit-Vahel, and A. Shikfa, A storage-efficient and robust
private information retrieval scheme allowing few servers, in Cryptology and Network
Security, pp. 222–239, Springer 2014.
[3] K. Banawan and S. Ulukus, The capacity of private information retrieval from
coded databases, arxiv.org/abs/1609.08138, September 2016.
[4] K. Banawan and S. Ulukus, Multi-message private information retrieval: capacity results and near-optimal schemes, arxiv.org/abs/1702.01739, February 2017.
[5] K. Banawan and S. Ulukus, Multi-message private information retrieval: capacity results and near-optimal schemes, Proc. of IEEE Int. Symp. on Inform. Theory
(ISIT), pp. 1898–1902, Aachen, Germany, June 2017.
[6] K. Banawan and S. Ulukus, The capacity of private information retrieval from
byzantine and colluding databases, arxiv.org/abs/1706.01442, June 2017.
25

[7] Z. Bar-Yossef, Y. Birk, T. S. Jayram, and T. Kol, Index coding with side
information, IEEE Trans. Information Theory, 57 (2011), 1479–1494.
[8] S. R. Blackburn and T. Etzion, PIR array codes with optimal PIR rate,
arxiv.org/abs/1607.00235, August 2016.
[9] S. R. Blackburn and T. Etzion, PIR array codes with optimal PIR rate, Proc.
of IEEE Int. Symp. on Information Theory (ISIT), pp. 2658–2662, Aachen, Germany, June 2017.
[10] S. R. Blackburn,T. Etzion, and M. Paterson, PIR schemes with small download complexity and low storage requirements, Proc. of IEEE Int. Symp. on Information Theory (ISIT), pp. 146–150, Aachen, Germany, June 2017.
[11] T. H. Chan, S. Ho, and H. Yamamoto, Private information retrieval for coded
storage, arxiv.org/abs/1410.5489, October 2014.
[12] T. H. Chan, S. Ho, and H. Yamamoto, Private information retrieval for coded
storage, Proc. of IEEE Int. Symp. on Inform. Theory (ISIT), pp. 2842–2846, Hong
Kong, June 2015.
[13] B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan, Private information
retrieval, Journal ACM, 45 (1998), 965–981.
[14] A. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran, Network coding for distributed storage systems, IEEE Trans. Information
Theory, 56 (2010), 4539–4551.
[15] A. Dimakis, K. Ramchandran, Y. Wu, and C. Suh, A survey on network
codes for distributed storage, Proc. of the IEEE, 56 (2011), 476–489.
[16] G. Fanti and K. Ramchandran,, Multi-server private information retrieval over
unsynchronized databases, Fifty-second Annual Allerton Conference, pp. 437–444,
Illinois, October 2014.
[17] G. Fanti and K. Ramchandran, Efficient private information retrieval over unsynchronized databases, IEEE J. on Selected Topics in Signal Processing, 9 (2015),
1229–1239.
[18] A. Fazeli, A. Vardy, and E. Yaakobi, Coded for distributed PIR with low
storage overhead, Proc. of IEEE Int. Symp. on Inform. Theory (ISIT), pp. 2852–
2856, Hong Kong, June 2015.
[19] A. Fazeli, A. Vardy, and E. Yaakobi, Private information retrieval without
storage overhead: coding instead of replication, arxiv.org/abs/1505.06241, May 2015.
[20] S. L. Frank-Fischer, V. Guruswamiy, and M. Wootters, Locality via partially lifted codes, arxiv.org/abs/1704.08627, April 2017.

26

[21] R. Freij-Hollanti, O. Gnilke, C. Hollanti, and D. Karpuk,
Private information retrieval from coded databases with colluding servers,
arxiv.org/abs/1611.02062, November 2016.
[22] P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin, On the locality of
codeword symbol, IEEE Trans. Information Theory, 58 (2012), 6925–6934.
[23] P. Huang, E. Yaakobi, B. Uchikawa, and P. H. Siegel, Linear locally repairable codes with availability, Proc. of IEEE Int. Symp. on Inform. Theory (ISIT),
pp. 1871–1875, Hong Kong, June 2015.
[24] Y. Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai, Batch codes and their
applications, Proc. 36-th ACM Symp. Theory Computing, pp. 262–271, Chicago, IL,
June 2004.
[25] S. Kadhe, B. Garcia, A. Heidarzadeh, S. El Rouayheb, and
A. Sprintson, Private information retrieval with side information,
arxiv.org/abs/1709.00112, September 2017.
[26] M. Karmoose, L. Song, M. Cardone, and C. Fragouli, Private croadcasting: and index coding approach, arxiv.org/abs/1701.04958, January 2017.
[27] S. Kumar, E. Rosnes, and A. G. Amat, Private information retrieval in distributed storage systems using an arbitrary linear code, arxiv.org/abs/1612.07084,
January 2017.
[28] E. Kushilevitz and R. Ostrovsky, Replication is not needed: Single database,
computationally-private information retrieval, Proc. 38-th IEEE Symp. Foundations
Computer Science, pp. 364–373, Miami Beach, FL, October 1997.
[29] H.-Y. Lin and E. Rosnes, Lengthening and extending binary private information
retrirval codes, arxiv.org/abs/arXiv:1707.03495, July 2017.
[30] S. Rao and A. Vardy, Lower bound on the redundancy of PIR codes,
arxiv.org/abs/1605.01869, May 2016.
[31] A. S. Rawat, D. S. Papailiopoulos, A. G. Dimakis, and S. Vishwanath,
Locality and availability in distributed storage, Proc. of IEEE Int. Symp. on Inform.
Theory (ISIT), pp. 631–635, Honolulu, HI, June 2014.
[32] A. Rawat, D. S. Papailiopoulos, A. G. Dimakis, and S. Vishwanath,
Locality and availability in distributed storage, IEEE Trans. Information Theory,
62 (2016), 4481–4493.
[33] A. S. Rawat, Z. Song, A. G. Dimakis, and A. Gaal, Batch codes through
dense graphs without short cycles, IEEE Trans. Information Theory, 62 (2016),
1592–1604.
[34] N. Silberstein, T.Etzion, and M. Schwartz, Locality and availability of array
codes constructed from subspaces, arxiv.org/abs/1701.07501, January 2017.
27

[35] N. Silberstein, T.Etzion, and M. Schwartz, Locality and availability of array
codes constructed from subspaces, Proc. of IEEE Int. Symp. on Information Theory
(ISIT), pp. 829–833, Aachen, Germany, June 2017.
[36] N.B. Shah, K.V. Rashmi and K. Ramchandran, One extra bit of download ensures perfectly private information retrieval, in Proc. of IEEE Int. Symp. on Inform.
Theory (ISIT), pp. 856–860, Honolulu, June 2014.
[37] H. Sun and A. Jafar, The capacity of private information retrieval, IEEE Trans.
Information Theory, 63 (2017), 4075–4088.
[38] H. Sun and A. Jafar, The capacity of robust private information retrieval with
colluding databases, arxiv.org/abs/1605.00635, May 2016.
[39] H. Sun and A. Jafar, The capacity of symmetric private information retrieval,
arxiv.org/abs/1606.08828, June 2016.
[40] H. Sun and A. Jafar, Optimal download cost of private information retrieval for
arbitrary message length, arxiv.org/abs/1610.03046, October 2016.
[41] H. Sun and A. Jafar, Multiround private information retrieval: capacity and
storage overhead, arxiv.org/abs/1611.02257, November 2016.
[42] H. Sun and A. Jafar, Private information retrieval from MDS coded
data with colluding servers: settling a conjecture by Preij-Hollanti et al.,
arxiv.org/abs/1701.02257, January 2017.
[43] H. Sun and A. Jafar, Private information retrieval from MDS coded data with
colluding servers: settling a conjecture by Preij-Hollanti et al., Proc. of IEEE Int.
Symp. on Information Theory (ISIT), pp. 1893–1897, Aachen, Germany, June 2017.
[44] R. Tajeddine and S. El Rouayheb, Private information retrieval from MDS
coded data in distributed storage systems, arxiv.org/abs/1602.01458, February 2016.
[45] R. Tajeddine and S. El Rouayheb, Private information retrieval from MDS
coded data in distributed storage systems, Proc. of IEEE Int. Symp. on Information
Theory (ISIT), pp. 1411–1415, Barcelona, Spain, July 2016.
[46] R. Tajeddine and S. El Rouayheb, Robust private information retrieval on
coded data, Proc. of IEEE Int. Symp. on Information Theory (ISIT), pp. 1903–1907,
Aachen, Germany, June 2017.
[47] R. Tajeddine, O. W. Gnilke, D. Karpuk, R. Freij-Hollanti, C. Hollanti, and S. El Rouayheb, Private information retrieval schemes for coded
data with arbitrary collusion patterns, arxiv.org/abs/1701.07636, January 2017.
[48] R. Tandon, The capacity of cache aided private information retrieval,
arxiv.org/abs/arXiv:1706.07035, June 2017.

28

[49] M. Vajha, V. Ramkumar, and P. V. Kumar, Binary, shortened
projective Reed Muller codes for coded private information retrieval,
arxiv.org/abs/arXiv:1702.05074, February 2017.
[50] M. Vajha, V. Ramkumar, and P. V. Kumar, Binary, shortened projective
Reed Muller codes for coded private information retrieval, Proc. of IEEE Int. Symp.
on Information Theory (ISIT), pp. 2653–2657, Aachen, Germany, June 2017.
[51] Q. Wang and M. Skoglund, Symmetric private information retrieval for MDS
coded distributed storage, arxiv.org/abs/1610.04530, October 2016.
[52] Q. Wang and M. Skoglund, Secure symmetric private information retrieval from
colluding databases with adversaries, arxiv.org/abs/1707.02152, July 2017.
[53] Q. Wang and M. Skoglund, Linear symmetric private information retrieval for
MDS coded distributed storage with colluding servers, arxiv.org/abs/1708.05673,
August 2017.
[54] S. Yekhanin, Private information retrieval, Comm. ACM, 53 (2010), 68–73.
[55] Y. Zhang and G. Ge, A general private information retrieval from MDS coded
databases with colluding servers, arxiv.org/abs/1704.06875, April 2017.
[56] Y. Zhang and G. Ge, Multi-file private information retrieval scheme for MDS
coded databases with colluding servers, arxiv.org/abs/1704.06875, May 2017.
[57] Y. Zhang, X. Wang, N. Wei, and G. Ge, On private information retrieval array
codes, arxiv.org/abs/1609.09167, September 2016.
[58] Z. Zhang and J. Xu, Private multi-file retrieval from distributed databases,
arxiv.org/abs/1704.00250, April 2017.

29

