Private Computation of Systematically Encoded
Data with Colluding Servers
David Karpuk

arXiv:1801.02194v2 [] 13 Jan 2018

Departamento de Matemáticas
Universidad de los Andes
Bogotá, Colombia
Email: da.karpuk@uniandes.edu.co

Abstract—Private Computation (PC), recently introduced by
Sun and Jafar, is a generalization of Private Information Retrieval (PIR) in which a user wishes to privately compute an
arbitrary function of data stored across several servers. We
construct a PC scheme which accounts for server collusion,
coded data, and non-linear functions. For data replicated over
several possibly colluding servers, our scheme computes arbitrary
functions of the data with rate equal to the asymptotic capacity
of PIR for this setup. For systematically encoded data stored
over colluding servers, we privately compute arbitrary functions
of the columns of the data matrix and calculate the rate explicitly
for polynomial functions. The scheme is a generalization of
previously studied star-product PIR schemes.

capacity of PIR with T -collusion. For data encoded using an
[N, K] systematic storage code, we construct a scheme which
evaluates arbitrary functions of the columns of the data matrix
and protects against T -collusion. When using Reed-Solomon
codes and computing polynomial functions of degree G, our
scheme has rate min{N − (G(K − 1) + T ), K}/N . While the
rates we obtain are highly suggestive of asymptotic capacity
results, we sidestep capacity questions in favor of explicit
constructions.

I. I NTRODUCTION

We assume basic familiarity with linear coding theory, and
refer to [12] as a general reference. If C is a linear code over
a finite field F with length N , dimension K, and minimum
distance D, we refer to it as an [N, K, D]F code, and possibly
omit the D or F if they are irrelevant or clear from context.
A generator matrix for C is denoted by GC ∈ FK×N , and
a parity-check matrix by HC ∈ FN ×(N −K) . Recall that C is
MDS if and only if D = N − K + 1 if and only if every K
columns of GC are linearly independent. The repetition code
over F is denoted by Rep(N )F , and it is an [N, 1] MDS code.
1) Star Products: Let C and D be linear codes of length N .
Their star product C ⋆ D ⊆ F1×N is the F-span of all vectors
of the form

A. Background and Summary of Current Results
The problem of Private Information Retrieval (PIR), introduced in [1], is to download a file from a database without
revealing the identity of the file. The data is usually assumed to
be encoded over several servers, subsets of which may collude
to try to deduce the identity of the file. The rate of a PIR
scheme is the size of the desired file to the total amount of
data the user must download, and the capacity of a given PIR
setup is the maximum possible rate.
The capacity of PIR for data replicated over several servers
was obtained in [2], for replicated data with colluding servers
in [3], and for MDS-coded data without server collusion in [4].
The capacity of PIR for MDS-coded data with server collusion
remains open, but the star-product scheme of [5] has, as far as
the author knows, the best rates yet obtained as the number of
files goes to infinity. Related PIR schemes and capacity results
have been studied in [6]–[10].
Private Computation (PC), introduced by Sun and Jafar
in [11], generalizes PIR by allowing the user to compute
arbitrary linear combinations of the files for replicated data.
Surprisingly, the capacity of this setup is equal to the PIR
capacity of [2]. This leaves open a multitude of questions,
most notably scheme constructions for PC which account for
colluding servers, coded data, non-linear functions, etc.
The current contribution generalizes the star-product scheme
of [5] to construct explicit PC schemes for colluding servers,
coded data, and non-linear functions. In particular, we show
that for a data vector replicated over N servers with T collusion, private computation of arbitrary functions is possible
with download rate (N − T )/N , which is the asymptotic

B. Some Coding-Theoretic Preliminaries

c ⋆ d = [c(1)d(1), . . . , c(N )d(N )] ∈ F1×N .

(1)

for c ∈ C and d ∈ D. For any G > 0, the G-fold star product
of C with itself is
C ⋆G = spanF {c1 ⋆ · · · ⋆ cG | cg ∈ C}

(2)

