Private information retrieval (PIR) code

Private information retrieval (PIR) code[1,2]

Description

A code used to obtain information from several servers privately, i.e., without the servers knowing what information was obtained.

A \(k\)-server PIR code is a block code for which one can recover any coordinate of a codeword from \(k\) disjoint sets of coordinates of the codeword [3].

Notes

See Ref. [2,4].

Parent

Block code

Cousins

Multiplicity code — Multiplicity codes can be used to construct PIR codes [5].
Batch code — Batch and PIR codes are related [6,7].
Locally recoverable code (LRC) — LRCs and PIR codes are related [3,7]: LRCs are designed to recover a codeword coordinate from a small set of other codeword coordinates, while PIR codes are designed to recover from many disjoint sets of arbitrary size [3].
Locally decodable code (LDC) — Any smooth LDC yields a PIR scheme [8]; see also Ref. [9].
Reed-Solomon (RS) code — RS codes can be used to construct PIR codes [10].

References

[1]: B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan, “Private information retrieval”, Journal of the ACM 45, 965 (1998) DOI
[2]: B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan, “Private information retrieval”, Proceedings of IEEE 36th Annual Foundations of Computer Science DOI
[3]: A. Fazeli, A. Vardy, and E. Yaakobi, “PIR with Low Storage Overhead: Coding instead of Replication”, (2015) arXiv:1505.06241
[4]: I. F. Blake, Essays on Coding Theory (Cambridge University Press, 2024) DOI
[5]: H. Asi and E. Yaakobi, “Nearly Optimal Constructions of PIR and Batch Codes”, (2017) arXiv:1701.07206
[6]: R. Henry, “Polynomial Batch Codes for Efficient IT-PIR”, Proceedings on Privacy Enhancing Technologies 2016, 202 (2016) DOI
[7]: V. Skachek, “Batch and PIR Codes and Their Connections to Locally Repairable Codes”, (2017) arXiv:1611.09914
[8]: H. Zhang, E. Yaakobi, and N. Silberstein, “Multiset Combinatorial Batch Codes”, (2017) arXiv:1701.02708
[9]: S. Yekhanin, Locally Decodable Codes and Private Information Retrieval Schemes (Springer Berlin Heidelberg, 2010) DOI
[10]: B. Sasidharan and E. Viterbo, “Private Data Access in Blockchain Systems Employing Coded Sharding”, 2021 IEEE International Symposium on Information Theory (ISIT) 2684 (2021) DOI

Page edit log

Victor V. Albert (2024-08-18) — most recent

Cite as:

“Private information retrieval (PIR) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/pir

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/properties/block/info_retrieval/pir.yml.