TY - GEN
T1 - On the Capacity of Leaky Private Information Retrieval
AU - Samy, Islam
AU - Tandon, Ravi
AU - Lazos, Loukas
N1 - Funding Information:
This work was supported in part by NSF grants CNS 1813401, CAREER 1651491, and CNS 1715947.
Publisher Copyright:
© 2019 IEEE.
PY - 2019/7
Y1 - 2019/7
N2 - Private information retrieval (PIR) allows users to retrieve data from databases without revealing the identity of that data. An extensive body of works has investigated efficient schemes to achieve computational and information-theoretic privacy. The latter guarantees that no information is revealed to the databases, irrespective of their computational power. Although information-theoretic PIR (IT-PIR) provides a strong privacy guarantee, it can be too taxing for certain applications. In this paper, we initiate the study of leaky private information retrieval (L-PIR), where a bounded amount of privacy leakage is allowed and measured through a parameter ϵ. The classical IT-PIR formulation is obtained by setting ϵ = 0, and for ϵ > 0, we explore the opportunities offered for reducing the download cost. We derive new upper and lower bounds on the download cost of L-PIR for any arbitrary ϵ, any number of messages K, and for N = 2 databases.
AB - Private information retrieval (PIR) allows users to retrieve data from databases without revealing the identity of that data. An extensive body of works has investigated efficient schemes to achieve computational and information-theoretic privacy. The latter guarantees that no information is revealed to the databases, irrespective of their computational power. Although information-theoretic PIR (IT-PIR) provides a strong privacy guarantee, it can be too taxing for certain applications. In this paper, we initiate the study of leaky private information retrieval (L-PIR), where a bounded amount of privacy leakage is allowed and measured through a parameter ϵ. The classical IT-PIR formulation is obtained by setting ϵ = 0, and for ϵ > 0, we explore the opportunities offered for reducing the download cost. We derive new upper and lower bounds on the download cost of L-PIR for any arbitrary ϵ, any number of messages K, and for N = 2 databases.
UR - http://www.scopus.com/inward/record.url?scp=85073143805&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85073143805&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2019.8849676
DO - 10.1109/ISIT.2019.8849676
M3 - Conference contribution
AN - SCOPUS:85073143805
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 1262
EP - 1266
BT - 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2019 IEEE International Symposium on Information Theory, ISIT 2019
Y2 - 7 July 2019 through 12 July 2019
ER -