Note that C ⋆ Rep(N )F = C for any linear code C, and that if
Rep(N )F ⊆ C then C ⊆ C ⋆ C and thus by induction C ⋆G1 ⊆
C ⋆G2 for any G1 ≤ G2 .
2) Reed-Solomon Codes: Let α = [α(1), . . . , α(N )] ∈
F1×N be such that α(i) 6= α(j) for all i 6= j. For any
K ≤ N , we define the [N, K] Reed-Solomon Code (RS code)
associated to this data by
RS K (α) = {φ(α) | φ ∈ F[X], deg(φ) < K}

(3)

where φ(α) = [φ(α(1)), . . . , φ(α(N ))] ∈ F1×N . We call
α the evaluation vector of RS K (α). It is well-known that

RS K (α) is an [N, K] MDS code. For two RS codes with the
same evaluation vector, we have the following:
RS K (α) ⋆ RS L (α) = RS min{K+L−1,N } (α)

(4)

for which we refer to [5] for a proof. By induction we have
RS K (α)⋆G = RS min{G(K−1)+1,N } (α).

(5)

3) Base Field Extension: Let C ⊆ F1×N be a linear code,
and let K/F be a finite field extension of F. We define the
extension of C to K to be the code CK ⊆ K1×N given by
the K-span of the rows of GC . Base field extension does not
change any essential properties of the code:
Proposition 1: Let C be an [N, K, D]F code, and let K/F
be a finite field extension. We have the following:
(i) CK is an [N, K, D]K code, hence if C is MDS so is CK .
(ii) The matrices GC and HC are generator and parity-check
matrices, respectively, for CK .
(iii) For any code D ⊆ F1×N , we have (C ⋆ D)K = CK ⋆ DK .
(iv) RS K (α)K is also an RS code over K, where we view
the vector α as an element of K1×N .
Proof: The proofs of all of these statements follow
immediately from the definitions.
II. S YSTEM M ODEL AND P ROBLEM S TATEMENT

Let F be a finite field, and let K/F be a finite field extension
of F. We consider a data matrix
(6)

consisting of K column vectors xk ∈ KM×1 . The matrix X
is stored across N servers using an [N, K]F storage code C
by defining
X · GC = Y = [y1 · · · yN ] ∈ KM×N

(7)

Server n now stores the nth column vector yn ∈ KM×1 .
It will be convenient to define
F = {all functions KM×1 → K}

ρ(Y) = [ρ1 (y1 ), . . . , ρN (yN )] ∈ K1×N

(8)

as the space of all possible queries. Given some B functions
φb ∈ F , the goal is to privately compute all values φb (xk ),
for 1 ≤ b ≤ B and 1 ≤ k ≤ K. We refer to B as the block
length, and view it as a flexible parameter the user can adjust
to download the φb (xk ) with maximal efficiency.
Definition 1: Given a data matrix X ∈ KM×K , an encoded
data matrix X · GC = Y ∈ KM×N , and a block length B, a
Private Computation (PC) scheme for this setup consists of:
1) A query space Q ⊆ F , from which B functions φb to
be evaluated on the columns of X are sampled according
to a random variable Q on QB . Both Q and Q are made
public.
2) Queries ρ1 , . . . , ρn ∈ Q, where ρn is transmitted by the
user to the nth server.

(9)

4) An iteration process, wherein the user repeats steps 2. and
3. a total of S times (choosing different queries during
each iteration) until all function values φb (xk ) can be
computed from all of the S vectors ρ(Y).
Our main measurement of the efficiency of a PC scheme is
the download rate, defined as follows.
Definition 2: Given a PC scheme with parameters as in the
previous definition, the PC rate, or download rate, or simply
rate of the PC scheme is defined to be
KB
.
(10)
R=
NS
The assumption that [K : F] ≫ 0 generally allows one
to ignore upload costs and focus on the download rate of
a scheme as the primary performance metric. Nothing is
lost mathematically in the construction and analysis of our
schemes, however, by assuming that K = F.
Definition 3: Let T ⊆ [N ] be a subset of servers of size T .
A PC scheme protects against the colluding set T if
I(Q; PT ) = 0

A. Basic Definitions

