PIR Schemes With Small Download Complexity and Low Storage Requirements
PIR Schemes With Small Download Complexity and Low Storage Requirements
复制标题
DOI：
10.1109/tit.2019.2942311
复制
发表时间：
2016-09
影响因子：
2.5
通讯作者：
S. Blackburn;T. Etzion;Maura B. Paterson
中科院分区：
文献类型：
--
作者：
S. Blackburn;T. Etzion;Maura B. Paterson
在由Chor、Goldreich、Kushilevitz和Sudan提出的（信息理论上安全的）私有信息检索（Private information Retrieval， PIR）的经典模型中，用户希望检索存储在一组${n}$服务器上的数据库的一个比特，以这样一种方式，没有任何单个服务器获得关于用户感兴趣的比特的信息。其目的是设计最小化用户和服务器之间总通信的方案。最近，人们开始考虑更现实的模型，其中一组服务器的总存储或每台服务器的存储应该最小化（可能使用分布式存储的技术），并且数据库被分成${R}$ -bit记录和${R}>1$，并且用户希望检索一条记录而不是一个记录。当${R}$很大时，从服务器到用户的下载控制了通信复杂性，因此目标是最小化下载比特的总数。Shah， Rashmi和Ramchandran的研究表明，在最坏的情况下，至少${R}+1$位必须从服务器下载，并提供了满足此限制的PIR方案。Sun和Jafar考虑了一个方案的下载成本，定义为消息长度${R}$与下载的总比特数之比。当${k}$消息数据库由${n}$服务器存储时，它们确定PIR方案（如${R}\rightarrow \infty $）的最佳渐近下载成本。本文提供了PIR方案的下载复杂性的各种限制，将Shah等人的限制推广到服务器数量${n}$有限制的情况，并提供了由于Chor等人的经典技术的链接。本文还提供了一系列PIR方案的结构，这些结构比以前已知的方案更简单或性能更好。这些结构包括实现Sun和Jafar的最佳渐近下载复杂性且上传复杂性显著降低的显式方案，以及从具有平均良好下载复杂性的方案构建具有良好最差情况下载复杂性的方案的一般技术。
In the classical model for (information theoretically secure) Private Information Retrieval (PIR) due to Chor, Goldreich, Kushilevitz and Sudan, a user wishes to retrieve one bit of a database that is stored on a set of ${n}$ servers, in such a way that no individual server gains information about which bit the user is interested in. The aim is to design schemes that minimise the total communication between the user and the servers. More recently, there have been moves to consider more realistic models where the total storage of the set of servers, or the per server storage, should be minimised (possibly using techniques from distributed storage), and where the database is divided into ${R}$ -bit records with ${R}>1$ , and the user wishes to retrieve one record rather than one bit. When ${R}$ is large, downloads from the servers to the user dominate the communication complexity and so the aim is to minimise the total number of downloaded bits. Work of Shah, Rashmi and Ramchandran shows that at least ${R}+1$ bits must be downloaded from servers in the worst case, and provides PIR schemes meeting this bound. Sun and Jafar have considered the download cost of a scheme, defined as the ratio of the message length ${R}$ and the total number of bits downloaded. They determine the best asymptotic download cost of a PIR scheme (as ${R}\rightarrow \infty $ ) when a database of ${k}$ messages is stored by ${n}$ servers. This paper provides various bounds on the download complexity of a PIR scheme, generalising those of Shah et al. to the case when the number ${n}$ of servers is bounded, and providing links with classical techniques due to Chor et al. The paper also provides a range of constructions for PIR schemes that are either simpler or perform better than previously known schemes. These constructions include explicit schemes that achieve the best asymptotic download complexity of Sun and Jafar with significantly lower upload complexity, and general techniques for constructing a scheme with good worst case download complexity from a scheme with good download complexity on average.