1

Private Information Retrieval from Transversal
Designs
Julien L AVAUZELLE
Laboratoire LIX, École Polytechnique, Inria & CNRS UMR 7161
Université Paris-Saclay

arXiv:1709.07952v1 [] 22 Sep 2017

Abstract
Private information retrieval (PIR) protocols allow a user to retrieve entries of a database without revealing the
index of the desired item. Information-theoretical privacy can be achieved by the use of several servers and specific
retrieval algorithms. Most of known PIR protocols focus on decreasing the number of bits exchanged between the
client and the server(s) during the retrieval process. On another side, Fazeli et. al. introduced so-called PIR codes in
order to reduce the storage overhead on the servers. However, only a few works address the issue of the computation
complexity of the servers.
In this paper, we show that a specific encoding of the database provides PIR protocols with reasonable communication complexity, low storage overhead and optimal computational complexity for the servers. This encoding
is based on incidence matrices of transversal designs, from which a natural and efficient recovering algorithm is
derived. We also present instances of our construction, making use of finite geometries and orthogonal arrays, and
we finally give a generalisation of our main construction for resisting collusions of servers.
Index Terms
Private information retrieval, linear code, transversal design, orthogonal array, finite geometry

I. I NTRODUCTION
A. Private Information Retrieval
A private information retrieval (PIR) protocol aims at ensuring a user that he can retrieve some part Di of a remote
database D without revealing the index i to the server(s) which hold the database. For example, such protocols
can be applied in medical data storage where physicians would be able to access parts of the genome while hiding
the specific gene they analyse. The PIR paradigm was originally introduced by Chor, Goldreich, Kushilevitz and
Sudan [6, 7].
A naive solution to the problem would consist in downloading the entire database each time the user wants a single
symbol. But the communication complexity would then be overwhelming, so we look for PIR protocols exchanging
less bits. However, Chor et. al. proved that, when the k -bits database is stored on a single server, a PIR protocol
cannot be information-theoretically secure with less than Θ(k) bits of communication [7]. Two alternatives were
then considered: restricting the protocol to computational security (initiated by Chor and Gilboa [5]), or allowing
several servers to store the database. Our work focuses on the last one.
In many such PIR protocols the database is replicated on the servers. Informally, the idea is that each server is asked
to compute some partial information related to a random-like query sent by the user, the index of the desired item
being hidden in each query. Then the user collects all the servers’ answers and retrieves the desired symbol with
an appropriate algorithm. For instance, Chor et. al. [7] use XOR properties on log(k)-dimensional binary vectors
to mask the index of the desired item and to retrieve the associated symbol. Their protocol achieves decreasing
communication as a function of the number of servers: with ` servers, the communication is O(` log ` k 1/ log ` ) bits.
A few years later, Katz and Trevisan [13] showed that any smooth locally decodable code (LDC) gives rise to a
Submitted to editors on July 28, 2017. A shorter version of this paper was presented at the Tenth International Workshop on Coding and
Cryptography 2017, September 18-22, 2017, Saint-Petersburg, Russia.

2

PIR protocol whose number of servers and communication complexity is basically the same than the LDC locality
([20] is a good survey on LDCs and their applications in PIR protocols). Building on this idea,√many PIR schemes
(notably [3, 19, 10, 9]) successively decreased the communication complexity, achieving O(k log log k/ log k ) with
only two servers. However, only few of them tried to lighten the computational and storage cost on the server side.

By preprocessing the database, Beimel, Ishai and Malkin [4] were the first to address the minimization of the server
storage/computation. Then, initiated by Fazeli, Vardy and Yaakobi [11], recent works used the concept of PIR codes
to address the storage issue. The idea is to turn an `-server replication-based PIR protocol into a more-than-`-server
distributed PIR protocol with a smaller overall storage overhead. For this purpose, the user encodes the database and
distributes pieces of the associated codeword among the servers, such that they hold distinct parts of the database
(plus some redundancy). Through this transformation, both communication complexity and computational cost keep
the same order of magnitude, but the storage overhead corresponds to the PIR code’s one, which can be brought
arbitrarily close to 1 when sufficiently many servers are used. Several recent works also address the PIR issue on
previously coded databases [18], and/or aim at reaching the so-called capacity of the model [17]. However, while
the storage drawback seems to be solved, potentially huge computational cost can still represent a barrier to the
practicality of such PIR protocols.
B. Motivations and results
Indeed, as pointed out by Yekhanin [20], “the overwhelming computational complexity of PIR schemes (...) currently
presents the main bottleneck to their practical deployment”. Consider a public database which is frequently queried,
e.g. a database storing stock exchange prices where private queries could be very relevant. Fast retrieval is necessary
is this context, hence one cannot afford each run of the PIR protocol to be computationally inefficient, for instance
Ω(k), where k is the size of the database. Therefore, we aim at building PIR protocols with sublinear computational
complexity in the length of the database stored by each server.
Naively, the computational complexity of a PIR protocol could be drastically reduced by letting all the possible
answers to its queries to be precomputed. Of course, storing all these answers dramatically increases the needed
storage, and we prefer to focus on another construction due to Augot, Levy-dit-Vehel and Shikfa [2], anterior to
the PIR codes breakthrough [11], and that we shortly explain now.
Their construction uses a specific family of high-rate locally decodable codes called multiplicity codes introduced
by Kopparty, Saraf and Yekhanin [14]. But instead of replicating the database on the several servers, the authors
split an encoded version c of the database D into parts c(1) , . . . , c(`) , and share these parts on the servers. The main
difference with PIR codes [11] is that Augot et. al.’s construction does not purpose to emulate a lighter PIR protocol
with an existing one, but uses specific properties of the encoding as a way to split the database on several servers.
In short, the multiplicity codes they use feature both the privacy of the PIR protocol and the storage reduction for
the servers. We refer to Section VII for more details on the construction.
In this work, we consider this “codeword support splitting” idea in the context of incidence properties in block
designs. We thus build a large family of codes leading to PIR schemes with low storage and low computational
complexity on the server side.
C. Organisation
We start by giving two formal definitions of PIR protocols in Section II, depending on whether the database is
replicated or distributed on the servers. We also present the standard construction of replication-based PIR protocols
from smooth locally decodable codes. Section III is devoted to recall definitions of combinatorial structures and
their associated codes that are used to build our 1-private PIR protocols in Section IV. Section V lists instances
of our construction with efficient parameters. Finally, a generalisation of our construction is given in Section VI
in order to keep up with collusions of servers, and a comparison with the PIR protocols coming from multiplicity
codes is presented in Section VII.

3

II. D EFINITIONS AND RELATED CONSTRUCTIONS
We first recall that we are only concerned with information-theoretically secure PIR protocols. In this paper, we
denote by U the user (or client) of the PIR protocol. User U owns a database denoted by D = (Di )1≤i≤k ∈ Fkq ,
where Fq represents the finite field with q elements. Database D hence contains |D| = k log q bits. We also denote
by S1 , . . . , S` the ` servers involved in the PIR protocol.
Given A, B two sets, with |B| = n < ∞, we denote by AB the set of n-tuples a = (ab )b∈B of A-elements indexed
by B , which can also be seen as functions from B to A. For T ⊂ B , we also write a|T := (at )t∈T the restriction
of the tuple a to the coordinates of T .
A. Two definitions for PIR protocols
A vast majority of existing PIR schemes start by simply cloning the database D on all the servers S1 , . . . , S` . Then,
the role of each server Sj is to compute some combination of symbols from D, related to the query sent by U .
This computation has a non-trivial cost, so in a certain sense, the computational complexity of the privacy of the
PIR scheme is mainly devoted to the servers.
More formally, one can define replication-based PIR protocols as follows:
Definition II.1 (standard, or replication-based PIR protocol). Assume that every server Sj , 1 ≤ j ≤ `, stores a
copy of the database D. An `-server replication-based PIR protocol is a set of three algorithms (Q, A, R) running
the following steps on input i ∈ [1, k]:
1) Query generation: the randomized algorithm Q generates ` queries Q(i) := (q1 , . . . , q` ). Query qj is sent to
server Sj .
2) Servers’ answer: each server Sj computes an answer aj = A(qj , D) and sends it back to the user1 .
3) Reconstruction: denote by a = (a1 , . . . , a` ) and q = (q1 , . . . , q` ). User U computes and outputs r = R(i, a, q).
The PIR protocol is said:
– correct if r = Di when the servers follow the protocol;
– t-private if, for every (i, i0 ) ∈ [1, k]2 and every T ⊆ [1, `] such that |T | ≤ t, the distributions Q(i)|T and
Q(i0 )|T are the same. We also say that the PIR protocol resists t collusions of servers.
We call communication complexity the number of bits sent between the user and the servers, and server (resp. user)
computational complexity the maximal number of Fq -operations made by a server in order to compute an answer
aj (resp. made by R to reconstruct the desired item).
According to this definition, one sees that the servers must jointly carry the ` copies of the database, so the storage
overhead of the scheme is (` − 1)|D| bits. Moreover, since D is a raw database without specific structure, the
algorithm A has no reason to be trivial and can incur superlinear computations for the servers — which is verified
for most of current replication-based PIR protocols.
A way to reduce the computation cost of PIR protocols is to preprocess the database. Therefore we need to model
PIR protocols for which the database can be encoded and distributed over the servers. From now on, let c = (ci )i∈I
denote an encoding of the database D, i.e. the image of D by an injective map Fkq → FIq , with |I| = n ≥ k . Besides,
(i )
(j)
for convenience we assume that I = [1, s] × [1, `] and for readability we write c(i1 ,i2 ) = ci12 and c(j) = (cr )r∈[1,s] .
Definition II.2 (distributed PIR protocol). Assume that for 1 ≤ j ≤ `, server Sj holds the part c(j) of the encoded
database. An `–server distributed PIR protocol is a set of three algorithms (Q, A, R) running the following steps
on input i ∈ I :
1) Query generation: the randomized algorithm Q generates ` queries Q(i) := (q1 , . . . , q` ). Query qj is sent to
server Sj .
2) Servers’ answer: each server Sj computes an answer aj = A(qj , c(j) ) and sends it back to the user.
3) Reconstruction: denote by a = (a1 , . . . , a` ) and q = (q1 , . . . , q` ). User U computes and outputs r = R(i, a, q).
1

algorithm A := Aj may depend on j

4