X = [x1 · · · xK ] ∈ KM×K

3) Responses ρn (yn ) ∈ K, computed by the servers and
transmitted back to the user, who receives the total
response vector

(11)

where PT is the random variable given by all queries sent
to all servers in T over all S iterations of the scheme. If a
PC scheme protects against every subset of servers of size
T , we say that the scheme protects against T -collusion, or is
T -private, and refer to it as a T -PC scheme.
B. Comparison with Other Private Computation Models and
Private Information Retrieval
We now briefly discuss how our model of Section II-A
compares with two previous works on Private Computation,
notably [11], [13]. Assume K = F for simplicity. In [11],
[13] the authors set K = 1 and consider a replication system
with C = Rep(N )F , so each of N servers is storing a copy
of X ∈ FM×1 . The vector X is divided into M ′ datasets
′
Xm ∈ FB×1 , so that M = BM ′ , and the user wishes to
compute a linear combination
′

λ1 X1 + · · · + λM ′ XM ∈ FB×1 ,

λm′ ∈ F

(12)

of the datasets. This is equivalent to computing the matrix
multiplication Φ · X, where Φ ∈ FB×M is the block matrix
Φ = [λ1 IB · · · λM ′ IB ]

(13)

Setting the φb to be the linear functions defined by the rows
of Φ then reproduces the main problem of [11], [13] as an
particular instance of our model (here one can set Q to be the
set of all linear functions FM×1 → F, and Q to be uniform on
some subset of all such above Φ). In addition to generalizing
the model of [11] from certain linear functions of the data
vector to arbitrary functions, our model is perhaps simpler in

the sense that we avoid discussing datasets and discard the
parameter M ′ .
Private Information Retrieval (PIR) is simply a special
instance of the above PC problem, in which some λw = 1
and λm′ = 0 for m′ 6= w. In general, one considers arbitrary
storage codes (K > 1) as well as non-trivial server collusion
(T > 1), but substituting an arbitrary storage code C into the
above discussion or accounting for server collusion does not
affect the way in which PC generalizes PIR.
C. Private Polynomial Computation
Our motivating example will be computing polynomial
functions of the data matrix. More precisely, given a positive
integer G, let
PG = {φ ∈ F[X1 , . . . , XM ] | deg(φ) ≤ G, φ(0) = 0} (14)
be the F-vector space of polynomials in M variables with
coefficients in F and no constant term, whose total degree
is bounded above by G. Here we recall that the degree of
aM
a1
a multivariate
P monomial φ = X1 · · · XM is defined to be
deg(φ) = m am , and for a general polynomial, deg(φ) is
the maximal degree of all the monomials appearing in φ.
Proposition 2: Consider the F-linear map η : PG → F
taking a polynomial to the function it defines. If G < |K|,
then this map is injective.
Proof: We have to show that φ does not define the zero
function on KM×1 , for all φ ∈ PG . Let x ∈ KM×1 be selected
uniformly at random. By the Schwartz-Zippel Lemma, we
have Pr(φ(x) = 0) ≤ G/|K| < 1. In particular, there exists
an x such that φ(x) 6= 0, which proves the statement.
To privately compute φb (xk ) where the functions φb are
polynomials of degree bounded by G, we set the query space
to be Q = η(PG ). When G < |K|, Proposition 2 allows us to
ignore the distinction between polynomials and the functions
they define, and simply set Q = PG .
III. T -P RIVATE C OMPUTATION

OF

R EPLICATED DATA

In this section we assume that C = Rep(N )F , so K = 1
and every server stores a copy of X ∈ KM×1 . Thus the goal
is to T -privately compute φb (X) for some B functions φb :
KM×1 → K. We show that for any query space Q which is
a vector space over F, we can perform this computation with
download rate equal to (N − T )/N , which is the asymptotic
capacity as M → ∞ of T -PIR.
A. Scheme Construction
We assume that Q ⊆ F is a vector space over F. We
do not assume that the elements of Q are themselves linear
functions, only that Q is closed under function addition and
scalar multiplication by elements of F.
We set Q = dimF Q and let {ψ 1 , . . . , ψ Q } ⊂ Q be an Fbasis of Q. Our scheme is based on the construction of [5] for
replicated data. In particular, we use an [N, T ] MDS retrieval
code D to guarantee that the queries sent to any T servers are
uniformly distributed on QT and independent of the functions
φb . We retrieve the function values by decoding in D.

