M.Sc Thesis


M.Sc StudentNassar Mohammad
SubjectArray Constructions for Functional PIR and Batch Codes
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Eitan Yaakobi
Full Thesis textFull thesis text - English Version


Abstract

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 Pt,\ell(s,k), Bt,\ell(s,k), FPt,\ell(s,k), FBt,\ell(s,k), respectively. Furthermore, we denote by D(s,k,t,r) the smallest m such that an (s,k,m,t,r) locality functional array code exists.


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.