The Capacity of Private Computation

arXiv:1710.11098v3 [] 25 Nov 2017

Hua Sun and Syed A. Jafar

Abstract
We introduce the problem of private computation, comprised of N distributed and noncolluding servers, K independent datasets, and a user who wants to compute a function of the
datasets privately, i.e., without revealing which function he wants to compute, to any individual
server. This private computation problem is a strict generalization of the private information
retrieval (PIR) problem, obtained by expanding the PIR message set (which consists of only
independent messages) to also include functions of those messages. The capacity of private
computation, C, is defined as the maximum number of bits of the desired function that can
be retrieved per bit of total download from all servers. We characterize the capacity of private
computation, for N servers and K independent datasets that are replicated at each server, when
the functions to be computed are arbitrary linear combinations of the datasets. Surprisingly, the
−1
capacity, C = 1 + 1/N + · · · + 1/N K−1
, matches the capacity of PIR with N servers and
K messages. Thus, allowing arbitrary linear computations does not reduce the communication
rate compared to pure dataset retrieval. The same insight is shown to hold even for arbitrary
non-linear computations when the number of datasets K → ∞.

Hua Sun (email: hua.sun@unt.edu) is with the Department of Electrical Engineering at the University of North
Texas. Syed A. Jafar (email: syed@uci.edu) is with the Center of Pervasive Communications and Computing (CPCC)
in the Department of Electrical Engineering and Computer Science (EECS) at the University of California Irvine.

1

1

Introduction

Motivated by privacy concerns in distributed computing applications, we introduce the private
computation (PC) problem, where a user wishes to privately compute a function of datasets that
are stored at distributed servers. Specifically, K datasets are stored at N non-colluding servers,
and a user wishes to compute a function of these datasets. A private computation scheme allows
the user to compute his desired function, while revealing no information to any individual server
about the identity of the desired function. The achievable rate of a private computation scheme is
the ratio of the number of bits of the desired function that the user is able to retrieve, to the total
number of bits downloaded from all servers. The capacity of private computation is the supremum
of achievable rates.
The private computation problem is a strict generalization of the private information retrieval
(PIR) problem, where one of the K datasets is desired by the user, i.e., the function to be computed
simply returns the desired dataset. The capacity was characterized recently for PIR in [1] and for
several of its variants in [2–7]. In the PIR setting, the datasets are called messages and all messages
are independent. Private computation may also be viewed as PIR with dependent messages, where
each possible function that may be desired by a user is interpreted as a dependent message, i.e., a
message whose value depends on other messages.
Our main result is the characterization of the capacity of private computation, where a user
wishes to compute arbitrary linear combinations of K independent datasets (messages), replicated
at N servers. Note that if the user can only choose one of M = K independent linear combinations,
then the setting is equivalent to the PIR problem with K messages and N servers. From [1], we
−1
. Surprisingly,
know that the capacity of PIR in this setting is equal to 1 + 1/N + · · · + 1/N K−1
we show that even if the user wishes to compute arbitrary linear combinations
of
the
K
datasets, the
−1
, i.e., in terms of capacity,
capacity of private computation remains 1 + 1/N + · · · + 1/N K−1
arbitrary linear computation incurs no additional penalty.
The capacity achieving scheme for private computation that is presented in this work is a
highly structured adaptation of the capacity achieving scheme for PIR that was introduced in [1].
Specifically, the private computation scheme utilizes an optimized symbol index structure, and a
sophisticated assignment of signs (‘+’ or ‘−’) to each symbol in order to optimally exploit the linear
dependencies. A surprising feature of the optimal private computation scheme is that the query
construction does not depend on the linear combining coefficients that define the set of possible
functions that may be computed by the user.
Finally, we note that following the ArXiv posting of our capacity results for the elemental
setting of private computation with N = 2, K = 2, arbitrary M (first version of this paper, posted
October 30, 2017), an independent work on ‘private function retrieval’ was posted on ArXiv by
Mirmohseni and Maddah-Ali (reference [8], posted November 13, 2017). Since the private function
retrieval problem is identical to the private computation problem, it is worthwhile to compare and
contrast the two works. To this end, we note that while there is no overlap in the achievable
schemes proposed in the two works, the general capacity result presented in this paper subsumes
and strictly improves upon the results of [8]. In particular, [8] presents two results. The first result
of [8] is a capacity characterization of private computation when N = 2, K is arbitrary, and the
set of functions that may be computed is comprised of all possible linear combinations of the K
message sets — albeit limited to binary coefficients. This result is recovered as a special case of
our general capacity result in this paper. In this case, although the achievable schemes of [8] and
this work are different, they both achieve capacity. The second result of [8] is an extension of their
2

achievable scheme to general N, K and non-binary combining coefficients, although the optimality
of the achievable scheme is left open. For this general case, our capacity characterization implies
that the achievable scheme of [8] is strictly suboptimal.
Notation: For integers Z1 , Z2 , Z1 ≤ Z2 , we use the compact notation [Z1 : Z2 ] = {Z1 , Z1 +
1, · · · , Z2 }. For an index set I = {i1 , i2 · · · , ik }, the notation AI represents the set {Ai , i ∈ I}.
The notation X ∼ Y is used to indicate that X and Y are identically distributed. For a matrix
A, AT represents its transpose and |A| represents its determinant. For a set S, |S| represents its
cardinality. For sets S1 , S2 , we define S1 /S2 as the set of elements that are in S1 and not in S2 .

2

Problem Statement and Definitions

Consider the private computation problem with N servers and K datasets. We will assume that
the datasets are replicated at all servers, that the servers do not collude, and that the functions
to be computed are linear combinations of the messages. We will focus primarily on this basic
setting which opens the door to numerous other open problems through various generalizations,
e.g., coded storage instead of replication, colluding servers, symmetric privacy requirements, nonlinear functions, etc.
The K datasets, denoted by Wd1 , · · · , WdK ∈ FpL×1 , are each comprised of L i.i.d. uniform
symbols from a finite field Fp . In p-ary units,
H(Wd1 ) = · · · = H(WdK ) = L,

(1)

H(Wd1 , · · · , WdK ) = H(Wd1 ) + · · · + H(WdK ).

(2)

A linear combination of these datasets is represented as a dependent message,
Wm = vm [Wd1 , · · · , WdK ]T = vm(1) Wd1 + · · · + vm(K) WdK , m ∈ [1 : M ]

(3)

where vm = [vm(1) , · · · , vm(K) ] consists of K constants from Fp , and ‘+’ represents element-wise
addition over Fp . Without loss of generality, we assume M ≥ K and [v1 ; v2 ; · · · ; vK ] = IK , where
IK is the K × K identity matrix. Thus, (W1 , W2 , · · · , WK ) = (Wd1 , Wd2 , · · · , WdK ).
There are N servers and each server stores all datasets Wd1 , · · · , WdK . A user privately generates
θ ∈ [1 : M ] and wishes to compute (retrieve) Wθ while keeping θ a secret from each server.
Depending on θ, there are M strategies that the user could employ to privately compute his
desired function. For example, if θ = m, then in order to compute Wm , the user employs N
[m]
[m]
queries, Q1 , · · · , QN . Since the queries are determined by the user with no knowledge of the
realizations of the messages, the queries must be independent of the messages,1
[m]

[m]

∀m ∈ [1 : M ], I(W1 , · · · , WM ; Q1 , · · · , QN ) = 0.
[m]

(4)

[m]

The user sends Qn , n ∈ [1 : N ] to the nth server. Upon receiving Qn , the nth server generates
[m]
[m]
an answering string An , which is a function of Qn and the data stored (i.e., all the messages),
[m]
∀m ∈ [1 : M ], n ∈ [1 : N ], H(A[m]
n |Qn , W1 , · · · , WM ) = 0.
[m]

Each server returns to the user its answer An . From all the information that is now available to
[m]
[m]
[m]
[m]
the user (A1 , · · · , AN , Q1 , · · · , QN ), the user decodes the desired message Wm according to a
1
The message sets (Wd1 , · · · , WdK ) and (W1 , W2 , · · · , WM ) are invertible functions of each other, so, e.g., conditioning on one is the same as conditioning on the other.

3

decoding rule that is specified by the private computation scheme. Let Pe denote the probability
of error achieved with the specified decoding rule.
To protect the user’s privacy, the M strategies must be indistinguishable (identically distributed)
from the perspective of each server, i.e., the following privacy constraint must be satisfied ∀n ∈ [1 :
N ], ∀m ∈ [1 : M ],
[1]
[m]
[m]
[Privacy] (Q[1]
n , An , W1 , · · · , WM ) ∼ (Qn , An , W1 , · · · , WM ).

(5)

The PC rate characterizes how many symbols of desired information are computed per downloaded symbol, and is defined as follows.
R,

L
D

(6)

where D is the expected value (over random queries) of the total number of symbols downloaded
by the user from all servers.
A rate R is said to be ǫ-error achievable if there exists a sequence of private computation
schemes, indexed by L, each of rate greater than or equal to R, for which Pe → 0 as L → ∞. Note
that for such a sequence of private computation schemes, from Fano’s inequality, we have
[m]

[m]

[m]

[m]

[Correctness] H(Wm |A1 , · · · , AN , Q1 , · · · , QN ) = o(L)

(7)

where any function of L, say f (L), is said to be o(L) if limL→∞ f (L)/L = 0. The supremum of
ǫ-error achievable rates is called the capacity C.

3

Capacity of Private Computation

Theorem 1 states our main result.
Theorem 1 For the private computation problem where a user wishes to privately retrieve one
of M arbitrary2 linear combinations
of K independent datasets from N servers, the capacity is
−1
K−1
.
C = 1 + 1/N + · · · + 1/N

When M = K, the problem reduces to the PIR
−1 problem with N servers and K messages, for
[1]. Adding more computation requirements
which the capacity is 1 + 1/N + · · · + 1/N K−1
M > K can not help (surprisingly it does not hurt either), so the converse of Theorem 1 is implied.
We only need to prove the achievability, which is presented in Section 4.
It is quite surprising that increasing the number of messages by including arbitrary linear
combinations of K datasets does not reduce capacity for all linear computation settings. A natural
question then is whether this insight holds more broadly. Remarkably, the insight is also true for
arbitrary non-linear computations, when the number of datasets is large (K → ∞). It turns out
that in this case, again the capacity of private computation is equal to the capacity of PIR. This
supplemental result is rather straightforward and is stated in the following theorem.

Theorem 2 For the private computation problem with K independent datasets, Wk , k ∈ [1 : K],
H(Wk ) = L, arbitrary N servers and M − K arbitrary (possibly non-linear) dependent messages,
Wm , m ∈ [K + 1 : M ], H(Wm | Wk , k ∈ [1 : K]) = 0, H(Wm ) ≤ L, if K → ∞, then the capacity
of private computation C → 1 − 1/N , which is the capacity of PIR with K → ∞ messages and N
servers.
2
Note that M ≥ K and the M linear combinations contain K linearly independent ones, so that
H(W1 , W2 , · · · , WM ) = H(Wd1 , Wd2 , · · · , WdK ) = KL.

4

Proof: For Theorem 2, the achievability is identical to the symmetric PIR3 scheme of Theorem 1
in [3] (see also [9, 10]), where the M functions are viewed as the messages in the symmetric PIR
problem and common randomness is not used. The dependence of the messages has no impact on
privacy or correctness of that scheme. The converse follows from the converse of regular PIR [1]
because restricting the message set to Wk , k ∈ [1 : K] cannot reduce capacity.

4

The Achievable Scheme

The private computation scheme needed for Theorem 1 builds upon and significantly generalizes
the capacity achieving PIR scheme presented in [1, 11]. If we ignore the dependence of the messages in the private computation problem and directly use the PIR scheme (capacity achieving for
−1
, which is strictly
independent messages) in [1], the rate achieved is 1 + 1/N + · · · + 1/N M −1
−1
K−1
(independent of M ), the capacity of private computation.
less than 1 + 1/N + · · · + 1/N
To optimally exploit the dependence of the messages, we start with the original PIR scheme of [1]
and incorporate two new ideas. For ease of reference, let us denote the original PIR scheme of [1]
as PIR1 .
(1) Index assignment: Additional structure is required from symbol indices within the queries
because dependence only exists across message symbols associated with the same index. This
requirement yields a new PIR scheme, that we will denote as PIR2 . If the messages are
independent, then in terms of downloads PIR2 is as efficient as PIR1 , i.e., they are both
capacity achieving schemes.
(2) Sign assignment: The index structure of PIR2 seems essential to accommodate dependent
messages. By itself, however, it is not sufficient.4 For example, the queries in both PIR1 and
PIR2 are comprised of sums of symbols. Depending on the form of message dependencies,
more sophisticated forms of combining symbols within queries may be needed. For our present
purpose, with linear message dependencies, we will need both sums and differences. To this
end, we need to carefully assign a ‘sign’ (‘+’ or ‘−’) to each symbol. The sign assignment
produces the optimal private computation scheme, denoted PC , for Theorem 1.
To present these schemes, we need to introduce the following notation. Let π represent a
permutation over [1 : L]. For all m ∈ [1 : M ], i ∈ [1 : L] let
um (i) = σi Wm (π(i))

