J M Dutertre
email: dutertre@emse.fr

R Possamai Bastos

O Potin

M L Flottes

B Rouzeyre

G Di Natale

A Sarafianos

Improving the ability of Bulk Built-In Current Sensors to detect Single Event Effects by using triple-well CMOS

Bulk Built-In Current Sensors (bbicss) were introduced to detect the anomalous transient currents induced in the bulk of integrated circuits when hit by ionizing particles. To date, the experimental testing of only one bbics architecture was reported in the scientific bibliography. It reports an unexpected weakness in its ability to monitor nmos transistors. Based on experimental measures, we propose an explanation of this weakness and also the use of triple-well cmos to offset it. Further, we introduce a new bbics architecture well suited for triple-well that offers high detection sensitivity and low area overhead.

Improving the ability of bulk built-in current sensors to detect Single Event Effects by using triple-well CMOS J.M. Dutertre a, * , R. Possamai Bastos b , O. Potin a , M.L. Flottes c , B. Rouzeyre c , G. Di Natale c , A. Sarafianos d

Introduction

Bulk Built-In Current Sensors (bbicss) [START_REF] Neto | Using bulk built-in current sensors to detect soft errors[END_REF] were introduced to monitor the currents induced in the bulk of integrated circuits (ics) by ionizing particle hits. Such currents may create transient errors into the circuit's calculations. bbicss are used to detect unusual bulk currents and to possibly trig recovery mechanisms to maintain the circuit's functionality. This paper is organized as follows: Section 2 describes the principles underlying bbicss. It also introduces the architecture of the only bbics that was, to date, experimentally tested. Its weaknesses, revealed during the testing of the test chip, are discussed. These weaknesses are explained in section 3, on the basis of measurements of the bulk currents induced by a laser into the pn junctions found in cmos circuits. In section 4, we propose the use of triple-well cmos to obtain an improved detection capability. A new bbics design well suited for triple-well cmos is also introduced. Then, section 5 draws a conclusion.

State-of-the-art

ics are known to suffer from Single Event Effects (sees) caused by ionizing particles in radioactive environments. In the following subsections we review the electrical phenomenon underlying sees and the principles of their detection by using bbics. We also describe the architecture of the nmos-bbics designed by Zhang et al. [START_REF] Zhang | A new bulk built-in current sensing circuit for single-event transient detection[END_REF] and the weakness revealed during its experimental testing with a laser [START_REF] Zhang | A bulk built-in voltage sensor to detect physical location of singleevent transients[END_REF].

Single Event Effects and related detection through bulk-current monitoring

When an ionic particle passes through silicon it generates electron-hole pairs along its path. These electrical charges generally recombine without any significant effect. However, the electron-hole pairs may be separated by the electric field found in a pn junction, thus creating a transient current. This phenomenon is generally introduced by studying the inverter case, see Fig. 1 as an illustration when the inverter's input is low (i.e. in = 0 and out = 1). In this configuration, the see sensitive part is the drain of the nmos transistor, which is in OFF state (note that the pmos drain is the sensitive part when the input is high: the sensitive part location is data dependent). The generated transient current, depicted by a current source in Fig. 1, flows through the pn junction existing between the N-type drain of the nmos and the P-type substrate which is grounded. This current has two components: one passing through the pmos transistor (in ON state), another discharging the output capacitance of the inverter (pictured in dotted lines). As a result of the latter, the inverter's output undergoes a transient alteration from 1 to 0. This voltage transient, also known as set (or single event transient), may thus propagate through the circuit logic creating soft errors. Furthermore, whether a set is induced directly in a memory element, the stored data may be flipped characterizing the so-called seu (or single event upset, i.e. a soft error). A significant property of the transient current induced by an ionic particle is that it flows through the bulk of the struck sensitive transistor. bbicss are designed to take advantage of this property: they monitor these bulk currents, hence they are able to detect unusual currents and, consequently, the advent of sees. Fig. 2 depicts the insertion of a bbics between the bulk (the P-type substrate) of an nmos transistor and the ground supply. The biasing of the P-substrate (node NMOS bulk) is provided by the bbics. Hence, as illustrated, any see induced current necessarily flows through the bbics. The bbics pur-pose is then to raise a warning flag indicating that the circuit's function may be affected. In Fig. 2, the bbics used to monitor nmos transistors is named a nbbics. There also exists pbbics dedicated to the monitoring of pmos transistors. Even if pbbics and nbbics have different architectures they rely on the same principle, i.e. the monitoring of bulk currents.

Zhang et al. bbics architecture

Among various bbics architecture proposals [START_REF] Neto | Tbulk-bics: A built-in current sensor robust to process and temperature variations for soft error detection[END_REF][START_REF] Simionovski | Simulation evaluation of an implemented set of complementary bulk built-in current sensors with dynamic storage cell[END_REF], only one [START_REF] Zhang | A new bulk built-in current sensing circuit for single-event transient detection[END_REF] was experimentally tested [START_REF] Zhang | A bulk built-in voltage sensor to detect physical location of singleevent transients[END_REF]. The authors designed both nmos-and pmos-bvis to monitor nmos and pmos. For the sake of brevity, we only report in Fig. 3 the architecture of their nmos-bvis (Built-In Voltage Sensor according to the authors' denomination). The core part of this nmos-bvis is a memory latch made of two cross-coupled inverters. In normal operating conditions, node outn is at low level while node outn bar is high. Node outn goes high to indicate the detection of any see induced bulk current. The bbics connection to the P-substrate of the monitored transistors (node NMOS bulk in Fig. 2) is used as a bias contact to Gnd through the ON transistors T2. When a particle hits a monitored sensitive area, the induced current (pictured in red) flows through the related pn junction into the input of the nmos-bivs: node NMOS bulk in Fig. 3. A part of this current flows to ground through T2, another part charges the gate capacitances of transistors T1 and T3. As a result, node NMOS bulk's voltage rises, hence T1 and T3 pass from OFF to ON state making the core latch flip. Node outn goes high indicating an see current detection. As the transient current ceases, node NMOS bulk returns to ground thanks to the always ON T2 transistor. Transistor Tr is used to reset the bbics in its initial condition.

A key point in designing a bbics is to obtain a detection threshold lower than the level of appearance of sees (the sensitivity threshold).

Experimental testing of the nmos-and pmosbivs

The nmos-and pmos-bvis were tested experimentally, the test was performed on a test chip (cmos 90nm) with a laser source to emulate the effect of an ionizing particle. The authors report the use of a one picosecond laser source at a 800nm wavelength [START_REF] Zhang | A bulk built-in voltage sensor to detect physical location of singleevent transients[END_REF]. The spot size was 1.6µm and the energy varied over a few hundreds pJ range. Their test chip embeds a multiplier as test element which is monitored by various nmos-and pmos-bivs. The multiplier sensitivity threshold against laser illumination was found at a laser energy of 82pJ. The detection threshold of a bbics increases with the number of standard cells it monitors. To evaluate this effect, different bivs were connected to 10, 20, 40, 80, or 160 cells biasing contacts. Table 1 reports the obtained detection thresholds.

Table 1: Detection threshold of the nmos-and pmos-bivs expressed as the minimal detected laser energy (pJ) given for various numbers of monitoring contacts (n.d. stands for 'not detected') extract from [START_REF] Zhang | A bulk built-in voltage sensor to detect physical location of singleevent transients[END_REF]. pmos-bivs detection threshold was found to be lower than the multiplier sensitivity threshold (82pJ) when monitoring up to 80 biasing contacts. However, even when monitoring only 10 biasing contacts, the nmos-bivs detection threshold (110pJ) was found higher than the multiplier sensitivity threshold (82pJ).

As a conclusion, nmos-bivs were found unable to detect all see occurrences on experimental basis. This result was unexpected because its relevance was previously ascertained on simulation basis [START_REF] Zhang | A new bulk built-in current sensing circuit for single-event transient detection[END_REF][START_REF] Zhang | A bulk built-in voltage sensor to detect physical location of singleevent transients[END_REF].

Analysis

Experimental measures

For the purpose of analyzing the weakness of the nmos-bivs, we performed a set of experiments on a test chip we designed to measure the currents involved in see generation. These measures were carried out on nmos and pmos transistors both for bulk and triple-well cmos 90nm technology. We used an infrared laser source (1064nm) applied through the test chip backside to induce the transient currents. Current measurements and biasing of the test elements were done with probes. Due to measurement constraints, we used 20µs laser pulses at 1.25W with a spot size of 5µm. These laser settings are not consistent with the emulation of an ionizing particle strike. However, we were more interested in comparing the magnitude of the currents induced in the various pn junctions of transistors than in precisely emulating an see.

nmos current: the sensitive part of an nmos transistor is the Psub-N + junction of his drain when it is reverse biased. We measured a 2.5mA current flowing from the drain (biased at 1.2V) into the P-substrate biasing contact (grounded) as depicted in Fig. 4. The other electrodes of the transistor were left floating. pmos currents: the sensitive part of a pmos transistor is the P + -Nwell junction of his drain when it is reverse biased. The laser path to this junction also crosses the Psubstrate-Nwell junction (it is similar when hit by an ionizing particle). We performed a first measure letting unbiased the Psubstrate (see top part of Fig. 5). We measured a 1.9mA current flowing from the Nwell biasing contact (biased at 1.2V) into the drain (grounded). Then, we performed a second measure with the Psubstrate grounded, which is the proper biasing in normal operation of a chip (see bottom part of Fig. 5). We measured only a 200µA current flowing through the P + -Nwell junction whereas we measured a 8mA current flowing through the Psubstrate-Nwell junction.

nmos-bvis weakness analysis

Current measurements on a pmos showed that the induced current had two components: one of 8mA flowing through the Psubstrate-Nwell junction, one of 200µA flowing through the P + -Nwell junction. set are induced by the second one, while the first one may be monitored by a pmos-bbics. This explains why the pmos-bvis had a detection threshold lower than the multiplier sensitivity threshold: there is more than an order of magnitude between the two related current components. This is different for a nmos: there is only one current component flowing both through its sensitive drain and through its bulk biasing contact. Moreover, if an nmos-bvis is connected to this contact it will not collect the whole current because there are other current return paths to the ground on-chip (for the pmos case the only current path is through the Nwell biasing contact). As a result, the weakness of the nmos-bivs has two causes: (a) it collects an see induced current lower than that collected by a pmosbivs, and (b) the current it collects is lower than the current generating the see.

Improving BBICS efficiency

Use of triple-well cmos

Modern cmos technologies generally offer a triplewell option. It consists in embedding the nmos transistors into P-type well (or Pwell) isolated from the Psubstrate. The Pwell containment is made laterally with Nwell implants and with a deep Nwell implant underneath. The deep Nwell and Nwell are electrically connected, both normally biased at 1.2V. Our assumption was that an nmos in an isolated Pwell will have a similar behavior regarding the see currents as a pmos. For validation purposes, we performed the same measurements on a triple-well nmos as those done on bulk cmos transistors (with the same laser settings as reported in 3.1). First we let the deep Nwell unbiased, second we biased it at 1.2V (see respectively the top and bottom parts of Fig. 6). With a floating deep Nwell, a 2.3mA current flowed through the nmos drain Pwell-N + junction. With the deep Nwell biased at 1.2V, the nmos drain junction current diminished to 200µA, whereas a 6mA current flowed through the Pwell-deep Nwell junction. These figures are similar to those of the pmos. Using triple-well cmos creates more than an order of magnitude difference between the lower current contributing to see generation and the higher current potentially monitored by a bbics. On basis of these experiments we recommend the use of triple-well cmos to obtain an optimal use of bbics.

Single bbics architecture

Description: we also developed a new bbics architecture well suited for the monitoring of triple-well cmos logic: the 'single bbics' pictured in Fig. 7. It is designed to monitor simultaneously nmos and pmos (which are respectively enclosed in Pwells and Nwells): its NMOS bulk and PMOS bulk inputs are respectively connected to the Pwell and Nwell biasing contacts. The core part of the single bbics is a latch made of two cross-coupled inverters. In monitoring state, node out is at low level while node outb is high. Node out goes high to indicate the detection of any see induced bulk current. The bbics connection to the Pwell (resp. Nwell) of the monitored nmos (resp. pmos) (node NMOS bulk, resp. node PMOS bulk) is used as a bias contact to Gnd (resp. to Vdd) through the ON transistor Mn4 (resp. Mp4). When a particle hits a monitored sensitive area, the induced current (pictured in red) flows through the related pn junction into (resp. from) the corresponding input of the single bbics. A part of this current charges (resp. discharges) the gate capacitance of transistor Mn3 (resp. Mp3): node NMOS bulk's (resp. PMOS bulk's) voltage rises (resp. decreases), hence Mn3 (resp. Mp3) passes from OFF to ON state, making the core latch flip. Node out goes high indicating an see detection. Transistors Mn reset and Mp reset are used to reset the bbics in its monitoring state. Transistors Mn t and Mp t are used to ease the flipping of the core latch from the monitoring state to the alarm state. This flipping ability was also reinforced by using low and high voltage threshold transistors (denoted LVT and HVT in Fig. 7), as explained in [START_REF] Dutertre | Sensitivity tuning of a bulk built-in current sensor for optimal transient-fault detection[END_REF].