Let D be an [N, T ]F MDS code. The first iteration of our
scheme proceeds as follows. We sample, independently and
uniformly, codewords d1 , . . . , dQ ∈ D. For each server n =
1, . . . , N , define
ψn = d1 (n) · ψ 1 + · · · + dQ (n) · ψ Q ∈ Q
q

th

(15)

q

where d (n) ∈ F denotes the n coordinate of d . Suppose
we want to evaluate functions φ1 , . . . , φB ∈ Q, sampled
according to Q. We define the queries as follows:

ψn + φn if n ≤ N − T
ρn =
(16)
ψn
if n > N − T
The total response from the servers is given by
ρ(X) = [ψ1 (X), . . . , ψN (X)] + [φ1 (X), . . . , φN −T (X), 0]
{z
}
|
=:ψ(X)

(17)

We claim that ψ(X) ∈ DK . To see this, we write
ψ(X) =

Q
X

[dq (1)ψ q (X), . . . , dq (N )ψ q (X)]

(18)

ψ q (X) · dq ∈ DK

(19)

q=1

=

Q
X
q=1

Let HD ∈ FN ×(N −T ) be a parity-check matrix of D in
systematic form. We retrieve the desired function evaluations
by right-multiplying ρ(X) by HD . Since ψ(X) ∈ DK we
have that ψ(X) · HD = 0, and hence
ρ(X) · HD = [φ1 (X), . . . , φN −T (X)]

(20)

hence we retrieve the desired function evaluations.
Now suppose that N − T divides B. To compute the
remaining function evaluations φN −T +1 (X), . . . , φB (X), we
simply iterate the above procedure a total of B/(N −T ) times,
each time choosing the next N − T of the functions φb in the
obvious way. The scheme construction is complete.
B. Proofs of Correctness and T -Privacy
The T -privacy of the above scheme construction will follow
from the following useful Lemma.
Lemma 1: Let V be a finite-dimensional vector space over a
finite field, and let U be a uniform random variable on V. Let
Z be any other random variable on V which is independent of
U. Then W = U + Z is uniform on V and I(W; Z) = 0.
Proof: This is a straightforward calculation using the
pmfs of all three random variables.
Theorem 1: Suppose that N − T divides B. Then for any
F-linear query space Q, the above PC scheme protects against
T -collusion and has download rate (N − T )/N .
Proof: The proof of T -privacy is analogous to that of the
main scheme of [5]. Specifically, let T ⊆ [N ] be a subset of
servers of size T , and consider the projection DT of D onto
the coordinates in T . Since D is MDS, this projection D →
DT = F1×T is surjective. It follows that if T = {n1 , . . . , nT },
then the tuple
(21)
[ψn1 , . . . , ψnT ] ∈ QT

defines the uniform random variable on QT . Since the φb and
ψn are chosen independently, Lemma 1 shows that we protect
against T -collusion during a single iteration. As the source of
randomness is independent between iterations, the condition
(11) follows in general. Computing the download rate gives
−T
as claimed.
R = BB ·N = NN
N −T
When T = 1 and N > 1, the PC scheme of [11] achieves
a rate of (1 − 1/N )/(1 − (1/N )M ), which they show is the
capacity for the query space Q of linear functions described
in Section II-B. The scheme of Section III-A achieves the
limiting value (N − 1)/N as M → ∞, for any F-linear query
space whatsoever. The capacity of T -PC is unknown for T > 1
and arbitrary Q, but it our hope that the rate (N − T )/N we
achieve is equal to asymptotic capacity, for any F-linear Q.
Example 1: Suppose that N = 3 and T = 2. To protect
against 2-collusion we set D to be the [3, 2, 2]F2 code with


