Achievable Rate of Private Function Retrieval from
MDS Coded Databases
Sarah A. Obead, Jörg Kliewer

arXiv:1802.08223v1 [cs.IT] 22 Feb 2018

Helen and John C. Hartmann Department of Electrical and Computer Engineering
New Jersey Institute of Technology
Newark, New Jersey 07102
Email: sao23@njit.edu, jkliewer@njit.edu

Abstract—We study the problem of private function retrieval
(PFR) in a distributed storage system. In PFR the user wishes
to retrieve a linear combination of M messages stored in noncolluding (N, K) MDS coded databases while revealing no information about the coefficients of the intended linear combination
to any of the individual databases. We present an achievable
scheme for MDS coded PFR with a rate that matches the
capacity for coded private information retrieval derived recently,
1−Rc
K
R = (1 + Rc + Rc2 + · · · + RcM −1 )−1 = 1−R
M , where Rc = N is
c
the rate of the MDS code. This achievable rate is tight in some
special cases.

I. I NTRODUCTION
The private retrieval of information from public databases
has received significant attention already for several decades
from researchers in the computer science community (see, e.g.,
[1], [2]). While this line of work, commonly known as private
information retrieval (PIR), is concerned with downloading
individual messages in a private manner from databases, a
recently proposed generalization of this problem [3], [4] addresses the private computation of functions of these messages.
In accordance with [3] we denote this approach as private
function retrieval (PFR) in the following. In PFR a user has
access to a given number of databases and intends to compute
a function of messages stored in these databases. This function
is kept private from the databases, as they may be under the
control of an eavesdropper. Both works [3], [4] characterize the
fundamental information theoretic communication overhead
needed to reliably compute the given function and specify the
corresponding capacity and achievable rates as a function of
the message size, the number of messages, and the number
of databases, respectively. Further, the authors assume that the
data is replicated on each database. Surprisingly, the obtained
PFR capacity result is equal to the PIR capacity of [5].
However, although repetition coding adds the largest amount
of redundancy and thus protects effectively against erasures, it
is associated with a large storage cost. A more general way to
optimally trade-off the available redundancy (or rate) versus
the erasure correcting capability is given by MDS codes. In
particular, for an (N, K) MDS code with N code symbols and
K information symbols and rate Rc = K/N N − K erasures
can be recovered from any K code symbols. Coded PIR has
been addressed in two different lines of work. Achievable
schemes for MDS coded PIR have been presented in [6], [7]
This work is supported by NSF grant CNS-1526547.

and the capacity has been established in [8]. On the other
hand, in [9] linear codes with k different reconstruction sets
for each code symbol have been proposed in form of so called
k-server PIR.
In this paper we propose coded PFR, which to the best
of our knowledge has not been addressed yet in the recent
literature, with the notable exception of the parallel work in
[10], which is based on a fixed (k-) server PIR scheme with the
inclusion of colluding databases. Our scheme is based on MDS
codes which in contrast to [10] minimize the storage overhead
and maximize the achievable download rate. In particular,
we provide a characterization of the achievable rate of MDS
coded PFR if the user wishes to compute an arbitrary linear
combination of M independent equal-sized messages over
some finite field Fq , distributed over N non-colluding MDScoded databases. Surprisingly, our achievable rate matches the
capacity for MDS coded PIR in [8]. This demonstrates that,
compared to the naive scheme, where M coded messages
are downloaded and linearly combined offline at the user
(requiring M -times the coded PIR rate), downloading the
result of the computation privately and directly from the
databases does not incur any penalty in rate compared to
the coded PIR case. Thus, our result strictly generalizes the
achievable schemes in [3], [4] which represent special cases
of our proposed PFR scheme.
II. P ROBLEM S TATEMENT
In the following, we use [1 : X] to denote the set
{1, . . . , X}. Similarly, X1:N = {X1 , . . . , XN }.
A. System Model
In coded PFR, a user wishes to privately retrieve a linear
combination of the messages stored in the databases such that
the coefficients of the linear combination are kept secret from
each individual database. Consider a linear distributed storage
system storing M equal-sized messages on N non-colluding
databases. The message Wm , m ∈ [1 : M ], is composed from
L symbols chosen independently and uniformly at random
from the finite field Fq with
H(W1 ) = · · · = H(WM ) = L log q,
(1)
H(W1 ,. . ., WM ) =H(W1 ) +. . .+ H(WM ) = M L log q. (2)
Each message is divided into L̃ segments, each of K
symbols, forming a L̃ × K matrix, where L = L̃K. The

