Julien Lavauzelle

Private Information Retrieval from Transversal Designs

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 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, few works address the issue of the computation complexity of the servers.

It this paper, we show that a specific encoding of the database yields 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 several instances for our construction, which make use of finite geometries and orthogonal arrays. We finally give a generalisation of our main construction in order to resist collusions of servers.

I. INTRODUCTION

A. Private Information Retrieval

A private information retrieval (PIR) protocol aims at ensuring a user that he can retrieve some part D i of a remote database D without revealing the index i to the server(s) holding 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 [START_REF] Chor | Private Information Retrieval[END_REF][START_REF] Chor | Private Information Retrieval[END_REF].

A naive solution to the problem consists in downloading the entire database each time the user wants a single entry. 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 which leaks no information on the index i (such a protocol being called informationtheoretically secure) must use Ω(k) bits of communication [START_REF] Chor | Private Information Retrieval[END_REF]. Two alternatives were then considered: restricting the protocol to computational security (initiated by Chor and Gilboa [START_REF] Chor | Computationally Private Information Retrieval[END_REF]), 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 servers, > 1. Informally, the idea is that each server is asked to compute some partial information related to a random-like query sent by the user. Then the user collects all the servers' answers and retrieves the desired symbol with an appropriate algorithm. For instance, Chor et al. [START_REF] Chor | Private Information Retrieval[END_REF] considered a smart arrangement of the database entries in a log( )-dimensional array, and used XOR properties to mask the index of the desired item and to retrieve the associated symbol. Their protocol features decreasing communication as a function of the number of servers: with servers, the communication is O( log( )k 1/ log ) bits. For constant , the authors also proposed a PIR protocol with communication O(k 1/ ). A few years later, Katz and Trevisan [START_REF] Katz | On the Efficiency of Local Decoding Procedures for Error-Correcting Codes[END_REF] showed that any smooth locally decodable code C ⊆ Σ n of locality gives rise to a PIR protocol with servers whose communication complexity is O( log(n|Σ|)) -see [START_REF] Yekhanin | Locally Decodable Codes[END_REF] for a good survey on locally decodable codes (LDCs) and their applications in PIR protocols. Building on this idea, many PIR schemes (notably [START_REF] Beimel | Breaking the O(n 1/(2k-1) ) Barrier for Information-Theoretic Private Information Retrieval[END_REF][START_REF] Yekhanin | Towards 3-query Locally Decodable Codes of Subexponential Length[END_REF][START_REF] Efremenko | 3-Query Locally Decodable Codes of Subexponential Length[END_REF][START_REF] Dvir | 2-Server PIR with Subpolynomial Communication[END_REF]) successively decreased the communication complexity, achieving O(k √ log log k/ log k ) with only = 2 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 [START_REF] Beimel | Reducing the Servers' Computation in Private Information Retrieval: PIR with Preprocessing[END_REF] were the first to address the minimization of the server storage/computation in PIR protocols. Then, initiated by Fazeli, Vardy and Yaakobi [START_REF] Fazeli | Codes for Distributed PIR with Low Storage Overhead[END_REF], 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 servers 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 [START_REF] Tajeddine | Private Information Retrieval from MDS Coded Data in Distributed Storage Systems[END_REF], and/or aim at reaching the so-called capacity of the model [START_REF] Sun | The Capacity of Private Information Retrieval[END_REF]. However, while the storage drawback seems to be solved, huge computational costs still represent a barrier to the practicality of such PIR protocols.

B. Motivations and results

As pointed out by Yekhanin [START_REF] Yekhanin | Locally Decodable Codes[END_REF], "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 crucial is this context. Hence, one cannot afford each run of the PIR protocol to be computationally inefficient, for instance Ω(k) if k is the size of the database. Therefore, a relevant goal is to build 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 if we let all possible answers to its queries to be precomputed. Of course, storing all these answers dramatically increases the needed storage, so let us focus on a construction due to Augot, Levy-dit-Vehel and Shikfa [START_REF] Augot | A Storage-Efficient and Robust Private Information Retrieval Scheme Allowing Few Servers[END_REF] anterior to the PIR codes breakthrough [START_REF] Fazeli | Codes for Distributed PIR with Low Storage Overhead[END_REF] -that address this issue.

The construction of Augot et al. [START_REF] Augot | A Storage-Efficient and Robust Private Information Retrieval Scheme Allowing Few Servers[END_REF] uses a specific family of high-rate locally decodable codes called multiplicity codes introduced by Kopparty, Saraf and Yekhanin [START_REF] Kopparty | High-Rate Codes with Sublinear-Time Decoding[END_REF]. But instead of replicating the database on servers ( > 1 being the locality of the codes), 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 [START_REF] Fazeli | Codes for Distributed PIR with Low Storage Overhead[END_REF] is that Augot et al.'s construction does not purpose to emulate a lighter PIR protocol with an existing one. It 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 reconsider this "codeword support splitting" idea, and we propose a new generic framework for the construction of PIR protocols which takes into account the computational complexity issue. More precisely, the protocols we give are computationally optimal with respect to the communication complexity of the protocol, in the sense that each server needs to read only one entry in the part of the database it holds.

Our construction is based on combinatorial structures called transversal designs, from which we naturally derive a linear code, a partition of its support and a local reconstruction algorithm. In practice, we give several instances of transversal designs that lead to codes with large rate, hence to PIR protocols with low storage overhead. The two first families come from incidences between points and lines in the affine (resp. projective) space. They are closely related to the classical geometric designs of 1-flats. A third family of instances makes use of a classical transformation of so-called orthogonal arrays of strength 2 into transversal designs. We then proceed to a thorough study of the dimension of codes coming from MDSlike orthogonal arrays of strength 2. A fourth and last family of practical instances appears when showing that orthogonal arrays built from divisible codes lead to PIR protocols with storage expansion less than 2. We finally prove that orthogonal arrays with strength t > 2 allow the construction of PIR protocols resisting to collusions of up to t -1 servers. We exhibit and analyzed instances of some orthogonal arrays with large strength to conclude this work.

C. Organization

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. In Section III, we recall definitions of combinatorial structures and their associated codes. The 1-private PIR protocols based on transversal designs are introduced in Section IV. Section V is devoted to four families of instances of the PIR construction having practical 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.

II. DEFINITIONS AND RELATED CONSTRUCTIONS

We first recall that we are only concerned with informationtheoretically 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 = (D i ) 1≤i≤k ∈ F k q , where F q represents the finite field with q elements. Database D hence contains |D| = k log q bits. We also denote by S 1 , . . . , S the servers involved in the PIR protocol. Given A, B two sets, with |B| = n < ∞, we denote by A B the set of n-tuples a = (a b ) 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 := (a t ) 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 S 1 , . . . , S . Then, the role of each server S j 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 S j , 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 1 , . . . , q ) := Q(i). Query q j is sent to server S j . 2) Servers' answer: each server S j computes an answer a j = A(q j , D) and sends it back to the user 1 .

