Array Codes for Functional PIR and Batch Codes
A functional PIR array code is a coding scheme which encodes some s information bits into a t× m 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 ℓ 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. Given the values of s, k, t, ℓ, the goal of this paper is to study the optimal value of the number of columns m such that these codes exist. Several lower bounds are presented as well as explicit constructions for several of these parameters.
READ FULL TEXT