The Capacity of Symmetric Private Information Retrieval

DOI10.1109/TIT.2018.2848977MaRDI QIDQ4611437zbMATH OpenOpenAlexWikidataFDO

Authors Hua Sun, Syed A. Jafar

Publication date 18 January 2019

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

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

Mathematics Subject Classification ID

Authentication, digital signatures and secret sharing (94A62)

Abstract: Private information retrieval (PIR) is the problem of retrieving as efficiently as possible, one out of $K$ messages from $N$ non-communicating replicated databases (each holds all $K$ messages) while keeping the identity of the desired message index a secret from each individual database. Symmetric PIR (SPIR) is a generalization of PIR to include the requirement that beyond the desired message, the user learns nothing about the other $K-1$ messages. The information theoretic capacity of SPIR (equivalently, the reciprocal of minimum download cost) is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. We show that the capacity of SPIR is $1-1/N$ regardless of the number of messages $K$, if the databases have access to common randomness (not available to the user) that is independent of the messages, in the amount that is at least $1/(N-1)$ bits per desired message bit, and zero otherwise. Extensions to the capacity region of SPIR and the capacity of finite length SPIR are provided.

Cited in

(7)

• Capacity-achieving private information retrieval scheme with a smaller sub-packetization
• Multi-value private information retrieval with colluding databases via trace functions
• Fault-tolerant symmetrically-private information retrieval
• The Capacity of Private Information Retrieval Under Arbitrary Collusion Patterns for Replicated Databases
• On the Storage Cost of Private Information Retrieval
• A survey on single server private information retrieval in a coding theory perspective
• Single server private information retrieval protocols with codes over rings

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

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