3) Reconstruction: denote by a = (a 1 , . . . , a ) and q = (q 1 , . . . , q ). User U computes and outputs r = R(i, a, q). The PIR protocol is said:

• correct if r = D i when the servers follow the protocol;

• t-private if, for every (i, i ) ∈ [1, k] 2 and every T ⊆ [1, ] such that |T | ≤ t, the distributions Q(i) |T and Q(i ) |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 F q -operations made by a server in order to compute an answer a j (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 = (c i ) i∈I denote an encoding of the database D, i.e. the image of D by an injective map F k q → F I q , with |I| = n ≥ k. Besides, for convenience we assume that I = [1, s] × [1, ] and for readability we write c (i1,i2) = c (i2) i1 and c (j) = (c (j) r ) r∈ [1,s] . Definition II.2 (distributed PIR protocol). Assume that for 1 ≤ j ≤ , server S j 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 1 , . . . , q ) := Q(i). Query q j is sent to server S j . 2) Servers' answer: each server S j computes an answer a j = A(q j , c (j) ) and sends it back to the user. 3) Reconstruction: denote by a = (a 1 , . . . , a ) and q = (q 1 , . . . , q ). User U computes and outputs r = R(i, a, q). 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. [START_REF] Augot | A Storage-Efficient and Robust Private Information Retrieval Scheme Allowing Few Servers[END_REF] 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 [START_REF] Katz | On the Efficiency of Local Decoding Procedures for Error-Correcting Codes[END_REF], but we emphasize that the main idea from [START_REF] Augot | A Storage-Efficient and Robust Private Information Retrieval Scheme Allowing Few Servers[END_REF] 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 [START_REF] Katz | On the Efficiency of Local Decoding Procedures for Error-Correcting Codes[END_REF], 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 → F n
q 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 ∈ F n q , if |{j ∈ [1, n], y j = C(m) j }| ≤ δn, then P(D (y) (i) = m i ) ≥ 1 -,
where the probability is taken over the internal randomness of D;

• D reads at most symbols y q1 , . . . , y q of y. Notation D (y) refers to the fact that D has oracle access to single symbols y qj 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 ⊂ F n q of dimension k and locality . Figure 1 1) Queries generation: user U calls D to generate at random a query (q 1 , . . . , q ) for decoding the symbol D i . Query q j is sent to server S j . 2) Servers' answer: each server S j reads the encoded symbol a j := c qj . Then S j sends a j to U . 3) Reconstruction: user U collects the codeword symbols (c qj ) j∈[1, ] and feeds the local decoding algorithm D in order to retrieve D i . 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 [START_REF] Augot | A Storage-Efficient and Robust Private Information Retrieval Scheme Allowing Few Servers[END_REF] for reducing the storage overhead is to benefit from a natural partition of the support of multiplicity codes [START_REF] Kopparty | High-Rate Codes with Sublinear-Time Decoding[END_REF]. Assume that each codeword c ∈ C can be split into disjoint parts c (1) , . . . , c ( ) , such that each coordinate q j of any possible query (q 1 , . . . , q ) of the PIR protocol corresponds to reading some symbols on c (j) . By sending the part c (j) to server S j , 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 the smoothness of the code serves their privacy. We also point out two important remarks.

1) Assuming a noiseless transmission and honest-butcurious 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 D i 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. TRANSVERSAL DESIGNS AND CODES

Let us give here the definition of transversal designs and how to build linear codes upon them. We refer to [START_REF] Assmus | Designs and Their Codes[END_REF], [START_REF] Douglas | Combinatorial Designs -Constructions and Analysis[END_REF] and [START_REF] Colbourn | Handbook of Combinatorial Designs[END_REF] 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 M D 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 M D is the rank of M D over the field F q .

For B ⊂ X, the incidence vector 1 B ∈ {0, 1} X is the row vector whose x-th coordinate is 1 if and only if x ∈ B. Let us notice that, given a design D = (X, B), one can build M D by stacking incidence vectors of blocks B ∈ B.

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 qrank 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 M D of a design D.

Example III.3. Let A 2 (F 3 ) be the affine plane over the finite field F 3 , and X be the set consisting of its 9 points: X = { (0, 0), (0, 1), (0, 2), (1, 0), [START_REF] Assmus | Designs and Their Codes[END_REF][START_REF] Assmus | Designs and Their Codes[END_REF], [START_REF] Assmus | Designs and Their Codes[END_REF][START_REF] Augot | A Storage-Efficient and Robust Private Information Retrieval Scheme Allowing Few Servers[END_REF], (2, 0), (2, 1), (2, 2) } .

We define the block set B as the set of the 12 affine lines of A 2 (F 3 ):

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

The pair D = (X, B) is then a block design, and its associated (12 × 9)-incidence matrix is

