The Capacity of Private Information Retrieval

DOI10.1109/TIT.2017.2689028MaRDI QIDQ5358554zbMATH OpenFDO

Authors Hua Sun, Syed A. Jafar

Publication date 21 September 2017

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

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

Mathematics Subject Classification ID

Authentication, digital signatures and secret sharing (94A62)

Abstract: In the private information retrieval (PIR) problem a user wishes to retrieve, as efficiently as possible, one out of $K$ messages from $N$ non-communicating databases (each holds all $K$ messages) while revealing nothing about the identity of the desired message index to any individual database. The information theoretic capacity of PIR is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. For $K$ messages and $N$ databases, we show that the PIR capacity is $(1+1/N+1/N^2+cdots+1/N^{K-1}{)}^{-1}$. A remarkable feature of the capacity achieving scheme is that if we eliminate any subset of messages (by setting the message symbols to zero), the resulting scheme also achieves the PIR capacity for the remaining subset of messages.

Cited in

(11)

• Private information and the `Information function': A survey of possible uses
• A general private information retrieval scheme for MDS coded databases with colluding servers
• Private information retrieval from locally repairable databases with colluding servers
• On the Storage Cost of Private Information Retrieval
• Multi-value private information retrieval with colluding databases via trace functions
• Private information retrieval from coded databases with colluding servers
• Capacity-achieving private information retrieval scheme with a smaller sub-packetization
• The Capacity of Private Information Retrieval Under Arbitrary Collusion Patterns for Replicated Databases
• On the optimal communication complexity of error-correcting multi-server PIR
• Tradeoff Relations Between Accessible Information, Informational Power, and Purity
• Private information retrieval schemes using cyclic codes

This page was built for publication: The Capacity of Private Information Retrieval

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