Multi-Message Private Information Retrieval: Capacity Results and Near-Optimal Schemes

DOI10.1109/TIT.2018.2828310MaRDI QIDQ4682956zbMATH OpenOpenAlexWikidataFDO

Authors Karim Banawan, Sennur Ulukus

Publication date 19 September 2018

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

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

Mathematics Subject Classification ID

Searching and sorting (68P10) Measures of information, entropy (94A17)

Abstract: We consider the problem of multi-message private information retrieval (MPIR) from $N$ non-communicating replicated databases. In MPIR, the user is interested in retrieving $P$ messages out of $M$ stored messages without leaking the identity of the retrieved messages. The information-theoretic sum capacity of MPIR $C_s^P$ is the maximum number of desired message symbols that can be retrieved privately per downloaded symbol. For the case $PgeqfracM2$, we determine the exact sum capacity of MPIR as $C_s^P=frac11+fracM-PPN$. The achievable scheme in this case is based on downloading MDS-coded mixtures of all messages. For $PleqfracM2$, we develop lower and upper bounds for all $M,P,N$. These bounds match if the total number of messages $M$ is an integer multiple of the number of desired messages $P$, i.e., $fracMPinmathbbN$. In this case, $C_s^P=frac1-frac1N1-(frac1N{)}^{M/P}$. The achievable scheme in this case generalizes the single-message capacity achieving scheme to have unbalanced number of stages per round of download. For all the remaining cases, the difference between the lower and upper bound is at most $0.0082$, which occurs for $M=5$, $P=2$, $N=2$. Our results indicate that joint retrieval of desired messages is more efficient than successive use of single-message retrieval schemes.

Cited in

(3)

• Capacity-achieving private information retrieval scheme with a smaller sub-packetization
• Multi-value private information retrieval with colluding databases via trace functions
• Multi-query Computationally-Private Information Retrieval with Constant Communication Rate

This page was built for publication: Multi-Message Private Information Retrieval: Capacity Results and Near-Optimal Schemes

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