Bounds on the Length of Functional PIR and Batch Codes

DOI10.1109/TIT.2020.2977631MaRDI QIDQ5124475zbMATH OpenOpenAlexFDO

Authors Yiwei Zhang, Tuvi Etzion, Eitan Yaakobi

Publication date 29 September 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.01605

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Bounds on codes (94B65)

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 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 on this number. For $kleq4$, exact bounds on the number of servers are proved. 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, when each linear combination contains exactly one information symbol. 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 a functional $k$-PIR code, 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.

Cited in

(2)

• PIR codes with short block length
• On some batch code properties of the simplex code

This page was built for publication: Bounds on the Length of Functional PIR and Batch Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5124475)