Capacity-Achieving Private Information Retrieval Codes From MDS-Coded Databases With Minimum Message Size
Capacity-Achieving Private Information Retrieval Codes From MDS-Coded Databases With Minimum Message Size
复制标题
DOI：
10.1109/tit.2020.2977073
复制
发表时间：
2019-03
影响因子：
2.5
通讯作者：
Ruida Zhou;C. Tian;Hua Sun;Tie Liu
中科院分区：
文献类型：
--
作者：
Ruida Zhou;C. Tian;Hua Sun;Tie Liu
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}/\text{gcd}({N},{T})$ where K is the total number of messages in the system and $\gcd (\cdot,\cdot)$ means the greatest common divisor, we establish, by providing both novel code constructions and a matching converse, the minimum message size as ${{\textrm {lcm}}}({N}-{T},{T})$ , where ${{\textrm {lcm}}}(\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 ${{\textrm {lcm}}}({N}-{T},{T})$ .
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}/\text{gcd}({N},{T})$ where K is the total number of messages in the system and $\gcd (\cdot,\cdot)$ means the greatest common divisor, we establish, by providing both novel code constructions and a matching converse, the minimum message size as ${{\textrm {lcm}}}({N}-{T},{T})$ , where ${{\textrm {lcm}}}(\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 ${{\textrm {lcm}}}({N}-{T},{T})$ .