messages are stored using an (N, K) MDS code with the full
rank generator matrix defined by


(3)
G = g1 g2 . . . gN K×N ,

with gn , n ∈ [1 : N ], denoting the n-th column vector of
G. The generator matrix produces a code that can tolerate
up to N − K erasures by retrieving data from any set K ⊂
{1, . . . , N } databases, where |K| ≥ K. The encoding process
for message Wm is defined as follows:




wm,t 1×K g1 g2 . . . gN K×N


(4)
T
= g1T wm,t . . . gN
wm,t 1×N ,

ν ∈ [1 : V ] from the perspective of each database n ∈ [1 : N ].
In other words, the scheme’s queries and answers strings must
be independent from the desired linear combination index,
therefore the following privacy constraint must be satisfied:
[ν]
(11)
I(A[ν]
n , Qn , WDBn ; ν) = 0, ∀ν ∈ [1 : V ].
After the user receives all answer strings from each database,
the user must be able to reliably decode the desired linear
fν with a probability of error Pe
combination message W
that goes to zero as the message size L approaches infinity.
Following Fano’s inequality, this translates to the decodability
constraint
fν |A[ν] , Q[ν] ) = o(L),
(12)
H(W
1:N
1:N

where wm,t , ∀m ∈ [1 : M ], ∀t ∈ [1 : L̃], denotes the
K-dimensional vector of symbols of the t-th segment from
the message Wm . The resulting N coded symbols for each
segment are then distributed over the N databases, and the
code rate is given by Rc = K
N.
Consequently, the code symbols stored at each database n ∈
[1 : N ] are given by

 T
gn w1,1 gnT w1,2 . . . gnT w1,L̃


..
..
..
..
WDBn = 
 , (5)
.
.
.
.
T
T
T
gn wM,1 gn wM,2 . . . gn wM,L̃

where o(L) represents any function of L, f (L), that satisfies
limL→∞ f (L)/L → 0.
The retrieval rate of the coded PFR scheme is characterized
by the message length L, the query structure Q, and the queryanswer function, and is defined as the ratio between the size of
the desired linear combination message and the total number
of downloaded symbols in bits as
fν )
H(W
R = PN
.
(13)
[ν]
n=1 H(An )

where we use W[t] to denote the t-th column, and Wm (t) for
the element of the m-th row and t-th column of the database,
respectively.
In PFR, the linear combination ν the user intends to retrieve
is represented as

III. ACHIEVABLE R ATE OF MDS C ODED PFR

fν = vν [W1 , . . . , WM ]T
W
= vν (1)W1 + · · · + vν (M )WM


= vν W[1] . . . vν W[L̃] ,

(6)
(7)
(8)

where vν is an M -dimensional non-zero coefficient vector
of the linear combination (row vector) indexed by ν, the
coefficients vν (m), ∀m ∈ [1 : M ], are chosen from the finite
field Fq , and the addition “+” is done element-wise over the
same field. We assume that the vector vν is an element of the
set V that contains all possible distinct M -dimensional vectors
M
−1
defined over Fq where ν ∈ [1 : V ], V = |V| = qq−1
.
In order for the user to retrieve the linear combination
fν , while keeping ν secret from each database, it generates
W
[ν]
[ν]
N query matrices for the databases {Q1 , . . . , QN }. Since
the query matrices are generated by the user without prior
knowledge of the realizations of the stored messages, the
queries must be independent of the messages,
[ν]

[ν]

I(Q1 , . . . , QN ; W1 , . . . , WM ) = 0,

∀ν ∈ [1 : V ].

(9)

[ν]

Upon the reception of the query Qn , the n-th database
[ν]
generates an answer string An as a deterministic function of
the received query and the stored symbols from each message.
Hence,
[ν]
H(A[ν]
n |Qn , WDBn ) = 0, ∀ν ∈ [1 : V ], ∀n ∈ [1 : N ]. (10)

To maintain user privacy, the query-answer function must be
identically distributed for each possible linear combination

A rate R is said to be achievable if there exist a sequence
of coded PFR schemes that satisfy the privacy and correctness
constraints of (11), (12) for Pe → 0 as L → ∞.

Theorem 1. For an (N, K) coded distributed storage system
with code rate Rc = K
N , M messages and a set of V linear
combinations defined over the field Fq , a PFR achievable rate
is given as
1 − Rc
R≤
(14)
1 − RcM

K M−1 −1
K2
K
+ 2 + · · · + M−1
. (15)
= 1+
N
N
N
Remark 1. This achievable rate generalizes the achievable rate
of repetition coded PFR [4] which corresponds to the special
case of K = 1. Also, (14) is only a function of the distributed
storage coding rate Rc and the number of stored independent
messages M, and is universal in the sense that it does not
depend on the number of linear combinations V defined over
the finite field Fq nor on the explicit structure of the code.
Remark 2. If we consider each of the V linear combinations
fν , and then
of messages in (6) as a new virtual message W
apply the coded PIR scheme of [8], the scheme rate will be
1−Rc
1−RV which is smaller than (14) since M ≤ V .
c

Remark 3. When the linear combination set V is reduced
to the first M linear combinations (i.e., v1:M ∈ V :
[v1 v2 . . . vM ] = IM ), the achievable rate of (14) is tight.
That is because in this setting the problem of coded PFR is
reduced to coded PIR where the converse is implied from
[8]. Also, we note that (14) is equivalent to the coded PIR
capacity [8], which has been observed in [4] for K = 1. Thus,
downloading linear combinations of messages does not incur
additional costs over downloading individual messages.

Remark 4. Eq. (14) is a strictly decreasing function in the
number of messages M for fixed Rc . As the number of
messages increases M → ∞, the achievable rate approaches
1
1 − Rc . Moreover, as Rc → 1 in (15), R → M
, indicating
that to maintain the privacy of the desired linear combination,
the user must download all the messages and perform the
computation off-line.
IV. P ROOF OF T HEOREM 1
A. Query generation
The generation of the queries is shown in Algorithm 1.
Let B ∈ [1 : V ] be the block indicator and R ∈ [1 : K]
be the repetition indicator, respectively. Let the v-sum be the
combination of v distinct elements out of V elements. Since
we have Vv different combinations, we denote each different
combination as a type of the v-sum. Let the components of
these combinations be symbols of the V virtual messages. As
mentioned above, we generate the query set for each database

in blocks, where a block represents a group of all Vv types
of v-sums for all v ∈ [1 : V ], resulting in V blocks in total.
To this end, we let the size of the dependent virtual messages
to be L = KN V (i.e., L̃ = N V ).
For a desired linear combination ν ∈ [1 : V ] we use
the notation Q[ν] (DBB ) to indicate the query set of the
database DBB ∈ [1 : N ]. This set is composed from V K
[ν]
disjoint subsets QB,R (DBB ) generated for each block B
and repetition R. We require K V −B (N − K)B−1 distinct
[ν]
instances of each type of v-sum for every set QB,R (DBB ).
Each block and repetition subset is further subdivided into two
[ν]
subsets: the first subset QB,R (DBB , M) consists of the v-sum
types with symbols from the desired linear combination, and
[ν]
the second subset QB,R (DBB , I) contains only v-sum types
with symbols from undesired linear combinations. The query
sets for all databases are generated by Algorithm 1 with the
following procedures.
1) Index assignment: In the MDS-coded PIR scheme [8],
the user privately applies a random permutation over the coded
symbols of each message independently. The goal is to make
the coded symbols queried from each database to appear
to be chosen randomly and independently from the desired
message. However, for the PFR problem the linear function is
computed element-wise, thus there is a dependency across the
symbols with the same index, which must be maintained under
a permutation. To this end, we modify the permutation to be
fixed across all messages. Let π(·) be a random permutation
function over [1 : L̃]. We use the notation Uν (t), where
fν (π(t)) = σt vν W[π(t)],
Uν (t) , σt W

