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/isit.2019.8849542
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
Ruida Zhou;Chao Tian;Tie Liu;Hua Sun
中科院分区：
文献类型：
--
作者：
Ruida Zhou;Chao Tian;Tie Liu;Hua Sun
我们考虑构建容量实现的线性码的私人信息检索（PIR）从N个非共谋数据库，其中每个消息是使用最大距离可分离（MDS）码编码，使它可以从任何T数据库的内容阅读恢复的最小消息大小。它示出的最小消息大小（有时也被称为子分组化水平）是显着的，事实上是指数，低于以前认为的。更准确地说，当K > T/ gcd（N，T）时，其中K是系统中消息的总数，gcd（·，·）表示最大公约数，我们通过提供新的代码结构和匹配的匡威，建立最小消息大小为lcm（N-T，T），其中lcm（·，·）表示最小公倍数。另一方面，当K是小的，我们表明，它实际上是可能的设计代码的消息大小甚至小于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 reading the contents of any T databases. It is shown that the minimum message size (sometimes also referred to as the sub-packetization level) is significantly, in fact exponentially, lower than previously believed. More precisely, when K > T/ gcd(N, T ) where K is the total number of message in the system and gcd(•, •) means the greatest common divisor, we establish, by providing both a novel code construction 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 ).