1 0 1
GD =
(22)
0 1 1
We take the block length to be B = 1 and set the query
space to be Q = P2 . We will 2-privately compute a degree
2 polynomial function φ(X) with rate (N − T )/N = 1/3.
To identify polynomials with the functions they define as in
Proposition 2, we assume that |K| ≥ 4.
Suppose we want to evaluate some φ ∈ P2 on the data
vector X. Choosing a basis of P2 and sampling the ψn ∈ P2
as in (15), the queries are of the form
ρ1 = ψ1 + φ, ρ2 = ψ2 , ρ3 = ψ3

(23)

P22

any two of which are uniform on
and independent of the
random variable Q. The response vector is of the form
ρ(X) = ψ(X) + [φ(X) 0 0] ∈ K1×3

(24)

Right-multiplication by HD (the all-ones column vector of
length 3) yields ρ(X) · HD = φ(X).
C. Remarks on Upload Cost
Using the T -PC scheme of Section III-A, every iteration
the user must upload N elements of Q, which amounts of
N Q elements of F. On the other hand, the user receives N
elements of K in return, or equivalently N · [K : F] elements
of F. Thus ignoring upload costs amounts to assuming that
[K : F] ≫ dimF Q. So ignoring upload costs when evaluating
high-degree polynomials thus requires the data matrix X to
be defined over a very large extension of F.
IV. T -P RIVATE C OMPUTATION OF S YSTEMATICALLY
E NCODED DATA
In this section we consider polynomial computation of data
encoded using a systematic storage code C. Our construction is
again a generalization of that of [5], in that the user guarantees
T -privacy by using an [N, T ] MDS retrieval code D. In
the PIR scheme of [5] the user recovers the desired file by
decoding in C ⋆ D. When the query space is generalized to
be Q = PG with G ≥ 1, the user now recovers the desired
function evaluations by decoding in C ⋆G ⋆ D. Reed-Solomon

(1)
[φb (xk )] = (2)
(3)

(1)
(2)
(3)

(1)
(2)
(4)

(1)
(2)
(4)

(1)
(3)
(4)

(1)
(3)
(4)

(2)
(3)
(4)

(2)
(3)
(4)

Fig. 1. Visualizing the iteration process for the PC scheme via the matrix
[φb (xk )] ∈ K3×8 , for a system with parameters K = 8, B = 3, and F = 6.
An integer (s) in an entry of the above signifies that that entry is downloaded
during the sth iteration. We require S = KB/F = 4 iterations in total.

codes are shown to be especially useful in this context, in
which case the download rate decreases linearly in G.
A. Scheme Construction
Let Q be an F-linear query space, and define
C Q = spanK {[ψ(y1 ), . . . , ψ(yN )] ∈ K1×N | ψ ∈ Q} (25)
where we range over all possible Y = [y1 , . . . , yN ] = X · GC
for X ∈ KM×K . For example, if Q = P1 then C Q = CK .
We pick an [N, T ]F MDS code D as before, and define the
ψn ∈ Q as in (15). The first iteration of the scheme proceeds
as follows. Let F ≤ K be a constant whose exact value will
be determined shortly. We define the queries by setting

ψn + φ1 if n ≤ F
ρn =
(26)
ψn
if n > F
so that the total response vector is of the form
ρ(Y) = [ψ1 (y1 ), . . . , ψN (yN )] + [φ1 (x1 ), . . . , φ1 (xF ), 0]
|
{z
}
=:ψ(Y)

(27)
where yk = xk for k ≤ F ≤ K because C is in systematic
form. One easily computes that
ψ(Y) =

Q
X

[ψ q (y1 ), . . . , ψ q (yN )] ⋆ dq ∈ C Q ⋆ DK

(28)

q=1

