The Capacity of Private Information Retrieval From Coded Databases

DOI10.1109/TIT.2018.2791994MaRDI QIDQ4566755zbMATH OpenOpenAlexWikidataFDO

Authors Karim Banawan, Sennur Ulukus

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/1609.08138

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Authentication, digital signatures and secret sharing (94A62)

Abstract: We consider the problem of private information retrieval (PIR) over a distributed storage system. The storage system consists of $N$ non-colluding databases, each storing a coded version of $M$ messages. In the PIR problem, the user wishes to retrieve one of the available messages without revealing the message identity to any individual database. We derive the information-theoretic capacity of this problem, which is defined as the maximum number of bits of the desired message that can be privately retrieved per one bit of downloaded information. We show that the PIR capacity in this case is $C=left(1+fracKN+frac{K}^2{N}^2+cdots+frac{K}^{M-1}{N}^{M-1}ight{)}^{-1}=(1+R_c+R_c^2+cdots+R_c^{M-1}{)}^{-1}=frac1-R_{c}1-R_c^M$, where $R_c$ is the rate of the $(N,K)$ code used. The capacity is a function of the code rate and the number of messages only regardless of the explicit structure of the storage code. The result implies a fundamental tradeoff between the optimal retrieval cost and the storage cost. The result generalizes the achievability and converse results for the classical PIR with replicating databases to the case of coded databases.

Cited in

(11)

• 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
• Private information retrieval from coded databases with colluding servers
• 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
• Private information retrieval schemes using cyclic codes
• Private information retrieval from locally repairable databases with colluding servers
• 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

This page was built for publication: The Capacity of Private Information Retrieval From Coded Databases

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