This architecture brings together the nmos and pmos monitoring ability of nmos-bvis and pmosbivs. Hence the area overhead is reduced from 16 transistors (8 + 8) to 14 transistors.

Validation on the basis of simulation: a test chip designed in a cmos 65 nm process that embeds single bbicss and various test structures is expected by the 2nd quarter of this year. We report in the following an evaluation, on the basis of simulation, of its very good efficiency to detect the advent of sees in triple-well cmos. The electrical simulation results we report were conducted after parasitic resistances and capacitances extraction with a standard CAD tool (substrate resistances were not considered). For the purpose of comparison, we first defined the see sensitivity threshold of the cmos 65 nm process we used. We expressed it as the magnitude (in µA) of the see induced transient current pulse sufficient to give rise to the propagation of an set along a chain of inverters. To obtain the lowest value of this sensitivity threshold, we used the smallest inverters among the standard cells. Note that the sensitivity threshold grows with the number of inverters. The next step was to obtain the detection threshold (i.e. the transient current magnitude sufficient to trigger an alarm) of the single bbics when connected to the same chain of 80 inverters. The transient current magnitude was progressively decreased (the pulse timings were left unchanged) until reaching the least magnitude sufficient to trigger the alarm: 82µA. Fig. 9 reports the signals of interest: the transient current, the voltage of nodes NMOS bulk and PMOS bulk, the flag signal, the outputs of the 2nd and 80th inverters. In response to the transient current, the flag went to high level indicating the advent of an see induced transient current. This current was too weak to induce an set.

We ran simulations for both bulk and triple-well cmos. The obtained results are given in table 2 (transient currents for both nmos and pmos sets were simulated at the nmos or pmos drain of the 2 nd inverter of the chain). Regarding bulk cmos, as suggested in section 3, for a chain of inverters length above 120 inverters the sensitivity threshold for nmos is lower than the detection threshold (underlined in bold in table 2): a set may be induced without being detected. Whereas, the sensitivity threshold for pmos remains higher than the detection threshold (we did not conducted simulations over 200 inverters): any set would be detected. Regarding triple-well cmos, the results of table 2 should be considered with care to avoid minimizing its efficiency. Indeed, as illustrated respectively in the bottom parts of Fig. 5 and6, the see induced currents flowing through the drain of the struck transistor is smaller than the total current flowing through the biasing contact of the transistor's well. Hence, the detection threshold is expressed as the transient current flowing through a Pwell or Nwell biasing contact, and the set sensitivity threshold is expressed as the transient current flowing through the nmos or pmos drain. As a result, considering the nmos set sensitivity threshold for a 200 inverters long chain, the related 100µA current will only be a part of a much bigger current flowing through the nmos' biasing contact into node NMOS bulk: the latter will outpace the 212 µA detection threshold.

Thus, the use of triple-well cmos appears to solve the weakness of nmos-bivs [START_REF] Zhang | A bulk built-in voltage sensor to detect physical location of singleevent transients[END_REF] in detecting sees. Moreover, given the area of the single bbics (22.6 µm 2 ) and that of a sub-chain of 10 inverters in triple-well (21.15 µm 2 , 19.8 µm 2 for bulk cmos), the area overhead for a 200 inverters chain is 5.4%.

Conclusion

Based on experiments, we explained the unexpected weakness of bbics in monitoring see induced in nmos transistors for bulk cmos processes. Consequently, we suggest using triple-well cmos to offset this weakness. Indeed, the enclosure of nmos into isolated Pwells allowed bbics to monitor an induced current that is an order of magnitude greater than the current contributing to the occurrence of an see. Moreover, the whole current will pass through the monitoring bbics because there is no other return path to Gnd or Vdd. By using triple-well, the efficiency of nmos-bbics will be similar to that of pmosbbics. Moreover, we introduced a new single bbics architecture that brings together the nmos and pmos monitoring ability. It is well adapted to triple-well cmos and reduces the area overhead.

Figure 1 :

 1 Figure 1: Single event transient mechanism: the inverter case.

Figure 2 :

 2 Figure 2: nmos sensitivity monitoring with an nbbics.

Figure 3 :

 3 Figure 3: Architecture of the nmos-bivs.

Figure 4 :

 4 Figure 4: View of the laser induced current in the Psub-N + junction of an nmos.

Figure 5 :

 5 Figure 5: View of the laser induced currents in the P + -Nwell and Psub-Nwell junctions of a pmos: P-substrate unbiased (top), P-substrate grounded (bottom).

Figure 6 :

 6 Figure 6: View of the laser induced currents in the Pwell-N + and Pwell-Nwell junctions of a triple-well nmos: deep Nwell unbiased (top), deep Nwell biased at 1.2V (bottom).

Figure 7 :

 7 Figure 7: Architecture of the single bbics.

Figure 8 :

 8 Figure 8: set generation and propagation -80 inverters chain, 104µA transient current magnitude (nmos).

Fig. 8

 8 reports the appearance of a set caused by a transient current which magnitude is 104µA. The timings (∼ 50 ps and ∼ 150 ps rise and fall times, respectively) of the transient current we used in simulations are those reported in[START_REF] Hubert | Single-event transient modeling in a 65-nm bulk cmos technology based on multi-physical approach and electrical simulations[END_REF]. The transient current was simulated between the nmos' drain of the 2nd inverter (node inv2) and the ground as illustrated in fig.1. It prop-agated through the third and fourth inverters (nodes inv3 and inv4) and the following ones to the output node inv80. Sensitivity thresholds obtained from simulation for transient current induced in nmos or pmos transistors and for various length of inverters chains are reported in table2

  .

Figure 9 :

 9 Figure 9: Single bbics' alarm flag trigerring -80 inverters chain, 82µA transient current magnitude (nmos).

Table 2 :

 2 set thresholds and single bbics detection thresholds for bulk and triple-well cmos as a function of the inverters chain lengthset nmos/pmos gives the sensitivity threshold (in µA) for a nmos/pmos transient current, bbics detection gives the corresponding detection threshold (in µA) of the single bbics.

	set and detection thresholds (µA), cmos-bulk
	# of inverters	40	80 120 150 200
	set nmos	102 104 104 104 104
	bbics detection 56	82 107 125 155
	set pmos	126 131 134 135 137
	bbics detection 45	67	90	107 134
	set and detection thresholds (µA), triple-well
	# of inverters	40	80 120 150 200
	set nmos	94	95	98	99 100
	bbics detection 75 112 147 173 212
	set pmos	118 125 127 127 130
	bbics detection 84 125 163 191 237


Daniel Augot

Françoise Levy-Dit-Vehel

Abdullatif Shikfa

A Storage-efficient and Robust Private Information Retrieval Scheme allowing few servers

. Our main contributions are on the one hand to avoid full replication of the database on each server; this significantly reduces the global redundancy. On the other hand, to have a much lower locality in the PIR context than in the LDC context. This shows that there exists two different notions: LDC-locality and PIR-locality. This is made possible by exploiting geometric properties of multiplicity codes.

Introduction

Private information retrieval allows a user to privately retrieve a record of a database, in the sense that the database server does not know which record the user is asking for. The applications of this functionality are numerous. Imagine for instance doctors having to query a company-wide database storing medical for patients, or a police officer wanting to request financial data from the fiscal administration. In both cases, to respect privacy of the patient, or secrecy of the inquiry, it is desirable that the central administration does not know about the queries sent by these users (the doctor or the police officer). A private information retrieval protocol will allow these users to send their queries to the databases, without revealing what they are asking for (either the name of patient, or the name of the suspect under inquiry). Another example is an Internet user who wants to use cloud-based remote storage services, like DropBox, GoogleDrive, CloudMe, hubiC, etc, to store data, and retrieve portion of its data without revealing to these remote services anything about what he is after.

