The Asymptotic Capacity of Private Search
The Asymptotic Capacity of Private Search
复制标题
DOI：
10.1109/tit.2020.2977082
复制
发表时间：
2020-03
影响因子：
2.5
通讯作者：
Zhen Chen;Zhiying Wang;S. Jafar
中科院分区：
文献类型：
--
作者：
Zhen Chen;Zhiying Wang;S. Jafar
引入了私有搜索问题，其中数据集由$L$ i.i.d.记录被复制到$N$个非共谋服务器上，并且用户希望搜索与私人选择的值相匹配的所有记录，而不向任何单独的服务器泄露关于所选择的值的任何信息。每个记录包含$P$符号，并且每个符号从大小为$K$的字母表中统一且独立地取值。考虑到现代数据集中的大量记录，假设$L$比字母表大小$K$大得多。私有搜索的容量是每比特下载可以检索到的所需信息的最大比特数。私有搜索的渐近容量（大K）为1 -1/N，甚至当私有搜索的范围进一步推广到OR搜索、AND搜索、NOT搜索和序列搜索时也是如此.结果是基于一个新的匡威界的渐近行为的私人信息检索与任意依赖的消息。渐近行为也适用于$T$ -合谋服务器或$（N，T）$ -MDS编码服务器。
The private search problem is introduced, where a dataset comprised of $L$ i.i.d. records is replicated across $N$ non-colluding servers, and a user wishes to search for all records that match a privately chosen value, without revealing any information about the chosen value to any individual server. Each record contains $P$ symbols, and each symbol takes values uniformly and independently from an alphabet of size $K$ . Considering the large number of records in modern datasets, it is assumed that $L$ is much larger than the alphabet size $K$ . The capacity of private search is the maximum number of bits of desired information that can be retrieved per bit of download. The asymptotic (large $K$ ) capacity of private search is shown to be $1-1/N$ , even when the scope of private search is further generalized to allow OR search, AND search, NOT search and sequence search. The results are based on the asymptotic behavior of a new converse bound for private information retrieval with arbitrarily dependent messages. The asymptotic behavior is also applicable to $T$ -colluding servers or $(N, T)$ -MDS coded servers.