(16)

to indicate the permuted message symbol from the virtual
fν . The random variable σ is used to indicate
message W
the sign assigned to each individual virtual message symbol,
σt ∈ {+1, −1} [4]. Both σt and π are randomly selected
privately and uniformly by the user.
2) Block B = 1: This block is described by Steps 3 to 10
of Algorithm 1, where we have v = 1 for the v-sum.
Initialization: In the initialization step, the user queries the
first database DB1 = 1 for K V −1 distinct symbols from the

desired linear combination Uν (i). This is done by calling the
function ”new(Uν )” that will select a symbol from message
Uν with a new index i each time it is called (Step 6).
Database symmetry: Database symmetry is obtained via the
“For” loop in Step 3, resulting in a total number of N K V −1
symbols over all databases.
Message symmetry: In Step 7, to maintain message symmetry, the user ask each database for the same number of
distinct symbols of all other linear combinations Uθ (i), θ ∈
{1, . . . , V } \ {ν}, resulting in a total number of N V K V −1
symbols. As a result, the query sets for each database are
symmetric with respect to all linear combination vectors in
[1 : V ]. We associate the symbols of undesired messages in K
groups G ∈ [1 : K] to be exploited as distinct side information
for different rounds of the scheme as shown in Step 7.
3) Side-information exploitation: In Steps 11 to 20, we
generate the blocks B ∈ [2 : V ] by applying two subroutines “Exploit-SI” and “M-Sym”, respectively. We first use
the subroutine “Exploit-SI” [4] to generate queries for new
symbols of the desired linear combination Uν by combining
these symbols with different side information groups from the
previous block associated with N − K neighboring databases,
as shown in Step 13. This is required by our proposed MDS
coded scheme to ensure privacy and is in contrast to [4], where
the side information of previous blocks from all databases is
utilized.
Then, the subroutine “M-Sym” [4] is used to generate side
information to be exploited in the following blocks. This
subroutine select symbols of undesired messages to generate vsums that enforce symmetry in the block queries. For example
in B = 2, if we have the queries Uν (i) + U2 (j), and
[ν]
Uν (l)+U3 (r) ∈ Q2,R (DB2 , M), this subroutine will generate
U2 (l) + U3 (i). As a result, we can show that the symmetry
over the linear combinations and databases
 is maintained. By
