Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 66, Issue 8, Pages 4904-4916Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2020.2977073
Keywords
Data storage; information retrieval; privacy
Funding
- National Science Foundation [CCF-18-32309, CCF-18-16546]
Ask authors/readers for more resources
We consider constructing capacity-achieving linear codes with minimum message size for private information retrieval (PIR) from N non-colluding databases, where each message is coded using maximum distance separable (MDS) codes, such that it can be recovered from accessing the contents of any T databases. It is shown that the minimum message size (sometimes also referred to as the sub-packetization factor) is significantly, in fact exponentially, lower than previously believed. More precisely, when K > T/gcd(N, T) where K is the total number of messages in the system and gcd(center dot, center dot) means the greatest common divisor, we establish, by providing both novel code constructions and a matching converse, the minimum message size as lcm(N - T, T), where lcm(center dot, center dot) means the least common multiple. On the other hand, when K is small, we show that it is in fact possible to design codes with a message size even smaller than lcm(N - T, T).
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available