Back to Search
Start Over
Bounds on the Length of Functional PIR and Batch Codes.
- Source :
- IEEE Transactions on Information Theory; Aug2020, Vol. 66 Issue 8, p4917-4934, 18p
- Publication Year :
- 2020
-
Abstract
- A functional k-Private Information Retrieval (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 minimum number of servers for given k and s. We provide lower bounds on the minimum number of servers and constructions which yield upper bounds on this number. For k ≤ 4, exact bounds on this number are proved. Furthermore, we provide some asymptotic bounds. The problem coincides with the well known PIR 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 minimum number of servers for functional k-batch codes. In particular we present a random construction and a construction based on simplex codes, Write-Once Memory (WOM) codes, and Random I/O (RIO) codes. [ABSTRACT FROM AUTHOR]
- Subjects :
- CIPHERS
INFORMATION retrieval
Subjects
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 66
- Issue :
- 8
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 144615698
- Full Text :
- https://doi.org/10.1109/TIT.2020.2977631