Correctness and privacy properties are identical to those of replication-based PIR protocols. Similarly, one can
also define communication and computational complexities, and since the database D has been encoded, we finally
define the storage overhead as the number of redundancy bits stored by the servers, that is, (s` − k) log q .
In this paper, we focus on distributed PIR protocols with low computational complexity on the server side. More
precisely, we build PIR protocols where the answering algorithm A consists only in reading some symbols of the
database. Thus, our PIR protocols are computationally optimal on the server side, in a sense that, compared to the
non-private retrieval, they incur no extra computational burden for the each server taken individually.
B. PIR protocols from locally decodable codes
As pointed out in the introduction, Augot et. al. [2] used a family of locally decodable codes (LDC) to design a
distributed PIR scheme. LDCs are known to give rise to PIR protocols for a long time, but we emphasize that the
main idea from [2] is to benefit from the fact that the encoded database can be smartly partitioned with respect to
the queries of the local decoder.
Based on the seminal work of Katz and Trevisan [13], we briefly remind how to design a PIR protocol based on
a perfectly smooth locally decodable code. First, let us define (linear) locally decodable codes.
Definition II.3 (locally decodable code). Let Σ be a finite set, 2 ≤ ` ≤ k ≤ n be integers, and δ,  ∈ [0, 1]. A code
C : Σk → Fnq is (`, δ, )–locally decodable if and only if there exists a randomized algorithm D such that, for every
input i ∈ [1, k] we have:
– for all m ∈ Σk and all y ∈ Fnq , if |{j ∈ [1, n], yj 6= C(m)j }| ≤ δn, then
P(D(y) (i) = mi ) ≥ 1 −  ,
where the probability is taken over the internal randomness of D;
– D reads at most ` symbols yq1 , . . . , yq` of y .
Notation D(y) refers to the fact that D has oracle access to single symbols yqj of the word y . The parameter `
is called the locality of the code. Moreover, the code C is said perfectly smooth if on an arbitrary input i, each
individual query of the decoder D is uniformly distributed over the coordinates of the word y .
Now let us say a user wants to use a PIR protocol on a database D ∈ Σk , and assume there exists a perfectly
smooth locally decodable code C ⊂ Fnq of dimension k and locality `. Figure 1 presents a distributed PIR protocol
based on C .
1) Initialisation step. User U encodes D into a codeword c0 ∈ C . Each server S1 , . . . , , S` holds a copy
of c0 . In the formalism of Definition II.2, it means that c(j) := c0 , for j = 1, . . . , `.
2) Retrieving step for symbol Di . Denote by D a local decoding algorithm for C .
1) Queries generation: user U calls D to generate at random a query (q1 , . . . , q` ) for decoding the
symbol Di . Query qj is sent to server Sj .
2) Servers’ answer: each server Sj reads the encoded symbol aj := c0qj . Then Sj sends aj to U .
3) Reconstruction: user U collects the ` codeword symbols (c0qj )j∈[1,`] and feeds the local decoding
algorithm D in order to retrieve Di .
Fig. 1: A distributed PIR protocol based on a locally decodable code C .
The main drawback of these LDC-based PIR protocols is their storage overhead, since the ` servers must store
`n/k = `/R times more data than the raw database (R := k/n represents the information rate, or rate, of the code).
This issue becomes especially crucial as building LDCs with small locality and high rate is highly non-trivial.
The idea of Augot, Levy-dit-Vehel and Shikfa [2] for reducing the storage overhead is to benefit from a natural
partition of the support of multiplicity codes [14]. Assume that each codeword c ∈ C can be split into ` disjoint

5

parts c(1) , . . . , c(`) , such that each coordinate qj of any possible query (q1 , . . . , q` ) of the PIR protocol corresponds
to reading some symbols on c(j) . By sending the part c(j) to server Sj , the PIR protocol of Figure 1 can be
improved in order to save storage. We devote Section VII to more explanation on this construction, as well as to
a comparison with our schemes.
Finally, one can notice that the communication complexity of LDC-based PIR protocols depends on the locality of
the code, while its smoothness serves their privacy. We also point out two important remarks.
1) Assuming a noiseless transmission and honest-but-curious servers (i.e. they want to discover the index of
the desired symbol but never give wrong answers), one does not need a powerful local decoding algorithm.
Indeed, it should be possible to reconstruct the desired symbol Di by local decoding only one erasure on the
codeword. For instance, computing a single low-weight parity-check sum should be enough.
2) Smoothness is sufficient for 1-privacy, but we need more structure for preventing collusions of servers.
Coupled with the fact that we want to split the database over several servers, these remarks lead us to design other
kinds of encoding, which answer as close as possible the needs of private information retrieval protocols. Our
construction relies on combinatorial structures, namely transversal designs, that we recall in the upcoming section.
III. T RANSVERSAL DESIGNS AND CODES
Let us give here the definition of transversal designs and how to build linear codes upon them. We refer to [1], [16]
and [8] for complementary details.
Definition III.1 (block design). A block design is a pair D = (X, B) where X is a finite set of so-called points,
and B is a set of non-empty subsets of X called the blocks.
Definition III.2 (incidence matrix). Let D = (X, B) be a block design. An incidence matrix MD of D is a matrix
of size |B| × |X|, whose (i, j)−entry, for i ∈ B and j ∈ X , is:

1 if the block i contains the point j
0 otherwise
The q -rank of MD is the rank of MD over the field Fq . We also define the incidence vector 1B ∈ {0, 1}B of a
block B ∈ B as the row vector indexed by B in MD .
Of course, any design admits many incidence matrices, depending on the way points and blocks are ordered.
However, all these incidence matrices are equal up to some permutation of their rows and columns, and, in particular,
they all have the same q -rank. Hence, we call q -rank of a design the q -rank of any of its incidence matrices. Moreover,
from now on we consider incidence matrices of designs up to an ordering of points and blocks, and we abusively
refer to the incidence matrix MD of a design D.
Example III.3. Let A2 (F3 ) be the affine plane over the finite field F3 , and X be the set consisting of its 9 points:
X = {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)} .

We define the block set B as the set of the 12 affine lines of A2 (F3 ):
B = { {(0, 0), (0, 1), (0, 2)},
{(0, 0), (1, 1), (2, 2)},
{(0, 0), (2, 1), (1, 2)},
{(0, 0), (1, 0), (2, 0)},

{(1, 0), (1, 1), (1, 2)},
{(1, 0), (2, 1), (0, 2)},
{(1, 0), (0, 1), (2, 2)},
{(0, 1), (1, 1), (2, 1)},

{(2, 0), (2, 1), (2, 2)}
{(2, 0), (0, 1), (1, 2)}
{(2, 0), (1, 2), (0, 2)}
{(0, 2), (1, 2), (2, 2)} } .

6

The pair D = (X, B) is then a block design, and its associated (12 × 9)–incidence matrix is


1 1 1 0 0 0 0 0 0
 1 0 0 1 0 0 1 0 0 


 1 0 0 0 1 0 0 0 1 


 1 0 0 0 0 1 0 1 0 


 0 1 0 1 0 0 0 0 1 


 0 1 0 0 1 0 0 1 0 

.
MD = 

0
1
0
0
0
1
1
0
0


 0 0 1 1 0 0 0 1 0 


 0 0 1 0 1 0 1 0 0 


 0 0 1 0 0 1 0 0 1 


 0 0 0 1 1 1 0 0 0 
0 0 0 0 0 0 1 1 1
A computation shows that over the field F2 , matrix MD is full-rank, while over F3 , it has only rank 6.
Definition III.4 (transversal design). Let s, ` ≥ 2 and λ ≥ 1 be integers. A transversal design, denoted TDλ (`, s),
is a block design (X, B) equipped with a partition G = {G1 , . . . , G` } of X called the set of groups, such that:
– |X| = `s;
– any group in G has size s and any block in B has size `;
– any unordered pair of elements from X is contained either in exactly one group or in exactly λ blocks.
When λ = 1, we use the simpler notation TD(`, s).
Remark III.5. A block cannot be secant to a group in more than one point, otherwise the third condition of the
definition would be disproved. Moreover, since the block size equals the number of groups, any block must meet
any group. Hence the following holds:
∀(B, G) ∈ B × G, |B ∩ G| = 1 .

The definition also implies there must lie exactly λs2 blocks in B .
Example III.6. Let D = (X, B) be the block design defined in Example III.3. Define G to be any set of 3 parallel
lines from B which partitions the point set X . For instance, one can consider
G = { {(0, 0), (0, 1), (0, 2)}, {(1, 0), (1, 1), (1, 2)}, {(2, 0), (2, 1), (2, 2)} } .

