Capacity-Achieving Private Information Retrieval Codes From MDS-Coded Databases With Minimum Message Size

DOI10.1109/TIT.2020.2977073MaRDI QIDQ5124474zbMATH OpenFDO

Authors Ruida Zhou, Chao Tian, Hua Sun, Tie Liu

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/1903.08229

Mathematics Subject Classification ID

Database theory (68P15) Authentication, digital signatures and secret sharing (94A62) Decoding (94B35)

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/extbfgcd(N,T)$ where $K$ is the total number of messages in the system and $extbfgcd(cdot,cdot)$ means the greatest common divisor, we establish, by providing both novel code constructions and a matching converse, the minimum message size as $extbflcm(N-T,T)$, where $extbflcm(cdot,cdot)$ 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 $extbflcm(N-T,T)$.

This page was built for publication: Capacity-Achieving Private Information Retrieval Codes From MDS-Coded Databases With Minimum Message Size

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