M D =                    
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 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 F 2 , matrix M D is full-rank, while over F 3 , 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 = {G 1 , . . . , 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 one group and no block or in no group and λ blocks. If λ = 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 λs 2 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 [START_REF] Beimel | Breaking the O(n 1/(2k-1) ) Barrier for Information-Theoretic Private Information Retrieval[END_REF][START_REF] Beimel | Breaking the O(n 1/(2k-1) ) Barrier for Information-Theoretic Private Information Retrieval[END_REF]. Indeed, T is composed of s = 9 points, = 3 groups of size s = 3 and s 2 = 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 A 2 (F q ). 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 that the dual code C ⊥ of a code C ⊆ F n q is the linear vector space consisting of vectors h ∈ F n q such that ∀c ∈ C, n i=1 c i h i = 0. Definition III.7 (code of a design). Let F q be a finite field, D = (X, B) be a block design and M D be its incidence matrix. The code Code q (D) is the F q -linear code of length |X| admitting M D as a parity-check matrix.

Remark III.8. The code Code q (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 F q of Code q (D) equals |X|-rank q (M D ). Since M D has coefficients in {0, 1}, one must notice that rank q (M D ) = rank p (M D ), where p is the characteristic of the field F q .

Remark III.9. Standard literature (e.g. [START_REF] Assmus | Designs and Their Codes[END_REF]) sometimes defines Code q (D) (and not Code q (D) ⊥ ) to be the vector space generated by the incidence matrix of the design. We favor this convention because Code q (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 = Code 3 (D), a linear code over F 3 , of length 9 and dimension 3. A full-rank generator matrix of C is given by:

G =   1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 2 2 2 0 1 2 0 1 2 0 1 2   .
One may notice that this code is the generalized Reed-Muller code of degree 1 and order 2 over F 3 , that is, the evaluation code of bivariate polynomials of total degree at most 1 over the whole affine plane F 2 3 . Definition III.11 (systematic encoding). Let C ⊆ F n q be a linear code of dimension k ≤ n. A systematic encoding for C is a one-to-one map φ : F k q → C, such that there exists an injective map σ :

[1, k] → [1, n] satisfying: ∀m ∈ F k q , ∀i ∈ [1, k], m i = φ(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 retrieving m from c efficiently, 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 non-communicating 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 [START_REF] Fazeli | Codes for Distributed PIR with Low Storage Overhead[END_REF] 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 = Code q (T ) ⊆ F n q the associated F q -linear code, and let k = dim Fq 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 F q , and T = TD( , s) be a transversal design, whose incidence matrix has rank s-k over F q . Then, there exists a distributed -server 1-private PIR protocol with:

• only one F q -symbol to read for each server,

• -1 field operations over F q 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.

Proof. Recall the PIR protocol we are dealing with is defined in Figure 2.

Correctness. By definition of the code C = Code q (T ), the incidence vector 1 B of any block B ∈ B belongs to the dual code C ⊥ . Hence, for c ∈ C, the inner product 1 B • c vanishes, or said differently, x∈B c x = 0. We recall that j * represents the index of the group which contains i. Since the servers S j , j = j * , receive queries corresponding to the points of a block B which contains i, we have c i = -x∈B\{i} c x = j =j * c qj , and our PIR protocol is correct as long as there is no error on the symbols a j := c qj returned by the servers.

Parameters: T = (X, B, G) is a TD λ ( , s); C = Code q (T ) has length n = s and dimension k.

1) Initialization step.

1) Encoding. User U computes a systematic encoding of the database D ∈ F k q , resulting in the codeword c ∈ C. 2) Distribution. Denote by c (j) = c |Gj the symbols of c whose support is the group G j ∈ G. Each server S j receives c (j) , for 1 ≤ j ≤ . 2) Retrieving step for symbol c i for i ∈ X. Denote by j * ∈ [1, ] the index of the unique group G j * which contains i -that is,

c i = c (j * ) r
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 = j * , user sends the unique index q j ∈ B ∩ G j to server S j . Server S j * receives a random query q j * uniformly picked in G j * . To sum up ( $ ←stands for "picked uniformly at random in"):

     Q(i) j * $ ← -G j * , for j * s.t. i ∈ G j * B $ ← -B * for j = j * Q(i) j ← B ∩ G j ,
2) Servers' answer. Each server S j (including S j * ) reads a j := c qj and sends it back to the user. That is,

A(q j , c (j) ) = c qj .
3) Reconstruction. Denote by a = {a 1 , . . . , a } and q = {q 1 , . . . , q }. User U computes r = R(i, a, q) := -

j =j * a j = - j =j * c qj
and outputs r.

Fig. 2: A 1-private distributed PIR protocol based on the F q -linear code defined by a transversal design.

Transversal design TD( , s)

incidence matrix TD-based linear code Code q (TD( , s)) ⊆ F s q database encoding Distributed PIR scheme Fig. 3: Summary of the steps leading to the construction of a transversal-design-based PIR scheme.

Security (1-privacy). We need to prove that for all j ∈ [1, ], it holds that P(i | q j ) = P(i), where probabilities are taken over the randomness of B ← B * . The law of total probability implies

P(i | q j ) = P(i | q j and i ∈ G j ) P(i ∈ G j ) + P(i | q j and i / ∈ G j ) P(i / ∈ G j ) = P(i | i ∈ G j ) P(i ∈ G j ) + P(i | i / ∈ G j ) P(i / ∈ G j ) = P(i) ,
and the reasons why we eliminated the random variable q j in the conditional probabilities are:

• in the case i ∈ G j (that is, j = j * ), by definition of our PIR protocol we know that q j is uniformly random, so q j and i are independent; • in the case i / ∈ G j , by definition of a transversal design, there are as many blocks containing both q j and i as there are blocks containing q j and any i in X \G j (the number of such blocks is always λ). So once again, the value of the random variable q j is not related to i.

