M.Sc Thesis | |

M.Sc Student | Nassar Mohammad |
---|---|

Subject | Array Constructions for Functional PIR and Batch Codes |

Department | Department of Computer Science |

Supervisor | ASSOCIATE PROF. Eitan Yaakobi |

Full Thesis text |

A *functional PIR array code* is a coding
scheme which encodes some *s* information bits into a *tXm* array
such that every linear combination of the *s* information bits has *k*
mutually disjoint *recovering sets*. Every recovering set consists of some
of the array's columns while it is allowed to read at most *\ell* encoded
bits from every column in order to receive the requested linear combination of
the information bits. *Functional batch array codes* impose a stronger
property where every multiset request of *k* linear combinations has *k*
mutually disjoint recovering sets. *Locality functional array codes*
demand that the size of every recovering set is restrained to be at most *r*.

Formally, assume *s* bits are encoded to
be stored in a *tXm* array, where each column corresponds to a *server*
that stores the encoded bits. It is required in *PIR codes* that every
information bit has *k* mutually disjoint recovering sets while it is
allowed to read at most *\ell* bits from every column. An array code with
these parameters and properties is defined as an *(s,k,m,t,\ell) PIR array code*.
Furthermore, it will be called an *(s,k,m,t,\ell) batch array code* if
every *multiset* request of *k* information bits has *k*
mutually disjoint recovering sets. In case the requests are not only of
information bits but any linear combination of them, we receive an *(s,k,m,t,\ell)
functional PIR array code*, if the same linear combination is requested *k*
times or *(s,k,m,t,\ell) functional batch array code* for a multiset
request of *k* linear combinations. In case where every request of a
linear combination has *k* recovering sets, where each is of size at most *r*,
we receive an *(s,k,m,t,r) locality functional array code*.

The main figure of merit when studying these
codes is to optimize the number of columns, i.e., servers, given the values of *s,k,t,\ell,r*.
Thus, the smallest *m* such that an *(s,k,m,t,\ell)* PIR, batch,
functional PIR, functional batch code exists, is denoted by *P _{t,\ell}(s,k),
B_{t,\ell}(s,k), FP_{t,\ell}(s,k), FB_{t,\ell}(s,k)*,
respectively. Furthermore, we denote by

The results we achieve in this work can be
divided into two main parts. In the first part, we initiate the study of
functional PIR and batch codes in the array setup and we present lower bounds
on the smallest number of columns for these families of codes. In addition, we
show several general array code constructions and results for *k=1,2*.
Also, we present three specific constructions of array codes that some of them
give us optimal or nearly optimal codes.

In the second part, we define and study locality functional array codes. We show connections between the problem of finding the minimal number of columns for locality functional array codes and some problems in subspaces. In addition, we show how covering codes are used to get lower bounds and constructions for locality functional array codes.