(8)

Thus, Wm (π(i)) are the symbols from message Wm , permuted by π, and um (i) are the corresponding
signed versions obtained by scaling with σi ∈ {+1, −1}. Since both m and i are indices in um (i),
if there is a potential for confusion, we will refer to m as the ‘message index’ and i as the ‘symbol
index’. Note that the same permutation is applied to all messages, and the same sign variable σi
is applied to symbols from different messages that have the same symbol index. Both π and σi are
generated privately, independently and uniformly by the user such that they are not known to the
servers.
3
Theorem 2 extends immediately to the symmetric private computation problem, where the user is prohibited
from learning anything beyond the desired function.
4
Remarkably, if the field Fp in (3) is restricted to F2 then PIR2 is sufficient to achieve the capacity of private
computation. This is because sign-assignments are redundant over F2 , i.e., +x and −x are equivalent over F2 .

5

We will refer to the message Wm equivalently as the message um . To illustrate the key ideas
we will use the special K = 2, M = 4, N = 2 setting as our running example in this work.

Example A
Suppose the M = 4 functions on the K = 2 datasets that we wish to compute over N = 2
servers are the following.
W1 = Wd1
W2 = Wd2
W3 = v3 Wd1 + v3′ Wd2
W4 = v4 Wd1 + v4′ Wd2

(9)

Each message consists of L = N M = 16 symbols from Fp . The specialized setting allows us to
use a simpler notation as follows.
(ai , bi , ci , di ) = (u1 (i), u2 (i), u3 (i), u4 (i))
The notation is simpler because we only have symbol indices. Message indices are not necessary
in this toy setting because a different letter is used for each message.
We will start with the query structure of the PIR scheme, which we will modify using the two
principles outlined earlier, to obtain the private computation scheme. First we explain the index
assignment step.

4.1

Index Assignment: PIR2

In this section, we introduce the PIR2 scheme, built upon PIR1 by an index assignment process.
The index assignments are necessary because unlike PIR1 where independent permutations are
applied to symbols from each message, in PIR2 the same permutation is applied to symbols from
every message. For ease of exposition, we will first illustrate the index assignment process through
Example A, and then present the general algorithm for arbitrary K, M, N . Since we do not use
sign assignments in PIR2 , the σi are redundant for this scheme. Without loss of generality, the
reader may assume σi = 1 for all i for PIR2 .

6

4.1.1

Example A

Suppose the desired message is W1 , i.e., θ = 1. Recall the query structure of PIR1 , where we have
left some of the indices of undesired symbols undetermined.
θ=1
Server 1

Server 2

a1 , b1 , c1 , d1
a2 , b2 , c2 , d2
a 3 + b2
a 6 + b1
a4 + c2
a7 + c1
a5 + d2
a8 + d1
b∗ + c∗
b∗ + c∗
b∗ + d∗
b∗ + d∗
c∗ + d∗
c∗ + d∗
a9 + b∗ + c∗
a12 + b∗ + c∗
a10 + b∗ + d∗
a13 + b∗ + d∗
a11 + c∗ + d∗
a14 + c∗ + d∗
b∗ + c∗ + d∗
b∗ + c∗ + d∗
a15 + b∗ + c∗ + d∗ a16 + b∗ + c∗ + d∗
Note that the first row of the query to Server n, n ∈ {1, 2}, is an , bn , cn , dn , just as in PIR1 . In
PIR1 , the permutations are chosen independently for each message, so that cn , dn are not necessarily
functions of an , bn . However, here, because we apply the same permutation to every message, and
because the same sign σn is applied to an , bn , cn , dn , the dependence of messages is preserved in
these symbols. In particular, cn = v3 an + v3′ bn , dn = v4 an + v4′ bn , and H(an , bn , cn , dn ) = 2 p-ary
units.
The next three rows of the queries to each server are 2-sums (i.e., sums of two symbols) that are
also identical to PIR1 , because these queries exploit the side-information from the other server to
retrieve new desired symbols. However, notice that because permutations of message symbols are
identical, there is a special property that holds here that is evident to each server. For example,
Server 1 notes that the 2-sums that contain ai symbols, i.e., a3 + b2 , a4 + c2 , a5 + d2 have the same
index for the other symbol, in this case the index 2. Since we do not wish to expose the identity
of the desired message, the same property must hold for all messages. This observation forces the
index assignments of all remaining 2-sums.
For example, let us consider the next query term, b∗ + c∗ , from, say, Server 1. Since b2 was
mixed with a3 in the query a3 + b2 , all 2-sums that include some bi must have index 3 for the other
symbol. Similarly, since c2 was mixed with a4 , all 2-sums that include some cj must have index 4
for the other symbol. Thus, for Server 1, the only index assignment possible for query b∗ + c∗ is
b4 + c3 . Similarly, the b∗ + d∗ must be b5 + d3 and c∗ + d∗ must be c5 + d4 . All indices for 2-sums
are similarly assigned for Server 2 as well. Thus all indices for 2-sums are settled.
Now let us consider 3-sums. The index assignments for the first three rows for the 3-sums are
again straightforward, because as in [1], these are side-information exploitation terms, i.e., new
desired message symbols must be mixed with the side-information symbols (2-sums) downloaded
from the other server that do not contain desired message symbols. This gives us the following

7

query structure.
θ=1
Server 1

Server 2

a1 , b1 , c1 , d1
a2 , b2 , c2 , d2
a 3 + b2
a 6 + b1
a4 + c2
a7 + c1
a5 + d2
a8 + d1
b4 + c3
b7 + c6
b5 + d3
b8 + d6
c5 + d4
c8 + d7
a9 + b7 + c6
a12 + b4 + c3
a10 + b8 + d6
a13 + b5 + d3
a11 + c8 + d7
a14 + c5 + d4
b∗ + c∗ + d∗
b∗ + c∗ + d∗
a15 + b∗ + c∗ + d∗ a16 + b∗ + c∗ + d∗
Now, again there is a special property that is evident to each server based on the 3-sums that
contain symbols from message a. Suppose we choose any two messages, one of which is a. For
example, suppose we choose a, b and consider Server 1. Then there are 2 instances of 3-sums that
contain a, b, namely, a9 + b7 + c6 and a10 + b8 + d6 . Note that the third symbol in each case has the
same index (6 in this case). The same is true if for example, we choose a, c or a, d instead. The two
3-sums that contain a, c are a9 + b7 + c6 and a11 + c8 + d7 , and in each case the third symbol has the
same index (7 in this case). The two 3-sums that contain a, d are a10 + b8 + d6 and a11 + c8 + d7 ,
and in each case the third symbol has the same index (8 in this case). Again, because we do not
wish to expose a as the desired message, the same property must be true for all messages. This
observation fixes the indices of the remaining 3-sum, b∗ + c∗ + d∗ as follows. The index of d in this
term must be 9 because the two 3-sums that contain b, c must have the same index for the third
symbol, and according to a9 + b7 + c6 this index must be 9. Similarly, the index of c in b∗ + c∗ + d∗
must be 10 because the two 3-sums that contain b, d must have the same index for the third term,
and according to a10 + b8 + d6 it has to be 10. The index of b in b∗ + c∗ + d∗ is similarly determined
by the term a11 + c8 + d7 to be 11. Thus, the query b∗ + c∗ + d∗ from Server 1 must be b11 + c10 + d9 .
Similarly, the query b∗ + c∗ + d∗ from Server 2 must be b14 + c13 + d12 .
The last step is again a side-information exploitation step, for which index assignment is trivial
(new desired symbol must be combined with the 3-sums queried from the other server that do not
contain the desired symbol). Thus, the index assignment is complete, giving us the queries for

8

PIR2 .
θ=1
Server 1

Server 2

a1 , b1 , c1 , d1
a 3 + b2
a4 + c2
a5 + d2
b4 + c3
b5 + d3
c5 + d4
a9 + b7 + c6
a10 + b8 + d6
a11 + c8 + d7
b11 + c10 + d9
a15 + b14 + c13 + d12

a2 , b2 , c2 , d2
a 6 + b1
a7 + c1
a8 + d1
b7 + c6
b8 + d6
c8 + d7
a12 + b4 + c3
a13 + b5 + d3
a14 + c5 + d4
b14 + c13 + d12
a16 + b11 + c10 + d9

For the sake of comparison, here are the queries generated with PIR2 when θ = 3, i.e., when
message W3 (symbols c) is desired.
θ=3
Server 1

Server 2

a1 , b1 , c1 , d1
c3 + a2
c4 + b2
c5 + d2
a 4 + b3
a5 + d3
b5 + d4
c9 + a7 + b6
c10 + a8 + d6
c11 + b8 + d7
a11 + b10 + d9
c15 + a14 + b13 + d12

a2 , b2 , c2 , d2
c6 + a1
c7 + b1
c8 + d1
a 7 + b6
a8 + d6
b8 + d7
c12 + a4 + b3
c13 + a5 + d3
c14 + b5 + d4
a14 + b13 + d12
c16 + a11 + b10 + d9

To see why the queries for θ = 1 are indistinguishable from the queries for θ = 3 under PIR2 , say
from the perspective of Server 1, note that the former is mapped to latter under the permutation
on [1 : L] that maps
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
−→ (1, 3, 4, 2, 5, 9, 6, 10, 7, 11, 8, 12, 15, 13, 14, 16)
The permutation π is chosen privately and uniformly by the user independent of θ, so both queries
are equally likely whether θ = 1 or θ = 3.

9

4.1.2

Arbitrary K, M, N

The extension to arbitrary M, N is formally presented5 in the query generation algorithm, Q-Gen,
that appears at the end of this section. Let us summarize the main ideas behind the generalization
with the aid of the illustration in Figure 1 for M = 4, N = 3.
B
1
2

3

4

Server 1
a1 , b1 , c1 , d1
a 4 + b2
Q(1, 2, M) : a5 + c2
a 6 + d2
b5 + c4
Q(1, 2, I) : b6 + d4
c6 + d5
a 7 + b3
Q(1, 3, M) : a8 + c3
a 9 + d3
b8 + c7
Q(1, 3, I) : b9 + d7
c9 + d8
a22 + b11 + c10
Q(1, 2, 1, M) : a23 + b12 + d10
a24 + c12 + d11
Q(1, 2, 1, I) : b24 + c23 + d22
a25 + b14 + c13
Q(1, 2, 3, M) : a26 + b15 + d13
a27 + c15 + d14
Q(1, 2, 3, I) : b27 + c26 + d25
a28 + b17 + c16
Q(1, 3, 1, M) : a29 + b18 + d16
a30 + c18 + d17
Q(1, 3, 1, I) : b30 + c29 + d28
a31 + b20 + c19
Q(1, 3, 2, M) : a32 + b21 + d19
a33 + c21 + d20
Q(1, 3, 2, I) : b33 + c32 + d31
Q(1, 2, 1, 2, M) : a58 + b36 + c35 + d34
Q(1, 2, 1, 3, M) : a59 + b39 + c38 + d37
Q(1, 2, 3, 1, M) : a60 + b42 + c41 + d40
Q(1, 2, 3, 2, M) : a61 + b45 + c44 + d43
Q(1, 3, 1, 2, M) : a62 + b48 + c47 + d46
Q(1, 3, 1, 3, M) : a63 + b51 + c50 + d49
Q(1, 3, 2, 1, M) : a64 + b54 + c53 + d52
Q(1, 3, 2, 3, M) : a65 + b57 + c56 + d55

