The Asymptotic Capacity of Private Search

DOI10.1109/TIT.2020.2977082MaRDI QIDQ5124458zbMATH OpenOpenAlexFDO

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)

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)

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.

Cited in

(3)

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

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)