the end of this step we have in total N VB K V −B (N −K)B−1
queries for each block from all databases.
4) Generation of further query rounds: We require further
query rounds to obtain K linear equations for each coded
symbol to be able to decode. To this end, we circularly
shift the order of the database at each repetition. The shift
is done for the initial block, B = 1, in Steps 22 to 25.
However, for the following blocks we only rotate the indices
of desired messages Uν and combine them with new groups
of side information from the neighboring databases from the
first round as seen in Steps 26 to 33. This rotation and side
information exploitation for B ∈ [2 : V ] is done using the
subroutine “Reuse-SI” (omitted in the interest of space).
5) Query set assembly: Finally, in Steps 35 to 37, we
assemble each query set from the queries disjoint subsets
obtained in the previous blocks and rounds.
Remark 5. Note that the proposed scheme significantly differs
from the one presented in [4] in terms of how the side
information is exploited due to coding. In particular, we
distribute the side information over K rounds such that every
database is queried for each message and linear combination
only once.

Algorithm 1: Query set generation algorithm
Input: ν, K, N, M, and V.
Output: Q[ν] (1), . . . , Q[ν] (N )
1. Initialize: All query sets are initialized as a null set
Q[ν] (1), . . . , Q[ν] (N ) ← ∅, the block counter B = 1, and
repetition counter R = 1. Let number of neighboring databases
Nb = N − K
2. Let repetition RB = K V −B (N − K)B−1 ∀B ∈ [1 : V ]
3. For first database block DB1 = 1 : N do
4. For side information group G = 1 : K do
5.
For repetition group RG = 1 : (R1 /K) do
[ν]

6.

Q1,R (DB1 , M) ←{uν }, uν = new(Uν )

7.

Q1,R (DB1 , IG ) ←{new(U1 ), . . . , new(UV )}\{uν }

[ν]

8.
End For (repeat within the same SI group)
9. End For (repetition for SI groups)
10. End For
11. For block B = 2 : V do
12. For DBB = 1 : N do
[ν]
[ν]
13.
QB,R (DBB , M) ←Exploit-SI QB−1,R (DBB +1, INb )