Communication complexity. Exactly one index in [1, s] and one symbol in F q 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 S j only needs to read the symbol defined by query q j , 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 Code q (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 = Code q (T ) arising from transversal designs T = TD( , s) with few groups (small ) and large dimension k = dim Fq C compared to their length n = s.

We first give a negative result, stating that the characteristic of the field F q should be chosen very carefully in order to obtain non-trivial codes.

Proposition IV.3. Let T = (X, B, G) be a TD λ ( , s). Let q = p e , p prime. If p λs, then

Code q (T ) ⊆ {c ∈ F s q , ∀G ∈ G, c |G ∈ Rep(s)} ,
where Rep(s) represents the repetition code of length s. In particular, if p λs, then Code q (T ) has dimension at most .

Proof. For x ∈ X, recall that B x = {B ∈ B, x ∈ B}, and denote by a (x) = B∈Bx 1 B . We know that a (x) ∈ Code q (T ) ⊥ , since Code q (T ) ⊥ is generated by {1 B , B ∈ B}. Denote by G x ∈ G the only group that contains x. We see that:

     a (x) x = λs a (x) i = 0 for all i ∈ G x \ {x} a (x) j = λ for all j ∈ X \ G x .
Therefore a (x) -a (y) = λs(1 {x} -1 {y} ) if x and y lie in the same group G. If p λs, then we get

1 {x} -1 {y} ∈ Code q (T ) ⊥ . Let now C = Span Fq {1 {x} -1 {y} , ∀x, y ∈ X s.t. {x, y} ⊂ G ∈ G} We see that C ⊥ = {c ∈ F s q , ∀G ∈ G, c |G ∈ Rep(s)}.
Therefore we obtain the expected result.

In the perspective of Problem IV.2, the following section is devoted to the construction of transversal designs with high rate.

V. EXPLICIT 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 highrate 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 A m (F q ) be the affine space of dimension m over F q , and H = {H 1 , . . . , H q } be q hyperplanes that partition A m (F q ). We define a transversal design T A (m, q) as follows:

• the point set X consists in all the points in A m (F q ); • 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 H j , 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 H j , 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(T A (m, q)).

Proposition IV.3 first proves that if p does not divide λs = q, then the code Code p (T A (m, q)) has poor dimension. Since our goal is to obtain the largest codes as possible, we choose p to be, for instance, the characteristic of the field F q .

Now notice that all blocks of T A (m, q) belong to the block set of the affine geometry design AG 1 (m, q) -which is defined as the incidence structure of all points and affine lines in A m (F q ). Thus, the incidence matrix M T A (m,q) is a sub-matrix of M AG1(m,q) , which implies that Code p (AG 1 (m, q)) ⊆ Code p (T A (m, q)) for any field F p . In fact, equality holds as shows the following result. Proposition V.2. For every q = p e and m ≥ 2, we have

Code p (AG 1 (m, q)) = Code p (T A (m, q)) .
Proof. Denote by B (AG) the blocks of AG 1 (m, q), and by B (T ) and G (T ) the blocks and groups of T A (m, q). Thanks to the previous discussion, we only need to show that for every block B ∈ B (AG) contained in a group G ∈ G (T ) , it holds that 1 B ∈ Code p (T A (m, q)) ⊥ . For this sake, first notice that Code p (T A (m, q)) ⊥ = Span{1 B , B ∈ B (T ) }.

Let now G ∈ G (T ) and B ∈ B (AG) such that B ⊆ G. Recall that G is a hyperplane of A m (F q ), and let P be a 2dimensional affine plane of A m (F q ) such that P ∩ G = B. We claim that 1 P ∈ Span{1 B , B ∈ B (T ) }. Indeed, P admits a partition into affine lines which are secant to every hyperplane in G. Thus 1 P can be written as sum of the characteristic vectors of these lines. Now let x ∈ B, and B (T )

x,P := {B ∈ B (T ) , x ∈ B ⊂ P } ⊆ B (T ) . Define b (x) = B ∈B (T ) x,P 1 B . It is clear that b (x) ∈ Span{1 B , B ∈ B (T )
}, and we can notice that

     b (x) x = q = 0, b (x) i = 0 for all i ∈ B \ {x}, b (x) j = 1
for all j ∈ P \ B .

In other words, b

(x) = 1 P -1 B , therefore 1 B ∈ Span{1 B , B ∈ B (T ) }.
The benefit to consider AG 1 (m, q) is that the p-rank of its incidence matrix has been well-studied. For instance, Hamada [START_REF] Hamada | The rank of the incidence matrix of points and d-flats in finite geometries[END_REF] 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.

However, if m = 2, we know that rank p (AG 1 (2, p e )) = For fixed p and k → ∞, we have

(k) = √ k + Θ(k 1 2 +cp ) and n(k)/k = 1 1-( 1+1/p 2 ) e = 1 + Θ(k cp ) → 1 , (1)
where c p = 1 2 log p ( 1+1/p 2 ) < 0. Proof. The existence of the PIR protocol is a consequence of the previous discussion, using the family of codes Code p (T A (2, p e )). Let us state the asymptotics of the parameters. Recall we fix the prime p and we let e → ∞. First we have:

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

log p k = 2e + log p 1 - 1 + 1/p 2 e = 2e + O 1 + 1/p 2 e .
Hence,

1 + 1/p 2 e = 1 + 1/p 2 1 2 log p k+O(( 1+1/p 2 ) e ) = k 1 2 log p ( 1+1/p 2 ) × 1 + 1/p 2 O(( 1+1/p 2 ) e ) = Θ (k cp ) , since 1+1/p 2 O(( 1+1/p 2 ) e ) → 1.
Using (2) we obtain the asymptotics we claimed on n(k)/k.

For (k), we see that n(k) = (k) 2 . Therefore, we get

(k) = √ k n(k)/k = √ k 1 + Θ(k cp ) = √ k + Θ(k 1 2 +cp ) .
We give in Table I the dimension of some codes arising from affine transversal designs. Notice that m is not restricted to 2, but we focus on codes with large, since they aimed at being applied in PIR protocols.

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.

B. Transversal designs from projective geometries

The projective space P m (F q ) is defined as (A m+1 (F q ) \ {0})/ ∼ , where for (P, Q) ∈ (A m+1 (F q ) \ {0}) 2 , we have P ∼ Q if and only if there exists λ ∈ F q such that P = λQ. A projective subspace can be defined as the zero set of a ,q). 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.

m = q n = s = q m k = dim C R = k/
collection of linear forms over F m+1 q . In particular, a projective hyperplane is the zero-set of one non-zero linear form over

F m+1 q .
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 H i which intersect on a fixed subspace of co-dimension 2 (call it Π ∞ ). Then, all the sets H i \ Π ∞ are disjoint, and their union gives exactly P m (F q ) \ Π ∞ , where P m (F q ) denotes the projective space of dimension m over F q . Besides, any projective line disjoint from Π ∞ is either contained in one of the H i , or is 1-secant to all of them. It results to the following construction: Construction V.4 (Projective transversal design). Let P m (F q ) and Π ∞ defined as above. Let us define

• a point set X = P m (F q ) \ Π ∞ ; • a group set G = {projective hyperplanes H ⊂ P m (F q ), Π ∞ ⊂ H}; • a block set B = {projective lines L ⊂ P m (F q ), L ∩ Π ∞ = ∅
and ∀H ∈ G, L ⊂ H} . Finally, denote by T P (m, q) := (X, B, G).

The design T P (m, q) is a TD(q + 1, q m-1 ) and, as in the affine setting, its p-rank is related to that of PG 1 (m, q), the classical design of point-line incidences in the projective space P m (F q ). Indeed, the incidence matrix M of T P (m, q) is a submatrix of M PG1(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 T P (m, q) contains (as a subcode) the Π ∞ -shortening of the code associated to PG 1 (m, q). Hence dim Code(T P (m, q)) ≥ dim Code(PG 1 (m, q)) -|Π ∞ |. Contrary to Proposition V.2, we could not prove equality, but this is of little consequence: up to using a subcode of Code(T P (m, q)) we can consider PIR protocols on databases with k entries, where k = dim Code(PG 1 (m, q)) -|Π ∞ |.

Once again, for projective geometries Hamada's formula gets simpler for m = 2, and leads to the following proposition. Proposition V.5. Let D be a database with k = p 2e + p e -p+1 2

e -1 entries, p a prime and e ≥ 1. There exists a distributed 1-private PIR protocol for D with:

(k) = p e + 1 and n(k) = p 2e + p e .

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. Fig. 4: Rate of binary codes coming from T A (m, q) (in red) and T P (m, q) (in blue). For every fixed m, we let q grow.

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.6 (orthogonal array). Let λ, s ≥ 1 and ≥ t ≥ 1, and let A be an array with columns and λs t 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 A of A formed by t columns and all its rows, every row vector from S t appears exactly λ times in the rows of A . 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). If both these parameters are omitted we write A = OA( , s).