θ=1
Server 2
a2 ,
b2 , c2 , d2
a10 + b1
Q(2, 1, M) : a11 + c1
a12 + d1
b11 + c10
Q(2, 1, I) : b12 + d10
c12 + d11
a13 + b3
Q(2, 3, M) : a14 + c3
a15 + d3
b14 + c13
Q(2, 3, I) : b15 + d13
c15 + d14
a34 + b5 + c4
Q(2, 1, 2, M) : a35 + b6 + d4
a36 + c6 + d5
Q(2, 1, 2, I) : b36 + c35 + d34
a37 + b8 + c7
Q(2, 1, 3, M) : a38 + b9 + d7
a39 + c9 + d8
Q(2, 1, 3, I) : b39 + c38 + d37
a40 + b17 + c16
Q(2, 3, 1, M) : a41 + b18 + d16
a42 + c18 + d17
Q(2, 3, 1, I) : b42 + c41 + d40
a43 + b20 + c19
Q(2, 3, 2, M) : a44 + b21 + d19
a45 + c21 + d20
Q(2, 3, 2, I) : b45 + c44 + d43
Q(2, 1, 2, 1, M) : a66 + b24 + c23 + d22
Q(2, 1, 2, 3, M) : a67 + b27 + c26 + d25
Q(2, 1, 3, 1, M) : a68 + b30 + c29 + d28
Q(2, 1, 3, 2, M) : a69 + b33 + c32 + d31
Q(2, 3, 1, 2, M) : a70 + b48 + c47 + d46
Q(2, 3, 1, 3, M) : a71 + b51 + c50 + d49
Q(2, 3, 2, 1, M) : a72 + b54 + c53 + d52
Q(2, 3, 2, 3, M) : a73 + b57 + c56 + d55

Server 3
a3 , b3 , c3 , d3
a16 + b1
Q(3, 1, M) : a17 + c1
a18 + d1
b17 + c16
Q(3, 1, I) : b18 + d16
c18 + d17
a19 + b2
Q(3, 2, M) : a20 + c2
a21 + d2
b20 + c19
Q(3, 2, I) : b21 + d19
c21 + d20
a46 + b5 + c4
Q(3, 1, 2, M) : a47 + b6 + d4
a48 + c6 + d5
Q(3, 1, 2, I) : b48 + c47 + d46
a49 + b8 + c7
Q(3, 1, 3, M) : a50 + b9 + d7
a51 + c9 + d8
Q(3, 1, 3, I) : b51 + c50 + d49
a52 + b11 + c10
Q(3, 2, 1, M) : a53 + b12 + d10
a54 + c12 + d11
Q(3, 2, 1, I) : b54 + c53 + d52
a55 + b14 + c13
Q(3, 2, 3, M) : a56 + b15 + d13
a57 + c15 + d14
Q(3, 2, 3, I) : b57 + c56 + d55
Q(3, 1, 2, 1, M) : a74 + b24 + c23 + d22
Q(3, 1, 2, 3, M) : a75 + b27 + c26 + d25
Q(3, 1, 3, 1, M) : a76 + b30 + c29 + d28
Q(3, 1, 3, 2, M) : a77 + b33 + c32 + d31
Q(3, 2, 1, 2, M) : a78 + b36 + c35 + d34
Q(3, 2, 1, 3, M) : a79 + b39 + c38 + d37
Q(3, 2, 3, 1, M) : a80 + b42 + c41 + d40
Q(3, 2, 3, 2, M) : a81 + b45 + c44 + d43

Figure 1: Query generation tree according to PIR2 for M = 4 messages and N = 3 servers. Red arrows
indicate the use of the Exploit-SI algorithm, and blue arrows indicate the use of the M-Sym algorithm.
Note that the symbol index assignments in any I partition are uniquely determined by the indices in the
corresponding M partition.
5
Both PIR2 and PC may be viewed as PIR schemes for N servers with M independent messages, so that K is
not directly needed for the query construction. Linear dependencies, if they are present, make some of the queries
redundant, and allow a reduction in the number of downloaded symbols. K only matters because it determines
the number of redundant queries. The specific linear combinations involved in the M functions are also not needed
for the query construction. Thus the query construction has an intriguing ‘universal’ character that exploits linear
dependencies while remaining oblivious to the specifics of those dependencies.

10

The construction of queries for arbitrary N servers is essentially a tree-like expansion of the
N = 2 construction. Therefore, the main insights all come from the N = 2 setting. In fact, the
index assignment process for K messages is comprised of localized operations within the sets of
queries that form the vertices of this tree, that operate exactly as in the N = 2 setting. Let us use
the tree terminology to explain the query construction for arbitrary K, M, N .
The root node (not shown because it carries no information) branches into N vertices at depth
1. These vertices, denoted Q(n1 ), n1 ∈ [1 : N ], represent the first set of queries from each server.
For our example, Q(n1 ) = (an1 , bn1 , cn1 , dn1 ). The queries associated with a vertex are internally
partitioned into two parts. Queries that include a desired message symbol have the identifier M,
and queries that do not include any desired message symbol have the identifier I. For our example
we assume θ = 1, so that the an1 symbols are the desired message symbols. Thus, Q(n1 , M) = an1
and Q(n1 , I) = (bn1 , cn1 , dn1 ).
Each level 1 vertex, Q(n1 ), n1 ∈ [1 : N ], branches into N − 1 vertices6 , Q(n2 , n1 ), n2 ∈ [1 :
N ], n2 6= n1 , to produce level 2 of the tree. The query vertex Q(n2 , n1 ) is assigned to Server n2 .
Thus, level 1 vertices at Server n1 generate level 2 vertices associated with every server other than
Server n1 . As a result each Server n2 , n2 ∈ [1 : N ], has N − 1 level 2 query vertices, denoted
Q(n2 , n1 ) for all n1 ∈ [1 : N ], n1 6= n2 . Level 2 query vertices are all comprised of 2-sums, i.e.,
sums of two symbols, and are internally partitioned into M and I based on whether or not they
contain desired message symbols. The queries in Q(n2 , n1 , M) are generated by exploiting the sideinformation (cf. the Exploit-SI algorithm [11]) contained in the level 1 queries Q(n1 , I), i.e., these
queries are generated by adding a new desired message symbol to each of the symbols in Q(n1 , I).
Thus, the query set Q(n2 , n1 , M) contains M − 1 elements. For our example, these M − 1 = 3
elements are Q(n2 , n1 , M) = {ai + bn1 , aj + cn1 , ak + dn1 }, where i, j, k are new symbol indices that
have not appeared in any queries so far. Next, the queries in Q(n2 , n1 , I) are generated to enforce
message symmetry (cf. the M-Sym algorithm [11]),
does not

 and contain a 2-sum of every type that
include the desired message, for a total of M2−1 elements. For our example, these 32 = 3 queries
are b∗ + c∗ , b∗ + d∗ , c∗ + d∗ . The symbol indices ‘*’ are assigned based on the query set Q(n2 , n1 , M)
as described in our previous example. Since Q(n2 , n1 , M) = {ai + bn1 , aj + cn1 , ak + dn1 } the index
assignment produces Q(n2 , n1 , I) = {bj + ci , bk + di , ck + dj }.
The query tree grows similarly to a total of M levels. A level m query vertex assigned to Server
nm , nm ∈ [1 : N ], is denoted as Q(nm , nm−1 , · · · , n1 ) and is comprised of m-sums that include desired message symbols, denoted Q(nm , nm−1 , · · · , n1 , M), and m-sums that do not include desired
message symbols, denoted Q(nm , nm−1 , · · · , n1 , I). The queries in Q(nm , nm−1 , · · · , n1 , M) are msums generated by adding a new desired message symbol to each query contained in Q(nm−1 , · · · , n1 , I).
This is formalized in the Exploit-SI algorithm. The queries in Q(nm , nm−1 , · · · , n1 , I) are generated by the M-Sym algorithm to force message symmetry, and contain an m-sum of every
type that does not include the desired message, for a total of Mm−1 elements.7 The index assignment for these queries takes place as follows. Consider a query q ∈ Q(nm , nm−1 , · · · , n1 , I),
q = ui1 (∗) + ui2 (∗) + · · · + uim (∗), where ∗ symbols represent indices that need to be assigned.
Note that since this query is in the I partition, θ ∈
/ {i1 , i2 , · · · , im }. The index ∗ for uil (∗),
l ∈ [1 : m], comes from the m-sum query in Q(nm , nm−1 , · · · , n1 , M) that contains symbols from
ui1 , ui2 , · · · , uil−1 , uθ , uil+1 , · · · uim . If the symbol index for uθ in this query is jl , i.e., the query
contains uθ (jl ) then the index jl is assigned to uil . In this way, the M-Sym algorithm assigns all
indices to generate the query q = ui1 (j1 ) + ui2 (j2 ) + · · · + uim (jm ). This completes the description
6
7

A query vertex at level m refers to the set of queries Q(nm , · · · , n1 ) = Q(nm , · · · , n1 , M) ∪ Q(nm , · · · , n1 , I).
If m = M , then Q(nm , nm−1 , · · · , n1 , I) is the empty set.

11

of PIR2 .
The following observations follow immediately from the query construction described above.

1. |Q(nm , nm−1 , · · · , n1 , I)| = Mm−1
−1
2. |Q(nm , nm−1 , · · · , n1 , M)| = |Q(nm−1 , · · · , n1 , I)| = M
m−1

3. The number of level m query vertices Q(nm , nm−1 , · · · , n1 ) assigned to Server i, (such that
nm = i), is (N − 1)m−1 . This is because there are N − 1 valid values for nm−1 that are not
equal to nm = i, there are N − 1 values for nm−2 that are not equal to nm−1 , and so on.


P
M −1
M −1
m−1
.
4. The total number of queries assigned to Server i is M
(N
−
1)
+
m=1
m
m−1
5. If Q and Q′ are two query vertices assigned to the same server, then the symbol indices that
appear in Q are distinct from the symbol indices that appear in Q′ .

The proof of privacy for PIR2 is similar to that for PIR1 in [1]. We note that once the labels
M, I are suppressed, and the queries sorted in lexicographic order, the structure of the queries
from any individual server is fixed regardless of the desired message index θ. For our M = 4, N = 3
example, this is illustrated in Figure 2.
Note that only distinct symbol indices are shown. All the remaining indices can be inferred
uniquely from the ones shown based on the index assignment rule. Thus, the particular query
realization (depending on θ) to Server n, n ∈ [1 : N ], depends only on the realization of these
distinct indices. However, the indices depend on the permutation π which is chosen uniformly and
privately by the user. Thus, all distinct choices for these indices are equally likely, regardless of θ,
and the scheme is private.
The correctness of PIR2 follows directly from the correctness of PIR1 . By the same token, if
the messages are independent then PIR1 and PIR2 have the same rate. Thus, the index assignment
process produces a new PIR scheme, PIR2 , that for independent messages, is equally efficient as
PIR1 in terms of download, i.e., PIR2 is capacity achieving for independent messages. However,
depending upon the form of the message dependencies, it turns out that the ‘sums’ may not be
sufficient and more sophisticated mixing of message symbols may be required. For the linear
dependencies that we consider in this paper, we will need sign assignments, that are explained
next.

12

B
1

2

3

4