Then, T = (X, B \ G, G) is a transversal design TD(3, 3). Indeed, T is composed of `s = 9 points, ` = 3 groups
of size s = 3 and s2 = 9 blocks of size ` = 3 each. Moreover, in the affine plane every unordered pair of points
belongs simultaneously to a unique line, which is represented in T either by a group or by a block. More generally,
for any prime power q , a transversal design TD(q, q) can be built with the affine plane A2 (Fq ). A generalisation
of this construction will be given in Subsection V-A.
A simple way to build linear codes from block designs is to associate a parity-check equation of the code to each
incidence vector of a block of the design. We recall P
that the dual code C ⊥ of a code C ⊆ Fnq is the linear vector
space consisting of vectors h ∈ Fnq such that ∀c ∈ C, ni=1 ci hi = 0.
Definition III.7 (code of a design). Let Fq be a finite field, D = (X, B) be a block design and MD be its incidence
matrix. The code Codeq (D) is the Fq -linear code of length |X| whose dual code is spanned by the rows of MD .
Remark III.8. The code Codeq (D) is uniquely defined up to a chosen order of the points X . For different orders,
the arising codes remain permutation-equivalent. Also notice that the way blocks are ordered does not affect the
code.
For any design D, the dimension over Fq of Codeq (D) equals |X| − rankq (MD ). Since MD has coefficients in
{0, 1}, one must notice that rankq (MD ) = rankp (MD ), where p is the characteristic of the field Fq .

7

Remark III.9. Standard literature (e.g. [1]) sometimes defines Codeq (D) (and not Codeq (D)⊥ ) to be the vector
space generated by the incidence matrix of the design. We favor this convention because Codeq (D) will serve to
encode the database in our PIR scheme.
Example III.10. The design D from Example III.3 gives rise to C
9 and dimension 3. A full-rank generator matrix of C is given by:

1 1 1 1 1 1 1
G= 0 0 0 1 1 1 2
0 1 2 0 1 2 0

= Code3 (D), a linear code over F3 , of length


1 1
2 2 .
1 2

One may notice that this code is the generalized Reed-Muller code of degree 1 and order 2 over F3 , that is, the
evaluation code of bivariate polynomials of total degree at most 1 over the whole affine plane F23 .
Definition III.11 (systematic encoding). Let C ⊆ Fnq be a linear code of dimension k ≤ n. A systematic encoding
for C is a one-to-one map φ : Fkq → C , such that there exists an injective map σ : [1, k] → [1, n] satisfying:
∀m ∈ Fkq , ∀i ∈ [1, k], mi = φ(m)σ(i) .

The set σ([1, k]) ⊆ [1, n] is called an information set of C .
In other words, a systematic encoding allows to view the message m as a subword of its associated codeword
φ(m) ∈ C . For instance, it is useful for efficiently retrieving m from c when the codeword c has not been corrupted.
A systematic encoding exists for any code C , is not necessarily unique, and can be computed through a Gaussian
elimination over any generator matrix of the code. Also notice that this computation can be tedious for large codes.
IV. 1- PRIVATE PIR PROTOCOLS BASED ON TRANSVERSAL DESIGNS
In this section we present our construction of PIR protocols relying on transversal designs. The idea is that the
knowledge of one point of a block of a transversal design gives (almost) no information on the other points lying
on this block. The code associated to such a design then transfers this property to the coordinates of codewords.
Hence, we obtain a PIR protocol which can be proven 1-private, that is, which ensures perfect privacy for noncommunicating servers. Though this protocol cannot resist collusions, we will see in Section VI that a natural
generalisation leads to t-private PIR protocols with t > 1.
Notice that both Fazeli et. al.’s work [11] and ours make use of codes in order to save storage in PIR protocols.
Nevertheless, we emphasize that the constructions are very different, since Fazeli et. al. emulate a PIR protocol
from an existing one while we build our PIR protocols from scratch.
A. The transversal-design-based distributed PIR protocol
Let T be a transversal design TD(`, s) and n = |X| = `s. Denote by C = Codeq (T ) ⊆ Fnq the associated Fq -linear
code, and let k = dimFq C . Our PIR protocol is defined in Figure 2. We then summarize the steps of the construction
in Figure 3.
B. Analysis
We analyse our PIR scheme by proving the following:
Theorem IV.1. Let D be a database with k entries over Fq , and T = TD(`, s) be a transversal design, whose
incidence matrix has rank `s − k over Fq . Then, there exists a distributed `-server 1-private PIR protocol with:
–
–
–
–

only one Fq -symbol to read for each server,
` − 1 field operations over Fq for the user,
` log(sq) bits of communication (` log s are uploaded, ` log q are downloaded),
a (total) storage overhead of (`s − k) log q bits on the servers.

8

Parameters: T = (X, B, G) is a TDλ (`, s); C = Codeq (T ) has length n = `s and dimension k .
1) Initialisation step.
1) Encoding. User U computes a systematic encoding of the database D ∈ Fkq , resulting in the
codeword c ∈ C .
2) Distribution. Denote by c(j) = c|Gj the symbols of c whose support is the group Gj ∈ G . Each
server Sj receives c(j) , for 1 ≤ j ≤ `.
2) Retrieving step for symbol ci for i ∈ X . Denote by j ∗ ∈ [1, `] the index of the unique group Gj ∗
(j ∗ )
which contains i — that is, ci = cr for some r ∈ [1, s]. Also denote by B ∗ the subset of blocks
containing i. The three steps of the distributed PIR protocol are:
1) Queries generation. U picks uniformly at random a block B ∈ B ∗ . For j 6= j ∗ , user sends the
unique index qj ∈ B ∩ Gj to server Sj . Server Sj ∗ receives a random query qj ∗ uniformly picked
$

in Gj ∗ . To sum up (←
− stands for “picked uniformly at random in”) :

$

− Gj ∗ for j ∗ such that i ∈ Gj ∗
 Q(i)j ∗ ←
$




B ←
− B∗
Q(i)j ← B ∩ Gj ,

j 6= j ∗

2) Servers’ answer. Each server Sj (including Sj ∗ ) reads aj := cqj and sends it back to the user. That
is,
A(qj , c(j) ) = cqj .
3) Reconstruction. Denote by a = {a1 , . . . , a` } and q = {q1 , . . . , q` }. User U computes
X
X
r = R(i, a, q) := −
aj = −
cqj
j6=j ∗

j6=j ∗

and outputs r.
Fig. 2: A 1-private distributed PIR protocol based on the Fq -linear code defined by a transversal design.

Transversal design

incidence
matrix

TD-based
/ linear code

database
encoding

/ Distributed PIR scheme

Fig. 3: Summary of steps the construction of a transversal-design-based PIR scheme.
Proof. Recall the PIR protocol we are dealing with is defined in Figure 2.
Correctness. By definition of the code C = Codeq (T ), the incidence vector 1B of anyPblock B ∈ B belongs to the
dual code C ⊥ . Hence, for c ∈ C , the inner product 1B · c vanishes, or said differently, x∈B cx = 0. We recall that
j ∗ represents the index of the group which contains i. Since P
the servers Sj , j 6=Pj ∗ , receive queries corresponding
to the points of a block B which contains i, we have ci = − x∈B\{i} cx = − j6=j ∗ cqj , and our PIR protocol is
correct as long as there is no error on the symbols aj := cqj returned by the servers.
Security (1-privacy). We need to prove that for all j ∈ [1, `], it holds that P(i | qj ) = P(i), where probabilities are
taken over the randomness of B ← B ∗ . The law of total probability implies
P(i | qj ) = P(i | qj and i ∈ Gj )P(i ∈ Gj ) + P(i | qj and i ∈
/ Gj )P(i ∈
/ Gj )
= P(i | i ∈ Gj )P(i ∈ Gj ) + P(i | i ∈
/ Gj )P(i ∈
/ Gj ) = P(i) ,

and the reasons why we eliminated the random variable qj in the conditional probabilities are:
– in the case i ∈ Gj (that is, j = j ∗ ), by definition of our PIR protocol we know that qj is uniformly random,
so qj and i are independent;

9