Related work.

The problem of Private Information retrieval (PIR) was introduced in 1995 by Chor, Goldreich, Kushilevitz and Sudan [START_REF] Chor | Private information retrieval[END_REF]. A PIR protocol is a cryptographic protocol the purpose of which is to protect the privacy of a user accessing a public database via a server, in the sense that it makes it possible for a user to query a particular record of the database without revealing to the server which record he wants to retrieve. We here deal with information theoretic PIR, as opposed to computationally secure PIR [START_REF] Kushilevitz | Replication is not needed: single database, computationally-private information retrieval[END_REF]. In an information theoretic PIR setting, a server gets no information about the identity of the record of user interest even if it has unlimited computing power: the queries sent to the server must not be correlated to the actual record the user is looking for. In [START_REF] Chor | Private information retrieval[END_REF] it is shown that when accessing a database located on a single server, to completely guarantee the privacy of the user in an information theoretic sense, one needs to download the entire database, which results in a communication complexity of O(N ), N being the bit-size of the database. Thus scenarios have been introduced where the database is replicated across several, say ℓ, servers, and the proposed schemes have communication complexity O(N 1/ℓ ), for ℓ ≥ 3. Such multiple-server settings have been investigated since then, and the best communication complexity to date is N O(1/(log 2 log 2 N )) for 3-server PIR protocols (from matching vector codes construction [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]) and N O((log 2 log 2 ℓ)/ℓ log 2 ℓ) for ℓ ≥ 3 [START_REF] Beimel | Breaking the n 1/(2k-1) barrier for information-theoretic private information retrieval[END_REF] .

Beimel and Stahl [START_REF] Beimel | Robust information-theoretic private information retrieval[END_REF][START_REF] Beimel | Robust information-theoretic private information retrieval[END_REF] have proposed several robust information theoretic PIR protocols, based on polynomial interpolation, as well as on Shamir's secret sharing scheme. They have built a generic transformation from regular to robust PIR protocols that relies on perfect hash families. They also addressed the Byzantine setting. Recently, Devet, Goldberg and Heninger [START_REF] Devet | Optimally robust private information retrieval[END_REF] proposed an Information-Theoretic PIR tolerating the maximum possible number of Byzantine servers. In all these previous proposals, the (encoded or not) database is fully replicated among the servers.

Our contribution. Our main concern is to reduce the global storage overhead. We achieve this by avoiding full replication of the database among the servers. We use multiplicity codes and exploit the geometry of F m q to partition the encoded database (codeword) of bit-size N into q shares of equal size, and distribute them among the servers (one share for one server). This way, we reduce the storage on each server from N bits down to N/q bits, q being the number of servers, while totally preserving the information theoretic security of the PIR protocol. Here N = log 2 (q σq m ) = σq m log 2 q, with σ = m+s-1 m , and s is an auxiliary small integer (say s ≤ 6) used in the construction of multiplicity codes. Given that the code has rate R, the storage overhead of our scheme is thus 1 R instead of 1 R ℓ for schemes with full replication of the encoded database (as in the standard LDC to PIR reduction), ℓ being the number of servers (ℓ = q in our scheme). The number of servers is also drastically reduced, from σ(q -1) to q, see Fig 3.

The communication complexity in bits (total number of bits sent by the user to all the servers as queries of our protocol) is (m -1)qσ log 2 q, and the total number of bits answered by the servers is qσ 2 log 2 q. Thus the communication complexity is (m -1 + σ)qσ log 2 q bits. Putting ℓ = q the number of servers, and in contexts where s is small, say s ≤ 6, this gives a communication complexity of O(ℓ(log 2 N ) s ).

Our protocol tolerates ν = ⌊t⌋ byzantine servers, t = 1/2(q -1-d/s), d being the degree of the multiplicity code, in the sense that even if ν out of q servers always answer wrongly, then the database item can still be correctly recovered by the user. Thus our protocol is a ν-Byzantine robust PIR protocol. The property of being robust is a built-in feature of the decoding algorithms that are involved in the process of retrieving the database item.

Organization of the paper. In section 2 we recall the basics of locally decodable and self-correctable codes, private information retrieval schemes, and the link between the two notions; we also set the necessary material and notation to define multiplicity codes, namely Hasse derivatives. Section 3 describes the multiplicity codes [START_REF] Kopparty | High-rate codes with sublinear-time decoding[END_REF] as a generalization of Reed Muller codes, and explains their local decoding. Section 4 contains our main ideas: we explain how we use multiplicity codes in a PIR scenario in such a way as to avoid full replication of the encoded database. We also explain how we achieve the Byzantine robustness property of our protocol. We end the paper by numerical tables showing the main features of the codes (rate, locality) for various parameter sizes.

Preliminaries

Locally decodable and locally self-correctable codes

A code in the ambient space is seen as an encoding map, which encodes a message of k symbols on an alphabet ∆ into code-vectors, or codewords of n symbols on some alphabet Σ (possibly different from ∆). That is, it is a one-to-one map C : ∆ k → Σ n . The decoding problem is to find codewords close enough to any element y in the ambient space (the "received word" in coding theory language). Formally, given a distance d(), code C ⊂ Σ n , for a given y = (y 1 , . . . , y n ) ∈ Σ n , one has to find one, some, or all codewords c ∈ C such that d(c, y) is small. In our setting, the distance d(x, y) is the Hamming distance which is the number of indices i where x i = y i . A major concern is to build codes with small redundancy, or equivalently, large rate, where the rate is (k log |∆|)/(n log |Σ|). In classical settings, ∆ = Σ, and the rate is simply k/n.

Locally decodable codes, in short LDCs, allow efficient sublinear time decoding. More precisely, an ℓ-query LDC allows to probabilistically recover any symbol of a message by looking at only ℓ ≤ k randomly chosen coordinates of its -possibly corrupted -encoding. The major objective is to have ℓ ≪ k. Although LDCs appeared in the PCP literature in early 90's [START_REF] Yekhanin | Locally Decodable Codes and Private Information Retrieval Schemes[END_REF], their first formal definition is due to Katz and Trevisan in 2000 [START_REF] Katz | On the efficiency of local decoding procedures for error-correcting codes[END_REF]. The number ℓ of queried symbols is the query complexity, that we also call here locality. Formally:

Definition 1. A code C : ∆ k → Σ n is (ℓ, δ)-
(i) = x i ] ≥ 2 3 , 2.
A makes at most ℓ queries to y.

Here, and in the following, A y means that A is given query access to y, and the probability is taken over all internal random coin tosses of A. In the case when one wants to probabilistically recover any codeword symbol and not only information symbols, one has the following definition.

Definition 2. A code C : ∆ k → Σ n is (ℓ, δ)-
(i) = c i ] ≥ 2 3 , 2.
A makes at most ℓ queries to y.

When ∆ = Σ = F q , the finite field with q elements, and when the code is F qlinear, one can easily construct an LDC from a LCC [START_REF] Yekhanin | of Foundations and Trends in Theoretical Computer Science[END_REF]. No known constructions of LDCs or LCCs minimize both ℓ and the length n simultaneously. The oldest class of LDCs are the Reed-Muller codes over F q , whose codewords are the evaluations of m-variate polynomials of total degree at most d over F q on all the points of F m q . The main issues are thus to minimize one parameter given that the other one is fixed. With this respect, constructions of subexponential length codes with constant query complexity ℓ ≥ 3 exist [START_REF] Yekhanin | Locally Decodable Codes and Private Information Retrieval Schemes[END_REF]. On the other side, constant rate LDCs feature an ℓ which is known to lie between Ω(log 2 k) and Θ(k ǫ ), with explicit constructions for the latter bound. A major result is the construction of high-rate (i.e. > 1/2) locally self-correctable codes with sublinear query complexity, in the presence of a constant (as a function of the distance of the code) fraction of errors. Those codes are known as Multiplicity Codes and were introduced by Kopparty, Saraf and Yekhanin in 2011 [START_REF] Kopparty | High-rate codes with sublinear-time decoding[END_REF]. They generalize the Reed-Muller codes by evaluating high degree multivariate polynomials as well as their partial derivatives up to some order s. Using high-degree polynomials improves on the rate, while evaluating their partial derivatives compensates for the loss in distance. Other LDC constructions achieving rate > 1/2 and query complexity n ǫ are the one of Guo et al. [START_REF] Guo | New affine-invariant codes from lifting[END_REF] based on lifting affine-invariant codes (namely, Reed-Solomon codes), and the Expander codes of Hemenway et al. [START_REF] Hemenway | Local correctability of expander codes[END_REF].

In this work, we use Multiplicity codes, but recall Reed-Muller codes and their local decoding for the sake of comprehension. These codes provide the simplest geometric setting for partitioning a codeword and laying it out on servers. We think such a partition can be done for other families of LDC codes, e.g. matchingvector codes, affine invariant codes and possibly Expander codes.

Private information retrieval schemes

We model the database as a string x of length k over ∆. An ℓ-server PIR scheme involves ℓ servers S 1 , . . . , S ℓ , each holding the same database x, and a user who knows k and wants to retrieve some value x i , i ∈ [k], without revealing any information about i to the servers.

Definition 3 (Private Information Retrieval (PIR)

). An ℓ-server p-PIR protocol is a triple (Q, A, R) of algorithms running as follows:

1. User obtains a random string s; then he invokes Q to generate an ℓ-tuple of queries (q 1 , . . . , q ℓ ) = Q(i, s). 2. For 1 ≤ j ≤ ℓ, User sends q j to server S j ; 3. Each S j answers a j = A(j, x, q j ) to User; 4. User recovers x i by applying the reconstruction algorithm R(a 1 , . . . , a ℓ , i, s).

Furthermore the protocol has the Correctness property: for any

x ∈ ∆ k , i ∈ [k],
User recovers x i with probability at least p; and the Privacy property: each server individually can obtain no information about i.

The Privacy property can be obtained by requiring that for all j ∈ [ℓ], the distribution of the random variables Q(i, •) j are identical for all i ∈ [k]. Katz and Trevisan [START_REF] Katz | On the efficiency of local decoding procedures for error-correcting codes[END_REF], introduced a notion very relevant in the context of locally decodable codes: that of smooth codes. The notion of smooth codes captures the idea that a decoder cannot read the same index too often, and implies that the distributions Q(i, •) j are close to uniform. All known examples are such that the distribution Q(i, •) j are actually uniform. Uniform distribution of the queries among codeword (or received word) coordinates is what is needed in the PIR setting in order to achieve information theoretic privacy of the queries. The locality as a core feature of LDCs, together with the fact that in all known constructions of LDCs the queries made by the local decoding algorithm A are uniformly distributed, make the application of LDCs to PIR schemes quite natural. Note also that conversely PIR schemes can be used to build LDCs with best asymptotic code-lengths [START_REF] Beimel | Breaking the 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]. The lemma below describes how it formally works.