Let E = C Q ⋆ DK , let DE be the minimum distance of E, and
choose F = min{DE −1, K}. Since every DE −1 rows of HE
are linearly independent, right-multiplication of ρ(Y) by HE
allows us to decode the function values φ1 (x1 ), . . . , φ1 (xF )
from (27). This is simple error decoding in E with errors in
prescribed positions, which can always correct up to DE − 1
such errors. Here the “errors” are the values φ1 (xk ).
We iterate the above by writing K = L·F +F̄ with 0 ≤ F̄ <
F . Suppose first that F̄ = 0, so that F divides K. To compute
the rest of the function evaluations φ1 (xF +1 ), . . . , φ1 (xK ) we
use L total iterations of the scheme, using the next successive
set of F servers each iteration when adding φ1 to the functions
ψn as in (26). After L iterations, we have thus computed
φ1 (xk ) for all 1 ≤ k ≤ K, and if B > 1 we simply repeat the
above process with each φb in place of φ1 . In the case where
F̄ = 0 the scheme is complete.
When F̄ > 0 we first iterate the scheme L times to compute
φ1 (x1 ), . . . , φ1 (xLF ) as above. In the (L + 1)st iteration, we
set

 ψn + φ1 if LF + 1 ≤ n ≤ K
ρn =
ψn + φ2 if 1 ≤ n ≤ F − F̄
(29)

ψn
otherwise

and decode in E to download the function values
φ1 (xLF +1 ), . . . , φ1 (xK ),
as
well
as
the
values
φ2 (x1 ), . . . , φ2 (xF −F̄ ), for a total of F values downloaded
during this iteration. The scheme now proceeds in an obvious
way, downloading values φ2 (xk ) in groups of F at a time
until we get to the end of the list of systematic servers, where
we “wrap around” and download values φ3 (xk ) starting with
server 1, as in (29) and as illustrated in Fig. 1. We continue
this way until all values φb (xk ) are downloaded, choosing
the block length B so that KB is divisible by F . In this case,
the scheme requires S = KB/F iterations.
Theorem 2: With the notation as in the above scheme
construction, assume that F divides KB. Then the above PC
scheme is T -private and has rate R = F/N .
Proof: The proof of T -privacy is exactly as in Theorem
1 and is thus omitted. The download rate is readily calculated
to be R = KB
SN = F/N as claimed.
B. T -Private Computation of Polynomial Functions of Systematically Encoded Data
In general, determining the code C Q and the minimum
distance and parity-check matrix of E may be intractable for
a general query space Q. However, when Q = PG , the codes
C Q and E take a particularly simple form.
Proposition 3: Let C be a linear code such that C ⊆ C ⋆ C.
Then for the query space Q = PG , we have C Q = (CK )⋆G
and therefore E = (C ⋆G ⋆ D)K .
Proof: Picking a basis of PG to consist only of monomials
with F-coefficients, we see that it suffices to show that
ψ q (Y) = [ψ q (y1 ), . . . , ψ q (yN )] is in (CK )⋆G for any monoaM
mial ψ q of degree ≤ G. Suppose that ψ q = X1a1 · · · XM
, and
write yn = [yn1 , . . . , ynM ]T . Note that for each m, the vector
[y1m , . . . , yN m ] is a codeword in CK . We have
" M
#
M
Y
Y
am
am
ψ q (Y) =
(30)
y1m
,...,
yN
m
m=1

m=1

= [y11 , . . . , yN 1 ]⋆a1 ⋆ · · · ⋆ [y1M , . . . , yN M ]⋆aM

∈ (CK )⋆a1 ⋆ · · · ⋆ (CK )⋆aM ⊆ (CK )⋆G
and hence ψ q (Y) ∈ (CK )⋆G as claimed. We have shown that
C Q ⊆ (CK )⋆G , and equality follows by picking the ψ q to be
all monomials of degree exactly G.
Due to the simplicity of the star-product of RS codes as
noted in (4) and (5), applying the above when C and D are
Reed-Solomon codes yields explicit rate expressions.
Theorem 3: Let C = RS K (α) and D = RS T (α), for some
evaluation vector α ∈ F1×N . Suppose that G(K −1)+T ≤ N .
Then the download rate of the T -PC scheme for the query
space Q = PG of the previous subsection is given by
R = min{N − (G(K − 1) + T ), K}/N

(31)

Proof: Note that all RS codes contain the repetition code,
so the condition C ⊆ C ⋆ C is satisfied. One now calculates
using Proposition 3, (4), and (5) that E = (CK )⋆G ⋆ DK is an
RS code with minimum distance N − (G(K − 1) + T ) + 1.