– in the case i ∈
/ Gj , by definition of a transversal design, there are as many blocks containing both qj and i as
there are blocks containing qj and any i0 in X \ Gj (the number of such blocks is always λ). So once again,
the value of the random variable qj is not related to i.
Communication complexity. Exactly one index in [1, s] and one symbol in Fq are exchanged between each server
and the user. So the overall communication complexity is ` × (log(s) + log(q)) = ` log(sq) bits.
Storage overhead. The number of bits stored on a server is s log q , giving a total storage overhead of (`s − k) log q ,
where k = dim C .
Computation complexity. Each server Sj only needs to read the symbol defined by query qj , hence our protocol
incurs no extra computational cost.
Theorem IV.1 shows that, if we want to optimize the practical parameters of our PIR scheme, we basically need
to look for small values of `, the number of groups. However, one observes that the dimension k of Codeq (T )
strongly depends on ` and n, and tiny values of ` can lead to trivial or very small codes. This issue should be
carefully taken into account, since instances with k < ` represent PIR protocols which are more communication
expensive to use than the trivial one which simply retrieves the whole database. Hence, it is very natural to raise
the main issue of our construction:
Problem IV.2. Find codes C = Codeq (T ) arising from transversal designs T = TD(`, s) with few groups (small
`) and large dimension k = dimFq C compared to their length n = `s.
The following section is devoted to the construction of such transversal designs.
V. E XPLICIT CONSTRUCTIONS OF 1- PRIVATE TD- BASED PIR PROTOCOLS
From now on, we denote by `(k) the number of servers involved in a given PIR protocol running on a database
with k entries, and by n(k) the actual number of symbols stored by all the servers. As it is proved in Theorem IV.1,
these two parameters are crucial for the practicality of our PIR schemes, and they respectively correspond to the
block size and the number of points of the transversal design used in the construction. In practice, we look for
small values of ` and n as explained in Problem IV.2.
In this section, we first give two classical instances of transversal designs derived from finite geometries (Subsections V-A and V-B), leading to good PIR parameters. We then show how orthogonal arrays produce transversal
designs, and we more deeply study a family of such arrays leading to high-rate codes. Subsection V-D is finally
devoted to another family of orthogonal arrays whose divisibility properties ensure to give an upper bound on the
storage overhead of related PIR protocols.
A. Transversal designs from affine geometries
Transversal designs can be built with incidence properties between subspaces of an affine space.
Construction V.1 (Affine transversal design). Let Am (Fq ) be the affine space of dimension m over Fq , and
H = {H1 , . . . , Hq } be q hyperplanes that partition Am (Fq ). We define a transversal design TA (m, q) as follows:
– the point set X consists in all the points in Am (Fq );
– the groups in G are the q hyperplanes from H ;
– the blocks in B are all the 1-dimensional affine subspaces (lines) which do not entirely lie in one of the Hj ,
j ∈ [1, q]. We also say that such lines are secant to the hyperplanes in H .
The design thus defined is a TD(q, q m−1 ), since an affine line is either contained in one of the Hj , or is 1-secant
(i.e. has intersection of size 1) to each of them. To complete the study of the parameters of the induced PIR protocol,
it remains to compute the dimension of Code(TA (m, q)).
First notice that all blocks of TA (m, q) belong to the block set of the affine geometry design AG1 (m, q) — which
is defined as the incidence structure of all points and affine lines in Am (Fq ). Thus, the incidence matrix MTA (m,q)

10

is a sub-matrix of MAG1 (m,q) , which implies that Codep (AG1 (m, q)) ⊆ Codep (TA (m, q)) for any field Fp . The
benefit to consider AG1 (m, q) is that the p-rank of its incidence matrix has been well-studied. Besides, when p
and q are coprime, it has been proved that its code over Fp has dimension 0 or 1 (Theorem 2.4.1 in [1]). Since
our goal is to obtain the largest codes as possible, we now assume that p is the characteristic of the field Fq .
In this setting (q = pe ), Hamada [12] gives a generic formula to compute the p-rank of a design coming from
projective geometry. Yet, as presented in Appendix A, asymptotics are hard to derive from his formula for a generic
value of m.

e ) = p+1 e , which implies that dim Code (T (2, pe )) ≥
However, when
m
=
2
,
we
know
that
rank
AG
(2,
p
p
1
p A
2
e
p2e − p+1
.
Hence
we
obtain
the
following
family
of
PIR
protocols.
2
e
Proposition V.2. Let D be a database with k = p2e − p+1
entries, p a prime, e ≥ 1. There exists a distributed
2
1-private PIR protocol for D with:
`(k) = pe and n(k) = p2e .
For fixed p and k → ∞, we have
√
1
`(k) = k + Θ(k 2 +cp )

and

1

n(k)/k =
1−

where cp =

1
2



1+1/p
2

e = 1 + Θ(k cp ) → 1 ,

(1)

logp ( 1+1/p
2 ) < 0.

Proof. The existence of the PIR protocol is a consequence of the previous discussion. Let us state the asymptotics
of the parameters. Recall we fix the prime p and we let e → ∞. First we have:


 !

1
1 + 1/p 2e
p2e
1 + 1/p e

e = 1 +
.
(2)
+O
n(k)/k =
e =
2
2
p2e − p+1
1 − 1+1/p
2
2
Notice that


logp k = 2e + logp 1 −



1 + 1/p
2

e 


= 2e + O

1 + 1/p
2

e 
.

Hence,


1+1/p e



1
O(( 1+1/p )e )
2
1+1/p
1
1 + 1/p e
1
+
1/p
1 + 1/p 2 logp k+O(( 2 ) )
= k 2 logp ( 2 ) ×
= Θ (k cp ) ,
=
2
2
2

O(( 1+1/p )e )
2
since 1+1/p
→ 1, and with (2) we obtain the asymptotics we claimed on n(k)/k .
2

For `(k), we see that n(k) = `(k)2 . Therefore, we get
√ p
√ p
√
1
`(k) = k n(k)/k = k 1 + Θ(k cp ) = k + Θ(k 2 +cp ) .

We give in Table I lower bounds on the dimension of some practical codes arising from affine transversal designs,
when m is not restricted to 2. Computations show that the lower bound is tight for small values of p, e and m
(only a few of them are presented in Table I), and we conjecture it to be tight for all of them.
Finally, for a better understanding of the parameters we can point out two PIR instances:
– choosing m = 2 and ` = 4096, there exists a PIR protocol on a ' 2.0 MB file with 6 kB of communication
and only 3.2% storage overhead;
– for a ' 46 GB database (m = 3, ` = 8192), we obtain a PIR protocol with 39 kB of communication and 27%
storage overhead.

11

m
2
2
2
2
2
2
2
2
3
3
3
3
3
3
4
4
4
5
5

`=q
8
16
32
64
1024
4096
16 384
65 536
8
16
64
256
1024
8192
8
64
256
8
64

n = s` = q m
64
256
1024
4096
1 048 576
16 777 216
268 435 456
4 294 967 296
512
4096
262 144
16 777 216
1 073 741 824
549 755 813 888
4096
16 777 216
4 294 967 296
32 768
1 073 741 824

lower bound on
k = dim C
37∗
175∗
781∗
3367∗
989 527
16 245 775
263 652 487
4 251 920 575
139∗
1377∗
118 873
9 263 777
680 200 873
400 637 408 211
406
2 717 766
890 445 921
994
44 281 594

lower bound on
R = k/n
0.578∗
0.684∗
0.763∗
0.822∗
0.944
0.968
0.982
0.990
0.271∗
0.336∗
0.453
0.552
0.633
0.729
0.099
0.162
0.207
0.030
0.041

TABLE I: Lower bounds on the dimension and rate of binary codes arising from TA (m, q). A star denotes
the bound is reached (shown by computation). Remind that the rate R of the code is related to the server
storage overhead of the PIR protocol, and that q = ` is essentially the communication complexity and the
number of servers.

B. Transversal designs from projective geometries
Projective geometries are closely related to affine geometries, but contrary to them, there is no partition of the
projective space into hyperplanes, since every pair of distinct projective hyperplanes intersects in a projective space
of co-dimension 2. To tackle this problem, an idea is to consider the hyperplanes Hi which intersect on a fixed
subspace of co-dimension 2 (call it Π∞ ). Then, all the sets Hi \ Π∞ are disjoint, and their union gives exactly
Pm (Fq ) \ Π∞ , where Pm (Fq ) denotes the projective space of dimension m over Fq . Besides, any projective line
disjoint from Π∞ is either contained in one of the Hi , or is 1-secant to all of them. It results to the following
construction:
Construction V.3 (Projective transversal design). Let Pm (Fq ) and Π∞ defined as above. Let us define
– a point set X = Pm (Fq ) \ Π∞ ;
– a group set G = {projective hyperplanes H ⊂ Pm (Fq ), Π∞ ⊂ H};
– a block set B = {projective lines L ⊂ Pm (Fq ), L ∩ Π∞ = ∅ and ∀H ∈ G, L 6⊂ H} .
Finally, denote by TP (m, q) := (X, B, G).
The design TP (m, q) is a TD(q + 1, (q + 1)q m−1 ) and, as in the affine setting, its p-rank is related to that of
PG1 (m, q), the classical design of point-line incidences in the projective space Pm (Fq ). Indeed, the incidence
matrix M of TP (m, q) is a submatrix of MPG1 (m,q) from which we removed:
– the columns corresponding to the points in Π∞ ,
– the rows corresponding to the lines not in B .
Said differently, the code associated to TP (m, q) contains (as a subcode) the Π∞ -shortening of the code associated
to PG1 (m, q). Hence dim Code(TP (m, q)) ≥ dim Code(PG1 (m, q)) − |Π∞ |. Once again, Hamada’s formula gets
simpler for m = 2, and leads to the following proposition.
e
Proposition V.4. Let D be a database with k = p2e + pe − p+1
− 1 entries, p a prime and e ≥ 1. There exists
2
a distributed 1-private PIR protocol for D with:
`(k) = pe + 1

and

n(k) = p2e + pe .

12

Asymptotics are the same as in Equation (1).
In order to emphasize that the two previous constructions are asymptotically the same, we draw the rates of the
codes involved in these two kinds of PIR schemes in Figure 4.
R = k/n (rate)
1
0.9
√
` = Θ( k)

0.8
0.7
0.6

` = Θ(k 1/3 )

0.5
0.4
0.3

` = Θ(k 1/4 )

0.2
0.1
0

` = Θ(k 1/5 )
210

220

230

240

n (code length)

Fig. 4: Rate of binary codes from Construction V.1 (red line) and Construction V.3 (blue line).

C. Orthogonal arrays and the incidence code construction
In this subsection, we first recall a way to produce plenty of transversal designs from other combinatorial constructions called orthogonal arrays.
Definition V.5 (orthogonal array). Let λ, s ≥ 1 and ` ≥ t ≥ 1, and let A be an array with ` columns and λst
rows, whose entries are elements of a set S of size s. We say that A is an orthogonal array OAλ (t, `, s) if, in any
subarray A0 of A formed by t columns and all its rows, every row vector from S t appears exactly λ times in the
rows of A0 . We call λ the index of the orthogonal array, t its strength and ` its degree. If t (resp. λ) is omitted, it
is understood to be 2 (resp. 1). When both these parameters are omitted we write A = OA(`, s).
From now on, for convenience we restrict Definition V.5 to orthogonal arrays with no repeated column and no
repeated row. Next paragraph introduces a link between orthogonal arrays and transversal designs.
1) Construction of transversal designs from orthogonal arrays: We can build a transversal design TD(`, s) from
an orthogonal array OA(`, s) with the following construction, given as a remark in [8, ch.II.2].
Construction V.6 (Transversal designs from orthogonal arrays). Let A be an OA(`, s) of strength t = 2 and index
λ = 1 with symbol set S , |S| = s, and denote by Rows(A) the s2 rows of A. We define the point set X = S ×[1, `].
To each row c ∈ Rows(A) we associate a block
Bc := {(ci , i), i ∈ [1, `]} ,

so that the block set is defined as
B := {Bc , c ∈ Rows(A)} .

Finally, let G := {S × {i}, i ∈ [1, `]}. Then (X, B, G) is a transversal design TD(`, s).

13

Example V.7. A very simple example of this construction is given in Figure 5, where for clarity we use letters
for elements of the symbol set {a, b}, while the columns are indexed by integers. On the left-hand side, A is an
OA1 (2, 3, 2) with symbol set {a, b}. On the right-hand side, the associated transversal design TD(3, 2) is represented
as a hypergraph: the nodes are the points of the design, the “columns” of the graph form the groups, and a block
consists in all nodes linked with a path of a fixed colour. One can check that every pair of nodes either belongs to
the same group or is linked with one path.



a
 b
A=
 b
a

b
b
a
a


b
a 

b 
a

(a, 1)

(a, 2)

(a, 3)

(b, 1)

(b, 2)

(b, 3)

⇒

Fig. 5: A representation of the construction of a transversal design from an orthogonal array.
Remark V.8. Listed in rows, all the codewords of a (generic) code C0 give rise to an orthogonal array, whose
strength t is derived from the dual distance d0 of C0 by t = d0 − 1. Notice that for linear codes, the dual distance is
simply the minimum distance of the dual code, but it can also be defined for non-linear codes (see [15, Ch.5.§5.]).
More details about the link between orthogonal arrays and codes can also be found in [8]. For example, the
orthogonal array of Figure 5 comes from the binary parity-check code of length 3 (by replacing a by 0 and b by
1). One can check that its dual distance is 3 and its associated transversal design has strength 2.
Given a code C0 , we denote by AC0 the orthogonal array it defines (see Remark V.8) and by TC0 the transversal
design built from AC0 thanks to Construction V.6.
Example V.9. Let x = (x1 , . . . , x` ) be an `-tuple of pairwise distinct elements of Fq and denote by RS2 (x) the
Reed-Solomon code of length ` and dimension 2 over Fq with evaluation points x:
RS2 (x) := {(f (x1 ), . . . , f (x` )), f ∈ Fq [X], deg f < 2} .

