Capacity-Achieving Private Information Retrieval Codes from MDS-Coded Databases with Minimum Message Size

2019/03/19 by Zhou, Ruida, Tian, Chao, Sun, Hua +1
#FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.1903.08229

Abstract

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(⋅,⋅) 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(⋅,⋅) 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).

Related

• Breaking the MDS-PIR Capacity Barrier via Joint Storage Coding
• A new Capacity-Achieving Private Information Retrieval Scheme with (Almost) Optimal File Length for Coded Servers
• On the Fundamental Limit of Private Information Retrieval for Coded Distributed Storage
• Achieving Maximum Distance Separable Private Information Retrieval Capacity With Linear Codes
• An MDS-PIR Capacity-Achieving Protocol for Distributed Storage Using Non-MDS Linear Codes