2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | P.8.3 | ||
| Paper Title | Array Codes for Functional PIR and Batch Codes | ||
| Authors | Mohammad Nassar, Eitan Yaakobi, Technion - Israel Institute of Technology, Israel | ||
| Session | P.8: Private Information Retrieval I | ||
| Presentation | Lecture | ||
| Track | Cryptography, Security and Privacy | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | A \emph{functional PIR array code} is a coding scheme which encodes some $s$ information bits into a $t\times m$ array such that every linear combination of the $s$ information bits has $k$ mutually disjoint \emph{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. \emph{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, \ell$, 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. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