Lemma 1 (Application of LDCs to PIR schemes). Suppose there exists an ℓ-query locally decodable code C : ∆ k → Σ n , in which each decoder's query is uniformly distributed over the set of codeword coordinates. Then there exists an ℓ-server 1-PIR protocol with O(ℓ(log

2 n + log 2 |Σ|)) communication to access a database x ∈ ∆ k .
Proof. Given an LDC C : ∆ k → Σ n as in the lemma, one constructs the following PIR protocol. First, in a preprocessing step, for 1 ≤ j ≤ ℓ, server S j encodes x with C. Then, to actually run the protocol, User tosses random coins and invokes the local decoding algorithm to determine the queries (q 1 , . . . , q ℓ ) ∈ [n] ℓ such that x i can be computed from {C(x) qj } 1≤j≤ℓ . For 1 ≤ j ≤ ℓ, User sends q j ∈ [n] to server S j , and each server S j answers C(x) qj ∈ Σ. Finally, User applies the local decoding algorithm of C to recover x i .

This protocol has the communication complexity claimed in the lemma. Furthermore, as the user applies the local decoding algorithm with non corrupted inputs {C(x) qj } 1≤j≤ℓ , he retrieves x i with probability 1. Uniformity of the distribution of the decoder's queries over [n] ensures the information-theoretic privacy of the protocol.

Hasse derivative for multivariate polynomials

Notation Considering m indeterminates X 1 , . . . , X m , and m positive integers i 1 , . . . , i m , we use the short-hand notation

X = (X 1 , . . . , X m ) X i = X i1 1 • • • X im m , F q [X] = F q [X 1 , . . . , X m ] i = (i 1 , . . . , i m ) ∈ N m |i| = i 1 + • • • + i m P = (p 1 , . . . , p m ) ∈ F m q
i.e. we use bold symbols for vectors, points, etc, and standard symbols for unidimensional scalars, variables, etc. In general, we write polynomials Q ∈ F q [X] = F q [X 1 , . . . , X m ] without parenthesis and without variables, and Q(X) (resp. Q(P )) when the evaluation on indeterminates (resp. points) has to be specified.

For i, j ∈ N m , i ≫ j means i t ≥ j t ∀1 ≤ t ≤ m.
Hasse derivative Given a multi-index i, and F ∈ F q [X], the i-th Hasse derivative of F , denoted by

H(F, i), is the coefficient of Z i in the polyno- mial F (X + Z) ∈ F q [X, Z], where Z = (Z 1 , . . . , Z m ). More specifically, let F (X) = j≫0 f j X j , then F (X + Z) = j f j (X + Z) j = i H(F, i)(X)Z i ,
where

Z i stands for Z i1 1 • • • Z im m , and
H(F, i)(X) = j≫i f j j i X j-i with j i = j 1 i 1 • • • j m i m .
Considering a vector V ∈ F m q \ {0}, and a base point P , we consider the restriction of F to the line D = {P + tV : t ∈ F q }, which is a univariate polynomial that we denote by F P ,V (T ) = F (P + T V ) ∈ F q [T ]. We have the following relations:

F P ,V (T ) = j H(F, j)(P )V j T |j| , (1) coeff
(F P ,V , i) = |j|=i H(F, j)(P )V j , (2)
H(F P ,V , i)(α) = |j|=i H(F, j)(P + αV )V j , for all α ∈ F q (3)
3 Multiplicity codes

Local decoding of Reed-Muller codes

We enumarte the finite field F q with q elements as F q = {α 0 = 0, α 1 , . . . , α q-1 }.

We denote by F q [X] d the set of polynomials of degree less than or equal to d, which has dimension k = m+d d . We enumerate all the points in F m q :

F m q = {P 1 , . . . , P n } (4)
where P i = (P i,1 , . . . , P i,m ) ∈ F m q , is an m-tuple of F q -symbols, and n = q m . We encode a polynomial F of degree ≤ d into a codeword c of length n using the evaluation map ev :

F q [X] d → F n q F → (F (P 1 ), . . . , F (P n ))
and the d-th order Reed-Muller code is Assuming d < q, we now recall how RM d achieves a locality of ℓ = q -1 as follows. Suppose that c = ev(F ) ∈ RM d is a codeword, and that c j = c P j is looked for. Then, the local decoding algorithm randomly picks a non-zero vector V ⊂ F m q \ {0} and considers the line D of direction V passing through P j :

RM d = {ev(F ) | F ∈ F q [X] d }
D = {P j + t • V | t ∈ F q } = {P j + 0 • V , P j + α 1 • V , . . . , P j + α q-1 • V } = {R 0 = P j , . . . , R q-1 } ⊂ F m q .
Then, the points R 1 , . . . , R q-1 are sent as queries, and the decoding algorithm receives the answer: y R1 , . . . , y Rq-1 ∈ F q-1 q .

In case of no errors, y R1 , . . . , y Rq-1 = c R1 , . . . , c Rq-1 . Now

c Ru = F (P j + α u • V ) = F P ,V (α u ), u = 1, . . . , q -1,
where

F P ,V = F (P + T • V ) ∈ F q [T ] (5)
is the restriction of F to the line D, which is a univariate polynomial of degree less than or equal to d. That is, c R1 , . . . , c Rq-1 belongs to a Reed-Solomon code RS d of length q -1 and dimension d + 1. In case of errors, y R1 , . . . , y Rq-1 is a noisy version of it. Using a decoding algorithm of RS d , one can recover F P ,V , and then c P j is found as c P j = F P ,V (0). The main drawback of these codes is the condition d < q, which imposes a dimension k = d+m m < q+m m ∼ q m /m!. For a fixed alphabet F q , the rate R = k/q m < 1/m! goes to zero very fast when the codes get longer.

Multiplicity codes and their local decoding

To obtain codes with higher rates, we need a derivation order s > 0 and an extended notion of evaluation. There are σ = m+s-1 m Hasse derivatives H(F, i) of a polynomial F for multi-indices i such that |i| < s. Letting Σ = F σ q , we generalize the evaluation map at a point P :

ev s P : F q [X] → F σ q F → (H(F, v)(P )) |v|<s
and, given an enumeration of the points as in Eq. 4, the total evaluation rule is

ev s : F q [X] → Σ n F → ev s P 1 (F ), . . . , ev s P n (F ) .
Given y = ev s P (F ) ∈ Σ, we denote by y v the coordinate of y corresponding to the v-th derivative of F . As in the case of classical Reed-Muller codes, we denote by (c 1 , . . . , c n ) = (c P 1 , . . . , c P n ) = ev s (F ), i.e. c i = c P i = ev s P i (F ). We can consider F q [X] d , with d < s(q -1) [START_REF] Kopparty | High-rate codes with sublinear-time decoding[END_REF], and the corresponding code is

Mult s d = {ev s (F ) | F ∈ F q [X] d } .
Using the language of locally decodable codes, we have a code Mult s d : ∆ k → Σ n , with ∆ = F q , and Σ = F σ q . The code Mult s d , is a F q -linear space, whose dimension over

F q is k = m+d d . Its rate is R = (log q |F q [X] d |)/(log q |Σ n |) = k/(σn) = m+d m / m+s-1 m • q m . Its minimum distance is (from Generalized Schwartz- Zippel Lemma) q m -d s q m-1
. This family of codes has a locality of (q -1)σ = (q -1) m+s-1 m queries. Here is how the local decoding algorithm works. Let j be the index of the point where we want to local decode, i.e. c j = c P j is looked for. The algorithm randomly picks σ vectors U i ∈ F m q \ {0}, i = 1, . . . , σ. For each U i , i = 1, . . . , σ, consider the line of direction U i passing through P j :

D i = {P j + 0 • U i , P j + α 1 • U i , . . . , P j + α q-1 • U i } = {R i,0 = P j , R i,1 , . . . , R i,q-1 } ⊂ F m q
For each i, 1 ≤ i ≤ σ, the algorithm queries the received word at points R i,1 , . . . , R i,q-1 , and gets the answers y Ri,1 , . . . , y Ri,q-1 ∈ Σ q-1 , thus a total of (q -1)σ queries in F m q , and σ(q -1) answers from Σ. In case of no errors, we have

(y R i,b ) v = H(F, v)(R i,b ), b = 1, . . . , q -1,
where (y R i,b ) v is the v-th coordinate of y R i,b , and, using Eq. 3, we can compute

H(F P j ,U i , e)(α b ) = |v|=e H(F, v)(R i,b )U v i 1 ≤ b ≤ q -1, 0 ≤ e < s (6)
Having the values H(F P j ,U i , e)(α b ), for 1 ≤ b ≤ q -1 and |v| < s, we can then recover F P j ,U i by Hermite interpolation. Next we solve, for the indeterminates H(F, v)(P j ), |v| < s, the linear system derived from Eq. 2:

coeff(F P j ,U i , e) = |v|=e H(F, v)(P j )U v i e = 0, . . . , s -1, i = 1, . . . σ,
and we output {H(F, v)(P j ), |v| < s} = ev s P j (F ). In case of errors, for each direction U i , we define a function h i :

F * q → F {0,...,s-1} q , α b → h i (α b ), such that (h i (α b ))(e) = |v|=e (y R i,b ) v U v i , 1 ≤ b ≤ q -1 0 ≤ e < s (7)
By virtue of Eq. 6, note that h i (α b )(e) is the (erroneous) e-th Hasse derivative of F P j ,U i at α b .

Having h i (α b )(e) for all e ∈ {0, . . . , s -1} and all b ∈ {1, . . . , q -1}, F P j ,U i is recovered using a decoding algorithm of univariate multiplicity codes (see [START_REF] Kopparty | High-rate codes with sublinear-time decoding[END_REF]), provided d(ev s (F P j ,U i ), h i ) ≤ (q-1)-d/s 2 . Once we have recovered F P j ,U i , we solve for the indeterminates H(F, v)(P j ), |v| < s, the linear system derived from Eq. 2:

coeff(F P j ,U i , e) = |v|=e H(F, v)(P j )U v i t = 0, . . . , s -1, i = 1, . . . σ (8)
and we output {H(F, v)(P j ), |v| < s} = ev s P j (F ). This local decoding algorithm is sketched in Alg 1. In case of more than (q-1)-d/s 2 errors in some directions, the linear system 8 may have erroneous equations. In this case, due to lack of space, we refer the reader to [START_REF] Kopparty | High-rate codes with sublinear-time decoding[END_REF].

Algorithm 1 Local decoding algorithm for Multiplicity Codes

Require: Oracle Access to y = (y1, . . . , yn), a noisy version of c = ev s (F ) ∈ Mult d . Input: j ∈ [n], the index of the symbol cj looked for in c Output: cj = c P j = ev s P j (F ) 1: Pick distinct σ non zero random vectors U 1, . . . , U σ giving σ different lines 2: for i=1 to σ do 3:

Consider the line

Di = {P j + 0 • U i, P j + α1 • U i, . . . , P j + αq-1 • U i} = {Ri,0, . . . , Ri,q-1} 4:
Send Ri,1, . . . , Ri,q-1, as queries, 5:

Receive the answers:

y R i,1 , . . . , y R i,q-1 , y R i,b ∈ F σ q . 6:
Recover F P j ,U i from (y R i,1 , . . . , y R i,q-1 ) using a univariate decoding algorithm on the values (hi(α b ))(e) defined in Eq. 7. 7: end for 8: Solve for the indeterminates H(F, v)(P j ), |v| < s, the linear system 8. 9: return {H(F, v)(P j ), |v| < s} = ev s P j (F ). 4 Hyperplane partitions and their use in PIRs

Affine hyperplanes and servers

Considering Mult s d , we show how to equally share a codeword c = ev s (f ) = ev s P 1 (f ), . . . , ev s P n (f ) on ℓ = q servers, using the geometry of F m q . This is done as follows: consider H a F q -linear subspace of F m q of dimension m -1. It can be seen as the kernel of a linear map f H :

F m q → F q (x 1 , . . . , x m ) → h 1 x 1 + • • • h m x m
for some (h 1 , . . . , h m ) ∈ F m q \ {0}. Now F m q can be split as the disjoint union of affine hyperplanes

F m q = H 0 ∪ H 1 ∪ • • • ∪ H q-1
, where

H i = P ∈ F m q | f H (P ) = α i , i = 0, . . . , q -1.
As a simple example, consider the F q -linear hyperplane H of F m q :

H = {P = (x 1 , . . . , x m ) | x m = 0} .
Then we have F m q = H 0 ∪ H 1 ∪ . . . H q-1 where

H i = P = (x 1 , . . . , x m ) ∈ F m q | x m = α i , i = 0, . . . , q -1.
Up to a permutation of the indices, we can write any codeword

c = c H0 | • • • |c Hq-1
, where c Hi = (ev s P (f )) P ∈Hi , i = 0 . . . , q -1. Now consider an affine line, which is transversal to all the hyperplanes. It is a line which can be given by any direction U ∈ F m q \ {0} such that f H (U ) = 0, and which contains a point P :

D = {P + t • U | t ∈ F q } .
In other words, it is a line not contained in any of the hyperplane H 0 , . . . , H q-1 . Then, D ∩ H j = Q j , j = 0, . . . , q -1, for some points Q 0 , . . . , Q q-1 . Now, as long as U i , i = 1, . . . , σ, does not belong to H, Algorithm 1 works, using the points {Q i,j } 0≤j≤q-1 , where D i ∩ H j = {Q i,j }, D i being the line with direction U i passing through P j , one query being a fake one (see section 4.2 below). Fig. 2. Parameters are q = 4, m = 3, s = 2, σ = 4. Queries for a Multiplicity code used as an LDC codes (a), used in PIR scheme (b), assuming that the point P j corresponding to query j lies on the H0 hyperplane. In the PIR scheme, random points X1,0, . . . , X4,0 are sent to the server S0 to hide him the fact that he hosts the index of the request. Not all point names are displayed for readability.

Use in PIR schemes

Given F m q = H 0 ∪ H 1 ∪ . . . H q-1 , the PIR scheme can be built by requiring that, for i = 1, . . . , q, Server S i is given c Hi to store. Local decoding must be done using transversal lines. The user will first select σ transversal lines D i , i = 1, . . . , σ, which passes through the point P j which corresponds to the requested symbol, and query each server S i at the point D ∩ H i . In algorithms 1, 2, the main and only change is to make sure that all lines under consideration are indeed transversal to the chosen hyperplanes. We here explain how this works: the code requires (q -1) queries along each line. In our context, when P j is requested, all σ lines have to pass through P j . For a direction U i , the queries sent to the servers correspond to q -1 points on the line D i defined by U i , those points being all different from P j . Assume for instance that P j = (x 1 , . . . , x m ) with x m = α u , for some u. Query P j must not be sent to server S u who stores the c Hu part of the encoded word: S u would then know that it has the index of the requested coordinate among its possibly queried indices. A solution to this problem is to send σ fake (i.e. random) queries X i,u , i = 1, . . . , σ, to server S u , see Fig 2. This is enough to obfuscate server S u . See Algorithm 2.

Algorithm 2 PIR Protocol from transversal lines on hyperplanes

Preprocessing Phase: The user:

1: chooses q, m, d, s so that the original data x of bit-size k can be encoded using Mult s d (q), i.e. parameters such that m+d d log 2 q ≥ k; 2: encodes the data x into the codeword c = ev s (F ), where the coefficients of F represent the original data x; 3: sends each server S ℓ the cH ℓ part of the codeword. Online Protocol: To recover cj = ev s P j (F ) for an index j ∈ [n], the user: 4: User selects σ distinct lines Di, 1 ≤ i ≤ σ, transversal to the hyperplanes, and passing through P j ; 5: Let ℓj be such that Di ∩ H ℓ j = P j , i = 1, . . . , σ 6: For 1 ≤ ℓ ≤ q, ℓ = ℓj, user sends the queries {Di ∩ H ℓ = R i,ℓ } 1≤i≤σ to server ℓ. 7: User sends σ random queries X i,ℓ j , i = 1, . . . , σ to server S ℓ j ; 8: For 1 ≤ ℓ ≤ q, server sends the answers {yR i,ℓ } 1≤i≤σ . Answers {yR i,u } 1≤i≤σ are discarded by the user. 9: User then proceeds as in steps 5 to 8 of algorithm 1 to retrieve ev s P j (F ).

5 Analysis of the protocol given in algorithm 2

Overall storage overhead

The natural reduction from locally decodable codes to information theoretically secure private information retrieval schemes leads to two overheads: the first one is 1/R where R is the rate of the code used for encoding the data, the second one is ℓ, where ℓ is the number of servers. The total overhead is thus ℓ • 1/R. Our scheme has an overhead of only 1/R, which is the natural overhead of the code. With respect to the amount of storage required in each server for encoding k symbols, only k/Rq symbols are required per server. In particular, when R ≥ 1/q, each server stores less than k symbols, which is the amount of information without redundancy.

Communication complexity

We count the communication complexity in terms of the number of exchanged bits during the online protocol, discounting the preprocessing phase. The user has to send σ points to each server S j , j = 1, . . . , q. A point consists in m coordinates in F q , but since it belongs to an hyperplane, it can be specified with (m -1) coordinates, i.e. (m -1) log 2 q bits. Thus σ(m -1) log 2 q bits are sent to each server S j , 1 ≤ j ≤ q, for a total of qσ(m -1) log 2 q. For his response, each server sends σ field elements for each of the σ points it receives in the query: σ 2 field elements, i.e. σ 2 log 2 q bits, and thus a total of qσ 2 log 2 q bits for all the servers. The overall communication complexity for the queries and the answers is qσ(m -1) log 2 q + qσ 2 log 2 q = (m -1 + σ)qσ log 2 q = O(qσ 2 log 2 q), since m ≤ σ as soon as s > 1. Fig. 3. Properties of our scheme for q = 16 and q = 256. We have to distinguish LDClocality (i.e. ♯ queries) and PIR-locality (i.e. ♯ servers), since they are not the same using our construction. The storage overhead is the global overhead among all the servers: in the standard case, using the standard LDC to PIR reduction as in Lemma 1, it is (q -1)/R; in our case, using partitioning on the servers, it is 1/R, R being the rate of the code. Similarly the communication complexities (in bits) are shown. The degree d has been chosen to be d = s(q -1) -1, the maximum possible value, with no correction capability.

PIR-locality

Our construction leads to introduce the notion of "PIR-locality": when an LDC code admits a nice layout as multiplicity codes do, the number of servers can be smaller than the locality of the code. We call this the PIR-locality. Here the (LDC-)locality, i.e. the number of queries, is (q -1)σ, while the PIR-locality, i.e. the number of servers, is q. The tables show the obtained parameters for q = 256 and q = 16 in Fig. 3. We can see that the rate and LDC-locality of the code grow with s, while the PIR-locality is constant for a fixed q. The global storage overhead is much smaller, and the communication complexities are very similar.

Robustness of the protocol

Algorithm 1 involves σ applications of decoding of univariate multiplicity codes of length q -1. From [START_REF] Kopparty | High-rate codes with sublinear-time decoding[END_REF], we can decode if the word y i = (y Ri,1 , . . . , y Ri,q-1 ) is t-far from a codeword ev s (F ), for a polynomial F ∈ F q [X 1 ] d , where t = 1/2(q -1 -d/s). The received word y i corresponds to the answers of the q -1 servers (all q servers except server u) for direction U i . Tolerating ν = ⌊t⌋ errors here means that ν servers can answer wrongly. Thus, following the terminology of Beimel and Stahl [START_REF] Beimel | Robust information-theoretic private information retrieval[END_REF], our protocol is a ν-Byzantine robust protocol. We sum up features of the protocol presented in Algorithm 2 in the following Theorem 1. Let q be a power of a prime, m, s ∈ N * , and d be an integer with d < s(q -1). Set σ = m+s-1 m , with the constraint σ ≤ (q m -1)/(q -1). Protocol from Algorithm 2 has:

-LDC-locality (i.e. number of queries) σ(q -1); -PIR-locality (i.e. number of servers) ℓ = q; -Communication complexity (m -1 + σ)qσ log 2 q bits; -Storage overhead 1/R, where R = m+d m /(q m σ) is the rate of the underlying multiplicity code; -ν-Byzantine robustness, where ν = ⌊1/2(q -1 -d/s)⌋, in the sense that it can tolerate up to ν servers wrongly.

6 Discussing parameters