Server n
Q(1) : ai1 , b, c, d
aj2,(1,2) + bi2,(1,2)
ak2,(1,2) + c
al2,(1,2) + d
Q(1, 2) :
b+c
b+d
c+d
aj2,(1,3) + bi2,(1,3)
ak2,(1,3) + c
al2,(1,3) + d
Q(1, 3) :
b+c
b+d
c+d
al3,(1,2,1) + bj3,(1,2,1) + ci3,(1,2,1)
as3,(1,2,1) + bk3,(1,2,1) + d
Q(1, 2, 1) :
at3,(1,2,1) + c + d
b+c+d
al3,(1,2,3) + bj3,(1,2,3) + ci3,(1,2,3)
as3,(1,2,3) + bk3,(1,2,3) + d
Q(1, 2, 3) :
at3,(1,2,3) + c + d
b+c+d
al3,(1,3,1) + bj3,(1,3,1) + ci3,(1,3,1)
as3,(1,3,1) + bk3,(1,3,1) + d
Q(1, 3, 1) :
at3,(1,3,1) + c + d
b+c+d
al3,(1,3,2) + bj3,(1,3,2) + ci3,(1,3,2)
as3,(1,3,2) + bk3,(1,3,2) + d
Q(1, 3, 2) :
at3,(1,3,2) + c + d
b+c+d
Q(1, 2, 1, 2) : al4,(1,2,1,2) + bk4,(1,2,1,2) + cj4,(1,2,1,2) + di4,(1,2,1,2)
Q(1, 2, 1, 3) : al4,(1,2,1,3) + bk4,(1,2,1,3) + cj4,(1,2,1,3) + di4,(1,2,1,3)
Q(1, 2, 3, 1) : al4,(1,2,3,1) + bk4,(1,2,3,1) + cj4,(1,2,3,1) + di4,(1,2,3,1)
Q(1, 2, 3, 2) : al4,(1,2,3,2) + bk4,(1,2,3,2) + cj4,(1,2,3,2) + di4,(1,2,3,2)
Q(1, 3, 1, 2) : al4,(1,3,1,2) + bk4,(1,3,1,2) + cj4,(1,3,1,2) + di4,(1,3,1,2)
Q(1, 3, 1, 3) : al4,(1,3,1,3) + bk4,(1,3,1,3) + cj4,(1,3,1,3) + di4,(1,3,1,3)
Q(1, 3, 2, 1) : al4,(1,3,2,1) + bk4,(1,3,2,1) + cj4,(1,3,2,1) + di4,(1,3,2,1)
Q(1, 3, 2, 3) : al4,(1,3,2,3) + bk4,(1,3,2,3) + cj4,(1,3,2,3) + di4,(1,3,2,3)

Figure 2: Structure of queries generated by PIR2 when M = 4 and N = 3.

4.2

Sign Assignment: PC

In this section, we present the sign assignment procedure that produces the private computation
scheme PC from PIR2 for arbitrary K, M, N . We will use Example A to illustrate its steps. The
sign assignment procedure depends on θ. Let us choose θ = 3 to illustrate the process. Note that
σi are now generated uniformly and independently from {+1, −1}.
13

To explain the sign assignment, it is convenient to express each query in lexicographic order.
For example, the query ui1 (j1 )+ui2 (j2 )+· · ·+uim (jm ) is in lexicographic order if i1 < i2 < · · · < im
regardless of the values of the indices j. For our M = 4 example, the query c9 + a7 + b6 is expressed
as a7 + b6 + c9 under lexicographic ordering. Note that the lexicographic order for the M = 4
example is simply the ordering a < b < c < d and the indices do not matter. The position of
the c∗ symbol within this lexicographic ordering of query q will be denoted as ∆c (q), i.e., for the
query q = a7 + b6 + c9 , we have ∆a (q) = 1, ∆b (q) = 2, ∆c (q) = 3 and ∆d (q) = 0 where the 0 value
indicates that a symbol from that message is not present in the query.
Next, the queries are sorted in increasing order of blocks, B, so that the mth block B = m,
contains only m-sums. Each block is partitioned into sub-blocks, S, such that all the queries q in
the same sub-block have the same value of ∆Wθ (q). The sub-blocks are sorted within a block in
descending order of ∆Wθ (q) and numbered S = 1, 2, · · · . With this sorting, the query structure is
represented as follows.
B
1
2

3

4

θ=3
S(∆c )
Server 1
Server 2
···
c1 , a1 , b1 , d1
c2 , a2 , b2 , d2
1(2)
a2 + c3
a1 + c6
1(2)
b2 + c4
b1 + c7
2(1)
c5 + d2
c8 + d1
3(0)
a4 + b3
a7 + b6
3(0)
a5 + d3
a8 + d6
3(0)
b5 + d4
b8 + d7
1(3)
a7 + b6 + c9
a4 + b3 + c12
2(2)
a8 + c10 + d6
a5 + c13 + d3
2(2)
b8 + c11 + d7
b5 + c14 + d4
3(0)
a11 + b10 + d9
a14 + b13 + d12
1(3) a14 + b13 + c15 + d12 a11 + b10 + c16 + d9

The sign assignment algorithm for arbitrary M is comprised of 4 steps.
Algorithm: SignAssign
(Step 1) Consider queries for which ∆Wθ (q) = 0, i.e., queries that do not contain desired
message symbols. The terms in these queries that occupy even positions (in lexicographic
order within each query) are assigned the ‘−’ sign. Thus, for example the query q = a11 +
b10 + d9 changes to q → q ′ = a11 − b10 + d9 after the sign assignment. Notice that the signs are
alternating in the lexicographic ordering of symbols within the query. The sign assignments
for the queries with ∆Wθ (q) = 0 are now settled.
(Step 2) If a symbol is assigned a negative sign in Step 1 then in Step 2 it is assigned a
negative sign everywhere it appears. Note that any undesired symbol that appears in the
query from one server, appears exactly once within the query to each server.

14

For our M = 4 example, at this point we have,
B
1
2

3

4

θ=3
S(∆c )
Server 1
···
c1 , a1 , b1 , d1
1(2)
a2 + c3
1(2)
b2 + c4
2(1)
c5 + d2
3(0)
a4 − b3
3(0)
a5 − d3
3(0)
b5 − d4
1(3)
a7 − b6 + c9
2(2)
a8 + c10 − d6
2(2)
b8 + c11 − d7
3(0)
a11 − b10 + d9
1(3) a14 − b13 + c15 + d12

Server 2
c2 , a2 , b2 , d2
a1 + c6
b1 + c7
c8 + d1
a 7 − b6
a8 − d6
b8 − d7
a4 − b3 + c12
a5 + c13 − d3
b5 + c14 − d4
a14 − b13 + d12
a11 − b10 + c16 + d9

(Step 3) Every query such that ∆Wθ (q) > 0, i.e., every query that contains a desired message
symbol is multiplied by (−1)S+1(θ6=1) , where S is the sub-block index and 1(θ 6= 1) is the
indicator function that takes the value 1 if θ 6= 1 and 0 if θ = 1.
(Step 4) Finally, in Step 4, for each query q that contains a desired symbol, i.e., ∆Wθ (q) > 0,
the desired symbol is assigned the negative sign if it occupies an even numbered position, i.e.,
if ∆Wθ (q) is an even number, and a positive sign if it occupies an odd numbered position, i.e.,
if ∆Wθ (q) is an odd number.
Following this procedure for our running example, we have the final form of the queries as follows.
B
1
2

3

4

θ=3
S(∆c )
Server 1
Server 2
···
c1 , a1 , b1 , d1
c2 , a2 , b2 , d2
1(2)
a2 − c3
a1 − c6
1(2)
b2 − c4
b1 − c7
2(1)
c5 − d2
c8 − d1
3(0)
a4 − b3
a7 − b6
3(0)
a5 − d3
a8 − d6
3(0)
b5 − d4
b8 − d7
1(3)
a7 − b6 + c9
a4 − b3 + c12
2(2)
−a8 − c10 + d6
−a5 − c13 + d3
2(2)
−b8 − c11 + d7
−b5 − c14 + d4
3(0)
a11 − b10 + d9
a14 − b13 + d12
1(3) a14 − b13 + c15 + d12 a11 − b10 + c16 + d9

To complete the illustration for our M = 4 example, let us also present the final queries for

15

θ = 1, 2, 4.
B
1
2

3

4

θ=1
S(∆c )
Server 1
Server 2
···
a1 , b1 , c1 , d1
a2 , b2 , c2 , d2
1(1)
a3 − b2
a6 − b1
1(1)
a4 − c2
a7 − c1
1(1)
a5 − d2
a8 − d1
2(0)
b4 − c3
b7 − c6
2(0)
b5 − d3
b8 − d6
2(0)
c5 − d4
c8 − d7
1(1)
a9 − b7 + c6
a12 − b4 + c3
1(1)
a10 − b8 + d6
a13 − b5 + d3
1(1)
a11 − c8 + d7
a14 − c5 + d4
2(0)
b11 − c10 + d9
b14 − c13 + d12
1(1) a15 − b14 + c13 − d12 a16 − b11 + c10 − d9

θ=2
B S(∆b )
Server 1
1
···
b1 , a1 , c1 , d1
2
1(2)
a2 − b3
2(1)
b4 − c2
2(1)
b5 − d2
3(0)
a4 − c3
3(0)
a5 − d3
3(0)
c5 − d4
3
1(2)
a7 − b9 − c6
1(2)
a8 − b10 − d6
2(1)
b11 − c8 + d7
3(0)
a11 − c10 + d9
4
1(2) a14 − b15 − c13 + d12

Server 2
b2 , a2 , c2 , d2
a1 − b6
b7 − c1
b8 − d1
a7 − c6
a8 − d6
c8 − d7
a4 − b12 − c3
a5 − b13 − d3
b14 − c5 + d4
a14 − c13 + d12
a11 − b16 − c10 + d9

θ=4
S(∆d )
Server 1
···
d1 , a1 , b1 , c1
1(2)
a2 − d3
1(2)
b2 − d4
1(2)
c2 − d5
2(0)
a 4 − b3
2(0)
a5 − c3
2(0)
b5 − c4
1(3)
a7 − b6 + d9
1(3)
a8 − c6 + d10
1(3)
b8 − c7 + d11
2(0)
a11 − b10 + c9
1(4) a14 − b13 + c12 − d15

Server 2
d2 , a2 , b2 , c2
a1 − d6
b1 − d7
c1 − d8
a 7 − b6
a8 − c6
b8 − c7
a4 − b3 + d12
a5 − c3 + d13
b5 − c4 + d14
a14 − b13 + c12
a11 − b10 + c9 − d16

B
1
2

3

4

16

We include the full algorithm here for completeness. Q(n, ‘θ’) denotes the queries for Server
n ∈ [1 : N ] when Wθ is desired. For any ordered tuple u, let new(u) be a function that, starting with
u(1), returns the “next” element in u each time it is called with the same tuple u as its argument.
Algorithm (1) Q-Gen Algorithm.
Input: θ
2: Output: Q(1, ‘θ’), · · · , Q(N, ‘θ’)
3: Initialize: All query sets are initialized as null sets. Also initialize Block = 1;
4: for DB1 = 1 : N do
1:

5:

Q(DB1 , ‘θ’, Block, M) ← {uθ (DB1 )}
Q(DB1 , ‘θ’, Block, I) ← {u1 (DB1 ), · · · , uM (DB1 )}/{uθ (DB1 )}
end for(DB1 )
for Block = 2 : M do
8:
for DBBlock = 1 : N do
9:
for each (DBBlock−1 , DBBlock−2 , · · · , DB1 ), where DBBlock−1
DBBlock−1 , · · · , DB1 6= DB2 do
6:

7:

6=

DBBlock , DBBlock−2

6=

10:

Q(DBBlock , DBBlock−1 , · · · , DB1 , ‘θ’, Block, M) ← Exploit-SI(Q(DBBlock−1 , DBBlock−2 , · · · , DB1 , ‘θ’, Block − 1, I))
Q(DBBlock , DBBlock−1 , · · · , DB1 , ‘θ’, Block, I) ← M-Sym(Q(DBBlock , DBBlock−1 , · · · , DB1 , ‘θ’, Block, M))

end for (DBBlock−1 , DBBlock−2 , · · · , DB1 )
12:
end for(DBBlock )
13: end for (Block)
14: for DBBlock = 1 : N do

11:

15:

Q(DBBlock , ‘θ’) ←