Then, RS2 (x) has dual distance 3, so its codewords form an orthogonal array ARS2 (x) = OA(`, q) of strength 2. Now,
one can use Construction V.6 to obtain a transversal design TRS2 (x) = TD(`, q). The point set is X = Fq × [1, `],
and the blocks are “labeled Reed-Solomon codewords”, that is, sets of the form {(ci , i), i ∈ [1, `]} with c ∈ RS2 (x).
The ` groups correspond to the ` coordinates of the code: Gi = Fq × {i}, 1 ≤ i ≤ `.
We can finally sum up our construction by introducing the code Codeq (TC0 ) arising from C0 , that we call incidence
code. Our motivation is that studying the structure of C0 may lead to properties of Codeq (TC0 ) which is used in
PIR schemes.
Definition V.10 (incidence code). Let C0 be a (generic) code of length ` over an alphabet S of size s. The incidence
code of C0 over Fq , denoted ICq (C0 ), is the Fq -linear code of length n = s` built from the transversal design TC0 ,
that is:
ICq (C0 ) := Code(TC0 ) .
Notice that the field Fq does not need to be the alphabet S of the code C0 .
Incidence codes are introduced in order to design PIR protocols, as summarizes Figure 6. We can show that, if C0
has dual distance more than 3, then the induced PIR protocol is 1-private. A generalisation is formally proved in
Corollary VI.8.
Example V.11. Here we provide a full example of the construction of an incidence code. Let C0 be the full-length
Reed-Solomon code of dimension 2 over the field F4 = {0, 1, α, α2 = α + 1}. The orthogonal array associated to
C0 is composed by the following list of codewords:

14

equivalence (Rem. V.8)
/ Orthogonal array
Base code C0 o
Construction V.6 [8, ch.II.2]

t

Transversal design

incidence
matrix

/ Incidence code of C0

database
encoding

/ Distributed PIR scheme

Fig. 6: A distributed PIR scheme using the incidence code construction.




0, 0, 0, 0
 1, 1, 1, 1 


 α, α, α, α 
 2 2 2 2
α , α , α , α 


 0, 1, α, α2 


 0, α, α2 , 1 


 0, α2 , 1, α 


 1, 0, α2 , α 


A=
2 , α, 0 
1,
α


 1, α, 0, α2 


 α, α2 , 0, 1 


 α, 0, 1, α2 


 α, 1, α2 , 0 


α2 , α, 1, 0 


α2 , 1, 0, α 
α2 , 0, α, 1

Using Construction V.6, we get a transversal design TC0 = (X, B, G) with 16 points (4 groups made of 4 points)
and 16 blocks. Let us recall how we map a row of A to a word in {0, 1}16 . For instance, consider the fifth row:
a := A5 = (0, 1, α, α2 ) .

We turn a into a block Ba := {(0, 1), (1, 2), (α, 3), (α, 4)} ∈ B , and we build the incidence vector 1Ba of the block
Ba over the point set X = {(β, i), i ∈ [1, 4], β ∈ F4 }. Of course, in order to see 1Ba as a word in {0, 1}16 , we
need to order elements in X , for instance:


(0, 1), (1, 1), (α, 1), (α2 , 1), (0, 2), (1, 2), (α, 2), (α2 , 2), (0, 3), . . . , (α2 , 4) .
Using this ordering, we get:

1Ba = 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 ∈ {0, 1}16 .

15

By computing all the 1Ba for a ∈ Rows(A), we obtain the

1000 1000
 0100 0100

 0010 0010

 0001 0001

 1000 0100

 1000 0010

 1000 0001

 0100 1000
M =
 0100 0001

 0100 0010

 0010 0001

 0010 1000

 0010 0100

 0001 0010

 0001 0100
0001 1000

incidence matrix M of the transversal design TC0 :

1000 1000
0100 0100 

0010 0010 

0001 0001 

0010 0001 

0001 0100 

0100 0010 

0001 0010 
,
0010 1000 

1000 0001 

1000 0100 

0100 0001 

0001 1000 

0100 1000 

1000 0010 
0010 0100

Notice that this matrix can be quickly obtained by respectively replacing entries 0, 1, α and α2 in the array A
by the binary 4-tuples (1000), (0100), (0010) and (0001) in the matrix M (of course this map depends on the
ordering of X we have chosen, but another choice would lead to a column-permutation-equivalent matrix, hence
a permutation-equivalent code). Notice that in matrix M , coordinates lying in the same group of the transversal
design have been distinguished by dashed vertical lines.
Matrix M then defines, over any extension F2e of the prime field F2 , the dual code of the so-called incidence code
IC2e (C0 ). For all values of e, the incidence codes IC2e (C0 ) have the same generator matrix of 2-rank 7, being:


1001 0010 0001 1010
 0101 0000 0110 1100 


 0011 0000 0011 1111 


.
0000
1010
0011
0011
G=


 0000 0110 0010 1110 


 0000 0001 0101 1110 
0000 0000 1111 0101
2) A deeper analysis of incidence codes coming from linear MDS codes of dimension 2: Incidence codes lead to
an innumerably large family of PIR protocols — as many as there exists codes C0 — but most of them are not
practical for PIR protocols (essentially because the kernel of the incidence matrix is too small). To simplify their
study, one can first remark that intuitively, the more blocks a transversal design, the larger its incidence matrix, and
consequently, the lower the dimension of its associated code. But the number of blocks of TC0 is the cardinality of
C0 . Hence, informally the smaller the code C0 , the larger IC(C0 ).
We recall that a [n, k, d] linear code is said to be maximum distance separable (MDS) if it reaches the Singleton
bound n + 1 = k + d. Besides, the dual code of an MDS code is also MDS, hence its dual distance is k + 1. In
this paragraph we analyse the incidence codes constructed with MDS codes of dimension 2. Their interest lies in
being the smallest codes with dual distance 3, which is the minimal setting for defining 1-private PIR protocols.
Generalised Reed-Solomon codes are the best-known family of MDS codes.
Definition V.12 (generalised Reed-Solomon code). Let ` ≥ k ≥ 1. Let also x ∈ F`q be a tuple of pairwise distinct
`
so-called evaluation points, and y ∈ (F×
q ) be the column multipliers. We associate to x and y the generalised
Reed-Solomon (GRS) code:
GRSk (x, y) := {(y1 f (x1 ), . . . , y` f (x` )), f ∈ Fq [X], deg f < k} .

16

Generalised Reed-Solomon codes GRSk (x, y) are linear MDS codes of dimension k over Fq , and give ReedSolomon codes when y = (1, . . . , 1). Moreover, GRS codes are essentially the only MDS codes of dimension 2,
as shows the following lemma.
Lemma V.13. All [`, 2, ` − 1] MDS codes over Fq with 2 ≤ ` ≤ q are generalised Reed-Solomon codes.
Proof. First we know that GRS codes are MDS.
Let C be an [`, 2, ` − 1]q code with 2 ≤ ` ≤ q . Since C is MDS, it has dual distance d⊥ = 3, and we claim there
exists a codeword c ∈ C with Hamming weight `. Indeed, let G = (P1 , . . . , P` ) be a generator matrix of C , where
Pi ∈ F2q is written in column. Notice that each point Pi is non-zero (otherwise d⊥ = 1) and 0, Pi , Pj are not on
the same line for i 6= j (otherwise d⊥ = 2). Moreover codewords in C are simply evaluations of bilinear maps
µ : F2q → Fq over (P1 , . . . , P` ):
C = {(µ(P1 ), . . . , µ(P` )), µ ∈ L(F2q , Fq )} ,