Impact of the Byzantine robustness on the storage overhead

Expressing d in terms of t for a given s gives d = (q -1)s -2st, which then gives a rate, say R t , to be compared with the rate R found for d = s(q -1) -1, when no error can be tolerated. For small m and s(q -1) large enough, we have a relative loss: R t /R = s(q-1)-2st+m m /σq m s(q-1)+m-1 m /σq m ≈ (q -1 -2t + m/s) (q -1 + (m -1)/s) m For m = s = 1, we find (q -2t)/(q -1), which is almost the rate of the t-error correcting classical Reed-Solomon code. Otherwise, we get, for small t R t /R ≈ 1 -2t -1/s q -1 + (m -1)/s m For t = 1 or 2 and m small, the relative loss is not drastic. But, if t is large, say (q -1)/2 R t /R ≈ (1/(sq)) m and the loss is bigger.

Choice of q

We discuss how the size of q may be chosen independently of the size of entries on the database. Consider a simple database, which is a table, with E entries, each entry having S records, all of the same bit-size b. I.e. the total bit-size of the database is thus N = E • S • b. A multiplicity code of F q -dimension k enables to encode k log 2 q bits. Thus, to encode the whole database, we need k log 2 q ≥ N = E • S • b. If furthermore a = b/ log 2 q is an integer, then, to recover a record of size b, the user needs to apply the PIR protocol a times. By definition of information theoretic PIR schemes, Protocol. 2 can be run any number of times, with no information leakage. This implies that q does not need to have a special relationship with the original data.

For instance, imagine a database of 90 000 IPV6 adresses. An IPV6 address consists in 128 bits addresses, i.e. 16 bytes. The database has E = 90 000, S = 1, b = 128, and requires 90 000 • 16 = 144 0000 bytes of storage. We first design a PIR scheme using q = 256 = 2 8 . Mapping a byte to an F q -symbol, we need a code of F q -dimension at least 144 000. From Table 3, using m = 3, s = 1, we find a code of F q -dimension 2796160 ∼ 2, 7 • 10 6 , and expansion 6. The LDC-locality is 255, and its PIR-locality is 256. The communication cost is 6144 bits.

But we could also use q 0 = 2 4 = 16. Then 144 0000 bytes require 2•144 0000 = 2, 88 • 10 6 F q0 -symbols. From Table 3, with m = 4 and s = 6, we find a code of F q0 -dimension 2919735 ∼ 2.9 • 10 6 , and expansion 2.8. Its LDC-locality is (q 0 -1) 4+6-1 4 = 15 • 126 = 1890 while its PIR-locality is 16. This is better in many aspects since less servers are needed, and a better rate is achieved. But the communication cost is now 1040256 bits.

Conclusion

Starting from multiplicity codes, we have designed a layout of the encoded data which leads to a new PIR scheme. It features a very small PIR-locality and much smaller global redundancy compared to PIR schemes naturally arising from LDCs, as well as Byzantine robustness. This layout is quite natural in the context of multiplicity codes. A straightforward question, to be investigated in a future work, is to construct layouts for other locally decodable codes, like affineinvariant codes [START_REF] Guo | New affine-invariant codes from lifting[END_REF] and matching vector codes [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]. This seems feasible due to the very multidimensional and geometric nature of these constructions.

  . The evaluation map ev encodes k symbols into n symbols, and the rate is R = k/n ∈ [0, 1]. A codeword c ∈ RM d can be indexed by integers as c = (c 1 , . . . , c n ) or by points as c = (c P 1 , . . . , c P n ), where c i = c P i .

Fig. 1 .

 1 Fig. 1. Transversal lines for simple Reed-Muller codes (a), for Multiplicity Codes (b), assuming that the point P j corresponding to query j lies on the H0 hyperplane. Parameters are q = 4, m = 3, s = 2, σ = 4. Not all point names are displayed for readability.

A Possible ranges for d

In order the encoding function ev s to be injective, it is sufficient to choose d < sq. Indeed: ev s (f ) = ev s (g) ⇔ ev s (f -g) = (0, . . . , 0), which means that f -g admits sq m zeroes, counting multiplicities. By Schwartz-Zippel lemma, we have:

that is here

Thus, if we want f -g to be identically zero, it suffices that d < sq. Now during the decoding phase, in the case of errors, one has to perform Reed-Solomon with multiplicities decoding (indeed, σ Reed-Solomon applications of decoding). In this case, the length of the Reed-Solomon code is always q -1 as we have q -1 noisy evaluations of the original polynomial F on each line. In order such a Reed-Solomon code to realize proper (i.e. injective) encoding, we need d < s(q -1), as shown below.

i.e. f -g admits s(q -1) zeroes, where here ev s (f ) is the encoding of a univariate degree ≤ d polynomial f ∈ F q [X] with a Reed-Solomon code of length q -1 and multiplicity s. But a univariate polynomial cannot have more zeroes, counted with multiplicities, than its degree:

thus if we want f -g to be identically zero, it suffices that d < s(q -1).

B Decoding univariate multiplicity codes

When the number m of variables is 1, then the codes lead to Reed-Solomon codes, also called derivative codes in [START_REF] Guruswami | Linear-algebraic list decoding for variants of Reed-Solomon codes. Information Theory[END_REF]. We briefly recall how to decode these codes, using the so-called Berlekamp-Welch framework [START_REF] Gemmell | Highly resilient correctors for polynomials[END_REF]. We consider univariate polynomials in F q [X]. For s > 0, we have Σ = F s q , and the code is the set of codewords of length n = q -1:

Decoding up to distance t is, for a given vector y ∈ Σ n , find all polynomials

where d Σ is the Hamming distance in Σ n . We first look for two polynomials N, E ∈ F q [X] of degree (sn + d)/2 and (sn -d)/2 respectively, as follows. Write the linear system of equations:

for i = 1, . . . , n, where the indeterminates are the coefficients of N and E. This is a system of sn homogeneous linear equations in (sn -d)/2 + 1 + (sn + d)/2 + 1 = sn + 2 unknowns. Thus a non-zero solution (N, E) always exists. Given any solution, F can then be recovered as N/E. Assuming that t = (n-d/s)/2, we can show the correctness of this algorithm: any univariate polynomial F of degree ≤ d, such that d Σ (ev s (F ), y) ≤ t will satisfy N -EF = 0 where (N, E) is a solution of the above system. Indeed, for any α u such that ev s αu (F ) = y u , the system is satisfied at α u , and hence the polynomial N -EF has a zero of multiplicity s at α u . Thus But deg(N -EF ) ≤ max{(sn+d)/2, d+(sn-d)/2} = (sn+d)/2. Thus N -EF , having more zeroes than its degree, is identically zero.


Daniel Augot

Generalization of Gabidulin Codes over Fields of Rational Functions

We transpose the theory of rank metric and Gabidulin codes to the case of fields which are not finite fields. The Frobenius automorphism is replaced by any element of the Galois group of a cyclic algebraic extension of a base field. We use our framework to define Gabidulin codes over the field of rational functions using algebraic function fields with a cyclic Galois group. This gives a linear subspace of matrices whose coefficients are rational function, such that the rank of each of this matrix is lower bounded, where the rank is comprised in term of linear combination with rational functions. We provide two examples based on Kummer and Artin-Schreier extensions.The matrices that we obtain may be interpreted as generating matrices of convolutional codes.

I. INTRODUCTION

Gabidulin codes are rank-metric codes defined over finite fields using so-called linearized polynomials [START_REF] Gabidulin | Theory of codes with maximal rank distance[END_REF]. They can be seen as analogues of Reed-Solomon codes, where polynomials are replaced by linearized polynomials, and the Hamming distance is replaced by the rank distance. For Gabidulin codes, the Frobenius automorphism x → x q plays a fundamental role. In [START_REF] Augot | Rank metric and Gabidulin codes in characteristic zero[END_REF], the authors generalized this construction to fields of characteristic zero, where the Frobenius automorphism does not exists, by considering extensions of number fields L/K, and using a Galois automorphism θ as the Frobenius automorphism, and replacing linearized polynomials by so-called skew polynomials or θpolynomials. The theory of Gabidulin transposes nicely, and Maximum Rank Distance (MRD) codes can be built, with a decoding algorithm (for the rank distance) transposed from a simple decoding of Reed-Solomon codes.

In this paper, we use the general abstract framework of [START_REF] Augot | Rank metric and Gabidulin codes in characteristic zero[END_REF] in the case of the base field being the field of rational functions (over a finite field). First we briefly recall facts from [START_REF] Augot | Rank metric and Gabidulin codes in characteristic zero[END_REF], in the case of a cyclic Galois extension whose Galois group is generated by θ: θ-polynomials, rank metric, decoding. We give a construction with Kummer extensions, a more precise example over the ground field F 8 , and another example with an Artin-Schreier extension over F 5 .

II. θ-POLYNOMIALS

In all the paper, we consider an algebraic field extension K ֒→ L with finite degree n, and an automorphism θ in the Galois group Gal(K ֒→ L), of order n = Gal(K ֒→ L). Given x ∈ L, we use the notation x θ i for θ i (x). In the finite field case, when θ is the Frobenius automorphism x → x q , x θ i = x q i , and the similarity is nicely reflected in this notation. We define θ-polynomials, which are a special case of skew polynomials, namely, when there is no derivation. 1 INRIA & LIX UMR 7161 X-CNRS, Bâtiment Alan Turing, Campus de l' École polytechnique, 91120 Palaiseau CEDEX, France Definition 1: A θ-polynomial is a finite summation of the form i≥0 p i Z θ i , with p i ∈ L. The greatest integer i < ∞ such that p i = 0 is called its θ-degree, and is denoted by deg θ (P ). We denote the set of θ-polynomials by L[Z; θ]. This is a L-vector space, which is also a non commutative algebra, using the skew product:

p i Z θ i • p j Z θ j = i,j p i q j θ i Z θ i+j .
An evaluation map can also be defined, for P ∈ L[Z; θ], and g ∈ L:

ev(P, g) = P (g) = p i g θ i .
The following is well known.

Proposition 1 ([3]):

The set of θ-polynomials (L[Z; θ], +, •) is a non-commutative integral domain, with unity Z θ 0 = Z. It is also a left and right Euclidean ring. We define the root-space of a θ-polynomial P (Z) to be the set of x ∈ L such that P (x) = 0. Then we have:

Theorem 1: The dimension of the root-space of a θpolynomial is less than or equal to its θ-degree.

