Technical Program

Paper Detail

Paper Title Bounds on the Length of Functional PIR and Batch Codes
Paper IdentifierTH3.R3.4
Authors Yiwei Zhang, Eitan Yaakobi, Tuvi Etzion, Technion - Israel Institute of Technology, Israel
Session Private Information Retrieval IV
Location Monge, Level 3
Session Time Thursday, 11 July, 14:30 - 16:10
Presentation Time Thursday, 11 July, 15:30 - 15:50
Manuscript  Click here to download the manuscript
Abstract A functional $k$-PIR code of dimension $s$ consists of $n$ servers storing linear combinations of $s$ linearly independent information symbols. Any linear combination of the $s$ information symbols can be recovered by $k$ disjoint subsets of servers (the reason for this somehow abused definition will be explained in the sequel). The goal is to find the smallest number of servers for given~$k$ and $s$. We provide lower bounds on the number of servers and constructions which yield upper bounds. For $k \leq 4$ we provide exact bounds on the number of servers. Furthermore, we provide some asymptotic bounds. The problem coincides with the well known private information retrieval problem based on a coded database to reduce the storage overhead. If any multiset of size $k$ of linear combinations from the linearly independent information symbols can be recovered by $k$ disjoint subset of servers, then the servers form a functional $k$-batch code. A functional $k$-batch code is also a functional $k$-PIR, where all the $k$ linear combinations in the multiset are equal. We provide some bounds on the number of servers for functional $k$-batch codes. In particular we present a random construction and a construction based on simplex codes, WOM codes, and RIO codes.