PIR Array Codes With Optimal Virtual Server Rate

DOI10.1109/TIT.2019.2920975zbMATH Open1432.94162arXiv1607.00235OpenAlexW2973003795WikidataQ127736366 ScholiaQ127736366MaRDI QIDQ5211432FDOQ5211432

Authors: Simon R. Blackburn, Tuvi Etzion 

Publication date: 28 January 2020

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

Abstract: There has been much recent interest in Private information Retrieval (PIR) in models where a database is stored across several servers using coding techniques from distributed storage, rather than being simply replicated. In particular, a recent breakthrough result of Fazelli, Vardy and Yaakobi introduces the notion of a PIR code and a PIR array code, and uses this notion to produce efficient PIR protocols. In this paper we are interested in designing PIR array codes. We consider the case when we have $m$ servers, with each server storing a fraction $(1/s)$ of the bits of the database; here $s$ is a fixed rational number with $s>1$. A PIR array code with the $k$-PIR property enables a $k$-server PIR protocol (with $kleqm$) to be emulated on $m$ servers, with the overall storage requirements of the protocol being reduced. The communication complexity of a PIR protocol reduces as $k$ grows, so the virtual server rate, defined to be $k/m$, is an important parameter. We study the maximum virtual server rate of a PIR array code with the $k$-PIR property. We present upper bounds on the achievable virtual server rate, some constructions, and ideas how to obtain PIR array codes with the highest possible virtual server rate. In particular, we present constructions that asymptotically meet our upper bounds, and the exact largest virtual server rate is obtained when $1<sleq2$. A $k$-PIR code (and similarly a $k$-PIR array code) is also a locally repairable code with symbol availability $k-1$. Such a code ensures $k$ parallel reads for each information symbol. So the virtual server rate is very closely related to the symbol availability of the code when used as a locally repairable code. The results of this paper are discussed also in this context, where subspace codes also have an important role.

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

Recommendations

• Nearly Optimal Constructions of PIR and Batch Codes
• Array Codes for Functional PIR and Batch Codes
• PIR codes from combinatorial structures
• On the privacy of a code-based single-server computational PIR scheme
• On Private Information Retrieval Array Codes
• PIR codes with short block length
• On the optimal communication complexity of error-correcting multi-server PIR
• The Optimal Sub-Packetization of Linear Capacity-Achieving PIR Schemes With Colluding Servers

zbMATH Keywords

private information retrieval (PIR)PIR array code

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Linear codes (general theory) (94B05) Privacy of data (68P27)

Cited In (2)

• A general private information retrieval scheme for MDS coded databases with colluding servers
• Locality via partially lifted codes

This page was built for publication: PIR Array Codes With Optimal Virtual Server Rate

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