Theorem 2: Let V be an s-dimensional K-subspace of L. Then there exists a unique monic θ-polynomial P V with θdegree s such that P V (x) = 0 for all x ∈ V. See [START_REF] Augot | Rank metric and Gabidulin codes in characteristic zero[END_REF] for proofs of these two Theorems.

III. RANK METRIC AND θ-CODES

In this section we recall the definition of the rank weight. All the proofs are to be found in [START_REF] Augot | Rank metric and Gabidulin codes in characteristic zero[END_REF]. The codes we are going to define have codewords c ∈ L n . We note

B = (b 1 , . . . , b m ) a fixed K-basis of L. Let c = (c 1 , • • • , c n ) ∈ L n . We define M c def =    c 1,1 • • • c n,1 . . . . . . . . . c 1,n • • • c n,n    ,
where c i = n j=1 c i,j b j . We then define the rank weight which is related to K-linear independence:

Definition 2: The rank weight is defined by

w(c) def = rank K (c B )
, for all c ∈ L n . It is easy to see that the w provides a distance defined by

d(c 1 , c 2 ) def = w(c 1 -c 2 )
. This definition is a generalization of rank metric as defined in Gabidulin [START_REF] Gabidulin | Theory of codes with maximal rank distance[END_REF]. In [START_REF] Augot | Rank metric and Gabidulin codes in characteristic zero[END_REF], we provided four equivalent definitions of the rank metric, a convenient one being w(c) def = deg θ (min(I c )), where min(I c ) is the right generator of the ideal

I c = {P ∈ L[Z; θ] : P (c i ) = 0, i = 1, . . . , n} .
We also define the generalization of Gabidulin codes.

Definition 3: Let g = (g 1 , • • • , g n ) ∈ L n , be K-linearly independent elements of L. The generalized Gabidulin code, with dimension k and length n, denoted Gab θ,k (g), as a L-subspace of L N , is L-generated by the matrix

G def =    g 1 θ 0 • • • g N θ 0 . . . . . . . . . g 1 θ k-1 • • • g N θ k-1    .
Using the evaluation map:

ev g : L[Z; θ] → L n P (Z) → ev g (P ) = (P (g 1 ), • • • , P (g n ))
we may also define the code as an evaluation code:

Gab θ,k (g) = {ev g (P ) : P ∈ L[Z; θ], deg θ P < k} . For k ≤ n, the dimension of Gab θ,k (g) is indeed k. Proposition 2 (Singleton bound): Let C be any [n, k, d] L code for the rank distance. Then d ≤ n -k + 1.
An optimal code satisfying the property that

d = n -k + 1 is called a Maximum Rank Distance (MRD) code.
Theorem 3: The generalized Gabidulin Gab θ,k (g) is an MRD code. We also briefly recall how to decode these codes. Actually, any decoding algorithm of Gabidulin codes may be transformed in a decoding algorithm for our codes, using θ in place of the Frobenius map: x → x q . We present a high level view of the decoding algorithm, inspired from Gemmel and Sudan's presentation of the algorithm of Welch-Berlekamp [START_REF] Gemmel | Highly resilient correctors for polynomials[END_REF], but relevant faster algorithms can be found in [START_REF] Loidreau | Welch-Berlekamp like algorithm for decoding Gabidulin codes[END_REF] or more recently in [START_REF] Wachter-Zeh | Fast decoding of Gabidulin codes[END_REF].

Consider a vector y = (y

1 , • • • , y n ) ∈ L n such that there exists e = (e 1 , • • • , e n ) , c = (c 1 , • • • , c n ) ∈ L n such that y = c + e, c ∈ Gab θ,k (g), w(e) ≤ ⌊(n -k)/2⌋.
Write t = ⌊(n -k)/2⌋. We define the following series of problems related to this situation.

Definition 4 (Decoding): Given y ∈ L n , find, if it exists, a pair (f, e) such that

y i = f (g i )+e i , i = 1, . . . , n ; w(e) ≤ t; deg θ (f ) < k. Definition 5 (Nonlinear reconstruction): Given y ∈ L n , find, if it exists, a pair of θ-polynomials (V, f ) such that deg θ (V ) ≤ t ; V = 0 ; deg θ (f ) < k ; V (y i ) = V (f (g i )), i = 1, . . . , n.
Note that this problem gives rise to quadratic equations, considering as indeterminates the coefficients of the unknowns (V, f ) over the basis B. We thus consider a linear version of the system.

Definition 6 (Linearized reconstruction): Given Y ∈ L n , find, if it exists, a pair of θ-polynomials (W, N ) such that

deg θ (W ) ≤ t ; W = 0 ; deg θ (N ) < k +t ; W (y i ) = N (g i ), i = 1, . . . , n.
When we have unique decoding, i.e. when the weight of the error e is less than or equal to ⌊(n -k)/2⌋, we have the following relations between the solutions of these problems.

Proposition 3: If t ≤ (n -k)/2, and if there is a solution to nonlinear reconstruction, then any solution of Linear reconstruction gives a solution to nonlinear reconstruction. The solution f can be found by dividing N by W .

Remark 1: The number of arithmetic operations used in this method is easily seen to be of O(n 3 ), using for instance Gaussian elimination for solving the linear system. However, since the system is highly structured, a better algorithm exists [START_REF] Loidreau | Welch-Berlekamp like algorithm for decoding Gabidulin codes[END_REF] whose complexity is O(n 2 ). This does not reflect the bit-complexity, only the arithmetic complexity.

IV. KUMMER EXTENSIONS OF FUNCTION FIELDS

We now use the previous theory when the field K is a function field on one variable, the simplest case being K = k(x) the field of rational functions over a base field k. We need to build cyclic extensions of k(x). An standard way of constructing a cyclic extension is to consider a Kummer extension. The ground field is the field of rational functions, which then extended by adding a n-th root of some element u ∈ k(x).

We refer the reader to Stichtenoth's book [START_REF] Stichtenoth | Algebraic Function Fields and Codes[END_REF] for the theory of algebraic function fields.

For simplicity, we consider the finite field case, when k = F q , for some prime power q, and k is containing an n-root of unity α, for n dividing q -1. Note that we can also deal with fields of characteristic zero like Q, but we may have to extend them by adjoining n-th roots of unity, see [START_REF] Augot | Rank metric and Gabidulin codes in characteristic zero[END_REF]. Then K = k(x) is the field of rational functions, and for u ∈ K such u = w d , for all d|n and w ∈ K, we can build the field L = K[y], where y is a root of Y n -u = 0. Then L is a cyclic extension of K of degree n, with basis B = g = 1, y, . . . , y n-1 and whose Galois group is generated by θ : y → αy. We can use the previous general framework for building a θ-code Gab θ,k (g) for all 1 ≤ k ≤ n. A generating matrix is

G def =     (1) θ 0 • • • y n-1 θ 0 . . . . . . . . . (1)
θ k-1 • • • y n-1 θ k-1     .
Then, this matrix defines an MRD code over L. Its codewords are of the form c

= (c 1 , . . . , c n ) = (m 1 , . . . , m k ) • G, c i , m i ∈ L.
Using the basis B = 1, y, . . . , y n-1 , a codeword can be seen as a matrix

M c =    c 11 • • • c 1n . . . . . . . . . c n1 • • • c nn   
where the c ij 's are K = F q (x). The construction implies that for any codeword rank M c ≥ n -k + 1, where is the rank is understood in terms of F q (X)-linear combinations.

m T =    β 3 x+β
         (2)
M c =          β 11 x
β 6 x 2 +β 6 x+1 x 3 +β 12 x 2 +β 8 x+β 7          (3) V. A WORKED OUT EXAMPLE We set k = F 16 = F 2 [β]
, with β 4 + β + 1 = 0, and we set α = β 3 , which is a primitive 5-th root of unity. Then, a Kummer extension is constructed by adjoining to K = F 16 (x), y a root of Y 5 -x, which is an irreducible polynomial, to build L = K[y]. The Galois group Gal(L ֒→ K) has order 5, with generator θ : y → αy. The matrix of the conjugates of the basis is given by:

      1 y y 2 y 3
y 4 1 β 3 y β 6 y 2 β 9 y 3 β 12 y 4 1 β 6 y β 12 y 2 β 3 y 3 β 9 y 4 1 β 9 y β 3 y 2 β 12 y 3 β 6 y 4 1 β 12 y β 9 y 2 β 6 y 3

β 3 y 4      
Picking the first three rows gives a generating matrix for a 3 dimensional θ-code:

G =   1 y y 2 y 3 y 4 1 β 3 y β 6 y 2 β 9 y 3 β 12 y 4 1 β 6 y β 12 y 2 β 3 y 3 β 9 y 4  
We give in Eqs. 1, 2, 3 an example of a codeword. A message m ∈ L 3 is shown (in transpose form) in Eq. 1, then c = m • G ∈ L 5 is computed, as shown in Eq. 2. We can expand c in the basis 1, y, . . . , y 4 to obtain the matrix M c , (Eq. 3).

Note that we obtain matrices with (unbounded) coefficients in K = F 16 [x], where the function field construction with the Kummer extension may be discarded.

VI. ARTIN-SCHREIER CASE

For completeness, we describe the Artin-Schreier situation, which is particular to the positive characteristic case. The theory of such extensions is also described in [START_REF] Stichtenoth | Algebraic Function Fields and Codes[END_REF]. Assume that k has characteristic p, and consider K = k(x), with an element u ∈ K such that u = w p -w for all w ∈ K.

Then the extension L = K[y], where y is a root of Y p -Y = w is an Artin-Schreier extension. Its Galois group is cyclic of order p, whose generator θ is defined by θ(y) = y + 1. Consider as an example k = F 5 , K = k(x), and L = K[y], with y 5 -y = x. Then θ(y) = y + 1, and we can build a [START_REF] Loidreau | Welch-Berlekamp like algorithm for decoding Gabidulin codes[END_REF][START_REF] Øre | Theory of non-commutative polynomials[END_REF][START_REF] Øre | Theory of non-commutative polynomials[END_REF] L code with generating matrix G given in Eq. 4. We give in Eqs. 5, 6, 7 an example of a codeword.

VII. POLYNOMIAL MATRICES

We briefly mention that in both constructions the basis are integral bases of L/K = L/k(x). The generating matrices G consist of integral elements. In that case, we can choose our messages m ∈ k[x, y] instead of k(x)[y], and the corresponding codewords will also belong to k[x, y]. When the codewords are expanded as matrices, we find n × n matrices with polynomial coefficients.

VIII. CONCLUSION

