The Capacity of Private Information Retrieval

DOI10.1109/TIT.2017.2689028zbMATH Open1370.94567arXiv1602.09134MaRDI QIDQ5358554FDOQ5358554

Syed A. Jafar, Hua Sun

Publication date: 21 September 2017

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

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.

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

Mathematics Subject Classification ID

Authentication, digital signatures and secret sharing (94A62)

Cited In (11)

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

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)