V. C ONCLUSIONS

AND

F UTURE W ORK

In this paper we have generalized the methods of [5] to
construct T -Private Computation schemes. The first scheme,
for a data vector replicated over N servers of which any T can
collude, achieves a rate of (N − T )/N for arbitrary functions
of the data. This is same as the PIR rate achieved in [5]. The
second scheme evaluates arbitrary functions of data encoded
systematically with an [N, K] storage code. When the storage
and retrieval codes are Reed-Solomon codes, we obtain a rate
of min{N − (G(K − 1) + T ), K}/N for evaluating degree G
polynomial functions.
We remark that when G = 1, an obvious variant of the
scheme of Section IV-A (which we save for an extended
version of this paper) improves the rate to (DE − 1)/N .
However, this improvement seems difficult for G > 1, as the
function evaluations φb (xk ) cannot be readily obtained from
values φb (yn ) when φb is non-linear and n is a non-systematic
node. Making this improvement for higher-degree polynomials
and general non-linear functions is our next immediate order
of business. Secondly, our scheme is easily symmetrizable by
having the servers jointly add a uniform random codeword in
E to the total response vector, a nice feature which we will
incorporate into future work. Lastly, many capacity achieving
schemes [2], [11] employ query spaces Q which are not Fvector spaces. Studying potential rate improvements given by
non-linear query spaces is thus a worthwhile open problem.
R EFERENCES
[1] B. Chor, E. Kushlevitz, O. Goldreich, and M. Sudan, “Private information retrieval,” Journal of the ACM, vol. 45, no. 6, pp. 965–981, 1998.
[2] H. Sun and S. A. Jafar, “The capacity of private information retrieval,”
IEEE Transactions on Information Theory, vol. 63, no. 7, pp. 4075–
4088, July 2017.
[3] ——, “The capacity of robust private information retrieval with colluding databases,” IEEE Transactions on Information Theory, 2017.
[4] K. Banawan and S. Ulukus, “The capacity of private information
retrieval from coded databases,” 2016, arXiv: 1609.08138.
[5] R. Freij-Hollanti, O. W. Gnilke, C. Hollanti, and D. A. Karpuk, “Private
information retrieval from coded databases with colluding servers,”
SIAM Journal on Applied Algebra and Geometry, vol. 1, no. 1, pp.
647–664, 2017.
[6] R. Tajeddine, O. W. Gnilke, D. Karpuk, R. Freij-Hollanti, C. Hollanti,
and S. E. Rouayheb, “Private information retrieval schemes for coded
data with arbitrary collusion patterns,” in 2017 IEEE International
Symposium on Information Theory (ISIT), June 2017, pp. 1908–1912.
[7] Y. Zhang and G. Ge, “Private information retrieval from mds coded
databases with colluding servers under several variant models,” 2017.
[Online]. Available: https://arxiv.org/abs/1705.03186
[8] S. Kumar, H.-Y. Lin, E. Rosnes, and A. G. i Amat, “Achieving private
information retrieval capacity in distributed storage using an arbitrary
linear code,” 2017. [Online]. Available: https://arxiv.org/abs/1712.03898
[9] R. Freij-Hollanti, O. Gnilke, C. Hollanti, A.-L. HorlemannTrautmann, D. Karpuk, and I. Kubjas, “t-private information
retrieval schemes using transitive codes,” 2017. [Online]. Available:
https://arxiv.org/abs/1712.02850
[10] K. Banawan and S. Ulukus, “The capacity of private information
retrieval from byzantine and colluding databases,” 2017. [Online].
Available: https://arxiv.org/abs/1706.01442
[11] H. Sun and S. Jafar, “The capacity of private computation,” 2017.
[Online]. Available: https://arxiv.org/abs/1710.11098
[12] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting
Codes. Amsterdam: North Holland, 1977.
[13] M. Mirmohseni and M. A. Maddah-Ali, “Private function retrieval,”
2017. [Online]. Available: https://arxiv.org/abs/1711.04677

