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
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
Searchable symmetric encryption: improved definitions and efficient constructions
Curtmola, R., Garay, J., Kamara, S., & Ostrovsky, R. (2006) · Proceedings of the 13th ACM conference on Computer and communications security · doi:10.1145/1180405.1180417 · Cited by 1,671
Self-citationChor, B., Kushilevitz, E., Goldreich, O., & Sudan, M. (1998) · Journal of the ACM · doi:10.1145/293347.293350 · Cited by 1,612
Self-citationEfficient Fully Homomorphic Encryption from (Standard) LWE
Brakerski, Z., & Vaikuntanathan, V. (2011) · 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2011.12 · Cited by 1,449
Conjunctive, Subset, and Range Queries on Encrypted Data
Boneh, D., & Waters, B. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-70936-7_29 · Cited by 1,432
A Survey on Homomorphic Encryption Schemes: Theory and Implementation
Acar, A., Aksu, H., Uluagac, A. S., & Conti, M. (2019) · ACM Computing Surveys · doi:10.1145/3214303 · Cited by 1,397
Searchable symmetric encryption: Improved definitions and efficient constructions
Curtmola, R., Garay, J., Kamara, S., & Ostrovsky, R. (2011) · Journal of Computer Security · doi:10.3233/jcs-2011-0426 · Cited by 914
Self-citationPrivate queries in location based services: anonymizers are not necessary
Ghinita, G., Kalnis, P., Khoshgozaran, A., Shahabi, C., & Tan, K.-L. (2008) · Proceedings of the 2008 ACM SIGMOD international conference on Management of data · doi:10.1145/1376616.1376631 · Cited by 758
Fully homomorphic SIMD operations
Smart, N. P., & Vercauteren, F. (2014) · Designs, Codes and Cryptography · doi:10.1007/s10623-012-9720-4 · Cited by 656
Information sharing across private databases
Agrawal, R., Evfimievski, A., & Srikant, R. (2003) · Proceedings of the 2003 ACM SIGMOD international conference on Management of data · doi:10.1145/872757.872771 · Cited by 634
Oblivious transfer and polynomial evaluation
Naor, M., & Pinkas, B. (1999) · Proceedings of the thirty-first annual ACM symposium on Theory of Computing · doi:10.1145/301250.301312 · Cited by 629
Efficient oblivious transfer protocols
Naor, M., & Benny Pinkas, B. (2001) · Symposium on Discrete Algorithms · doi:10.5555/365411.365502 · Cited by 614
Computationally Private Information Retrieval with Polylogarithmic Communication
Cachin, C., Micali, S., & Stadler, M. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48910-x_28 · Cited by 579
Delegating computation: interactive proofs for muggles
Goldwasser, S., Kalai, Y. T., & Rothblum, G. N. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374396 · Cited by 484
Secure multi-party computation problems and their applications: a review and open problems
Du, W., & Atallah, M. J. (2001) · Proceedings of the 2001 workshop on New security paradigms · doi:10.1145/508171.508174 · Cited by 453
Keyword Search and Oblivious Pseudorandom Functions
Freedman, M. J., Ishai, Y., Pinkas, B., & Reingold, O. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30576-7_17 · Cited by 441
Priced Oblivious Transfer: How to Sell Digital Goods
Aiello, B., Ishai, Y., & Reingold, O. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44987-6_8 · Cited by 400
Function Secret Sharing: Improvements and Extensions
Boyle, E., Gilboa, N., & Ishai, Y. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978429 · Cited by 358
Boyle, E., Gilboa, N., & Ishai, Y. (2015) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-46803-6_12 · Cited by 328
Single-Database Private Information Retrieval with Constant Communication Rate
Gentry, C., & Ramzan, Z. (2005) · Lecture Notes in Computer Science · doi:10.1007/11523468_65 · Cited by 313
An Oblivious Transfer Protocol with Log-Squared Communication
Lipmaa, H. (2005) · Lecture Notes in Computer Science · doi:10.1007/11556992_23 · Cited by 271
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
Private Stateful Information Retrieval
Patel, S., Persiano, G., & Yeo, K. (2018) · Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3243734.3243821 · Cited by 61
“In this work, we are interested in single-server PIR with computational security as first considered by Kushilevitz and Ostrovsky [36].”
BackgroundMethodPrivate 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
SHECS-PIR: Somewhat Homomorphic Encryption-Based Compact and Scalable Private Information Retrieval
Park, J., & Tibouchi, M. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-59013-0_5 · Cited by 32
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.