From now on, for convenience we restrict Definition V.6 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.7 (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 s 2 rows of A. We define the point set X = S × [1, ]. To each row c ∈ Rows(A) we associate a block

B c := {(c i , i), i ∈ [1, ]} ,
so that the block set is defined as

B := {B c , c ∈ Rows(A)} . Finally, let G := {S × {i}, i ∈ [1, ]}. Then (X, B, G) is a transversal design TD( , s).
Example V.8. 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 OA 1 (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 color. One can check that every pair of nodes either belongs to the same group or is linked with one path. Remark V.9. Listed in rows, all the codewords of a (generic) code C 0 give rise to an orthogonal array, whose strength t is derived from the dual distance d of C 0 by t = d -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 nonlinear codes (see [15, Ch.5. §5.]). More details about the link between orthogonal arrays and codes can also be found in [START_REF] Colbourn | Handbook of Combinatorial Designs[END_REF].

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 C 0 , we denote by A C0 the orthogonal array it defines (see Remark V.9) and by T C0 the transversal design built from A C0 thanks to Construction V.7.

Example V.10. Let x = (x 1 , . . . , x ) be an -tuple of pairwise distinct elements of F q and denote by RS 2 (x) the Reed-Solomon code of length and dimension 2 over F q with evaluation points x:

RS 2 (x) := {(f (x 1 ), . . . , f (x )), f ∈ F q [X], deg f < 2} .
Then, RS 2 (x) has dual distance 3, so its codewords form an orthogonal array A RS2(x) = OA( , q) of strength 2. Now, one can use Construction V.7 to obtain a transversal design T RS2(x) = TD( , q). The point set is X = F q × [1, ], and the blocks are "labeled Reed-Solomon codewords", that is, sets of the form {(c i , i), i ∈ [1, ]} with c ∈ RS 2 (x). The groups correspond to the coordinates of the code:

G i = F q × {i}, 1 ≤ i ≤ .
We can finally sum up our construction by introducing the code Code q (T C0 ) arising from the transversal design defined by C 0 . To the best of our knowledge, the construction C 0 → Code q (T C0 ) is new. We name Code q (T C0 ) the incidence code of C 0 , since its parity-check matrix M T C 0 essentially stores incidence relations between all the codewords in C 0 . Definition V.11 (incidence code). Let C 0 be a (generic) code of length over an alphabet S of size s. The incidence code of C 0 over F q , denoted IC q (C 0 ), is the F q -linear code of length n = s built from the transversal design T C0 , that is:

IC q (C 0 ) := Code(T C0 ) .
Notice that the field F q does not need to be the alphabet S of the code C 0 .

Incidence codes are introduced in order to design PIR protocols, as summarizes Figure 6. We can show that, if C 0 has dual distance more than 3, then the induced PIR protocol is Example V.12. Here we provide a full example of the construction of an incidence code. Let C 0 be the full-length Reed-Solomon code of dimension 2 over the field F 4 = {0, 1, α, α 2 = α + 1}. The orthogonal array associated to C 0 is composed by the following list of codewords:

A =                             0, 0, 0, 0 1, 1, 1, 1 α, α, α, α α 2 , α 2 , α 2 , α 2 0, 1, α, α 2 0, α, α 2 , 1 0, α 2 , 1, α 1, 0, α 2 , α 1, α 2 , α, 0 1, α, 0, α 2 α, α 2 , 0, 1 α, 0, 1, α 2 α, 1, α 2 , 0 α 2 , α, 1, 0 α 2 , 1, 0, α α 2 , 0, α, 1                            
Using Construction V.7, we get a transversal design T C0 = (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 := A 5 = (0, 1, α, α 2 ) .
We turn a into a block B a := {(0, 1), (1, 2), (α, 3), (α, 4)} ∈ B, and we build the incidence vector 1 Ba of the block B a over the point set

X = {(β, i), i ∈ [1, 4], β ∈ F 4 }.
Of course, in order to see 1 Ba 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), (1, 3), (α, 3), (α 2 , 3), [START_REF] Assmus | Designs and Their Codes[END_REF][START_REF] Beimel | Reducing the Servers' Computation in Private Information Retrieval: PIR with Preprocessing[END_REF], [START_REF] Assmus | Designs and Their Codes[END_REF][START_REF] Beimel | Reducing the Servers' Computation in Private Information Retrieval: PIR with Preprocessing[END_REF], (α, 4), (α 2 , 4) .

Using this ordering, we get:

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

By computing all the 1 Ba for a ∈ Rows(A), we obtain the incidence matrix M of the transversal design T C0 :

M =                            
1000 1000 1000 1000 0100 0100 0100 0100 0010 0010 0010 0010 0001 0001 0001 0001 1000 0100 0010 0001 1000 0010 0001 0100 1000 0001 0100 0010 0100 1000 0001 0010 0100 0001 0010 1000 0100 0010 1000 0001 0010 0001 1000 0100 0010 1000 0100 0001 0010 0100 0001 1000 0001 0010 0100 1000 0001 0100 1000 0010 0001 1000 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 columnpermutation-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 F 2 e of the prime field F 2 , the dual code of the so-called incidence code IC 2 e (C 0 ). For all values of e, the incidence codes IC 2 e (C 0 ) have the same generator matrix of 2-rank 7, being:

G =          
1001 0000 0011 1010 0101 0000 0110 0011 0011 0000 0101 0110 0000 1001 0101 1100 0000 0101 0011 0110 0000 0011 0110 0101 0000 0000 1111 1111

          .
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 C 0 -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 T C0 is the cardinality of C 0 . Hence, informally the smaller the code C 0 , the larger IC(C 0 ).

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.

Generalized Reed-Solomon codes are the best-known family of MDS codes. Definition V.13 (generalized 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 generalized Reed-Solomon (GRS) code:

GRS k (x, y) := {(y 1 f (x 1 ), . . . , y f (x )), f ∈ F q [X], deg f < k} .
Generalized Reed-Solomon codes GRS k (x, y) are linear MDS codes of dimension k over F q , and they give usual Reed-Solomon codes when y = (1, . . . , 1). Moreover, GRS codes are essentially the only MDS codes of dimension 2, as states the following lemma whose proof can be found in the Appendix.

Lemma V.14. All [ , 2, -1] MDS codes over F q with 2 ≤ ≤ q are generalized Reed-Solomon codes.

Let us study the consequences of Lemma V.14 in terms of transversal designs. We say a map φ : X → X is an isomorphism between transversal designs (X, B, G) and (X , B , G ) 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 , φ(B) = B , φ(G) = G . Lemma V.15. Let C, C be two codes such that C = y * C for some y ∈ (F × q )
, where * is the coordinate-wise product of -tuples. Recall T C , T C are the transversal designs they respectively define. Then, T C and T C are isomorphic.

Proof. Write T C = (X, B, G) and T C = (X , B , G ). From the definition it is clear that X = X = F q × [1, ] and G = G = {F q × {i}, 1 ≤ i ≤ }. Now consider the blocks sets. We see that B = {{(c i , i), 1 ≤ i ≤ }, c ∈ C} and B = {{(y i c i , i), 1 ≤ i ≤ }, c ∈ C}. Let: φ y : F q × [1, ] → F q × [1, ] (x, i) → (y i 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 by definition of C and C .

Proposition V.16. Let 2 ≤ ≤ q and C 0 be an [ , 2, -1] q linear (MDS) code. Let also F p be any finite field. The incidence code

IC p (C 0 ) is permutation-equivalent to IC p (RS 2 (x)), with x ∈ F q , x i = x j .
Proof. Lemma V.14 shows that all [ , 2, -1] q linear codes C 0 can be written as y * RS 2 (x) for some x ∈ F q . Moreover, with the previous notation φ y (T RS2(x) ) = T y * RS2(x) , so we have u ∈ IC p (y * RS 2 (x)) if and only if u ∈ Code p (φ y (T RS2(x) )). Now, let:

φy : F X p → F X p u = (u x ) x∈X → (u φy(x) ) x∈X .
Clearly φy (IC p (RS 2 (x))) = Code p (φ y (T RS2(x) )) and φy is a permutation of coordinates. So IC p (C 0 ) is permutationequivalent to IC p (RS 2 (x)) which proves the result.

In our study of incidence codes of 2-dimensional MDS codes C 0 , the previous proposition allows us to restrict our work on Reed-Solomon codes C 0 = RS 2 (x) with x an -tuple on pairwise distinct F q -elements.

A first result proves that if x contains all the elements in F q , then IC q (RS 2 (x)) is the code which has been previously studied in subsection V-A. More precisely, Proposition V.17. The following two codes are equal up to permutation:

1) C 1 = IC q (RS 2 (F q )), the incidence code over F q of the full-length Reed-Solomon code of dimension 2 over F q ; 2) C 2 , the code over F q based on the transversal design

T A (2, q).
Proof. It is sufficient to show that the transversal design defined by C 0 = RS 2 (F q ) is isomorphic to T A (2, q). Let us enumerate F q = {x 1 , . . . , x q }. We recall that T C0 = (X, B, G) where:

X = F q × [1, q], B = {{(c i , i), i ∈ [1, q]}, c ∈ C 0 }, G = {{(α, i), α ∈ F q }, i ∈ [1, q]} ,
and that T A (2, q) = (X , B , G ) with:

X = F q × F q , B = {{(ax i + b, x i ), i ∈ [1, q]}, (a, b) ∈ F 2 q } G = {{(α, x i ), α ∈ F q }, i ∈ [1, q]} .
In the light of the above, one defines φ : X → X , (α, i) → (α, x i ), which is clearly one-to-one and satisfies φ(G) = G . Moreover, a codeword c ∈ C 0 is the evaluation of a polynomial of degree ≤ 1 over F q . Hence for some (a, b) ∈ F 2 q , we have c i = ax i + b, ∀i. This proves that φ extends to a one-to-one map B → B , giving the desired isomorphism.

It remains to study the case of tuples x of length < q. First, one may notice that IC q (RS 2 (x)) is a shortening of IC q (RS 2 (F q )). Indeed, we have the following property: Lemma V.18. Let C 0 be a linear code of length over F q , and C 0 be a puncturing of C 0 on s positions. Then for all prime powers q , IC q (C 0 ) is a shortening of IC q (C 0 ) on the coordinates corresponding to s groups of the transversal design T C0 .

Proof. Without loss of generality, we can assume that C 0 is punctured on its s last coordinates in order to give C 0 . Let us analyse the link between T C0 = (X, B, G) and T C0 = (X, B, G). We have:

X = F q × [1, -s] ⊂ X, G = {F q × {i}, i ∈ [1, -s]} ⊂ G, B = {B ∩ X, B ∈ B} Let C = IC q (C 0 ) and C = IC q (C 0 ).
For clarity, we index words in C (resp. C) by X (resp. X). For c ∈ F X q , we define ext(c) := c ∈ F X q , such that c |X = c and c |X\X = 0. By definition of code's puncturing/shortening, all we need to prove is:

C = {c ∈ F X q , ext(c) ∈ C}.
Remind that C is defined as the set of c ∈ F X q satisfying b∈B c b = 0 for every B ∈ B. Hence we have:

c ∈ C ⇐⇒ b∈B c b = 0, ∀B ∈ B ⇐⇒ b∈B∩X c b = 0, ∀B ∈ B ⇐⇒ b∈B∩X ext(c) b + b∈B∩(X\X) ext(c) b = 0, ∀B ∈ B ⇐⇒ b∈B ext(c) b = 0, ∀B ∈ B ⇐⇒ ext(c) ∈ C
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 RS 2 (x) remain hard to classify for |x| = < q. Indeed, for a given length < q, some IC(RS(x)) appear to be nonequivalent. Their dimension can even be different, as shows an exhaustive search on IC 16 (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 C 0 satisfying a divisibility condition yield incidence codes whose rate is roughly greater than 1/2. Let us first define divisible codes. Definition V.19 (divisibility of a code). Let p ≥ 2. A linear code is p-divisible if p divides the Hamming weight of all its codewords.

A study of the incidence matrix which defines an incidence code leads to the following property. Lemma V.20. Let C 0 be a code of length over a set S, and let T be the transversal design associated to C 0 . We denote by M the incidence matrix of T , where rows of M are indexed by codewords from C 0 . Then we have:

(M M T ) c,c = -d(c, c ) ∀c, c ∈ C 0 ,
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 ∈ C 0 (for the row), and (α, i) ∈ S × [1, ] (for the column). We also denote by 1 U (c,i,α) ∈ {0, 1} the boolean value of the property U, that is,

1 U (c,i,α) = 1 if and only if U(c, i, α) is satisfied. Now, let c, c ∈ C 0 . (M M T ) c,c = α∈S, i∈[1, ] M [c, (α, i)]M [c , (α, i)] = α∈S, i∈[1, ] 1 ci=α 1 c i =α = i=1 α∈S 1 ci=c i =α = i=1 1 ci=c i = -d(c, c ) .
Hence, if some prime p divides as well as the weight of all the codewords in C 0 , then the product M M T vanishes over any extension of F p , and M is a parity-check matrix of a code containing its dual. A more general setting is analyzed in the following proposition.

Proposition V.21. Let C 0 be a linear code of length over S, |S| = s. Let also C = IC q (C 0 ) with char(F q ) = p. Denote the length of C by n = s. If C 0 is p-divisible, then

C ⊥ ∩ C par ⊆ C ,
where C par denotes the parity-check code of length n over F q . In particular, we get dim C ≥ n-1 2 . Moreover, if p | , then C ⊥ ⊆ C and dim C ≥ n 2 . Proof. Let M be the incidence matrix of the transversal design T C0 . Also denote by J and J the all-ones matrices of respective size |C 0 | × n and |C 0 | × |C 0 |. If we assume that C 0 is p-divisible, then Lemma V.20 translates into

M M T = J mod p (3)
while an easy computation shows that

M J T = J .
Hence, over F q we obtain

M (M -J) T = 0 (4)
which brings us to consider the code A of length n generated over F q by the matrix M -J. Equation ( 4) indicates that A ⊆ C. Let C par := {c ∈ F n q , i c i = 0} be the parity-check code of length n over F q . Notice that c ∈ C par ⇐⇒ cJ T = 0 and uJ = 0 ⇐⇒ uJ = 0. If p , this leads to:

C ⊥ ∩ C par = {c = uM ∈ F n q , cJ T = 0} = {c = uM ∈ F n q , uJ = 0} = {c = uM ∈ F n q , uJ = 0} = {u(M -J) ∈ F n q , 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 ⊥ ∩ C par ) ≥ 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.22. Let p be a prime, and assume there exists a p-divisible linear code of length 0 over F q . Then, there exists k ≥ ( 0 q -1)/2 such that we can build a distributed PIR protocol for a k-entries database over F q , 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 [START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF]ch.II.6], or the famous MDS codes of dimension 3 and length q + 2 over F q [START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF]ch.XI.6].

Example V.23. 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 Code 2 (Golay) has length n = 24 × 2 = 48 and dimension ≥ 24, and by computation we can show that this bound is tight.

Remark V.24. In our application for PIR protocols, we would like to find divisible codes C 0 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.23 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.23 represents the worst possible case for our construction, in a sense that the rate of IC 2 (Golay 2 ) 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 generalize 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 = {G 1 , . . . , G } partitioning X such that:

• |X| = s ;
• any group has size s and any block has size ;

• for any T ⊆ [1, ] with |T | = t and for any (x 1 , . . . , x t ) ∈ G T1 × . . . × G Tt , there exist exactly λ blocks B ∈ B such that {x 1 , . . . , x t } ⊂ B. A t-transversal design with parameters s, , t, λ is denoted t-TD λ ( , s), or t-TD( , s) if λ = 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 = Code q (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 λs t-1-|T | ≥ λ = 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 F q , and T = t-TD( , s) be a t-transversal design, whose incidence matrix has rank s -k over F q . 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 F 2 q , and G = {G 1 , . . . , G q } be a partition of X in q parallel lines. W.l.o.g. we choose the following partition: G i = {(y, α i ), y ∈ F q } for each α i ∈ F q . Blocks are now defined as the sets of the form

B F = {(F (x), x), x ∈ F q }, where F ∈ F q [x], deg F ≤ t-1.
Lemma VI.4. The design (X, B, G) given in Construction VI.3 forms a t-transversal design t-TD 1 (q, q). Proof. The group set indeed partitions X into q groups, each of size q. It remains to check the incidence property. Let {G T1 , . . . , G Tt } be a set of t distinct groups, and let ((y T1 , x T1 ), . . . , (y Tt , x Tt )) ∈ G T1 ו • •×G Tt . From Lagrange interpolation theorem, we know there exists a unique polynomial F ∈ F q [X] of degree ≤ t -1 such that:

F (x Tj ) = y Tj ∀1 ≤ j ≤ t .
Said differently, there is a unique block which contains the t points {(y Tj , x Tj )} 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 ttransversal 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 a i = (a i,j ) 1≤j≤ for 1 ≤ i ≤ λs t . We define the following design:

• its point set is X = S × [1, ]; • its group set is G = {S × {i}, 1 ≤ i ≤ }; • its blocks are B i = {(a i,j , j), 1 ≤ j ≤ } for all a i ∈ 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 (x 1 , . . . , x t ) ∈ G T1 × . . . × G Tt . We need to prove that there are exactly λ blocks B ∈ B such that {x 1 , . . . , x t } ⊂ B.

Consider the map from blocks in B to rows of A given by:

ψ : B → Rows(A) B i = {(a i,j , j), 1 ≤ j ≤ } → (a i,1 , . . . , a i, )
Since we assumed that orthogonal arrays have no repeated row, the map ψ is one-to-one. Denote by x = (x 1 , , . . . , x t ) ∈ S t the vector formed by the first coordinates of (x 1 , , . . . , x t ) ∈ X t . From the definition of an orthogonal array of strength t and index λ, we know that x 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 B F = {(F (x), x), x ∈ F q }, with deg F ≤ t -1 is in one-to-one correspondence with a codeword c F of a Reed-Solomon code of dimension t.

Corollary VI.8. Let C 0 be a code of length and dual distance t + 2 ≤ over a set S of size s. Then, IC q (C 0 ) defines a tprivate PIR protocol.

Proof. Let A be the orthogonal array defined by C 0 . We know that A has strength t + 1 (see e.g. [START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF]), 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, if the code C 0 is divisible, then we can give a lower bound on 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.21 then ensures their incidence codes have non-trivial rate. In Remark V.24, 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 [START_REF] Hamada | The rank of the incidence matrix of points and d-flats in finite geometries[END_REF][START_REF] Chor | Private Information Retrieval[END_REF][START_REF] Chor | Private Information Retrieval[END_REF] 3 extended ternary Golay code, that we denote Golay 3 . It is self-dual, hence d ⊥ (Golay 3 ) = 6. Then, C = IC 3 e (Golay 3 ), e ≥ 1, has length 36 and Proposition V.21 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 F 3 e -symbols encoded into 36, uses 12 servers (each storing 3 F 3 e -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 F 2 e 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.21 come from binary Reed-Muller codes of order 1, denoted RM 2 (m, 1). These codes are 2-divisible since they are known to be equivalent to extended Hamming codes. They also have length n = 2 m and dual distance d ⊥ = n/2.

For instance, RM 2 (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 F 2 e -symbols, where each server stores 2 symbols. For m = 4, RM 2 (4, 1) gives a 6-private 16server PIR protocol on a database with 20 F 2 e -symbols, each server storing 2 symbols. We conjecture that IC 2 (RM 2 (m, 1)) leads to a (2 m-1 -2)-private 2 m -server PIR protocol on a database with 2 m +m symbols, each server storing 2 symbols.

As pointed out in Subsection V-C, high-rate incidence codes C = IC(C 0 ) have the best chance to occur when the dimension of C 0 is small, since the cardinality of C 0 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 t + 2, i.e. a code C 0 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 C 0 = RS t+1 (F q ) and varying values of q and t, we were able to compute the rate of IC(C 0 ), 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.

VII. COMPARISON 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. [START_REF] Augot | A Storage-Efficient and Robust Private Information Retrieval Scheme Allowing Few Servers[END_REF] and all the works involving the use of PIR codes initiated by Fazeli et al [START_REF] Fazeli | Codes for Distributed PIR with Low Storage Overhead[END_REF]. 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 [START_REF] Augot | A Storage-Efficient and Robust Private Information Retrieval Scheme Allowing Few Servers[END_REF].

Sketch of the construction [START_REF] Augot | A Storage-Efficient and Robust Private Information Retrieval Scheme Allowing Few Servers[END_REF]. Multiplicity codes C have the property that a codeword c ∈ C can be seen as the vector of evaluations of a multivariate polynomial f c ∈ F q [X 1 , . . . , X m ] and its derivatives over the space F m q , where F q denotes the finite field with q elements. Every affine line of the space F m q then induces linear relations between f c and its derivatives, which translates into low-weight parity-check equations for the codewords. This allows to define a local decoder for C: when trying to retrieve a symbol D i indexed by i ∈ F m q , Rate R = k/n t = 1 t = 2 t = 4 t = log(q) t = √ q t = q/8 t = q/3 t = q -1 Fig. 7: Rate of incidence codes of C 0 that are used for building t-private PIR protocols. Codes C 0 are fulllength Reed-Solomon codes of dimension t + 1 (dual distance t + 2) over F q . Associated PIR protocols then need q servers, each storing q symbols. one can pick random affine lines going through i and recover D i by computing short linear combinations of the symbols associated to the evaluations of f c and their derivatives along these lines. We refer to [START_REF] Kopparty | High-Rate Codes with Sublinear-Time Decoding[END_REF] for more details on these codes.

Augot et al. [START_REF] Augot | A Storage-Efficient and Robust Private Information Retrieval Scheme Allowing Few Servers[END_REF] realized that partitioning F m 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, they obtained a huge cut 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 [START_REF] Augot | A Storage-Efficient and Robust Private Information Retrieval Scheme Allowing Few Servers[END_REF] 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 collusionfree setting, d = s(q -1) -1 is the optimal choice. Let σ = m+s-1 m . The associated PIR protocol uses q servers to store an original database containing d+m m F q -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: ρ = σq ms(q -1) + m -1 m log q .

Concerning the communication complexity, let us only focus on the download cost (which is often the bottleneck in practice). The multiplicity code local decoding algorithm needs to query symbols of σ distinct lines of the space. Hence, each server must answer σ symbols of size σ 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.

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).

Remark VII.1. Recent constructions of PIR protocols (for instance results of Sun and Jafar such that [START_REF] Sun | The Capacity of Private Information Retrieval[END_REF]) 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. CONCLUSION

In this work, we have presented a generic construction of codes yielding distributed PIR protocols with optimal server computational complexity, in a sense that each server only has to read one symbol of the part of the database it stores. Our construction makes use of transversal designs, whose incidence properties ensure a natural distribution of the coded database on the servers, as well as the privacy of the queries. Our PIR protocols also feature efficient reconstructing steps since the user has to compute a simple linear combination of the symbols it receives. Finally, they 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 a better resilience to collusions.

The generality of our construction allows the user to choose appropriate settings according to the context (low storage capability, few colluding servers, etc.). It also raises 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 needed servers.

  presents a distributed PIR protocol based on C. 1) Initialization step. User U encodes D into a codeword c ∈ C. Each server S 1 , . . . , , S holds a copy of c . In the formalism of Definition II.2, it means that c (j) := c , for j = 1, . . . , . 2) Retrieving step for symbol D i . Denote by D a local decoding algorithm for C.

p+1 2 e 2 e

 22 , which implies that dim(Code p (T A (2, p e ))) = p 2e -p+1 2 e . Hence we obtain the following family of PIR protocols. Proposition V.3. Let D be a database with k = p 2e -p+1 entries, p a prime, e ≥ 1. There exists a distributed 1-private PIR protocol for D with: (k) = p e and n(k) = p 2e .

Fig. 5 :

 5 Fig. 5: A representation of the construction of a transversal design from an orthogonal array.

Fig. 6 :

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

TABLE I :

 I Dimension and rate of binary codes C arising from T A (m

  1private. A generalisation is formally proved in Corollary VI.8.

	Base code C 0 O O
	equivalence (Rem. V.9)
	Orthogonal array
	Construction V.7 [8, ch.II.2]
	Transversal design
	incidence matrix
	Incidence code of C 0
	database encoding
	Distributed PIR scheme

algorithm A := A j may depend on j

ACKNOWLEDGMENTS

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.

This work is partially funded by French ANR-15-CE39-0013-01 "Manta".

Hamada [START_REF] Hamada | The rank of the incidence matrix of points and d-flats in finite geometries[END_REF] gives a generic formula to compute the p-rank of a projective geometry design PG t (m, q), for q = p e :

where S ⊂ Z e+1 contains elements (s 0 , . . . , s e ) such that:

, and L(s j+1 , s j ) = sj+1p-sj p . The p-rank of the associated affine geometry design AG t (m, q) can be derived from the projective one by:

Despite its heavy expression, Hamada's formula can be simplified by picking very specific values of m, p or e. For instance we have: , this equality being found by interpolation, since rank p (AG 1 (m, p e )) is a polynomial of degree at most me in p.

B. Proof of Lemma V.14

Let us recall the result we want to state.

Lemma. All [ , 2, -1] MDS codes over F q with 2 ≤ ≤ q are generalized 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 = (P 1 , . . . , P ) be a generator matrix of C, where P i ∈ F 2 q is written in column. Notice that each point P i is non-zero (otherwise d ⊥ = 1) and 0, P i , P j are not on the same line for i = j (otherwise d ⊥ = 2). Moreover codewords in C are simply evaluations of bilinear maps µ : F 2 q → F q over (P 1 , . . . , P ):

q , F q )} , and the P i 's are not all on the same line (otherwise, dim C ≤ 1).

Since ≤ q, there exists Q = (Q 0 , Q 1 ) ∈ F 2 q \ {0} such that Q does not lie in the (vector) line defined by any of the P i 's. Let now µ Q (X, Y ) = Q 1 X -Q 0 Y : it is a nonzero bilinear form which must vanish on a line of F 2 q , and since µ Q (Q) = 0, it vanishes on the one spanned by Q. To sum up, for every i ∈