The DOI matches its Crossref record; 28 of the 28 references it cites were found in a registry or an index.
The Capacity of Private Information Retrieval
Abstract
In the private information retrieval (PIR) problem, a user wishes to retrieve, as efficiently as possible, one out of K messages from N non-communicating databases (each holds all K messages) while revealing nothing about the identity of the desired message index to any individual database. The information theoretic capacity of PIR is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. For K messages and N databases, we show that the PIR capacity is (1+1/N+1/N2+· · ·+1/NK-1)-1. A remarkable feature of the capacity achieving scheme is that if we eliminate any subset of messages (by setting the message symbols to zero), the resulting scheme also achieves the PIR capacity for the remaining subset of messages.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Shamir, A. (1979) · Communications of the ACM · doi:10.1145/359168.359176 · Cited by 13,756
Ahlswede, R., Cai, N., Li, S.-Y. R., & Yeung, R. W. (2000) · IEEE Transactions on Information Theory · doi:10.1109/18.850663 · Cited by 7,814
Chor, B., Kushilevitz, E., Goldreich, O., & Sudan, M. (1998) · Journal of the ACM · doi:10.1145/293347.293350 · Cited by 1,612
Chor, B., Goldreich, O., Kushilevitz, E., & Sudan, M. (2002) · Proceedings of IEEE 36th Annual Foundations of Computer Science · doi:10.1109/sfcs.1995.492461 · Cited by 1,116
On the Locality of Codeword Symbols
Gopalan, P., Huang, C., Simitci, H., & Yekhanin, S. (2012) · IEEE Transactions on Information Theory · doi:10.1109/tit.2012.2208937 · Cited by 831
A Survey on Network Codes for Distributed Storage
Dimakis, A. G., Ramchandran, K., Wu, Y., et al. (2011) · Proceedings of the IEEE · doi:10.1109/jproc.2010.2096170 · Cited by 639
Protecting data privacy in private information retrieval schemes
Gertner, Y., Ishai, Y., Kushilevitz, E., & Malkin, T. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276723 · Cited by 445
Birk, Y., & Kol, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.874540 · Cited by 324
Topological Interference Management Through Index Coding
Jafar, S. A. (2014) · IEEE Transactions on Information Theory · doi:10.1109/tit.2013.2285151 · Cited by 305
Self-citationOn the Index Coding Problem and Its Relation to Network Coding and Matroid Theory
El Rouayheb, S., Sprintson, A., & Georghiades, C. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2048502 · Cited by 293
Aiming Perfectly in the Dark-Blind Interference Alignment Through Staggered Antenna Switching
Gou, T., Wang, C., & Jafar, S. A. (2011) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2011.2129517 · Cited by 255
Self-citationA Survey of Single-Database Private Information Retrieval: Techniques and Applications
Ostrovsky, R., & Skeith, W. E. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-71677-8_26 · Cited by 246
Hiding instances in multioracle queries
Beaver, D., & Feigenbaum, J. (1990) · Lecture Notes in Computer Science · doi:10.1007/3-540-52282-4_30 · Cited by 235
Jafar, S. A. (2012) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2012.2187877 · Cited by 224
Self-citationBreaking the O(n/sup 1/(2k-1)/) barrier for information-theoretic Private Information Retrieval
Beimel, A., Ishai, Y., Kushilevitz, E., & Raymond, J.-F. (2003) · The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. · doi:10.1109/sfcs.2002.1181949 · Cited by 218
A Survey on Private Information Retrieval
Gasarch, W. I. (2004) · Cited by 207
Yekhanin, S. (2010) · Communications of the ACM · doi:10.1145/1721654.1721674 · Cited by 202
One extra bit of download ensures perfectly private information retrieval
Shah, N. B., Rashmi, K. V., & Ramchandran, K. (2014) · 2014 IEEE International Symposium on Information Theory · doi:10.1109/isit.2014.6874954 · Cited by 201
1Private Information Retrieval for Coded StoragePreprint
Chan, T., Ho, S., & Yamamoto, H. (2016) · Cited by 173
Upper bound on the communication complexity of private information retrieval
Ambainis, A. (1997) · Lecture Notes in Computer Science · doi:10.1007/3-540-63165-8_196 · Cited by 172
Private information retrieval for coded storage
Chan, T. H., Ho, S.-W., & Yamamoto, H. (2015) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2015.7282975 · Cited by 136
General constructions for information-theoretic private information retrieval
Beimel, A., Ishai, Y., & Eyal Kushilevitz, Z. (2005) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2005.03.002 · Cited by 107
On hiding information from an oracle
Abadi, M., Feigenbaum, J., & Kilian, J. (1987) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/28395.28417 · Cited by 87
Locally random reductions: Improvements and applications
Beaver, D., Feigenbaum, J., Kilian, J., & Rogaway, P. (1997) · Journal of Cryptology · doi:10.1007/s001459900017 · Cited by 73
Share Conversion and Private Information Retrieval
Beimel, A., Ishai, Y., Kushilevitz, E., & Orlov, I. (2012) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2012.23 · Cited by 68
Locally Decodable Codes and Private Information Retrieval Schemes
Yekhanin, S. (2010) · Information security and cryptography · doi:10.1007/978-3-642-14358-8 · Cited by 51
Feigenbaum, J. (2007) · Springer eBooks · doi:10.1007/3-540-39799-x_38 · Cited by 34
Storage Capacity of Repairable Networks
Mazumdar, A. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2472521 · Cited by 34
Cited by
The Capacity of Private Information Retrieval From Coded Databases
Banawan, K., & Ulukus, S. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2018.2791994 · Cited by 362
The Capacity of Robust Private Information Retrieval With Colluding Databases
Sun, H., & Jafar, S. A. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2777490 · Cited by 312
Self-citationPrivate information retrieval with side information: The single server case
Kadhe, S., Garcia, B., Heidarzadeh, A., Rouayheb, S. E., & Sprintson, A. (2017) · 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton) · doi:10.1109/allerton.2017.8262860 · Cited by 38
Metadata
- Authors
- Sun, H., & Jafar, S. A.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2017-07
- Volume
- 63
- Issue
- 7
- Pages
- 4075-4088
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2599749253
- Cited by
- 447
- References
- 28
- FWCI
- 34.77
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.