The Asymptotic Capacity of Private Search

DOI10.1109/TIT.2020.2977082zbMATH Open1446.68048arXiv1801.05768OpenAlexW3010196816MaRDI QIDQ5124458FDOQ5124458

Authors: Zhen Chen, Zhiying Wang, Syed A. Jafar 

Publication date: 29 September 2020

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: The private search problem is introduced, where a dataset comprised of $L$ i.i.d. records is replicated across $N$ non-colluding servers, each record takes values uniformly from an alphabet of size $K$, 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. 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 as the scope of private search is further generalized to allow approximate (OR) search over a number of realizations that grows with $K$. The results are based on the asymptotic behavior of a new converse bound for private information retrieval with arbitrarily dependent messages.

Full work available at URL: https://arxiv.org/abs/1801.05768

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Searching and sorting (68P10) Authentication, digital signatures and secret sharing (94A62) Privacy of data (68P27)

Cited In (3)

• Private approximation of search problems
• Private Approximation of Search Problems
• Coefficient bounds for certain two subclasses of bi-univalent functions

This page was built for publication: The Asymptotic Capacity of Private Search

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5124458)