[

[

Q(DBBlock , DBBlock−1 , · · · , DB1 , ‘θ’, Block, I)∪

Block∈[1:M ] DBBlock−1 6=DBBlock ,
··· ,DB1 6=DB2

16:
17:

end for(DBBlock )
SignAssign(Q(1, ‘θ’), · · · , Q(N, ‘θ’))


Q(DBBlock , DBBlock−1 , · · · , DB1 , ‘θ’, Block, M)

The sub-routines are as follows. θ, Block are assumed to be available to the sub-routines as
→
−
global variables. Tm represents the set of all possible choices of m distinct indices in [1 : M ]. T
indicates that the elements of T are to be accessed in the natural lexicographic increasing order.

17

Algorithm (2) M-Sym Algorithm.
Input: Q = Q(DBBlock , DBBlock−1 , · · · , DB1 , ‘θ’, Block, M)
Output: Q∗ = Q(DBBlock , DBBlock−1 , · · · , DB1 , ‘θ’, Block, I)
3: Initialize: Q∗ ← ∅.
−−−→
4: for each i[1:Block] ∈ TBlock , θ ∈
/ i[1:Block] do
1:

2:

5:

Q∗ ←Q∗ ∪ {ui1 (j1 ) + ui2 (j2 ) + · · · + uiBlock (jBlock )}
such that ∀l ∈ [1 : Block]
X
∃ uθ (jl ) +
uir (∗) ∈ Q
r∈[1:Block],r6=l

6:

end for (i[1:Block] )

Algorithm (3) Exploit-SI Algorithm.
Input: Q = Q(DBBlock−1 , DBBlock−2 , · · · , DB1 , ‘θ’, Block − 1, I)
Output: Q′ = Q(DBBlock , DBBlock−1 , · · · , DB1 , ‘θ’, Block, M)
Initialize: Q′ ← ∅.
→
−
4: for each q ∈ Q do
1:

2:
3:
5:

Q′ ← Q′ ∪ {new(uθ ) + q}
6:

end for (q)

This completes the description of the scheme PC . The correctness of PC follows from that of
PIR2 . Remarkably, if the messages are independent, then PC may be seen as another PIR scheme
that achieves the same rate as PIR1 , PIR2 , i.e., all three are capacity achieving schemes. The
proof of privacy of PC is deferred to Section 6.1 for Example A and to Section 6.2 for arbitrary
K, M, N .
The main advantage of PC is that for the dependent message setting of Theorem 1, it is the
optimal private computation scheme. Its proof of optimality is presented next.

Proof of Optimality of PC

5

In this section, we show how PC achieves the capacity of private computation when the messages
are dependent. The key idea is that the message dependencies combined with the special index
and sign structure of PC create redundant queries, and by downloading generic combinations of
the queries8 instead of downloading each query separately, the download requirement is reduced
without compromising on privacy.
8

Alternatively, random binning (Slepian-Wolf coding) may be used.

18

Proof of Optimality for Example A

5.1

To prove optimality, we need to show that the scheme achieves a rate that matches the capacity
of private computation according to Theorem 1. Specifically, let us prove that the rate achieved
is 8/12 = 2/3. For this, we will show that the user downloads only 12 symbols from each server.
Note that ostensibly there are 15 symbols that are queried from each server. However, it turns out
that based on the information available from the other server, 3 of these symbols are redundant.
Thus, 12 generic combinations of these 15 symbols are sufficient.
Let us see why this is the case for the queries from Server 1. c1 , d1 are clearly redundant
symbols because according to (9) they are functions of a1 , b1 . So we need one more redundant
symbol. Suppose a is desired (θ = 1). Then, consider the 2-sum queries that do not involve the
desired message, a. There are 3 such queries. However, the key is that from any 2 we can construct
the 3rd . In this case from Server 1 we have: b4 − c3 , b5 − d3 , c5 − d4 . But note that
v3′ (b5 − d3 ) − v4′ (b4 − c3 ) − (v3 v4′ − v4 v3′ )a3 − v4 a4 + v3 a5 = (c5 − d4 )
Verify:
LHS

= v3′ (b5 − d3 ) − v4′ (b4 − c3 ) − (v3 v4′ − v4 v3′ )a3 − v4 a4 + v3 a5
(9)
= v3′ (b5 − v4 a3 − v4′ b3 ) − v4′ (b4 − v3 a3 − v3′ b3 ) − (v3 v4′ − v4 v3′ )a3 − v4 a4 + v3 a5
(9)
= v3 a5 + v3′ b5 − v4 a4 − v4′ b4 = (c5 − d4 ) = RHS

Since the user knows a3 , a4 , a5 due to the side information available from the other server, out of
these 3 equations, 1 is redundant. Thus, one more symbol is saved, giving us 12 effective downloaded
symbols, and the rate 8/12 is achieved. Since this is also the outer bound, this scheme achieves
capacity. It can similarly be verified for Example A that the redundancy exists no matter which
message is desired.
As another example, suppose c is desired (θ = 3). Referring to the scheme, from Server 1, the
three queries (that are 2-sums) not involving c are a4 − b3 , a5 − d3 , b5 − d4 . But note that
(v3 v4′ − v4 v3′ )(a4 − b3 ) − v3 (a5 − d3 ) − v4 c3 − v4′ c4 + c5 = v3′ (b5 − d4 )
Verify
LHS

= (v3 v4′ − v4 v3′ )(a4 − b3 ) − v3 (a5 − d3 ) − v4 c3 − v4′ c4 + c5
(9)
= (v3 v4′ − v4 v3′ )(a4 − b3 ) − v3 (a5 − v4 a3 − v4′ b3 )
− v4 (v3 a3 + v3′ b3 ) − v4′ (v3 a4 + v3′ b4 ) + (v3 a5 + v3′ b5 )
= v3′ (b5 − v4 a4 − v4′ b4 )
(9)
= v3′ (b5 − d4 ) = RHS

Note that the scheme is designed to satisfy server symmetry, so redundancy exists for Server 2
as well. Note also that the redundant symbols are created in the message symmetry step so that
regardless of the value of θ, the sign structure (alternating) is maintained and the symbol index
structure is guaranteed to be symmetric. So for all θ ∈ [1 : 4], we always have 3 redundant
symbols from each server, and downloading 12 symbols per server suffices. The rate achieved is
L/D = 16/24 = 2/3 = C.
19

5.2

Proof of Optimality for Arbitrary K, M and N = 2

−1
=
To prove optimality, we need to show that the scheme achieves a rate 
of 1 + 1/2 + · ·· + 1/2K−1
PM
M
M −K 
2K
M
M
−K
. For this, we will show that the user downloads only m=1 m − m
= 2 −2
2(2K −1)

symbols from each server. Note that the message size is L = 2M , then the rate achieved is
K
2M
= 2(22K −1) , as desired. Note that there are M
m symbols queried in Block m, m ∈ [1 : M ]
2(2M −2M −K )
from each
server. However, it turns out that based on information
available from the other sever,


M −K
M
M −K
of
these
symbols
are
redundant.
Thus,
−
generic
combinations of these M
m
m
m
m
symbols are sufficient.
Next we prove why this is the case in the following lemma.

−K 
Lemma 1 For all θ ∈ [1 : M ], for each server, in Block m ∈ [1 : M − K], Mm
of the M
m
symbols are redundant, based on the information available from the other server.

Proof: Let us start with the case where
 θ = 1. Consider the m-sum queries that do not involve the
desired message u1 . There are Mm−1 such queries, divided into two groups:

−K 
1. Mm−1 − Mm
queries that involve at least one element in {u2 , · · · , uK },

−K
2. Mm
queries that do not involve any element in {u2 , · · · , uK }.

The key is that the symbols in Group 2 are redundant. Specifically, we show that they are
functions of the symbols in Group 1 when u1 is known.9
Example 1: We accompany the general proof with a concrete example to explain the idea. For
this example, assume K = 3 datasets, M = 6 messages, and denote symbols u1 , u2 , · · · , u6 by
distinct letters a, b, · · · , f , respectively, for simplicity. Consider Block m = 3. The queries that do
not involve the desired message u1 are shown below. For this example, we will see that the only
symbol in Group 2 is a function of the 9 symbols in Group 1.
bj5 − cj2 + dj1
bj6 − cj3 + ej1
bj7 − cj4 + fj1
bj8 − dj3 + ej2
bj9 − dj4 + fj2
bj10 − ej4 + fj3
cj8 − dj6 + ej5
cj9 − dj7 + fj5
cj10 − ej7 + fj6
Group 2 dj10 − ej9 + fj8
Group 1

To simplify the notation, define
q(ui[1:m] ) = q({ui1 , ui2 , · · · , uim }) ,

m
X
(−1)l−1 uil

(10)

l=1

9

This is guaranteed because the desired variable u1 in Block k is mixed with side information in Block k − 1
available from the other server.

20

where the message indices i1 < i2 · · · < im , and the symbol indices are suppressed. Consider an
arbitrary query in Group 2:
q0 = q(ui[1:m] )
where K < i1 < i2 · · · < im . We show that when
u1 is known, the query q0 is a function of

m+K−1
m+K−1
− 1 queries in Group 1. These
− 1 queries contain an m-sum of every type in
m
m
I , [2 : K] ∪ i[1:m] (except i[1:m] ).
n
o
Q , q(uj[1:m] ) : j[1:m] ⊂ T

(11)

where the set of all possible m distinct indices (types of m-sums) in I except i[1:m] is denoted as T .
Without loss of generality, we assume j1 < j2 < · · · < jm . The indices of these queries are assigned
by the index assignment process.
From the linear dependence of the messages (3), we have
uil (∗) = vil (1) u1 (∗) + · · · + vil (K) uK (∗), l ∈ [1 : m]

(12)

Note that u1 (∗) are assumed known, so we may set u1 (∗) to zero. Now we show that q0 is a linear
function of the queries in Q.
X
(13)
q0 =
h(uj[1:m] )q(uj[1:m] )
j[1:m] ∈T

where the linear combining coefficients h(uj[1:m] ) are functions of vi1 , · · · , vim . The elements of the
matrix V∗ , (viT1 viT2 · · · viTm ) are shown below (the rows and columns are labelled by corresponding
messages).

V∗ =

viT1

viT2

ui1

u2 vi1 (2)

u3  vi1 (3)
= .  .
..  ..

· · · viTm

uK

vi1 (K)

ui2
vi2 (2)
vi2 (3)
..
.

···
···
···
..
.

vi2 (K)

···

ui m
vim (2) 
vim (3) 
.. 
. 

vim (K)

In particular, h(uj[1:m] ) are specified as follows. Suppose |j[1:m] ∩ [2 : K]| = t, where t ∈ [1 : m] and
denote these t elements as j̄[1:t] , j[1:m] ∩[2 : K]. Then |j[1:m] ∩i[1:m] | = m−t and denote these m−t
elements as ī[1:m−t] , j[1:m] ∩ i[1:m] . We further define ei[1:t] , i[1:m] /ī[1:m−t] , where ei1 < · · · < eit . We
are now ready to give h(uj[1:m] ). h(uj[1:m] ) is equal to the determinant of the t × t square matrix
obtained as the sub-matrix of V∗ where the rows correspond to messages uj̄[1:t] and the columns
correspond to messages uei .
[1:t]

Pt

h(uj[1:m] ) = (−1)

r=1

Ω(eir )+t(t−1)/2+1

21

vei1 (j̄1 ) vei2 (j̄1 ) · · · veit (j̄1 )
vei1 (j̄2 ) vei2 (j̄2 ) · · · veit (j̄2 )
..
..
..
..
.
.
.
.
vei1 (j̄t ) vei2 (j̄t ) · · · veit (j̄t )

(14)

where Ω(eir ) is defined as the position of eir in the lexicographic ordering of the elements of i[1:m] .
For example, suppose i[1:k] = {4, 6, 7, 9}. Then if eir = 6, then Ω(eir ) = 2. Similarly, if eir = 9, then
Ω(eir ) = 4.

Let us verify that (13) holds. In (13), m+K−1
distinct symbol indices appear, and each of those
m−1
symbol indices is assigned to K message variables. Pick any m − 1 messages from the m + K − 1
messages uI , say uα[1:m−1] , where α1 < · · · < αt ≤ K < αt+1 < · · · < αm−1 , t ∈ [0 : K − 1]. The
same index (denoted by #) is assigned to the variables
uI /uα[1:m−1] , uβ[1:K]

(15)

where β1 < · · · < βK−1−t ≤ K < βK−t < · · · < βK . From (15), we have
α[1:t] ∪ β[1:K−1−t] = [2 : K]

(16)

α[t+1:m−1] ∪ β[K−t:K] = i[1:m]

(17)

The K variables uβ[1:K] (#) appear in the following K queries.
ql , q(uα[1:m−1] ∪βl ), l ∈ [1 : K].

(18)

We show that for any m − 1 distinct indices α[1:m−1] in I, (13) holds for the K variables
uβ[1:K] (#). Using (12), we write uβ[1:K] (#) as linear combinations of u[2:K](#). Next we prove that
(13) holds for uη (#), ∀η ∈ [2 : K]. Define

V = [Vi,j ](t+1)×(t+1)






,



vβK−t (η) vβK−t+1 (η) · · · vβK (η)
vβK−t (α1 ) vβK−t+1 (α1 ) · · · vβK (α1 )
vβK−t (α2 ) vβK−t+1 (α2 ) · · · vβK (α2 )
..
..
..
..
.
.
.
.
vβK−t (αt ) vβK−t+1 (αt ) · · · vβK (αt )









(19)

and the minor of V (the determinant of the submatrix formed by deleting the i-th row and jcolumn) is denoted by Mi,j . Note that α[t+1:m−1] ∪ β[K−t:K] = i[1:K] , so
{Ω(αt+1 ) ∪ · · · ∪ Ω(αm−1 ) ∪ Ω(βK−t ) ∪ · · · Ω(βK )} = {Ω(i1 ) ∪ · · · ∪ Ω(iK )} = 1 : K

(20)

∆uβr (qr ) = t + Ω(βγ ) − (r − (K − t)) , ∀r ∈ [K − t : K]

(21)

and

We now consider two cases for η.
Case 1: η ∈ α[1:t] . In this case, uη (#) variables come from uβ[K−t:K] (#). (13) boils down to
K
X

∆uβ (qr )+1

h(uα[1:m−1] ∪βr ) × (−1)

r

vβr (η)

r=K−t
∆uβ

⇐= vβK−t (η) (−1)

K−t

(qK−t )+1

∆uβ

+vβK−t+1 (η) (−1)

K−t+1

PK

(−1)

s=K−t

(qK−t+1 )+1

× uη (#) = 0

Ω(βs )−Ω(βK−t )+t(t−1)/2+1
PK

(−1)

22

!

s=K−t

(22)
M1,1

Ω(βs )−Ω(βK−t+1 )+t(t−1)/2+1

M1,2 + · · ·

∆u β

+vβK (η) (−1)

K

(qK )+1

PK

(−1)

s=K−t

Ω(βs )−Ω(βK )+t(t−1)/2+1
t+2

⇐= vβK−t (η) M1,1 − vβK−t+1 (η) M1,2 · · · + (−1)

M1,t+1 = 0

(23)

vβK (η) M1,t+1 = 0

(24)

⇐= V1,1 M1,1 − V1,2 M1,2 · · · + (−1)t+2 V1,t+1 M1,t+1 = |V| = 0

(25)

where (24) follows from the observation that consecutive terms in (23) have alternating signs,
proved as follows. For any r ∈ [K − t : K − 1],
∆uβ (qr )+1

(−1)
(21)

r

PK

(−1)

Ω(βs )−Ω(βr )+t(t−1)/2+1

s=K−t

PK

=

(−1)t+Ωβr −(r−(K−t))+1 (−1)

=

(−1)t−(r−(K−t))+1 (−1)

s=K−t

PK

s=K−t

Ω(βs )−Ω(βr )+t(t−1)/2+1

Ω(βs )+t(t−1)/2+1
PK

= (−1) × (−1)t+Ω(βr+1 )−(r+1−(K−t))+1 (−1) s=K−t Ω(βs )−Ω(βr+1 )+t(t−1)/2+1
PK
(21)
∆u
(qr+1 )+1
= (−1) × (−1) βr+1
(−1) s=K−t Ω(βs )−Ω(βr+1 )+t(t−1)/2+1

(26)

(25) is due to the fact that η ∈ α[1:t] , so V has two identical rows and its determinant is 0.
Case 2: η ∈ β[1:K−1−t] . In this case, uη (#) variables come from uβ[K−t:K] ∪η (#). If α[1:m−1] ∩[2 : K] 6= ∅,
(13) boils down to
∆uη (q(uα[1:m−1] ∪η ))+1

h(uη∪α[1:m−1] )(−1)

+

K
X

∆uβr (qr )+1

h(uα[1:m−1] ∪βr ) × (−1)

vβr (η)

r=K−t

× uη (#) = 0

(27)

⇐= |V| − |V| = 0

(28)

where the second term of (28) follows from (25) and the ‘−’ sign in (28) is due to the fact
that in (27), the sign of the first term is different from the sign of the second term, proved as
follows.
∆uη (q(uα[1:m−1] ∪η ))+1

(−1)

∆uη (q(uα[1:m−1] ∪η ))+1

(−1)

PK

PK

(−1)

s=K−t

Ω(βs )+t(t+1)/2+1

= (−1) × (−1)t+Ω(βK−t )+1 (−1) s=K−t+1 Ω(βs )+t(t−1)/2+1
PK
(21)
(qK−t )+1
∆u
(−1) s=K−t+1 Ω(βs )+t(t−1)/2+1
= (−1) × (−1) βK−t
∆

(q(u

(29)

))+1

α[1:m−1] ∪η
Note that in the first line, the first (−1) uη
term is to account for the different
ordering of the vectors in V that appear in defining h(uη∪α[1:m−1] ).
Otherwise, if α[1:m−1] ∩ [2 : K] = ∅, i.e., α[1:m−1] ⊂ i[1:m] , we have t = 0 and (13) boils down to

∆uβ

(−1)
⇐=

!

K

(qK )+1

∆uη (q(uα[1:m−1] ∪η ))+1

vβK(η) = h(uη∪α[1:m−1] )(−1)

(−1)ω(βK )+1 vβK(η) = h(uη∪α[1:m−1] )

(30)
(31)

where (31) follows from ∆uβK (qK ) = ω(βK ) as in qK , the messages are uβK ∪ uα[1:m−1] = ui[1:m] ,
and ∆uη (q(uα[1:m−1] ∪η )) = 1 as η ≤ K < α1 . Note that (31) is the definition of h(uη∪α[1:m−1] ) (see
(14)). Therefore the proof is complete.

23

Example 1 (Continued): Consider the query in Group 2, dj10 − ej9 + fj8 . We show that it is a
function of the 9 queries in Group 1, when the desired variables (a∗ ) are set to zero.
dj10 − ej9 + fj8
v5(2) v6(2)
v4(2) v6(2)
v
v
(bj5 − cj2 + dj1 ) +
(bj6 − cj3 + ej1 ) − 4(2) 5(2)
v5(3) v6(3)
v4(3) v6(3)
v4(3) v5(3)
+ v6(2) (bj8 − dj3 + ej2 ) − v5(2) (bj9 − dj4 + fj2 ) + v4(2) (bj10 − ej4 + fj3 )

= −

(bj7 − cj4 + fj1 )

+ v6(3) (cj8 − dj6 + ej5 ) − v5(3) (cj9 − dj7 + fj5 ) + v4(3) (cj10 − ej7 + fj6 )
Example 2: Let us include another example, where K = 4, M = 8. Consider Block m = 3
and the desired message index θ = 1. The queries that do not involve u1 are divided into Group
1 (where u2 , u3 or u4 appears) and Group 2 (where none of u2 , u3 , u4 appears). Consider a query
in Group 2, q0 =
 q(u5,6,8 ), i.e., i1 = 5, i2 = 6, i3 = 8. When u1 is known, q0 is a function of the
− 1 = 19 queries. Here I = {2, 3, 4, 5, 6, 8}.
following 3+4−1
3
n
Q =
q(u2,3,4 ), q(u2,3,5 ), q(u2,3,6 ), q(u2,3,8 ), q(u2,4,5 ), q(u2,4,6 ), q( u2,4,8 ), q( u2,5,6 ), q( u2,5,8 ), q(u2,6,8 ),
o
q(u3,4,5 ), q(u3,4,6 ), q(u3,4,8 ), q(u3,5,6 ), q(u3,5,8 ), q(u3,6,8 ), q(u4,5,6 ), q(u4,5,8 ), q(u4,6,8 )
(32)

The linear combining coefficients in (13) are designed following (14). Let us verify (13) for the
symbols with a particular index value, #. To this end, let us pick the m − 1 = 2 message indices
α1 = 3, α2 = 4 (note that {3, 4} ⊂ I). As α2 = 4 ≤ K = 4, we have t = 2. The variables
with index # are from u2 , u5 , u6 , u8 (from the difference set of I and {α1 , α2 }), so that we have
β1 = 2, β2 = 5, β3 = 6, β4 = 8. These 4 variables appear in queries
q1 = q(u2,3,4 ), q2 = q(u3,4,5 ), q3 = q(u3,4,6 ), q4 = q(u3,4,8 )

(33)

We can write u5 (#), u6 (#), u8 (#) as a linear combination of u2 (#), u3 (#), u4 (#) after u1 (#) is
eliminated, or equivalently, set to zero. Next we show that (13) holds for u3 (#). In this case, η = 3
and η ⊂ {α1 , α2 } = {3, 4}, so we are in Case 1. We want to show the following.

h(u3,4,5 ) × (−1)∆u5 (q(u3,4,5 ))+1 v5(3) + h(u3,4,6 ) × (−1)∆u6 (q(u3,4,6 ))+1 v6(3)

(34)
+ h(u3,4,8 ) × (−1)∆u8 (q(u3,4,8 ))+1 v8(3) u3 (#) = 0
⇐⇒ h(u3,4,5 )v5(3) + h(u3,4,6 )v6(3) + h(u3,4,8 )v8(3) = 0

(35)

Note that ∆u5 (q(u3,4,5 )) is related to Ω(5). We now find h(u3,4,5 ). Referring to (14), we have
j1 = 3, j2 = 4, j3 = 5, j̄1 = 3, j̄2 = 4
ī = 5, ei1 = 6, ei2 = 8, Ω(6) = 2, Ω(8) = 3

h(u3,4,5 ) = (−1)2+3+2×1/2+1

v6(3) v8(3)
v6(4) v8(4)

(36)
(37)
=−

v6(3) v8(3)
v6(4) v8(4)

(38)

Similarly,
h(u3,4,6 ) =

v5(3) v8(3)
v5(4) v8(4)

, h(u3,4,6 ) = −
24

v5(3) v6(3)
v5(4) v6(4)

(39)

Therefore (35) is equivalent to
−

v6(3) v8(3)
v6(4) v8(4)

v5(3) +

v5(3) v8(3)
v5(4) v8(4)

v6(3) −

v5(3) v6(3)
v5(4) v6(4)

v5(3) v6(3) v8(3)
v8(3) = − v5(3) v6(3) v8(3)
v5(4) v6(4) v8(4)

= 0(40)

and thus (35) holds. For the other case (Case 2), we show that (13) holds for u2 (#), i.e., η = 2
and η = β1 = 2. In this case, we want to show

h(u2,3,4 ) × (−1)∆u2 (q(u2,3,4 ))+1 + h(u3,4,5 ) × (−1)∆u5 (q(u3,4,5 ))+1 v5(2)

+ h(u3,4,6 ) × (−1)∆u6 (q(u3,4,6 ))+1 v6(2) + h(u3,4,8 ) × (−1)∆u8 (q(u3,4,8 ))+1 v8(2)
×u2 (#) = 0

(41)

⇐⇒ h(u2,3,4 ) + h(u3,4,5 )v5(2) + h(u3,4,6 )v6(2) + h(u3,4,8 )v8(2) = 0

(42)

Following the definition of h(u2,3,4 ) (refer to (14)), we find that
h(u2,3,4 ) =

v5(2) v6(2) v8(2)
v5(3) v6(3) v8(3)
v5(4) v6(4) v8(4)

(43)

Then (42) is equivalent to
v5(2) v6(2) v8(2)
v5(3) v6(3) v8(3)
v5(4) v6(4) v8(4)

−

v5(2) v6(2) v8(2)
v5(3) v6(3) v8(3)
v5(4) v6(4) v8(4)

=0

(44)

and thus (42) holds. Let us consider another index (#′ ) where α1 = 5, α2 = 6, i.e., α1 > K = 4
and t = 0. The index #′ is assigned to variables from u2 , u3 , u4 , u7 (β1 = 2, β2 = 3, β3 = 4, β4 = 7)
in queries
q1 = q(u2,5,6 ), q2 = q(u3,5,6 ), q3 = q(u4,5,6 ), q4 = q(u5,6,7 )

(45)

After writing every variable in terms of u2 , u3 , u4 (u1 terms are set to zero because they are known
and can be removed), we show that (13) holds for u2 (#′ ), u3 (#′ ), u4 (#′ ). Note that no matter which
variable we pick, say u4 (#′ ), i.e., η = 4, η ∈ {2, 3, 4} = {β1 , β2 , β3 }. Further {α1 , α2 }∩{2, 3, 4} = ∅.
In this case, we want to show
(−1)∆u7 (q5,6,7 )+1 v7(4) u4 (#′ ) = h(u4,5,6 )(−1)∆u4 (q(u4,5,6 )+1 u4 (#′ )
⇐⇒ v7(4) = h(u4,5,6 )

(46)
(47)

which matches the definition of h(u4,5,6 ) (see (14)) thus holds.
The proof for arbitrary θ 6= 1 follows similarly. Since the first K of the M linear combinations
are linearly independent (in fact, they are the K independent datasets), there exist K − 1 messages
from u[1:K] (denoted as ur[2:K] , r[2:K] ⊂ [1 : K]) such that uθ ∪ ur[2:K] are independent. Similarly,
consider the m-sum queries that do not involve the desired message uθ , which are further divided
into two groups, depending on whether at least one element from ur[2:K] is involved (Group 1) or not
(Group 2). We show that any query q0 = q(ui[1:m] ), i[1:m] ∩ (θ ∪ r[2:K] ) = ∅ in Group 2 is a function
25

of the queries in Group 1. q0 exists as m ≤ M − K. The symbol indices in q0 are assigned by the
index assignment process. By a change of basis, we express each variable as a linear combination of
uθ ∪ ur[2:K] . Then we show that q0 is a linear combination of the queries q(uj[1:m] ), where j[1:m] ∈ T ′ ,
and T ′ is the set of all possible m distinct indices in r[2:K] ∪ i[1:m] except i[1:m] . The rest of the
proof, where we design the linear combining coefficients and show the linear combination holds, is
identical to the case of θ = 1 (by an invertible mapping from r[2:K] to [2 : K], and between i[1:m] of
the two cases).
Example 3: We give an example where θ 6= 1. Assume K = 3 datasets, M = 6 messages,
θ = 5, and denote symbols u1 , u2 , · · · , u6 by distinct letters a, b, · · · , f , respectively. Consider Block
m = 2. There exists two messages in a, b, c (assume without loss of generality, a, b) such that a, b, e
are independent. The queries that do not involve the desired message e are shown below. The
queries are divided into Group 1 (where a or b appears) and Group 2 (where none of a, b appears).
aj2 − bj1
aj3 − cj1
aj4 − dj1
aj 5 − f j 1
bj3 − cj2
bj4 − dj2
bj 5 − f j 2
Group 2 cj4 − dj3
cj5 − fj3
dj5 − fj4
Group 1

We express c, d, f as a linear combination of a, b, e (note that a, b, e are linearly independent).
Assume
c = vc(a) a + vc(b) b + vc(e) e

(48)

d = vd(a) a + vd(b) b + vd(e) e

(49)

f

(50)

= vf (a) a + vf (b) b + vf (e) e

The queries in Group 2 are functions of the queries in Group 1. For example, consider cj5 − fj3 .
When e∗ are set to zero, we have
cj5 − fj3 = −

vc(a) vf (a)
vc(b) vf (b)

(aj2 − bj1 ) − vf (a) (aj3 − cj1 ) + vc(a) (aj5 − fj1 )

− vf (b) (bj3 − cj2 ) + vc(b) (bj5 − fj2 )
where the linear combining coefficients are determined by the following matrix.
 c
a vc(a)
b vc(b)

f 

vf (a)
vf (b)

For example, for aj3 − cj1 , from (14), the linear coefficient is (−1)2+0+1 vf (a) = −vf (a) .

26

(51)

5.3

Proof of Optimality for Arbitrary K, M, N

The proof of optimality when N > 2 follows from that when N = 2. The query structure of any
query vertex at level m for arbitrary N is identical to the structure of a query vertex at level m
for the N = 2 setting. From the observations listed in Section 4.1.2, recall that for any N > 2, the
queries from each server in block m are made up of (N − 1)m−1 query vertices. Also let us recall
−K
from Lemma 1 that when N = 2, for each server there are Mm
redundant symbols within each
M −K 
level m query vertex, m ∈ [1 : M − K]. Therefore, when N > 2, there are (N − 1)m−1
redunm


PM
M
M −K 
m−1
dant symbols in block m, and it suffices to download only N
(N
−
1)
−
m=1
m
m
symbols in total from all N servers. The rate achieved is
R =
N

P
M

NM

m−1
m=1 (N − 1)



M
m

−



M −K 
m

N − 1 NK
NM
=
N NK − 1
N × N 1−1 (N M − N M −K )
−1

1
1
+ · · · + K−1
=
1+
N
N
=

(52)

(53)
(54)

which matches the capacity of private computation. The optimality proof is therefore complete.

6
6.1

Proof of Privacy of PC
Proof of Privacy for Example A

To see why this scheme is private, we show that the queries are identically distributed, regardless
of the value of θ. To this end, we show that the query for θ = 2, 3, 4 has a one-to-one mapping to
the query for θ = 1, respectively, through a choice of permutation π and signs σi which is made
privately and uniformly by the user.
For example, for Server 1 and Server 2, the query for θ = 2 can be converted into the query for
θ = 1 by the following mapping:
Server 1:

−→

(2, 3, 9, 7, 8, 10, 14, 15, σ6 , σ12 , σ13 )

Server 2:

−→

(3, 2, 7, 9, 10, 8, 15, 14, −σ6 , −σ12 , −σ13 )
(6, 1, 12, 4, 13, 5, 16, 11, −σ3 , −σ9 , −σ10 )
(1, 6, 4, 12, 5, 13, 11, 16, σ3 , σ9 , σ10 )

However, these mappings are privately generated by the user and both alternatives are equally
likely regardless of desired message. Hence, these queries are indistinguishable.
We can similarly verify that the other remaining queries for θ = 3, 4, are indistinguishable as
well. For Server 1 and Server 2, the query for θ = 3 can be converted into the query for θ = 1 by
the following mapping:
Server 1:

−→
Server 2:

(3, 4, 2, 7, 6, 9, 10, 11, 8, −σ8 , 14, 13, 15, −σ12 )
(2, 3, 4, 9, 7, 6, 8, 10, 11, σ11 , 15, 14, 13, σ12 )
(7, 6, 1, 4, 3, 12, 14, 13, 5, −σ5 , 11, 10, 16, −σ9 )
27

−→

(6, 1, 7, 12, 4, 3, 13, 5, 14, σ14 , 16, 11, 10, σ9 )

The last case is when θ = 4. The mapping from that to θ = 1 is as follows.
Server 1:

(3, 4, 5, 2, 6, 7, 8, 9, 10, 11, 14, 13, 12, 15)

−→

(2, 3, 4, 5, 8, 10, 11, 6, 7, 9, 15, 14, 13, 12)

Server 2:

(6, 7, 8, 1, 3, 4, 5, 12, 13, 14, 11, 10, 9, 16)

−→

(1, 6, 7, 8, 5, 13, 14, 3, 4, 12, 16, 11, 10, 9)

Again, since these mappings are privately generated by the user and both alternatives are equally
likely regardless of desired message, these queries are indistinguishable. Thus all queries are indistinguishable and the scheme is private.

6.2

Proof of Privacy for Arbitrary K, M, N

We prove that PC is private. We know that PIR2 is private and PC is obtained from PIR2 by the
sign assignment. Therefore it suffices to show that the sign assignment does not destroy privacy,
i.e., Q(n, ‘θ’) still has a one-to-one mapping to Q(n, ‘1’) by a choice of permutation π and signs σi
which is made by the user privately and uniformly.
The one-to-one mapping is quite simple. Note that each query in Q(n, ‘1’) has alternating
signs. Consider Q(n, ‘θ’). We only need to consider the non-desired symbols in queries introduced
by Exploit-SI (so uθ is involved). The reason is that the signs of the desired symbols introduced
by Exploit-SI and the other queries introduced by M-Sym are the same as the signs of the queries
in Q(n, ‘1’).10 These queries all satisfy that ∆Wθ > 0. Now to map Q(n, ‘θ’) to Q(n, ‘1’), for each
block, we flip the signs (i.e., replace σi with −σi ) of variables to the right of uθ in queries from
sub-blocks S if S is odd, and the signs of variables to the left of uθ in queries from sub-blocks S if
S is even.
Example 4: We accompany the general proof with a concrete example to explain the idea. Consider M = 6 (messages), block m = 4, desired message index θ = 4. For simplicity, we denote
6−1
= 10 queries introduced by
u1 , u2 , · · · , u6 by a, b, · · · , f . In Block B = m = 4, we have 4−1
Exploit-SI (contains d) as follows. The signs that need to be flipped are colored in red.
B
4

θ=4
S(∆d )
Server n
1(4)
aj5 − bj2 + cj1 − d∗
2(3) −aj6 +bj3 + d∗ − ej1
2(3) −aj7 +bj4 + d∗ − fj1
2(3) −aj8 +cj3 + d∗ − ej2
2(3) −aj9 +cj4 + d∗ − fj2
2(3)
−bj8 +cj6 + d∗ − ej5
2(3) −bj9 +cj7 + d∗ − fj5
3(2)
aj10 − d∗ −ej4 +fj3
3(2)
bj10 − d∗ −ej7 +fj6
3(2)
cj10 − d∗ −ej9 +fj8

10
Note that the indices of the non-desired symbols introduced by Exploit-SI do not appear in the queries introduced
by M-Sym. The reason is seen as follows. Consider a symbol ui , i 6= θ that appears in a query introduced by ExploitSI (denote the query by q, so uθ appears in q) and suppose the index of ui is j (i.e., we have ui (j)). Now from
index assignment, symbols with index j all appear in terms that contain uθ (thus these terms are all generated by
Exploit-SI).

28

Note that σi appears in all message variables with symbol index i, so σi might be flipped
multiple times and we need to make sure that σi is flipped consistently, i.e., the sign flipping rule
either changes or does not change the signs of all variables with the same index. This is indeed
true, proved as follows. Note that we flip the signs depending on whether the sub-block index is
even or odd and if the variables are to the left or right of uθ . This means, for variables in two
consecutive sub-blocks, the variables to the left of uθ in one sub-block and the variables to the right
of uθ in the other sub-block are simultaneously flipped or unflipped. So it suffices to show that all
variables with the same index are
• either in the same sub-block, and all are on the same side of uθ ,
• or in two consecutive sub-blocks, but are on different sides of uθ .
Example 4 (continued): Referring to the table above, consider all variables with index j1 , i.e.,
cj1 , ej1 , fj1 . cj1 is in sub-block 1 and is to the left of d. ej1 , fj1 are in sub-block 2 and are to the right
of d. Further, the signs of cj1 , ej1 , fj1 are all unflipped. As another example, consider all variables
with index j10 , i.e., aj10 , bj10 , cj10 . They are all in sub-block 3 and their signs are all unflipped. One
more example: all variables with index j6 , aj6 , cj6 , fj6 . aj6 , cj6 are in sub-block 2 and are to the left
of d. fj6 is in sub-block 3 and is to the right of d. The signs of aj6 , cj6 , fj6 all need to be flipped.
We now find variables with the same symbol index, say #. From index assignment, we know
that all occurrences of symbol index # are in queries that contain the same m − 1 (distinct)
variables (uθ included). Suppose the message indices of these m − 1 variables are i[1:m−2] ∪ θ,
and let the remaining M − (m − 1) message indices be denoted by r[1:M −(m−1)] . Assume that
i1 < i2 · · · < ij < uθ < uj+1 · · · < uim−2 . Then the symbol index # appears in queries
±ur1 (#) ± ui1 () ± · · · ± uij () ± uθ () ± uij+1 () ± · · · ± uim−2 ()
..
.
±ui1 () ± · · · ± uij () ± uθ () ± uij+1 () ± · · · ± uim−2 () ± urM −(m−1) (#)

(55)

where ± represents either ‘+’ or ‘−’, determined by sign assignment. These M − (m − 1) variables
url , l ∈ [1 : M − (m − 1)] can be divided into two sets (one set could be empty), where
• the first set are those url where rl < θ
• and the second set are those url where rl > θ
So the variables in the first set are to the left of uθ and the variables in the second set are to
the right of uθ . Further, the two sets are in consecutive sub-blocks because ∆uθ only differs by 1.
Therefore the sign flipping rule is consistent and the privacy proof is complete.
Example 4 (continued): Suppose we want to find all variables with index # = j1 . They appear
in queries that contain a, b, d. The queries in (55) are
aj5 − bj2 + cj1 − d∗
−aj6 +bj3 + d∗ − ej1
−aj7 +bj4 + d∗ − fj1
The 3 variables with index # = j1 are cj1 , ej1 , fj1 (colored in blue). The first set contains cj1 (< d)
(in sub-block 1) and the second set contains ej1 , fj1 (> d) (in sub-block 2). As another example,
29

suppose we want to find all variables with index # = j10 . The queries in (55) are
aj10 − d∗ −ej4 +fj3
bj10 − d∗ −ej7 +fj6
cj10 − d∗ −ej9 +fj8
The 3 variables with index # = j10 are aj10 , bj10 , cj10 (< d). They all belong to the first set (sub-block
3). One more example: find all variables with index # = j6 . The queries in (55) are
−aj6 +bj3 + d∗ − ej1
−bj8 +cj6 + d∗ − ej5
bj10 − d∗ −ej7 +fj6
The 3 variables with index # = j6 are aj6 , cj6 , fj6 . The first set contains aj6 , cj6 (< d) (in sub-block
2) and the second set contains fj6 (> d) (in sub-block 3).

7

Conclusion

Motivated by privacy concerns in distributed computing, we introduce the private computation
problem where a user wishes to compute a desired function of datasets stored at distributed servers
without disclosing any information about the function that he wishes to compute to any individual
server. The private computation problem may be seen as a generalization of the PIR problem
by allowing dependencies among messages. We characterize in Theorem 1 the capacity of private
computation for arbitrary N servers, arbitrary K independent datasets, and arbitrary M linear
combinations of the K independent datasets as the possible functions. Surprisingly, this capacity
turns out to be identical to the capacity of PIR with N servers and K independent messages.
Thus, there is no loss in capacity from the expansion of possible messages to include arbitrary
linear combinations.
Going beyond linear-combinations, we show in Theorem 2 that in the asymptotic limit where
the number of independent datasets K → ∞, the capacity of private computation is not affected by
allowing non-linear functions into the set of functions that may be computed by the user, provided
the symbol-wise entropy of each of these functions is no more than the entropy of a symbol from a
dataset.
In the non-asymptotic regime, the capacity of private computation with arbitrary (non-linear)
functions is an interesting direction for future work. Along these lines, let us conclude with the
following two observations. The first observation is a general achievability argument for private computation. Consider the most general setting, where we allow the M messages to be arbitrarily dependent and even the entropies of the message symbols are allowed to be different for different messages.
Suppose each message Wm , m ∈ [1 : M ] is made of L symbols Wm = (Wm,1 , Wm,2 , · · · , Wm,L ).
While the messages may have arbitrary dependencies, the sequence of symbols is generated i.i.d.
in l, i.e., for all l ∈ [1 : L], the symbols (W1,l , W2,l , · · · , WM,l ) ∼ (w1 , w2 , · · · , wM ). We have
H(W1 , · · · , WM ) = LH(w1 , · · · , wM )
H(Wm ) = LH(wm ), m ∈ [1 : M ]

(56)
(57)

Symbols from different messages may not have the same entropy, i.e., we allow the possibility that
Hmin
(1 − N1 ) is always
H(wi ) 6= H(wj ). In this general setting, the private computation rate of R = H
max
30

achievable, (although not optimal in general) where Hmax = max(H(w1 ), H(w2 ), · · · , H(wM )) and
Hmin = min(H(w1 ), H(w2 ), · · · , H(wM )). Just like the achievability argument for Theorem 2, the
general achievability claim follows essentially from [3]. For example, suppose N = 2. First we
compress each message separately into Hmax bits per message symbol. This is possible because
∀m ∈ [1 : M ], H(wm ) ≤ Hmax . Then, in order to retrieve the ith bit ofP
the compressed desired
M
message, Wθ,i , the user requests from Server 1, the linear combination
m=1 cm Wm,i and from
PM
Server 2, the linear combination m=1 cm Wm,i +Wθ,i , where cm are i.i.d. uniform binary coefficients
generated privately by the user and all operations are over F2 . Adding the answers received from
the two servers, allows the user to recover Wθ,i . The total number of bits downloaded is 2Hmax ,
while the number of desired bits retrieved is at least Hmin . Thus, the rate achieved is at least
Hmin
Hmin
Hmin
1
1
2Hmax = Hmax (1 − N ) for N = 2. Similarly, following the approach of [3], the rate Hmax (1 − N ) is
achieved for arbitrary N .
The second observation is the capacity characterization for an elemental case where we have
M = 2 arbitrarily correlated messages and N servers. Again consider the general setting with
arbitrary dependencies and without loss of generality, suppose H(w1 ) ≥ H(w2 ). In this case, the
H(w2 )
capacity is C = H(w1 ,w2N)+(N
−1)H(w1 ) .
The converse is proved as follows. From Fano’s inequality, we have
LH(w1 )
(57)

=

(7)

=
(4)
=
=
(6)
≤
=
(5)
=

H(W1 )

(58)
[1]

[1]

[1]

[1]

I(W1 ; A1 , Q1 , · · · , AN , QN ) + o(L)
[1]

[1]

[1]

(59)

[1]

I(W1 ; A1 , · · · , AN |Q1 , · · · , QN ) + o(L)
[1]
H(A1 , · · ·

[1]
[1]
, AN |Q1 , · · ·

[1]

[1]

[1]
, QN )

−

(60)

[1]
H(A1 , · · ·

[1]
[1]
, AN |W1 , Q1 , · · ·

[1]
, QN )

+ o(L)

[1]

D − H(A1 |W1 , Q1 , · · · , QN ) + o(L)
D−

[1]
[1]
H(A1 |W1 , Q1 )

(61)
(62)

+ o(L)

(63)

D − H(A1 |W1 , Q1 ) + o(L)

(64)

[2]

[2]

[1]

[1]

[1]

[1]

[1]

where (63) follows from that H(A1 |W1 , Q1 , · · · , QN ) = H(A1 |W1 , Q1 ), proved as follows.
[1]

[1]

[1]

[1]

I(A1 ; Q2 , · · · , QN |W1 , Q1 )
[1]

[1]

[1]

[1]

≤

I(A1 , W2 ; Q2 , · · · , QN |W1 , Q1 )

=

[1]
I(W2 ; Q2 , · · ·

(5)

[1]
[1]
, QN |W1 , Q1 ) +

(65)

[1]
[1]
I(A1 ; Q2 , · · ·

[1]
[1]
, QN |W1 , W2 , Q1 )

(66)

[1]

(67)

I(W2 , W1 ; Q2 , · · · , QN |Q1 )

[1]

(68)

[1]
I(W2 , W1 ; Q1 , · · ·

(69)

[1]

[1]

=

I(W2 ; Q2 , · · · , QN |W1 , Q1 )

≤

[1]

≤
(4)
= 0

[1]

[1]
, QN )

(70)

By a similar argument, we have
[2]

[2]

[2]

[2]

I(A1 ; Q2 , · · · , QN |W1 , Q1 ) = 0
31

(71)

[2]

[2]

[2]

[2]

[2]
I(A[2]
n ; Q1 , · · · , Qn−1 , Qn+1 , · · · , QN |W1 , Qn ) = 0

(72)

Next, from (64), by symmetry, we have
[2]
LH(w1 ) ≤ D − H(A[2]
n |W1 , Qn ) + o(L), ∀n ∈ [2 : N ]

(73)

Adding (64) and (73) for all n ∈ [2 : N ], we have
N LH(w1 )

≤
(71)(72)

=

ND −
ND −

N
X

n=1
N
X

[2]
H(A[2]
n |W1 , Qn ) + o(L)

[2]

(74)

[2]

H(A[2]
n |W1 , Q1 , · · · , QN ) + o(L)

(75)

n=1

≤
(7)
=

[2]

[2]

[2]

[2]

[2]

[2]

N D − H(A1 , · · · , AN |W1 , Q1 , · · · , QN ) + o(L)
[2]

[2]

N D − H(A1 , · · · , AN , W2 |W1 , Q1 , · · · , QN ) + o(L)
[2]
H(W2 |W1 , Q1 , · · ·

[2]
, QN )

+ o(L)
≤
ND −
(4)
≤
N D − H(W2 |W1 ) + o(L)
(56)(57)
=
N D − LH(w2 |w1 ) + o(L)
H(W2 )
LH(w2 )
=⇒ R
=
≤ lim 1
L→∞
D
N (N LH(w1 ) + LH(w2 |w1 ) + o(L))
N H(w2 )
=
H(w1 , w2 ) + (N − 1)H(w1 )

(76)
(77)
(78)
(79)
(80)
(81)
(82)

The converse proof is thus complete.
The achievability is based on PIR2 . Consider L = N 2 symbols of each message at a time. The
user privately generates a random permutation over [1 : N 2 ], and applies the same permutation to
both messages, taken N 2 symbols at a time. Denote this random permutation of the N 2 symbols
from W1 as a1 , a2 , · · · , aN 2 . Similarly, the corresponding random permutation of the N 2 symbols
from W2 is denoted as b1 , b2 . · · · , bN 2 . Note that only symbols with the same index are correlated.
Without loss of generality, suppose W2 is desired, and consider the queries generated according to
PIR2 .
θ=2
Server 1

Server 2

a1 , b1
a2 + bN +1
..
.

a2 , b2
a1 + b2N
..
.

···
Server N
···
a N , bN
· · · a1 + bN 2 −N +2
..
..
.
.

aN + b2N −1 aN + b3N −2 · · ·

aN −1 + bN 2

In order to send (a1 , b1 ), Server 1 needs only H(w1 , w2 ) bits. Note that optimal compression
requires long sequences, so the scheme operates over LN 2 symbols each of W1 and W2 , for large
L, so that a1 is a sequence of L symbols from W1 , and b1 is the corresponding sequence of L
symbols from W2 , and optimal compression is possible as L → ∞. Thus, for (a1 , b1 ) the server
sends LH(w1 , w2 ) + o(L) bits. For a2 + bN +1 , the key is that the server first compresses the L
32

symbols of a2 , and the L symbols of bN +1 , separately, each into LH(w1 ) + o(L) bits. This is
possible because H(w1 ) ≥ H(w2 ). And then the server sends the sum of the compressed bits,
for a total of LH(w1 ) + o(L) bits. Each 2-sum a + b is compressed similarly. Thus, the total
download from Server 1 is LH(w1 , w2 ) + L(N − 1)H(w1 ) + o(L) bits. The total download from all
servers is N times that number of bits. The total number of desired bits retrieved is LN 2 H(w2 ).
Therefore, the rate achieved is limL→∞ LN 2 H(w2 )/N (LH(w1 , w2 ) + L(N − 1)H(w1 ) + o(L)) =
N H(w2 )/(H(w1 , w2 ) + (N − 1)H(w1 )), and the capacity for this case is settled. Finding the
capacity for 3 or more dependent messages with arbitrary dependencies is the next immediate open
problem for future work.

References
[1] H. Sun and S. A. Jafar, “The Capacity of Private Information Retrieval,” IEEE Transactions
on Information Theory, vol. 63, no. 7, pp. 4075–4088, 2017.
[2] ——, “The Capacity of Robust Private Information Retrieval with Colluding Databases,”
arXiv preprint arXiv:1605.00635, 2016.
[3] ——, “The Capacity of Symmetric Private Information Retrieval,”
arXiv:1606.08828, 2016.

arXiv preprint

[4] K. Banawan and S. Ulukus, “The Capacity of Private Information Retrieval from Coded
Databases,” arXiv preprint arXiv:1609.08138, 2016.
[5] Q. Wang and M. Skoglund, “Symmetric private information retrieval for mds coded distributed
storage,” in Communications (ICC), 2017 IEEE International Conference on. IEEE, 2017,
pp. 1–6.
[6] K. Banawan and S. Ulukus, “The capacity of private information retrieval from byzantine and
colluding databases,” arXiv preprint arXiv:1706.01442, 2017.
[7] R. Tandon, “The capacity of cache aided private information retrieval,” arXiv preprint
arXiv:1706.07035, 2017.
[8] M. Mirmohseni and M. A. Maddah-Ali, “Private function retrieval,” arXiv preprint
arXiv:1711.04677, 2017.
[9] B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan, “Private Information Retrieval,” Journal
of the ACM (JACM), vol. 45, no. 6, pp. 965–981, 1998.
[10] N. Shah, K. Rashmi, and K. Ramchandran, “One Extra Bit of Download Ensures Perfectly Private Information Retrieval,” in Proceedings of IEEE International Symposium on Information
Theory (ISIT), 2014, pp. 856–860.
[11] H. Sun and S. A. Jafar, “Optimal Download Cost of Private Information Retrieval for Arbitrary
Message Length,” arXiv preprint arXiv:1610.03048, 2016.

33

