Private information retrieval
Open accessAbstract
Publicly accessible databases are an indispensable resource for retrieving up-to-date information. But they also pose a significant risk to the privacy of the user, since a curious database operator can follow the user's queries and infer what the user is after. Indeed, in cases where the users' intentions are to be kept secret, users are often cautious about accessing the database. It can be shown that when accessing a single database, to completely guarantee the privacy of the user, the whole database should be down-loaded; namely n bits should be communicated (where n is the number of bits in the database). In this work, we investigate whether by replicating the database, more efficient solutions to the private retrieval problem can be obtained. We describe schemes that enable a user to access k replicated copies of a database ( k ≥2) and privately retrieve information stored in the database. This means that each individual server (holding a replicated copy of the database) gets no information on the identity of the item retrieved by the user. Our schemes use the replication to gain substantial saving. In particular, we present a two-server scheme with communication complexity O(n 1/3 ).
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
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.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Hyperparameter optimization (HPO) has a long history under AutoML, but it mainly concerns improving model accuracy rather than communication and computing efficacy for mobile devices.
“Hyperparameter optimization (HPO) has a long history under the framework of AutoML [395, 273, 277], but it mainly concerns how to improve the model accuracy [64, 426, 374, 180] rather than communication and computing efficacy for mobile devices.”
From Advances and Open Problems in Federated Learning (2021) · cites this paper as [273]
The Introduction and §2.4 (pages not supplied) discuss private information retrieval, including its communication and computational complexity. Searches for hyperparameter optimization, AutoML, model accuracy, and mobile devices found no passage addressing what HPO mainly concerns. The paper’s focus on communication complexity does not, by itself, contradict a claim about HPO. (LLM, conf=0.76)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot the international journal of robotics research and application · doi:10.1108/ir.1999.04926fae.001 · Cited by 39,228 · see citing works
Information Theory and Reliable Communication.
Lee, P. M., & Gallager, R. T. (1970) · Journal of the Royal Statistical Society Series A (General) · doi:10.2307/2344305 · Cited by 5,559 · see citing works
Information Theory and Reliable Communication
Bell, D. A. (1969) · Electronics and Power · doi:10.1049/ep.1969.0319 · Cited by 4,023 · see citing works
Cryptography and data security
Denning, D. E. (1982) · Calhoun: The Naval Postgraduate School Institutional Archive (Naval Postgraduate School) · Cited by 1,912 · see citing works
(1978) · Cited by 1,875 · see citing works
Software protection and simulation on oblivious RAMs
Goldreich, O., & Ostrovsky, R. (1996) · Journal of the ACM · doi:10.1145/233551.233553 · Cited by 1,630 · see citing works
Self-citationChor, B., Goldreich, O., Eyal Kushilevitz, Z., & Sudan, M. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1995.492461 · Cited by 1,116 · see citing works
Self-citationSecurity-control methods for statistical databases: a comparative study
Adam, N. R., & Worthmann, J. C. (1989) · ACM Computing Surveys · doi:10.1145/76894.76895 · Cited by 975 · see citing works
Replication is not needed: single database, computationally-private information retrieval
Eyal Kushilevitz, Z., & Ostrovsky, R. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646125 · Cited by 933 · see citing works
Distributed Databases: Principles and Systems
Ceri, S., & Pelagatti, G. (1984) · CERN Document Server (European Organization for Nuclear Research) · Cited by 713 · see citing works
Checking computations in polylogarithmic time
Babai, L., Fortnow, L., Levin, L. A., & Szegedy, M. (1991) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/103418.103428 · Cited by 627 · see citing works
Non-deterministic exponential time has two-prover interactive protocols
Babai, L., Fortnow, L., & Lund, C. (1992) · Computational Complexity · doi:10.1007/bf01200430 · Cited by 528 · see citing works
Foundations of secure computation
DeMillo, R. A., Lipton, R. J., Dobkin, D., & Jones, A. K. (1978) · SMARTech Repository (Georgia Institute of Technology) · Cited by 462 · see citing works
Protecting data privacy in private information retrieval schemes
Gertner, Y., Ishai, Y., Eyal Kushilevitz, Z., & Malkin, T. (1998) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/276698.276723 · Cited by 449 · see citing works
Principles of Data Base Systems
Ullman, J. D. (1980) · Cumulative Index of Computer Aided Architectural Design · Cited by 426 · see citing works
Approximating clique is almost NP-complete
Feige, U., Goldwasser, S., Lovász, L., et al. (2002) · doi:10.1109/sfcs.1991.185341 · Cited by 397 · see citing works
Computationally private information retrieval (extended abstract)
Chor, B., & Gilboa, N. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258609 · Cited by 249 · see citing works
Self-citationHiding instances in multioracle queries
Beaver, D., & Joan Feigenbaum, A. (1990) · Lecture notes in computer science · doi:10.1007/3-540-52282-4_30 · Cited by 237 · see citing works
Private information storage (extended abstract)
Ostrovsky, R., & Shoup, V. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258606 · Cited by 223 · see citing works
Dobkin, D., Jones, A. K., & Lipton, R. J. (1979) · ACM Transactions on Database Systems · doi:10.1145/320064.320068 · Cited by 203 · see citing works
On hiding information from an oracle
Abadi, M., Feigenbaum, J., & Kilian, J. (1989) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(89)90018-4 · Cited by 202 · see citing works
Algebraic methods for interactive proof systems
Lund, C., Fortnow, L., Karloff, H. J., et al. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/fscs.1990.89518 · Cited by 195 · see citing works
Private Information Retrieval by Keywords
Chor, B., Gilboa, N., & Naor, M. (1997) · Cited by 175 · see citing works
Self-citationUpper 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 173 · see citing works
Private Information StoragePreprint
Ostrovsky, R., & Shoup, V. (1996) · IACR Cryptology ePrint Archive · Cited by 97 · see citing works
Security with Low Communication Overhead
Beaver, D., Joan Feigenbaum, A., Kilian, J., & Rogaway, P. (2007) · Springer eBooks · doi:10.1007/3-540-38424-3_5 · Cited by 92 · see citing works
Security problems on inference control for SUM, MAX, and MIN queries
Chin, F. Y. L. (1986) · Journal of the ACM · doi:10.1145/5925.5928 · Cited by 83 · see citing works
Locally random reductions: Improvements and applications
Beaver, D., Feigenbaum, J., Kilian, J., et al. (1997) · Journal of Cryptology · doi:10.1007/s001459900017 · Cited by 76 · see citing works
A modified random perturbation method for database security
Tendick, P., & Matloff, N. (1994) · ACM Transactions on Database Systems · doi:10.1145/174638.174641 · Cited by 71 · see citing works
Modified bounds for covering codes
Honkala, I. S. (1991) · IEEE Transactions on Information Theory · doi:10.1109/18.75253 · Cited by 61 · see citing works
Boolean Circuits, Tensor Ranks, and Communication Complexity
Pudlák, P., Rödl, V., & Sgall, J. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539794264809 · Cited by 58 · see citing works
Simultaneous messages vs. communication
Babai, L., Kimmel, P. G., & Lokam, S. V. (1995) · Lecture notes in computer science · doi:10.1007/3-540-59042-0_88 · Cited by 39 · see citing works
Modified ranks of tensors and the size of circuits
Pudlák, P., & Rödl, V. (1993) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/167088.167228 · Cited by 26 · see citing works
On the power of two-local random reductions
Fortnow, L., & Szegedy, M. (1992) · Information Processing Letters · doi:10.1016/0020-0190(92)90104-4 · Cited by 8 · see citing works
Flagged first, then by citations
Research works printed but not linked: 3
- CHOR, B., AND GILBOA, N. 1997. Computationally private information retrieval. In Proceedings of the 29th Annual Symposium on the Theory of Computing (El Paso, Tex., May 4 -6). ACM, New York, pp. 304 -313.
- DENNING, D. 1982. Crytography and Data Security. Addison-Wesley, Reading, Mass.
- ULLMAN, J. D. 1982. Principles of Database Systems, 2nd ed. Computer Science Press, Potomac, Md. RECEIVED APRIL 1996; REVISED MARCH 1998; ACCEPTED APRIL 1998 Journal of the ACM, Vol. 45, No. 6, November 1998.
Cited by
Sorted by citations
Advances and Open Problems in Federated Learning
Kairouz, P., & McMahan, H. B. (2021) · Foundations and Trends in Machine Learning · doi:10.1561/2200000083 · Cited by 7,772 · see citing works
XPIR: Private information retrieval for everyone
Aguilar-Melchor, C., Barrier, J., Fousse, L., & Killijian, M.-O. (2016) · Proceedings on Privacy Enhancing Technologies · doi:10.1515/popets-2016-0010 · Cited by 185 · see citing works
Riffle: An Efficient Communication System With Strong Anonymity
Kwon, A., Lazar, D., Devadas, S., & Ford, B. (2016) · Proceedings on Privacy Enhancing Technologies · doi:10.1515/popets-2016-0008 · Cited by 84 · see citing works
Private 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 · see citing works
Yu, R., Bai, Z., Yang, L., Wang, P., Move, O. A., & Liu, Y. (2016) · IEEE Access · doi:10.1109/access.2016.2607766 · Cited by 33 · see citing works
Staircase-PIR: Universally Robust Private Information Retrieval
Bitar, R., & Rouayheb, S. E. (2018) · 2018 IEEE Information Theory Workshop (ITW) · doi:10.1109/itw.2018.8613532 · Cited by 27 · see citing works
Nair, D. G., Binu, V. P., & Kumar, G. S. (2014) · 2014 International Conference on Data Science & Engineering (ICDSE) · doi:10.1109/icdse.2014.6974639 · Cited by 11 · see citing works
- Authors
- Chor, B., Kushilevitz, E., Goldreich, O., & Sudan, M.
- Affiliations
- Technion – Israel Institute of Technology (IL)
- Technion, Haifa, Israel
- Weizmann Institute of Science (IL)
- Massachusetts Institute of Technology (US)
- Venue
- Journal of the ACM
- Published
- 1998-11
- Volume
- 45
- Issue
- 6
- Pages
- 965-981
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2073346043
- Cited by
- 1,612
- References
- 34
- Citations by year
- 2026: 55 · 2025: 82 · 2024: 79 · 2023: 53 · 2022: 52 · 2021: 62 · 2020: 64 · 2019: 90 · 2018: 105 · 2017: 92 · 2016: 92 · 2015: 108 · 2014: 93 · 2013: 73 · 2012: 55
- FWCI
- 10.96
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Journal of the ACM (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Cryptography and Data Security
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Physical Sciences › Computer Science › Information Systems › Cloud Data Security Solutions
- Keywords
- private information retrieval, database privacy, database replication, communication complexity, query privacy, information-theoretic privacy
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