[ν]
∪ . . .∪ QB−1,R (DBB +N b, I1 )
14.
15.
16.

For side-information group G = 1 : K do
For RG = 1 : (RB /K) do
[ν]

[ν]

QB,R (DBB , IG ) ← M-Sym(QB,R (DBB , M))

17.
End For (repeat within the same SI group)
18.
End For (repeat for SI groups)
19. End For (repeat for each database)
20. End for (repeat for each block)
21. For query round R = 2 : K do
22. For DB1 = 1 : N do
[ν]
[ν]
23.
Q1,R (DB1 , M) ← Q1,R−1 (DB1 − 1, M)
24.

[ν]

[ν]

Q1,R (DB1 , IG ) ← Q1,R−1 (DB1 − 1, IG )

25. End For (initializing rounds)
26. For block B = 2 : V do
27. For DBB = 1 : N do
28.
For side information group G = 1 : K do
[ν]

[ν]

29.

QB,R (DBB , IG ) ← QB,R−1 (DBB − 1, IG )

30.

QB,R (DBB , M) ← Reuse-SI QB,R (DBB , IG ),
[ν]
QB−1,1 (DBB + 1, INb+R−1 ) ∪ . . .

[ν]
· · · ∪ QB−1,1 (DBB + N b, IR )

[ν]

[ν]

