The Capacity of Robust Private Information Retrieval with Colluding Databases

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 $M\ge N$ databases, out of which any $M-N$ may fail to respond. For $K$ messages and $M\ge N$ 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}\right)}^{-1}$. The result includes as special cases the capacity of PIR without robustness ($M=N$) or $T$-privacy constraints ($T=1$).

Cited by in corpus (16)

• Private Information Retrieval from Coded Databases with Colluding Servers
• Linear Symmetric Private Information Retrieval for MDS Coded Distributed Storage with Colluding Servers
• Private Information Retrieval from MDS Coded Databases with Colluding Servers under Several Variant Models
• A general private information retrieval scheme for MDS coded databases with colluding servers
• Private Information Retrieval from Storage Constrained Databases -- Coded Caching meets PIR
• Private Information Retrieval Schemes for Coded Data with Arbitrary Collusion Patterns
• The Capacity of Private Computation
• The Capacity of Private Information Retrieval with Partially Known Private Side Information
• Multiround Private Information Retrieval: Capacity and Storage Overhead
• Multi-Message Private Information Retrieval: Capacity Results and Near-Optimal Schemes
• Secure Symmetric Private Information Retrieval from Colluding Databases with Adversaries
• Fundamental Limits of Cache-Aided Private Information Retrieval with Unknown and Uncoded Prefetching
• Optimal Download Cost of Private Information Retrieval for Arbitrary Message Length
• The Asymptotic Capacity of Private Search
• Private Information Retrieval from MDS Coded Data with Colluding Servers: Settling a Conjecture by Freij-Hollanti et al.
• Cache-Aided Private Information Retrieval with Partially Known Uncoded Prefetching: Fundamental Limits