We have generalized Gabidulin codes to the field of rational functional, using cyclic extensions L of k(x), for instance Kummer extensions, or Artin-Schreier extensions. We can easily find generating matrices for codes with symbols in L. These codewords, when expanded over k(x) give naturally matrices which have high rank, where the rank has to understood by considering k(x) linear combinations of the rows of the matrix. When the Gabidulin code has dimension k, each of these matrices has k(x)-rank at least n -k + 1, since the codes are Maximum Rank Distance. Given such a matrix, when its weight, i.e. its rank, is w, its gives rise to a rate w/n convolutional codes, using the language of rational fractions as in [START_REF] Huffman | Fundamentals of Error-Correcting Codes[END_REF], replacing x with D, the delay operator. We did not consider the framework of Laurent series as in [START_REF] Roth | Introduction to Coding Theory[END_REF], but we think we can adapt the general theory to this field.

G =

  1 y y 2 y 3 y 4 1 y + 1 y 2 + 2y + 1 y 3 + 3y 2 + 3y + 1 y 4 + 4y 3 + y 2 + 4y + 1 1 y + 2 y 2 + 4y + 4 y 3 + y 2 + 2y + 3 y 4 + 3y 3 + 4y

2 + 2y + 1   (4) m =   x+1 x+3 y 4 + 1 x y 3 + (4x + 4)y 2 + x+2 x y + 4x+1 x , (3x + 2)y 4 + 4x+3 x y 3 + 1 x+2 y 2 + (2x + 1)y + 1, 2 x+1 y 4 + 4x+4 x+2 y 3 + 4y 2 + y + 3 x+1   (5) c T =         3x 3 +x+3 x 2 +4x+3 y 4 + 3x 2 +x+3 x 2 +2x y 3 + 4x 2 +x+2 x+2 y 2 + 2x 2 +3x+2 x y + 4x+1 x 2 +x 3x 4 +4x 3 +x+3 x 3 +3x 2 +2x y 4 + 4x 3 +3x 2 +x+1 x 2 +2x y 3 + 2x 3 +4
x 2 +2x y 2 + x 2 +2x+3

x 2 +3x y + 3x 4 +2x 2 +3x+1

x 2 +4x+3 2x 3 +x 2 +3x+1

x 2 +x y 4 + 2x 2 +3x+4 x+2 y 3 + 2x 4 +2x 2 +4x+1

x 3 +x y 2 + 3x 6 +4x 5 +3x 4 +2x 3 +x 2 +x+4

x 4 +x 3 +x 2 +x y + x 4 +2x 2 +3x+4

x 2 +3x+2 4x 2 +x+1

x 2 +x y 4 + 4x 4 +x 3 +2x 2 +4

x 3 +x y 3 + 3x 6 +x 5 +2x 2 +4x+4

x 4 +x 3 +x 2 +x y 2 + 4x 4 +3x 3 +3x 2 +x+4

x 2 +x y + 3x 3 +x 2 +x+3 x+2 4x 5 +x 4 +2x 3 +2x+3

x 4 +x 3 +x 2 +x y 4 + 3x 6 +x 4 +3x 3 +2x 2 +x+2

x 4 +x 3 +x 2 +x y 3 + 2x 5 +2x 4 +2x 3 +x 2 +2x+4

x 3 +3x 2 +2x y 2 + 2x 3 +x 2 +2x x+1 y + 4x 4 +3x+3

x 2 +3x+2         (6)
M c =         4x+1 x 2 +x 2x 2 +3x+2 x 4x 2 +x+2 x+2 3x 2 +x+3 x 2 +2x 3x 3 +x+3 x 2 +4x+3 3x 4 +2x 2 +3x+1
x 2 +4x+3

x 2 +2x+3 x 2 +3x 2x

IX. ACKNOWLEDGMENTS

  10 x+β 5 y 4 + β 5 x+β 2 x+β 4 y 3 + β 6 x+β 13 x+β 3 y 2 + β 10 x+β 6 x+β 9 y + βx+β 12 x+1 β 9 x+β 14 x+β 6 y 4 + β 6 x+β x+β 4 y 3 + β 14 x+β 13 x+β 3 y 2 + β 8 x+β 7 x+β 12 y + β 11 x+β 11 x+β β 4 x+β 11 x+β 5 y 4 + β 6 x+β 10 x+β 11 y 3 + β 5 x+β 11 x y 2 + β 8 x+β 6 x+β 7 y + βx+β 12 2 +β 2 x+β 8 x 2 +β 9 x+β 11 y 4 + β 5 x 2 +β 7 x 2 +β 13 x+1 y 3 + β 4 x 2 +β 7 x+β 14 x 2 +β 3 x y 2 + β 10 x 3 +β 4 x 2 +β 13 x+β 13 x 3 +β 11 x 2 +β 13 x+β 13 y + β 11 x 3 +β 13 x 2 +β 3 x+β 9 x 3 +β 12 x 2 +β 8 x+β 7 β 4 x+β 5 x+β 11 y 4 + β 5 x 2 +βx+β 5 x 2 +β 3 x y 3 + β 11 x 2 +β 2 x+1 x 3 +β 11 x 2 +β 13 x+β 13 y 2 + β 10 x+β 5 x 3 +β 12 x 2 +β 8 x+β 7 y + β 7 x 2 +β 6 x x 2 +β 9 x+β 11 β 11 x 2 +β 13 x+β 11 x 2 +β 3 x y 4 + β 3 x 3 +βx 2 +β 2 x 3 +β 11 x 2 +β 13 x+β 13 y 3 + β 7 x 3 +β 7 x 2 +1 x 3 +β 12 x 2 +β 8 x+β 7 y 2 + β 7 x 3 +β 4 x 2 +β 6 x x 2 +β 9 x+β 11 y + x 3 +β 3 x 2 +β 7 x x 2 +β 13 x+1 β 13 x 3 +β 6 x 2 +β 5 x+β x 3 +β 11 x 2 +β 13 x+β 13 y 4 + β 10 x 3 +β 9 x 2 +β 4 x+β 12 x 3 +β 12 x 2 +β 8 x+β 7 y 3 + β 7 x 3 +β 14 x 2 +β 14 x x 2 +β 9 x+β 11 y 2 + β 13 x 3 +β 12 x 2 +β 8 x x 2 +β 13 x+1 y + β 6 x 2 +x+β 2 x+β 3 β 6 x 2 +β 6 x+1 x 3 +β 12 x 2 +β 8 x+β 7 y 4 + β 14 x 3 +β 3 x 2 +β 11 x x 2 +β 9 x+β 11 y 3 + β 12 x 3 +βx 2 +βx x 2 +β 13 x+1 y 2 + β 7 x 2 +β 3 x+β 8 x+β 3 y + β 8 x 4 +β 4 x 2 +β 13 x x 3 +β 11 x 2 +β 13 x+β 13

		x+β 6	  	(1)
	c T =	        

x

  3 +β 13 x 2 +β 3 x+β 9 x 3 +β 12 x 2 +β 8 x+β 7 β 10 x 3 +β 4 x 2 +β 13 x+β 13 x 3 +β 11 x 2 +β 13 x+β 13 β 4 x 2 +β 7 x+β 14 x 2 +β 3 x β 5 x 2 +β 7 x 2 +β 13 x+1 x 2 +β 2 x+β 8 x 2 +β 9 x+β 11 β 7 x 2 +β 6 x x 2 +β 9 x+β 11 β 10 x+β 5 x 3 +β 12 x 2 +β 8 x+β 7 β 11 x 2 +β 2 x+1 x 3 +β 11 x 2 +β 13 x+β 13 β 5 x 2 +βx+β 5 x 2 +β 3 x β 4 x+β 5 x+β 11 x 3 +β 3 x 2 +β 7 x x 2 +β 13 x+1 β 7 x 3 +β 4 x 2 +β 6 x x 2 +β 9 x+β 11 β 7 x 3 +β 7 x 2 +1 x 3 +β 12 x 2 +β 8 x+β 7 β 3 x 3 +βx 2 +β 2 x 3 +β 11 x 2 +β 13 x+β 13 β 11 x 2 +β 13 x+β 11 x 2 +β 3 x β 6 x 2 +x+β 2 x+β 3 β 13 x 3 +β 12 x 2 +β 8 x x 2 +β 13 x+1 β 7 x 3 +β 14 x 2 +β 14 x x 2 +β 9 x+β 11 β 10 x 3 +β 9 x 2 +β 4 x+β 12 x 3 +β 12 x 2 +β 8 x+β 7 β 13 x 3 +β 6 x 2 +β 5 x+β x 3 +β 11 x 2 +β 13 x+β 13 β 8 x 4 +β 4 x 2 +β 13 x x 3 +β 11 x 2 +β 13 x+β 13 β 7 x 2 +β 3 x+β 8 x+β 3 β 12 x 3 +βx 2 +βx x 2 +β 13 x+1 β 14 x 3 +β 3 x 2 +β 11 x x 2 +β 9 x+β 11

  +2x 4 +2x 3 +x 2 +2x+4 x 3 +3x 2 +2x 3x 6 +x 4 +3x 3 +2x 2 +x+2 x 4 +x 3 +x 2 +x 4x 5 +x 4 +2x 3 +2x+3 x 4 +x 3 +x 2 +x

	x 4 +2x 2 +3x+4 x 2 +3x+2 3x 3 +x 2 +x+3 x+2 4x 4 +3x+3 x 2 +3x+2	3x 6 +4x 5 +3x 4 +2x 3 +x 2 +x+4 x 4 +x 3 +x 2 +x 4x 4 +3x 3 +3x 2 +x+4 x 2 +x 2x 3 +x 2 +2x x+1	3 +4 x 2 +2x 2x 4 +2x 2 +4x+1 x 3 +x 3x 6 +x 5 +2x 2 +4x+4 x 4 +x 3 +x 2 +x 2x 5  4x 3 +3x 2 +x+1 x 2 +2x 3x 4 +4x 3 +x+3 x 3 +3x 2 +2x 2x 2 +3x+4 x+2 2x 3 +x 2 +3x+1 x 2 +x 4x 4 +x 3 +2x 2 +4 x 3 +x 4x 2 +x+1 x 2 +x       

We are thankful to V. Sidorenko for suggesting us to expand the framework of [2] to the context of rational function fields. We also thank Hans-Andrea Loeliger, Emina Soljanin, and Judy L. Walker, the organizers of the Dagstuhl "Coding Theory" Seminar, 25-30 August 2013, for providing a nice atmosphere for discussing these topics.