31.
End For (SI groups)
32. End For (repeating for each database)
33. End For (repeating for each block)
34. End For (repeating for each round)
35. For DBB = 1 : N do
V [
K
[

[ν]
[ν]
36.
Q[ν] (DBB ) ←
QB,R (DBB , I) ∪ QB,R (DBB , M)
B=1R=1

37. End For (assembling the query sets)

B. Sign assignment and redundancy elimination
We carefully assign an alternating sign σt ∈ [+1, −1] to
each symbol in the query set, based on the desired linear
combination index ν [4]. The intuition behind the sign assignment is to introduce a uniquely solvable linear equation system
from the different v-sum types. By obtaining such an equation
system in each block, the user can opt from downloading these
queries, compute them off-line, and thus reduce the download
rate. Based on this insight we can state the following lemma.

Lemma 1 ([4]). For all ν ∈ [1 : V ], each database
n ∈ [1 : N ], and based on the side information
 available
from the neighboring databases, there are V −M
redundant
v
v-sum types out of all possible types Vv in each block
v ∈ [1 : V − M ] of the query sets.
Lemma 1 is also applicable when the desired linear function
is performed over MDS-coded databases due to the fact that
each MDS-coded symbol is itself a linear combination. That
is, the MDS code can be seen as an inner code and the
desired linear function as an outer “code” with respect to the
databases. Hence, the redundancy resulting from the linear
dependencies between messages is also present under MDS
coding and we can extend Lemma 1 to our scheme. We
now make the final modification to our PFR query sets. We
first directly apply the sign assignment σt , then remove the
redundant v-sum types from every block B ∈ [1 : V ]. Finally,
[ν]
we generate the query matrices Q1:N using a one-to-one
[ν]
mapping function f, for which Q (DBB ) is the preimage.
Proof. The proof of optimality for arbitrary N, K, M and V
follows from the structure of the query and Lemma 1. The
achievable rate is given as
(a)

R ≤
KN

PV



v=1




V
v

−

KN V

V −M
v

NV

K V −v (N − K)v−1

N −K
N




V −v (N − K)v
K V −v (N − K)v − V −M
K
v=1
v

−K
N V NN
(b)
=

PV −M
(N V − K V ) − v=1 V −M
K V −v (N − K)v
v

V N −K
N
N
=

PV −M
(N V − K V ) − K M v=1 V −M
K V −M−v (N − K)v
v

NV 1 − K
N

=
(N V − K V ) − K M N V −M − K V −M

NV 1 − K
N
=
(N V − K V ) − K M N V −M + K V

NV 1 − K
1 − Rc
N
= V
=
;
N − K M N V −M
1 − RcM
=P
V

V
v

where (a) follows from the definition of the PFR rate (13); (b)
follows from the fact that the second term of the summation
in the denominator is equal to zero for v > V − M and consequently we can change the upper bound of the summation;
and the first term of the summation follows from the binomial
theorem.

C. Correctness (decodability)
To prove correctness, we show that the user can obtain
fν from the answers retrieved
the desired linear combination W
[ν]
from N databases. From the query answers A1:N , we group
the K identical queries from different rounds and databases.
Each group will result in K linearly independent equations
that can be uniquely solved. We decode, block by block,
starting from block
which we directly decode and obtain
 one,
KN Vv − V −M
K V −v (N −K)v−1 decoded symbols. Now,
v


using these symbols we regenerate V −M
v  redundant symbols
according to Lemma 1 and obtain KN Vv K V −v (N − K)v−1
symbols in total. Out of these queries there are KN Vv −
 V −v
V −1
fν .
K
(N − K)v−1 symbols from W
v
Next, for blocks B ∈ [2 : V ], we use the symbols obtained
in the previous block B − 1 to remove the side information
associated with the desired linear combination symbols of
the current block B, then the operations from the first block
(decode and retrieve redundancy) are repeated. As
we
PaV result,
V
obtaina total number of symbols equal to KN v=1
−
v

V −1
N
V
V −1
V
V −v
v−1
N
−
KN
=
KN
K
(N
−
K)
=
N −K
v
fν .
denoting precisely the number of symbols in W

D. Privacy
Privacy is guaranteed by preserving an equal number of
fν , where the requests
requests for any linear combination W
are symmetric from the perspective of the accessed virtual
messages. As the MDS code can be seen as an outer code,
the arguments in [3], [4] apply here as well. In particular,
each database is queried with precisely the same v-sum
type components, i.e., Uν (t), which ensures symmetry. This
can be seen from Step 16 in Algorithm 1 where the same
subroutine “M-Sym” is used for each block and database.
By selecting a permutation π(t) and a sign assignment σt
uniformly at random, queries for code symbols are permuted
in the same way over all databases. With other words, for
any Uν (t) = σt vν W[π(t)] there exist σt , π(t) such that
[ν]
Q[θ] (DBB ) ↔ Q[ν] (DBB ) ∀ν, θ ∈ [1 : V ]. Thus, An , and
[ν]
Qn are statistically independent of ν and (11) holds.

V. E XAMPLE
We consider M = 2 messages stored using a (3, 2) MDS
code. The user wishes to obtain a linear combination over
V = 3). Therefore, we have
the binary field (i.e., vν ∈ FM
2 ,
the linear combinations v1 = [1 0], v2 = [0 1], v3 = [1 1], and
each message must be of length L = KN V = 54 symbols.
We simplify the notation by letting at = U1 (t), bt = U2 (t),
and ct = U3 (t) for all t ∈ [1 : 27]. Let σt = 1 ∀t and let the
desired linear combination index be ν = 3.
Query set construction: Algorithm 1 starts with B = 1
by generating queries for each database and K V −1 = 4
distinct instances of ct (i.e., from database 1 query g1T (c1:4 ) ,
{g1T c1 , . . . , g1T c4 }). By message symmetry this also applies
for at and bt to form two groups of side information sets
to be used in the next block with N K V −1 = 12 symbols
in total from each linear combination. Next, one group of
side information is queried jointly with a new instant of the
desired message. For example, for database 1 and type b + c
we have g1T (b5:6 − c13:14 ) , {g1T b5 − g1T c13 , g1T b6 − g1T c14 }.
The remaining blocks and rounds follow from Algorithm 1.
After generating the query set for each database, we apply the
sign assignment and remove the redundant queries.
Decoding: The answer strings from each query are shown
in Table 1. Note that there is no ct in the first block as they
are redundant and can be generated by the user. To decode we
start with Block 1, and we obtain g1T a1 from database 1 and
g2T a1 from database 2. Thus, by the MDS code properties we

can decode and obtain the segment a1 ; similarly for all other
queries in this block. Now for Block 2, we first remove the
side information from the types containing symbols of ct . For
example, for g1T b5 − g1T c13 from database 1, we have b5 from
the previous block. As a result, we obtain g1T c13 . Similarly
we obtain g2T c13 from database 2, and c13 can be recovered.
TABLE I
T HE QUERY RESPONSE FOR PFR FROM (3, 2) MDS CODED DATABASES ,
M = 2, V = 3, AND ν = 3
(R,B)

DB1

DB2

DB3

(1, 1)

g1T (a1:4 )
g1T (b1:4 )

g2T (a5:8 )
g2T (b5:8 )

g3T (a9:12 )
g3T (b9:12 )

(1, 2)

g1T (b5:6 − c13:14 )
g1T (a5:6 − c15:16 )

g2T (b9:10 − c17:18 )
g2T (a9:10 − c19:20 )

g3T (b1:2 − c21:22 )
g3T (a1:2 − c23:24 )

g1T (a13:14 − b15:16 ) g2T (a17:18 − b19:20 ) g3T (a21:22 − b23:24 )
T (a −b +c )
(1, 3) g1
17
19
25

g2T (a21 −b23 +c26 )

g3T (a13 −b15 +c27 )

(2, 1)

g1T (a9:12 )
g1T (b9:12 )

g2T (a1:4 )
g2T (b1:4 )

g3T (a5:8 )
g3T (b5:8 )

(2, 2)

g1T (b7:8 − c21:22 )
g1T (a7:8 − c23:24 )

g2T (b11:12 − c13:14 )
g2T (a11:12 − c15:16 )

g3T (b3:4 − c17:18 )
g3T (a3:4 − c19:20 )

g1T (a21:22 − b23:24 ) g2T (a13:14 − b15:16 ) g3T (a17:18 − b19:20 )
(2, 3) g1T (a18 −b20 +c27 )

g2T (a22 −b24 +c25 )

g3T (a14 −b16 +c26 )

VI. O UTER B OUND FOR THE S PECIAL C ASE V = 2
In the special case of V = 2, M independent messages,
and any (N, K) MDS code an outer bound for the coded
PFR problem is obtained by combining the independence of
answer strings from any K databases [8, Lemma 2] with [4].
Thus, we can show that the retrieval rate is upper bounded as
H(ω1 )
, where the joint distribution of
R ≤ KH(ω1 ,ωN
2 )+H(ω1 )(N −K)
f1,ℓ , W
f2,ℓ ) for all ℓ ∈ [1 :
(ω1 , ω2 ) is the joint distribution of (W
L̃] selected iid with respect to the symbols of the messages.
R EFERENCES
[1] B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan, “Private information retrieval,” J. ACM, vol. 45, no. 6, pp. 965–981, Nov. 1998.
[2] S. Yekhanin, “Private information retrieval,” Commun. ACM, vol. 53,
no. 4, pp. 68–73, Apr. 2010.
[3] M. Mirmohseni and M. A. Maddah-Ali, “Private function retrieval,” ArXiv e-prints, 2017. [Online]. Available:
http://arxiv.org/abs/1711.04677
[4] H. Sun and S. A. Jafar, “The capacity of private computation,” ArXiv
e-prints, 2017. [Online]. Available: http://arxiv.org/abs/1710.11098
[5] ——, “The capacity of private information retrieval,” IEEE Transactions
on Information Theory, vol. 63, no. 7, pp. 4075–4088, July 2017.
[6] T. H. Chan, S.-W. Ho, and H. Yamamoto, “Private information retrieval
for coded storage,” in Proc. IEEE Int. Sympos. on Inform. Theory. IEEE,
June 2015, pp. 2842–2846.
[7] R. Tajeddine and S. E. Rouayheb, “Private information retrieval from
MDS coded data in distributed storage systems,” in Proc. IEEE Int. Sympos. on Inform. Theory, July 2016, pp. 1411–1415.
[8] K. Banawan and S. Ulukus, “Private information retrieval from coded
databases,” in IEEE Int. Conf. on Commun. (ICC), May 2017, pp.
1–6.
[9] A. Fazeli, A. Vardy, and E. Yaakobi, “Codes for distributed PIR with
low storage overhead,” in Proc. IEEE Int. Sympos. on Inform. Theory,
June 2015, pp. 2852–2856.
[10] D. Karpuk, “Private computation of systematically encoded data with
colluding servers,” ArXiv e-prints, Jan. 2018. [Online]. Available:
https://arxiv.org/abs/1801.02194

