The asymptotic capacity of private search

Z Chen, Z Wang, SA Jafar - IEEE Transactions on Information …, 2020 - ieeexplore.ieee.org
IEEE Transactions on Information Theory, 2020ieeexplore.ieee.org
The private search problem is introduced, where a dataset comprised of L iid 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 …
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.
ieeexplore.ieee.org
以上显示的是最相近的搜索结果。 查看全部搜索结果