The Capacity of Robust Private Information Retrieval With Colluding Databases

DOI10.1109/TIT.2017.2777490MaRDI QIDQ4569188zbMATH OpenOpenAlexFDO

Authors Hua Sun, Syed A. Jafar

Publication date 27 June 2018

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

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

Mathematics Subject Classification ID

Database theory (68P15) Cryptography (94A60)

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. The information theoretic capacity of PIR (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. $T$-private PIR is a generalization of PIR to include the requirement that even if any $T$ of the $N$ databases collude, the identity of the retrieved message remains completely unknown to them. Robust PIR is another generalization that refers to the scenario where we have $MgeqN$ databases, out of which any $M-N$ may fail to respond. For $K$ messages and $MgeqN$ databases out of which at least some $N$ must respond, we show that the capacity of $T$-private and Robust PIR is $left(1+T/N+T^2/N^2+cdots+T^{K-1}/N^{K-1}ight{)}^{-1}$. The result includes as special cases the capacity of PIR without robustness ($M=N$) or $T$-privacy constraints ($T=1$).

Cited in

(15)

• Capacity-achieving private information retrieval scheme with a smaller sub-packetization
• Multi-value private information retrieval with colluding databases via trace functions
• A general private information retrieval scheme for MDS coded databases with colluding servers
• Robust information-theoretic private information retrieval
• Private information retrieval from coded databases with colluding servers
• The Capacity of Private Information Retrieval Under Arbitrary Collusion Patterns for Replicated Databases
• A survey on single server private information retrieval in a coding theory perspective
• Private information retrieval schemes using cyclic codes
• On the optimal communication complexity of error-correcting multi-server PIR
• Private information retrieval from locally repairable databases with colluding servers
• Committed private information retrieval
• Single server private information retrieval protocols with codes over rings
• The Schur product of evaluation codes and its application to CSS-T quantum codes and private information retrieval
• On the definition of malicious private information retrieval
• Extended results on privacy against coalitions of users in user-private information retrieval protocols

This page was built for publication: The Capacity of Robust Private Information Retrieval With Colluding Databases

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