| Paper Title |
Bounds on the Length of Functional PIR and Batch Codes |
| Paper Identifier | TH3.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. |
