XPIR: Private information retrieval for everyone
Open accessThe DOI matches its Crossref record; 46 of the 46 references it cites were found in a registry or an index.
Abstract
A Private Information Retrieval (PIR) scheme is a protocol in which a user retrieves a record from a database while hiding which from the database administrators. PIR can be achieved using mutuallydistrustful replicated databases, trusted hardware, or cryptography. In this paper we focus on the later setting which is known as single-database computationally- Private Information Retrieval (cPIR). Classic cPIR protocols require that the database server executes an algorithm over all the database content at very low speeds which impairs their usage. In [1], given certain assumptions, realistic at the time, Sion and Carbunar showed that cPIR schemes were not practical and most likely would never be. To this day, this conclusion is widely accepted by researchers and practitioners. Using the paradigm shift introduced by lattice-based cryptography, we show that the conclusion of Sion and Carbunar is not valid anymore: cPIR is of practical value. This is achieved without compromising security, using standard crytosystems, and conservative parameter choices.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
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?
In the citing paper
“Furthermore, Koh et al. [276] recently showed that many heuristic defenses based on data sanitization remain vulnerable to adaptive poisoning attacks, suggesting that even a federated approach to data sanitization may not be enough to defend against data poisoning.”
From Advances and Open Problems in Federated Learning (2021) · cites this paper as [276]
Citations
Cites
Public-Key Cryptosystems Based on Composite Degree Residuosity Classes
Paillier, P. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48910-x_16 · Cited by 7,250 · cited 7×
“Parameters are dependent on each cryptographic system: ** NoCryptography if a trivial full database download is to be done after which PIRClient stores only the element the user is interested in. ** Paillier:A:B:C if Paillier’s cryptosystem is to be used with A security bits, a plaintext modulus of B bits and a cipher…”
BackgroundInfluentialGoldwasser, S., & Micali, S. (1984) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(84)90070-9 · Cited by 2,603 · cited 1×
“This property offers strong guaranties on ciphertext secrecy as proved by Goldwasser and Micali [50].”
BackgroundOn Ideal Lattices and Learning with Errors over Rings
Lyubashevsky, V., Peikert, C., & Regev, O. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-13190-5_1 · Cited by 1,831
(Leveled) fully homomorphic encryption without bootstrapping
Brakerski, Z., Gentry, C., & Vaikuntanathan, V. (2012) · Proceedings of the 3rd Innovations in Theoretical Computer Science Conference · doi:10.1145/2090236.2090262 · Cited by 1,782
Chor, B., Kushilevitz, E., Goldreich, O., & Sudan, M. (1998) · Journal of the ACM · doi:10.1145/293347.293350 · Cited by 1,612
Ohm, J.-R., Sullivan, G. J., Schwarz, H., Tan, T. K., & Wiegand, T. (2012) · IEEE Transactions on Circuits and Systems for Video Technology · doi:10.1109/tcsvt.2012.2221192 · Cited by 1,279 · cited 1×
“265 - High Efficiency Video Coding (HEVC) is the forthcoming standard for video-streams compression[44, 45].”
BackgroundFully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages
Brakerski, Z., & Vaikuntanathan, V. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-22792-9_29 · Cited by 1,096 · cited 8×
“This is basically the symmetric homomorphic encryption scheme of [28] with a composite modulus.”
BackgroundMethodInfluentialReplication is not needed: single database, computationally-private information retrieval
Kushilevitz, E., & Ostrovsky, R. (2002) · Proceedings 38th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646125 · Cited by 932
Better Key Sizes (and Attacks) for LWE-Based Encryption
Lindner, R., & Peikert, C. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-19074-2_21 · Cited by 688 · cited 2×
“Each of the encryption schemes has a predefined list of possible parameters for security varying from 80 to 256 bits (following NIST recommendations for factoring-based cryptography for Paillier and [32] for lattice-based schemes).”
MethodKeyword 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 · cited 1×
“The basic idea of private keyword search [34] is that the database can arrange its elements by grouping them us-ing keywords.”
Background
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
“Recent results on PIR have shown dramatic reductions in the computational cost through the use of lattice-based cryptosystems [16, 313, 17, 25, 175].”
BackgroundFunction 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
“Indeed all known single-server PIR protocols require (additively homomorphic) public-key encryption of the whole database to evaluate a PIR query (cf. [25] and references therein).”
BackgroundPIR with Compressed Queries and Amortized Query Processing
Angel, S., Chen, H., Laine, K., & Setty, S. (2018) · 2018 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2018.00062 · Cited by 251
“For XPIR, we use the publicly available source code [9] and integrate it into our testing framework using Rust wrappers.”
MethodPrivacy enhancing technologies for solving the privacy-personalization paradox: Taxonomy and survey
Kaaniche, N., Laurent, M., & Belguith, S. (2020) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2020.102807 · Cited by 136
PEGASUS: Bridging Polynomial and Non-polynomial Evaluations in Homomorphic Encryption
Lu, W.-J., Huang, Z., Hong, C., Ma, Y., & Qu, H. (2021) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp40001.2021.00043 · Cited by 141
“, the private information retrieval [42] and the decisiontree evaluation [37], [51].”
Background
Metadata
- Authors
- Aguilar-Melchor, C., Barrier, J., Fousse, L., & Killijian, M.-O.
- Affiliations
- Univ de Toulouse, IRIT, France
- Centre National de la Recherche Scientifique (FR)
- Univ de Grenoble, LJK, France
- Venue
- Proceedings on Privacy Enhancing Technologies
- Published
- 2015-12-30
- Volume
- 2016
- Issue
- 2
- Pages
- 155-174
- ISSN
- 2299-0984 (ISSN-L)
- OpenAlex
- W2401976587
- Cited by
- 185
- References
- 46
- Citations by year
- 2026: 24 · 2025: 25 · 2024: 17 · 2023: 18 · 2022: 14 · 2021: 20 · 2020: 17 · 2019: 18 · 2018: 8 · 2017: 15 · 2016: 9
- FWCI
- 10.46
- Type
- journal article
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- Locations
- Proceedings on Privacy Enhancing Technologies (publishedVersion, cc-by-nc-nd)
- HAL (submittedVersion, other-oa)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Computer Networks and Communications › Cryptography and Data Security
- Physical Sciences › Computer Science › Information Systems › Cloud Data Security Solutions
- Physical Sciences › Computer Science › Artificial Intelligence › Internet Traffic Analysis and Secure E-voting
- Keywords
- private information retrieval, lattice-based cryptography, database 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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: XPIR: Private information retrieval for everyone. https://app.cochat.ai/papers/10.1515/popets-2016-0010
- The paper
- Aguilar-Melchor, C., Barrier, J., Fousse, L., & Killijian, M.-O. (2016). XPIR: Private information retrieval for everyone. Proceedings on Privacy Enhancing Technologies. https://doi.org/10.1515/popets-2016-0010
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.