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 et al., “Private information retrieval”, Journal of the ACM 45, 965 (1998) DOI
[2]: B. Chor et al., “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) (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.