Linear symmetric private information retrieval for MDS coded distributed storage with colluding servers
Linear symmetric private information retrieval for MDS coded distributed storage with colluding servers
复制标题
DOI：
10.1109/itw.2017.8277997
复制
发表时间：
2017-08
期刊：
影响因子：
--
通讯作者：
Qiwen Wang;M. Skoglund
中科院分区：
文献类型：
--
作者：
Qiwen Wang;M. Skoglund
研究了分布式存储在共谋服务器之间的编码数据库的对称私有信息检索（SPIR）问题。具体地，数据库包括K个文件，使用(N，M)-MDS存储代码存储在N个服务器之间。用户希望通过与 N 个服务器通信来从数据库中检索一个文件，而不向任何服务器透露所需文件的身份。此外，用户不会了解数据库中其他 K-1 个文件。在 T 共谋 SPIR 问题（因此称为 TSPIR）中，N 个服务器中的任何 T 个服务器都可能共谋，也就是说，它们可能会与用户进行交互以猜测所请求文件的身份。我们表明，对于线性方案，MDS-TSPIR 问题的信息论容量（定义为每个下载位检索的所需文件的最大信息位数）等于 1 − M+T−1/N，如果服务器共享公共随机性（用户不可用），数量至少为 M+T−1/N−M−T+1 倍的文件大小。否则，容量为零。
The problem of symmetric private information retrieval (SPIR) from a coded database which is distributively stored among colluding servers is studied. Specifically, the database comprises K files, which are stored among N servers using an (N, M)-MDS storage code. A user wants to retrieve one file from the database by communicating with the N servers, without revealing the identity of the desired file to any server. Furthermore, the user shall learn nothing about the other K − 1 files in the database. In the T-colluding SPIR problem (hence called TSPIR), any T out of N servers may collude, that is, they may communicate their interactions with the user to guess the identity of the requested file. We show that for linear schemes, the information-theoretic capacity of the MDS-TSPIR problem, defined as the maximum number of information bits of the desired file retrieved per downloaded bit, equals 1 − M+T−1/N, if the servers share common randomness (unavailable at the user) with amount at least M+T−1/N−M−T+1 times the file size. Otherwise, the capacity equals zero.