The DOI matches its Crossref record; 20 of the 20 references it cites were found in a registry or an index.
Replication is not needed: single database, computationally-private information retrieval
Abstract
We establish the following, quite unexpected, result: replication of data for the computational private information retrieval problem is not necessary. More specifically, based on the quadratic residuosity assumption, we present a single database, computationally private information retrieval scheme with O(n/sup /spl epsiv//) communication complexity for any /spl epsiv/>0.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
Goldreich, O., Micali, S., & Wigderson, A. (1987) · Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87 · doi:10.1145/28395.28420 · Cited by 3,590
The knowledge complexity of interactive proof systems
Goldwasser, S., Micali, S., & Rackoff, C. (1989) · SIAM Journal on Computing · doi:10.1137/0218012 · Cited by 3,285
Bhunia, C. T. (1997) · IETE Journal of Education · doi:10.1080/09747338.1997.11415666 · Cited by 2,701
Goldwasser, S., & Micali, S. (1984) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(84)90070-9 · Cited by 2,603
Software protection and simulation on oblivious RAMs
Goldreich, O., & Ostrovsky, R. (1996) · Journal of the ACM · doi:10.1145/233551.233553 · Cited by 1,617
Self-citationA Randomized Protocol for Signing Contracts
Even, S., Goldreich, O., & Lempel, A. (1983) · Advances in Cryptology · doi:10.1007/978-1-4757-0602-4_19 · Cited by 1,450
(2017) · Effective Library and Information Centre Management · doi:10.4324/9781315256894-38 · Cited by 1,119
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
Self-citationA Simple Unpredictable Pseudo-Random Number Generator
Blum, L., Blum, M., & Shub, M. (1986) · SIAM Journal on Computing · doi:10.1137/0215025 · Cited by 1,036
How to Exchange Secrets with Oblivious TransferPreprint
Rabin, M. O. (1981) · IACR Cryptology ePrint Archive · Cited by 870
Limits on the provable consequences of one-way permutations
Impagliazzo, R., & Rudich, S. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73012 · Cited by 575
Towards a theory of software protection and simulation by oblivious RAMs
Goldreich, O. (1987) · Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87 · doi:10.1145/28395.28416 · Cited by 507
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
Self-citationBlum, M., De Santis, A., Micali, S., & Persiano, G. (1991) · SIAM Journal on Computing · doi:10.1137/0220068 · Cited by 427
Pseudorandomness and Cryptographic Applications
Luby, M. (1996) · Princeton University Press eBooks · doi:10.1515/9780691206844 · Cited by 374
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
Private Information Retrieval by Keywords
Chor, B., Gilboa, N., & Naor, M. (1997) · Cited by 175
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 StoragePreprint
Ostrovsky, R., & Shoup, V. (1996) · IACR Cryptology ePrint Archive · Cited by 97
Self-citationOdds and ends from cryptology and computational number theory
McCurley, K. S. (1991) · Proceedings of symposia in applied mathematics · doi:10.1090/psapm/042/1095555 · Cited by 9
Research works printed but not linked: 6
- bach, 1996, Algorithmic Number Theory, 1
- 10.1109/SFCS.1986.33 · doi:10.1109/sfcs.1986.33
- 10.1145/3812.3818 · doi:10.1145/3812.3818
- 0, STOC '85, 291
- odlyzko, 1995, The future of Integer Factorization, Crypto- Bytes, 1, 5
- ostrovsky, 1992, Software protection and simulation on oblivious RAMs
Cited by
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
“MPC approaches to PIR break down into two main categories: computational PIR (cPIR), in which a single party can execute the entire server side of the protocol [249], and information theoretic PIR (itPIR), in which multiple non-colluding parties are required to execute the server side of the protocol [106].”
BackgroundPractical techniques for searches on encrypted data
Song, D. X., Wagner, D., & Perrig, A. (2002) · Proceeding 2000 IEEE Symposium on Security and Privacy. S&P 2000 · doi:10.1109/secpri.2000.848445 · Cited by 3,350
Public Key Encryption with Keyword Search
Boneh, D., Di Crescenzo, G., Ostrovsky, R., & Persiano, G. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24676-3_30 · Cited by 3,134
Self-citationPors: proofs of retrievability for large files
Juels, A., & Kaliski, B. S. (2007) · Proceedings of the 14th ACM conference on Computer and communications security · doi:10.1145/1315245.1315317 · Cited by 1,894
Evaluating 2-DNF Formulas on Ciphertexts
Boneh, D., Goh, E.-J., & Nissim, K. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30576-7_18 · Cited by 1,692
Metadata
- Authors
- Kushilevitz, E., & Ostrovsky, R.
- Venue
- Proceedings 38th Annual Symposium on Foundations of Computer Science
- Publisher
- IEEE Comput. Soc
- Published
- 2002-11-22
- Pages
- 364-373
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2154654620
- Cited by
- 932
- References
- 20
- FWCI
- 17.40
- Type
- conference paper
- 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.