and the Pi ’s are not all on the same line (otherwise, dim C ≤ 1).
Since ` ≤ q , there exists Q = (Q0 , Q1 ) ∈ F2q \ {0} such that Q does not lie in the (vector) line defined by any
of the Pi ’s. Let now µQ (X, Y ) = Q1 X − Q0 Y : it is a non-zero bilinear form which must vanish on a line of F2q ,
and since µQ (Q) = 0, it vanishes on the one spanned by Q. To sum up, for every i ∈ [1, `], we have µQ (Pi ) 6= 0.
Hence, c = (µQ (P1 ), . . . , µQ (P` )) belongs to C and has Hamming weight `.
Let now u ∈ C such that {c, u} spans C . We denote by c ∗ u the coordinate-wise product (c1 u1 , . . . , c` u` ) and by
1 the all-one vector of length `. Then c = 1 ∗ c and u = c ∗ (c−1 ∗ u), where c−1
 is the coordinate-wise inverse of
1
0
0
0
c through ∗. Hence, the code C can be written c ∗ C where C has G = c−1 ∗u as generator matrix. It means that
C is the GRS code with evaluation points x = c−1 ∗ u, multipliers y = c and dimension 2.
We now study the consequences of Lemma V.13 in terms of transversal designs. We say a map φ : X → X 0 is
an isomorphism between transversal designs (X, B, G) and (X 0 , B 0 , G 0 ) if it is one-to-one and if it preserves the
incidence relations, or in other words, if φ is invertible on the points, blocks and groups:
φ(X) = X 0 ,

φ(B) = B 0 ,

φ(G) = G 0 .

`
Lemma V.14. Let C, C 0 be two codes such that C 0 = y ∗ C for some y ∈ (F×
q ) , where ∗ is the coordinatewise product of `-tuples. Recall TC , TC 0 are the transversal designs they respectively define. Then, TC and TC 0 are
isomorphic.

Proof. Write TC = (X, B, G) and TC 0 = (X 0 , B 0 , G 0 ). From the definition it is clear that X = X 0 = Fq × [1, `] and
G = G 0 = {Fq × {i}, 1 ≤ i ≤ `}. Now consider the blocks sets. We see that B = {{(ci , i), 1 ≤ i ≤ `}, c ∈ C} and
B 0 = {{(yi ci , i), 1 ≤ i ≤ `}, c ∈ C}. Let:
φy : Fq × [1, `] → Fq × [1, `]
(x, i)
7→ (yi x, i)

The vector y is ∗-invertible, hence φy is one-to-one on the point set X . It remains to notice that φy maps G to
itself since it only acts on the first coordinate, and that φy (B) is exactly B 0 by definition of C and C 0 .
Proposition V.15. Let 2 ≤ ` ≤ q and C0 be an [`, 2, ` − 1]q linear (MDS) code. Let also Fp be any finite field. The
incidence code ICp (C0 ) is permutation-equivalent to ICp (RS2 (x)), with x ∈ F`q , xi 6= xj .
Proof. Lemma V.13 shows that all [`, 2, ` − 1]q linear codes C0 can be written as y ∗ RS2 (x) for some x ∈ F`q .
Moreover, with the previous notation φy (TRS2 (x) ) = Ty∗RS2 (x) , so we have u ∈ ICp (y ∗ RS2 (x)) if and only if
u ∈ Codep (φy (TRS2 (x) )). Now, let:
φ̃y : FX
p
u = (ux )x∈X

→ FX
p
.
7
→
(uφy (x) )x∈X

Clearly φ̃y (ICp (RS2 (x))) = Codep (φy (TRS2 (x) )) and φ̃y is a permutation of coordinates. So ICp (C0 ) is permutationequivalent to ICp (RS2 (x)) which proves the result.

17

In our study of incidence codes of 2-dimensional MDS codes C0 , the previous proposition allows us to restrict our
work on Reed-Solomon codes C0 = RS2 (x) with x an `-tuple on pairwise distinct Fq -elements.
A first result proves that if x contains all the elements in Fq , then ICq (RS2 (x)) is the code which has been
previously studied in subsection V-A. More precisely,
Proposition V.16. The following two codes are equal up to permutation:
1) C1 = ICq (RS2 (Fq )), the incidence code over Fq of the full-length Reed-Solomon code of dimension 2 over
Fq ;
2) C2 , the code over Fq based on the transversal design TA (2, q).
Proof. It is sufficient to show that the transversal design defined by C0 = RS2 (Fq ) is isomorphic to TA (2, q). Let
us enumerate Fq = {x1 , . . . , xq }. We recall that TC = (X, B, G) where:
X = Fq × [1, q],

B = {{(ci , i), i ∈ [1, q]}, c ∈ C0 },

G = {{(α, i), α ∈ Fq }, i ∈ [1, q]} ,

and that TA (2, q) = (X 0 , B 0 , G 0 ) with:
X 0 = Fq × Fq ,

B 0 = {{(axi + b, xi ), i ∈ [1, q]}, (a, b) ∈ F2q },

G 0 = {{(α, xi ), α ∈ Fq }, i ∈ [1, q]} .

In the light of the above, one defines φ : X → X 0 , (α, i) 7→ (α, xi ), which is clearly one-to-one and satisfies
φ(G) = G 0 . Moreover, a codeword c ∈ C0 is the evaluation of a polynomial of degree ≤ 1 over Fq . Hence for some
(a, b) ∈ F2q , we have ci = axi + b, ∀i. This proves that φ extends to a one-to-one map B → B 0 , giving the desired
isomorphism.
It remains to study the case of tuples x of length ` < q . First, one may notice that ICq (RS2 (x)) is a shortening of
ICq (RS2 (Fq )). Indeed, we have the following property:
Lemma V.17. Let C0 be a linear code of length ` over Fq , and C0 be a puncturing of C0 on s positions. Then
for all prime powers q 0 , ICq0 (C0 ) is a shortening of ICq0 (C0 ) on the coordinates corresponding to s groups of the
transversal design TC0 .
Proof. Without loss of generality, we can assume that C0 is punctured on its s last coordinates in order to give C0 .
Let us analyse the link between TC0 = (X, B, G) and TC0 = (X, B, G). We have:
X = Fq × [1, ` − s]
⊂ X,
G = {Fq × {i}, i ∈ [1, ` − s]} ⊂ G,
B = {B ∩ X, B ∈ B}

Let C = ICq0 (C0 ) and C = ICq0 (C0 ). For clarity, we index words in C (resp. C ) by X (resp. X ). For c ∈ FX
q 0 , we
define ext(c) := c ∈ FX
=
=
0
.
By
definition
of
code’s
puncturing/shortening,
all
we
,
such
that
c
c
and
c
0
q
|X
|X\X
need to prove is:
C = {c ∈ FX
q 0 , ext(c) ∈ C}.
P
Remind that C is defined as the set of c ∈ FX
q 0 satisfying
b∈B cb = 0 for every B ∈ B . Hence we have:
X
c ∈ C ⇐⇒
cb = 0, ∀B ∈ B
b∈B

⇐⇒

X

cb = 0,

∀B ∈ B

b∈B∩X

⇐⇒

X

ext(c)b +

b∈B∩X

⇐⇒

X

ext(c)b = 0,

b∈B

⇐⇒ ext(c) ∈ C

X
b∈B∩(X\X)

∀B ∈ B

ext(c)b = 0,

∀B ∈ B

18

We conclude the proof by pointing out that X \ X is a union of s distinct groups from G .
Despite this result, incidence codes of Reed-Solomon codes RS2 (x) remain hard to classify for |x| = ` < q . Indeed,
for a given length ` < q , some IC(RS(x)) appear to be non-equivalent. Their dimension can even be different, as
shows an exhaustive search on IC16 (RS(x)) with pairwise distinct x ∈ F`q , q = 16 and ` = 5: we observe that
48 of these codes have dimension 24 while the 4320 others have dimension 22. Further interesting research would
then be to understand the values of x leading to the largest codes, for a fixed length |x| = `.
D. High-rate incidence codes from divisible codes
In this subsection, we prove that linear codes C0 satisfying a divisibility condition yield incidence codes whose rate
is roughly greater than 1/2. Let us first define divisible codes.
Definition V.18 (divisibility of a code). Let p ≥ 2. A linear code is p-divisible if p divides the Hamming weight
of all its codewords.
When studying the incidence matrix which defines an incidence code, we exhibit the following property.
Lemma V.19. Let C0 be a code of length ` over a set S , and let T be the transversal design associated to C0 . We
denote by M the incidence matrix of T , where rows of M are indexed by codewords from C0 . Then we have:
(M M T )c,c0 = ` − d(c, c0 )

∀c, c0 ∈ C ,

where d(·, ·) denotes the Hamming distance.
Proof. For clarity we adopt the notation M [c, (α, i)] for the entry of M which is indexed by the codeword c ∈ C0
(for the row), and (α, i) ∈ S × [1, `] (for the column). We also denote by 1U (c,i,α) ∈ {0, 1} the boolean value of
the property U , that is, 1U (c,i,α) = 1 if and only if U(c, i, α) is satisfied. Now, let c, c0 ∈ C0 .
X
X
(M M T )c,c0 =
M [c, (α, i)]M [c0 , (α, i)] =
1ci =α 1c0i =α
α∈S, i∈[1,`]

=

` X
X

α∈S, i∈[1,`]

1ci =c0i =α =

i=1 α∈S

`
X

1ci =c0i = ` − d(c, c0 ) .

i=1

Hence, if some prime p divides ` as well as the weight of all the codewords in C0 , then the product M M T vanishes
over any extension of Fp , and M is a parity-check matrix of a code containing its dual. A more general setting is
analysed in the following proposition.
Proposition V.20. Let C0 be a linear code of length ` over S , |S| = s. Let also C = ICq (C0 ) with char(Fq ) = p.
Denote the length of C by n = `s. If C0 is p-divisible, then
C ⊥ ∩ Cpar ⊆ C ,

where Cpar denotes the parity-check code of length n over Fq . In particular, we get dim C ≥

n−1
2 .

Moreover, if p|`, then C ⊥ ⊆ C and dim C ≥ n2 .
Proof. Let M be the incidence matrix of the transversal design TC0 . Also denote by J and J 0 the all-ones matrices
of respective size |C0 | × n and |C0 | × |C0 |. If we assume that C0 is p-divisible, then Lemma V.19 translates into
M M T = `J 0

mod p

(3)

while an easy computation shows that
M J T = `J 0 .

Hence, over Fq we obtain

M (M − J)T = 0

(4)

19

which brings us to consider the code A of
P length n generated over Fq by the matrix M − J . Equation (4)
indicates that A ⊆ C . Let Cpar := {c ∈ Fnq , i ci = 0} be the parity-check code of length n over Fq . Notice that
c ∈ Cpar ⇐⇒ cJ T = 0 and uJ = 0 ⇐⇒ uJ 0 = 0. If p 6 | `, this leads to:
C ⊥ ∩ Cpar = {c = uM ∈ Fnq , cJ T = 0}
= {c = uM ∈ Fnq , `uJ 0 = 0} = {c = uM ∈ Fnq , uJ = 0}
= {u(M − J) ∈ Fnq , uJ = 0} ⊆ A ⊆ C .

On the other hand, if p|`, then equation (3) turns into M M T = 0, meaning that C ⊥ ⊆ C .
Finally, the first bound on the dimension comes from
dim C ≥ dim(C ⊥ ∩ Cpar ) ≥ dim C ⊥ − 1 = n − dim C − 1 ,

while the second one is straightforward.
In terms of PIR protocols, previous result translates into the following corollary.
Corollary V.21. Let p be a prime, and assume there exists a p-divisible linear code of length `0 over Fq . Then,
there exists k ≥ (`0 q − 1)/2 such that we can build a distributed PIR protocol for a k -entries database over Fq ,
and whose parameters are `(k) = `0 and n(k) = `0 q ≤ 2k + 1.
Divisible codes over small fields have been well-studied, and contain for instance the extended Golay codes [15,
ch.II.6], or the famous MDS codes of dimension 3 and length q + 2 over Fq [15, ch.XI.6].
Example V.22. The extended binary Golay code is a self-dual [24, 12, 8]2 linear code. It produces a transversal
design with 24 groups, each storing 2 points. Its associated incidence code Code2 (Golay) has length n = 24×2 = 48
and dimension ≥ 24, and by computation we can show that this bound is tight.
Remark V.23. In our application for PIR protocols, we would like to find divisible codes C0 defined over large
alphabets (compared to the code length), but these two constraints seem to be inconsistent. For instance, the binary
Golay code presented in Example V.22 leads to a PIR protocol with a too expensive communication cost (24 bits of
communication for an original file of size... 24 bits: that is exactly the communication cost of the trivial PIR protocol
where the whole database is downloaded). Nevertheless, Example V.22 represents the worst possible case for our
construction, in a sense that the rate of IC2 (Golay2 ) is exactly 1/2 (it attains the lower bound), and that each server
stores 2 bits (which is the smallest possible). Codes with better rate and/or with larger server storage capability
would then give PIR protocols with relevant communication complexity. For instance, the extended ternary Golay
code gives better parameters — see Example VI.9.
Divisible codes over large fields seems not to have been thoroughly studied (to the best of our knowledge), since
coding theorists use to consider codes over small alphabets as more practical. We hope that our construction of
PIR protocols based on divisible codes may encourage research in this direction.
VI. PIR PROTOCOLS WITH BETTER PRIVACY
When servers are colluding, the PIR protocol based on a simple transversal design does not ensure a sufficient
privacy, because the knowledge of two points on a block gives some information on it. To solve this issue, we
propose to use orthogonal arrays with higher strength t.
A. Generic construction and analysis
In the previous section, classical (t = 2) orthogonal arrays were used to build transversal designs. Considering
higher values of t, we naturally generalise the latter as follows:
Definition VI.1 (t-transversal designs). Let ` ≥ t ≥ 1. A t-transversal design is a block design D = (X, B)
equipped with a group set G = {G1 , . . . , G` } partitioning X such that:

20

– |X| = s`;
– any group has size s and any block has size `;
– for any T ⊆ [1, `] with |T | = t and for any (x1 , . . . , xt ) ∈ GT1 × . . . × GTt , there exist exactly λ blocks B ∈ B
such that {x1 , . . . , xt } ⊂ B .
A t-transversal design with parameters s, `, t, λ is denoted t-TDλ (`, s), or t-TD(`, s) when λ = 1.
Given a t-transversal design T , we can build a (t − 1)-private PIR protocol with the exactly the same steps as in
section IV. First, we define the code C = Codeq (T ) associated to the design according to Definition III.7, and then
we follow the algorithm given in Figure 2. Since a t-transversal design is also a 2-transversal design for t ≥ 2, the
analysis is identical for every PIR feature, except for the security where it remains very similar.
Security ((t − 1)-privacy). Let T be a collusion of servers of size |T | ≤ t − 1. For varying i ∈ I , the distributions
Q(i)|T are the same because there are exactly λst−1−|T | ≥ λ 6= 0 blocks which contain both i and the queries
known by the servers in T .
To sum up, the following theorem holds:
Theorem VI.2. Let D be a database with k entries over Fq , and T = t-TD(`, s) be a t-transversal design, whose
incidence matrix has rank `s − k over Fq . Then, there exists an `-server (t − 1)-private PIR protocol with:
–
–
–
–

only 1 symbol to read for each server,
` − 1 field operations for the user,
` log(sq) bits of communication,
a (total) storage overhead of (`s − k) log q bits on the servers.

B. Instances and results
1) t-transversal designs from curves of degree ≤ t − 1: Looking for instances of t-transversal designs, it is natural
to try to generalise the transversal designs of Construction V.1. An idea is to turn affine lines into higher degree
curves.
Construction VI.3. Let X be the set of points in the affine plane F2q , and G = {G1 , . . . , Gq } be a partition of X
in q parallel lines. W.l.o.g. we choose the following partition: Gi = {(αi , y), y ∈ Fq } for each αi ∈ Fq . Blocks are
now defined as the sets of the form
BF = {(x, F (x)), x ∈ Fq }, where F ∈ Fq [x], deg F ≤ t − 1.

Lemma VI.4. The design (X, B, G) given in Construction VI.3 forms a t-transversal design t-TD1 (q, q).
Proof. The group set indeed partitions X into q groups, each of size q . It remains to check the incidence property.
Let {GT1 , . . . , GTt } be a set of t distinct groups, and let ((xT1 , yT1 ), . . . , (xTt , yTt )) ∈ GT1 × · · · × GTt . From
Lagrange interpolation theorem, we know there exists a unique polynomial F ∈ Fq [X] of degree ≤ t − 1 such that:
F (xTj ) = yTj

∀1 ≤ j ≤ t .

Said differently, there is a unique block which contains the t points {(xTj , yTj )}1≤j≤t .
We do not yet analyse the rank properties of these designs, since Construction VI.3 corresponds to a particular
case of the generic construction given below.
2) t-transversal designs from orthogonal arrays of strength t: In this paragraph we give a generic construction
of t-transversal designs, which is a simple generalisation of the way we build transversal designs with orthogonal
arrays (Subsection V-C).
Construction VI.5. Let A be an orthogonal array OAλ (t, `, s) on a symbol set S . Recall that the array A is
composed of rows ai = (ai,j )1≤j≤` for 1 ≤ i ≤ λst . We define the following design:
– its point set is X = S × [1, `];
– its group set is G = {S × {i}, 1 ≤ i ≤ `};

21

– its blocks are Bi = {(ai,j , j), 1 ≤ j ≤ `} for all ai ∈ Rows(A).
Proposition VI.6. If A is an OAλ (t, `, s), then the design defined with A by Construction VI.5 is a t-TDλ (`, s).
Proof. It is clear that G is a partition of X and that blocks and groups have the claimed size. Now focus on the
incidence property. Let T ⊂ [1, `] with |T | = t, and let (x1 , . . . , xt ) ∈ GT1 × . . . × GTt . We need to prove that
there are exactly λ blocks B ∈ B such that {x1 , . . . , xt } ⊂ B .
Consider the map from blocks in B to rows of A given by:
ψ:

B
→
Rows(A)
Bi = {(ai,j , j), 1 ≤ j ≤ `} 7→ (ai,1 , . . . , ai,` )

Since we assumed that orthogonal arrays have no repeated row, the map ψ is one-to-one. Denote by x0 =
(x01 , , . . . , x0t ) ∈ S t the vector formed by the first coordinates of (x1 , , . . . , xt ) ∈ X t . From the definition of an
orthogonal array of strength t and index λ, we know that x0 appears exactly λ times in the submatrix of A defined
by the columns indexed by T . Hence this defines λ preimages in B , which proves the result.
Remark VI.7. As we noticed before, Construction VI.3 is a particular case of Construction VI.5. Indeed, a block
BF = {(x, F (x)), x ∈ Fq }, with deg F ≤ t − 1 is in one-to-one correspondence with a codeword cF of a ReedSolomon code of dimension t.
Corollary VI.8. Let C0 be a code of length ` and dual distance t + 2 ≤ ` over a set S of size s. Then, ICq (C0 )
defines a t-private PIR protocol.
Proof. Let A be the orthogonal array defined by C0 . We know that A has strength t + 1 (see e.g. [15]), hence from
Proposition VI.6, the associated transversal design is a (t + 1)-TD(`, s). Theorem VI.2 then ensures that the PIR
protocol induced by this transversal design is t-private.
As in Section V, when the code C0 is divisible, we can lower bound the rate of its incidence code. We provide two
examples in finite (and small) length.
Example VI.9. A first example would be to consider extended Golay codes. Indeed, they are known to be divisible
by their characteristic [15, ch.II.6], they have large dual distance, and Proposition V.20 then ensures their incidence
codes have non-trivial rate. In Remark V.23, we noticed that the binary Golay code does not lead to a practical PIR
protocol due to a large communication complexity. Thus, let us instead consider the [12, 6, 6]3 extended ternary
Golay code, that we denote Golay3 . It is self-dual, hence d⊥ (Golay3 ) = 6. Then, C = IC3e (Golay3 ), e ≥ 1, has
length 36 and Proposition V.20 shows that dim C ≥ 18 (the bound can be proved to be tight by computation).
Hence, the associated PIR protocol works on a raw file of 18 F3e -symbols encoded into 36, uses 12 servers (each
storing 3 F3e -symbols) and resists any collusion of one third (i.e. 4) of them.
Example VI.10. A second example arises from the exceptional [q + 2, 3, q]q MDS codes in characteristic 2 [15,
ch.XI.6]. For instance, for q = 4, we obtain a 2-private PIR protocol with 6 servers, each storing 4 symbols of F2e
for some e ≥ 1. Once again, the dimension of the incidence code attains the lower bound, here k = 12.
Example VI.11. Examples of incidence codes which do not attain the lower bound of Proposition V.20 come from
binary Reed-Muller codes of order 1, denoted RM2 (m, 1). These codes are 2-divisible since they are known to be
equivalent to extended Hamming codes. They also have length n = 2m and dual distance d⊥ = n/2.
For instance, RM2 (3, 1) provides an incidence code of dimension k = 11 > 8, that is, a 2-private 8-server PIR
protocol on a database with 11 F2e -symbols, where each server stores 2 symbols. For m = 4, RM2 (4, 1) gives a
6-private 16-server PIR protocol on a database with 20 F2e -symbols, each server storing 2 symbols. We conjecture
that IC2 (RM2 (m, 1)) leads to a (2m−1 − 2)-private 2m -server PIR protocol on a database with 2m + m symbols,
each server storing 2 symbols.
As pointed out in Subsection V-C, high-rate incidence codes C = IC(C0 ) have the best chance to occur when
the dimension of C0 is small, since the cardinality of C0 is the number of rows in a (non-full-rank) parity-check
matrix which defines C . Besides, in order to define t-private PIR protocols, we need an orthogonal array of strength

22

t + 2, i.e. a code C0 with dual distance t + 2. Conciliating both constraints, we are tempted to pick MDS codes of
dimension t + 1.

A well-known family of MDS codes is the family of Reed-Solomon codes. For C0 = RSt+1 (Fq ) and varying
values of q and t, we were able to compute the√rate of IC(C0 ), and these codes lead to t-private PIR protocols
with communication complexity approximately n, where n is the length of the encoded database. These rates
are presented in Figure 7 and as expected, the rate of our families of incidence codes decreases with t, the privacy
parameter. Figure 7 also shows that Reed-Solomon-based instances cannot expect to reach at the same time constant
information rate and resistance to a constant fraction of colluding servers.
rate R = k/n
1
0.9

t=1

0.8
0.7

t=2

0.6
0.5
t=4

0.4
0.3

t=log(q)

0.2

t=q1/2
t=q/2

0.1

t=q/3

t=q-1
0
6

8

10

12

14

16

18

20

log n = 2 log q

Fig. 7: Rate of incidence codes of C0 that are used for building t-private PIR protocols. Codes C0 are fulllength Reed-Solomon codes of dimension t + 1 (dual distance t + 2) over Fq . Associated PIR protocols then
need q servers, each storing q symbols.

VII. C OMPARISON WITH OTHER WORKS
Our construction fits into the model of distributed (or coded) PIR protocols, which is currently instantiated in a few
schemes, notably the construction of Augot et. al. [2] and all the works involving the use of PIR codes initiated
by Fazeli et. al [11]. We recall that we aimed at building PIR protocols with very low burden for the servers, in
terms of storage and computation. While PIR codes are a very efficient way to reduce the storage overhead, they
do not cut down the computation complexity of the original replication-based PIR protocol used for the emulation.
Hence, for the sake of consistency, we will only compare the parameters of our PIR schemes with those of the
multiplicity code construction presented in [2].
Sketch of the construction [2]. Multiplicity codes C have the property that a codeword c ∈ C can be seen as the
vector of evaluations of a multivariate polynomial fc ∈ Fq [X1 , . . . , Xm ] and its derivatives over the space Fm
q , where
Fq denotes the finite field with q elements. Every affine line of the space Fm
then
induces
linear
relations
between
q
fc and its derivatives, which translates into low-weight parity-check equations for the codewords. This allows to
define to a local decoder for C :when trying to retrieve a symbol Di indexed by i ∈ Fm
q , one can pick random
affine lines going through i and recover Di by computing short linear combinations of the symbols associated to
the evaluations of fc and their derivatives along these lines. We refer to [14] for more details on these codes.
Augot et. al. [2] realized that partitioning Fm
q into q parallel hyperplanes gives rise to storage improvements.
By splitting the encoded database according to these hyperplanes and giving one part to each of the q servers,

23

they obtained a huge cutdown on both the total storage and the number of servers, while keeping an acceptable
communication complexity. Their construction requires a minor modification of the LDC-based PIR protocol of
Figure 1; indeed, in the query generation process, the only server which holds the desired symbol must receive
a random query. Nevertheless, the PIR scheme they built was at that time the only one to let the servers store
less than twice the size of the database. Moreover, the precomputation of the encoding of the database ensures
an optimal computational complexity for the servers. As noticed previously, we emphasize the significance of this
feature when the database is very frequently queried.
Parameters of the distributed PIR protocol [2] based on multiplicity codes. This PIR scheme depends on four
main parameters: the field size q , the dimension m of the underlying affine space, the multiplicity order s and
the maximal degree d of evaluated polynomials.
For an error-free and collusion-free setting, d = s(q − 1) − 1 is

m+s−1
the optimal choice.
Let
σ
=
.
The
associated
PIR protocol uses q servers to store an original database
m

d+m
containing m Fq -symbols, but encoded into codewords of length q m , where each symbol has size σ log q bits.
Hence the redundancy (in bits) of the scheme is:



s(q − 1) + m − 1
ρ = σq m −
log q .
m
Concerning the communication complexity, let us only focus on the download cost (which is often the bottleneck in
practice). Each server answers a symbol of size σ 2 log q bits. Thus it leads to a download communication complexity
of
γ = σ 2 q log q bits.
Note about the comparison strategy. We consider a database D of size 100 MB. Since the protocols may be
initially constructed for databases of smaller size k , we split D into k chunks of size |D|/k . Hence, when running
the PIR protocol, the user is allowed to retrieve a whole chunk, and the chunk size will be precised in our tables.
For instance, in the first row of Table II, one shall understand that the user is able to retrieve 31.1kB of the database
privately, with 1.99MB of communication, while each server only produces 1 operation over the chunks (of size
31.1kB) it holds.
Instance
TA (m = 2, q = 64)
TA (m = 3, q = 64)
Mult(q = 64, m = 3, s = 6)
Mult(q = 64, m = 4, s = 2)

download
communication
1.99 MB
56 kB
2.32 MB
15 kB

complexity
(#op./server)
1
1
56
5

storage overhead
22.7 MB
126 MB
64.8 MB
694 MB

chunk size
31.1 kB
882 B
16 B
13 B

TABLE II: Comparison of some distributed PIR protocols with 64 servers on a 100MB initial database.
Parameters of multiplicity codes have been chosen in order to obtain simultaneously low communication
complexity and storage overhead.

Instance
TA (m = 2, q = 8)
TA (m = 3, q = 8)
Mult(q = 8, m = 4, s = 2)
Mult(q = 8, m = 6, s = 3)

download
communication
22.7 MB
6.03 MB
8.8 MB
2.86 MB

complexity
(#op./server)
1
1
5
28

storage overhead
76 MB
281 MB
797 MB
3.24 GB

chunk size
2.83 MB
754 kB
117 kB
1.2 kB

TABLE III: Comparison of some distributed PIR protocols with 8 servers on a 100MB initial database. We
notice that for q = 8 servers, there only exist a few non-Reed-Muller (s ≥ 2) multiplicity codes whose
associated PIR protocols have communication complexity strictly less than the size of the original database.
Tables II and III first reveal that our PIR schemes are more storage efficient than the PIR schemes relying on
multiplicity codes. Moreover, our constructions provide a better communication rate (defined as the ratio between
communication cost and chunk size), though the multiplicity code PIR protocols allow to retrieve smaller chunks
(hence is more flexible).

24

Remark VII.1. Recent constructions of PIR protocols (for instance results of Sun and Jafar such that [17]) lead
to better parameters in terms of communication complexity. However, we once more emphasize that we aimed at
minimizing the computation carried out by the servers, which is a feature that is mostly not considered in those
works.
VIII. C ONCLUSION
In this paper, we have presented a generic construction of codes which turns out to be appropriate for distributed
PIR protocols. Our construction makes use of transversal designs, whose incidence properties ensure a natural
distribution of the database on the servers, as well as the privacy of the queries. We point out that our scheme is
computationnally optimal for the servers, in a sense that they only have to read one symbol of the file they hold.
Moreover, it also admits an efficient reconstructing step since the user only needs to compute a linear combination
of the symbols it receives. Our PIR protocols also require low storage for the servers and acceptable communication
complexity.
We instantiated our construction with classical transversal designs coming from affine and projective geometries,
and with transversal designs emerging from orthogonal arrays of strength 2. The last construction that we call
incidence code can even be generalized, since stronger orthogonal arrays lead to PIR protocols with better privacy.
The genericity of our construction allows the user to choose appropriate settings according to the context (low
storage capability, few colluding servers, etc.). This genericity also leads to the question of finding transversal
designs with the most practical PIR parameters for a given context. Indeed, while affine and projective geometries
give excellent PIR parameters for the servers (low computation, low storage), there seems to remain room for
improving the communication complexity and the number of servers needed in the PIR scheme.
ACKNOWLEDGEMENTS
This work is partially funded by French ANR-15-CE39-0013-01 “Manta”. The author would like to thank Françoise
Levy-dit-Vehel and Daniel Augot for their valuable comments, and more specifically the first collaborator for her
helpful guidance all along the writing of the paper.
R EFERENCES
[1] Edward F. Assmus and Jennifer D. Key. Designs and Their Codes. Cambridge University Press, 1992.
[2] Daniel Augot, Françoise Levy-dit-Vehel, and Abdullatif Shikfa. A storage-efficient and robust private information retrieval scheme allowing few servers. In Dimitris Gritzalis, Aggelos Kiayias, and Ioannis G. Askoxylakis,
editors, Cryptology and Network Security - 13th International Conference, CANS 2014, Heraklion, Crete,
Greece, October 22-24, 2014. Proceedings, volume 8813 of Lecture Notes in Computer Science, pages 222–
239. Springer, 2014.
[3] Amos Beimel, Yuval Ishai, Eyal Kushilevitz, and Jean-François Raymond. Breaking the O(n1/(2k−1) ) barrier
for information-theoretic private information retrieval. In 43rd Symposium on Foundations of Computer Science
(FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings, pages 261–270. IEEE Computer
Society, 2002.
[4] Amos Beimel, Yuval Ishai, and Tal Malkin. Reducing the servers’ computation in private information retrieval:
PIR with preprocessing. J. Cryptology, 17(2):125–151, 2004.
[5] Benny Chor and Niv Gilboa. Computationally private information retrieval. In Frank Thomson Leighton and
Peter W. Shor, editors, Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing,
El Paso, Texas, USA, May 4-6, 1997, pages 304–313. ACM, 1997.
[6] Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan. Private information retrieval. In 36th
Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, 23-25 October 1995, pages
41–50. IEEE Computer Society, 1995.
[7] Benny Chor, Eyal Kushilevitz, Oded Goldreich, and Madhu Sudan. Private information retrieval. J. ACM,
45(6):965–981, 1998.

25

[8] Charles J. Colbourn and Jeffrey H. Dinitz. Handbook of Combinatorial Designs, Second Edition. Chapman
& Hall/CRC, 2006.
[9] Zeev Dvir and Sivakanth Gopi. 2-server PIR with subpolynomial communication. J. ACM, 63(4):39:1–39:15,
2016.
[10] Klim Efremenko. 3-query locally decodable codes of subexponential length. SIAM J. Comput., 41(6):1694–
1703, 2012.
[11] Arman Fazeli, Alexander Vardy, and Eitan Yaakobi. Codes for distributed PIR with low storage overhead.
In IEEE International Symposium on Information Theory, ISIT 2015, Hong Kong, China, June 14-19, 2015,
pages 2852–2856. IEEE, 2015.
[12] Noboru Hamada. The rank of the incidence matrix of points and d-flats in finite geometries. Journal of
Science of the Hiroshima University, Series A-I (Mathematics), 32(2):381–396, 1968.
[13] Jonathan Katz and Luca Trevisan. On the efficiency of local decoding procedures for error-correcting codes.
In F. Frances Yao and Eugene M. Luks, editors, Proceedings of the Thirty-Second Annual ACM Symposium
on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 80–86. ACM, 2000.
[14] Swastik Kopparty, Shubhangi Saraf, and Sergey Yekhanin. High-rate codes with sublinear-time decoding. J.
ACM, 61(5):28:1–28:20, 2014.
[15] F.J. MacWilliams and N.J.A. Sloane. The Theory of Error-Correcting Codes. North Holland, 1977.
[16] Douglas R. Stinson. Combinatorial Designs - Constructions and Analysis. Springer, 2004.
[17] Hua Sun and Syed Ali Jafar. The capacity of private information retrieval. IEEE Trans. Information Theory,
63(7):4075–4088, 2017.
[18] Razan Tajeddine and Salim El Rouayheb. Private information retrieval from MDS coded data in distributed
storage systems. In IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, July
10-15, 2016, pages 1411–1415. IEEE, 2016.
[19] Sergey Yekhanin. Towards 3-query locally decodable codes of subexponential length. J. ACM, 55(1):1:1–1:16,
2008.
[20] Sergey Yekhanin. Locally decodable codes. Foundations and Trends in Theoretical Computer Science,
6(3):139–255, 2012.
A PPENDIX
Hamada [12] gives a generic formula to compute the p-rank of a projective geometry design PGt (m, q), for q = pe :



j+1 ,sj )
e−1
X
Y L(sX
m + 1 m + sj+1 p − sj − ip
rankp PGt (m, q) =
(−1)i
i
m
(s0 ,..., se )∈S j=0

where L(sj+1 , sj ) =

b sj+1pp−sj c

i=0

and (s0 , . . . , se ) ∈ S ⊂ Ze+1 are such that:

 s0 = se
t + 1 ≤ sj ≤ m + 1

0 ≤ sj+1 p − sj ≤ (m + 1)(p − 1) .

The p-rank of the associated affine geometry design AGt (m, q) can be derived from the projective one by:
rankp AGt (m, q) = rankp PGt (m, q) − rankp PGt (m − 1, q) .

Despite its heavy expression, Hamada’s formula can be simplified by picking very specific values of m, p or e.
For instance we have:


p+1 e
e
m = 2 : ∀p, e, rankp AG1 (2, p ) =
,
2


m+p−2
m
e = 1 : ∀p, m, rankp AG1 (m, p) = p −
,
m



 

p+1 2
p p+1
2
3
m = 3 and e = 2 : ∀p, rankp AG1 (3, p ) = p −
+2
,
3
2
3

26

where the last equality has been found by interpolation (since rankp AG1 (m, pe ) is a polynomial of degree at most
me in p).

