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.”
BackgroundAll-or-Nothing Disclosure of Secrets
Brassard, G., Crepeau, C., & Robert, J.-M. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-47721-7_17 · Cited by 297 · cited 1×
“Works considering only computational or communication costs In the Oblivious Transfer setting [27], the objective is to limit the computational cost for the user and the database without considering communication effi-ciency.”
BackgroundNew lattice-based cryptographic constructions
Regev, O. (2004) · Journal of the ACM · doi:10.1145/1039488.1039490 · Cited by 292
An Oblivious Transfer Protocol with Log-Squared Communication
Lipmaa, H. (2005) · Lecture Notes in Computer Science · doi:10.1007/11556992_23 · Cited by 271 · cited 2×
“In our library, we have decided to stick to the basic approach for recursion although it would be interesting to develop other optimizations, such as those proposed in [33].”
BackgroundMethodNew Algorithms for Learning in Presence of Errors
Arora, S., & Ge, R. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-22006-7_34 · Cited by 243 · cited 1×
“As number theoretic approaches failed to provide efficient cPIR schemes, some alternatives were explored [6, 7, 8], but all of them were based on non-standard problems and have been broken [9, 10, 11, 12, 13].”
BackgroundA Survey on Private Information Retrieval
Gasarch, W. I. (2004) · Cited by 225
On the Design of Hardware Building Blocks for Modern Lattice-Based Encryption Schemes
Göttert, N., Feller, T., Schneider, M., Buchmann, J. A., & Huss, S. A. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-33027-8_30 · Cited by 180 · cited 1×
“In XPIR we use a mixed NTT-CRT representation to reduce computational costs: Number-Theoretic Transform (NTT) for polynomials [39] and Chinese Remainder Theorem (CRT) for integers.”
MethodOn the Computational Practicality of Private Information Retrieval
Sion, R., & Cărbunar, B. (2006) · Cited by 171
A New and Efficient All-Or-Nothing Disclosure of Secrets Protocol
Stern, J. P. (1998) · Lecture notes in computer science · doi:10.1007/3-540-49649-1_28 · Cited by 139 · cited 3×
“In this paper, we use a simple cPIR protocol based on [33], described hereafter.”
MethodInfluentialRevisiting the Computational Practicality of Private Information Retrieval
Olumofin, F., & Goldberg, I. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-27576-0_13 · Cited by 132 · cited 1×
“Instead of using a trusted hardware module, it is also possible to build efficient PIR protocols using replicated databases as shown by Olumofin and Goldberg [26].”
MethodPractical server privacy with secure coprocessors
Smith, S. W., & Safford, D. R. (2001) · IBM Systems Journal · doi:10.1147/sj.403.0683 · Cited by 114 · cited 1×
“It is possible to transform an ORAM protocol into a PIR protocol using a trusted hardware module (e.g. see [25]).”
MethodAchieving Efficient Query Privacy for Location Based Services
Olumofin, F., Tysowski, P. K., Goldberg, I., & Hengartner, U. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14527-8_6 · Cited by 105 · cited 1×
“These works total about eighty citations, and have been used as a fundamental building block (or as a benchmark) in major and recent venues such as Usenix Security [15] (2011), NDSS [16, 17] (2013, 2014), and PETs [18, 19, 20, 21] (2010, 2012,”
BackgroundDecoding of Interleaved Reed Solomon Codes over Noisy Data
Bleichenbacher, D., Kiayias, A., & Yung, M. M. (2003) · Lecture notes in computer science · doi:10.1007/3-540-45061-0_9 · Cited by 91 · cited 1×
“As number theoretic approaches failed to provide efficient cPIR schemes, some alternatives were explored [6, 7, 8], but all of them were based on nonstandard problems and have been broken [9, 10, 11, 12, 13].”
BackgroundPrivate Searching on Streaming Data
Ostrovsky, R., & Skeith, W. E. (2007) · Journal of Cryptology · doi:10.1007/s00145-007-0565-3 · Cited by 90 · cited 2×
“With these parameters, ciphertext size (and thus query element size) is 500Kbits and the expansion factor of encryption is F (cid:39) 5.”
BackgroundEfficient Private File Retrieval by Combining ORAM and PIR
Mayberry, T., Blaß, E.-O., & Chan, A. H. (2014) · Network and Distributed System Security Symposium · doi:10.14722/ndss.2014.23033 · Cited by 88 · cited 1×
“These works total about eighty citations, and have been used as a fundamental building block (or as a benchmark) in major and recent venues such as Usenix Security [15] (2011), NDSS [16, 17] (2013, 2014), and PETs [18, 19, 20, 21] (2010, 2012,”
BackgroundFaster arithmetic for number-theoretic transforms
Harvey, D. (2013) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2013.09.002 · Cited by 88 · cited 2×
“First we use Harvey’s NTT algorithm [47] which is very fast but only works for some polynomials degrees (powers of two).”
BackgroundMethodFirst CPIR Protocol with Data-Dependent Computation
Lipmaa, H. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14423-3_14 · Cited by 82 · cited 1×
“As number theoretic approaches failed to provide efficient cPIR schemes, some alternatives were explored [6, 7, 8], but all of them were based on non-standard problems and have been broken [9, 10, 11, 12, 13].”
BackgroundPIR-Tor: scalable anonymous communication using private information retrieval
Mittal, P., Olumofin, F., Troncoso, C., Borisov, N., & Goldberg, I. (2011) · Cited by 80
A fast private information retrieval protocol
Melchor, C. A., & Gaborit, P. (2008) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2008.4595308 · Cited by 72 · cited 3×
“The (broken) schemes of Aguilar et al. [7] and Tros-tle and Parrish [8] represented the state-of-the-art in ef-ficient private information retrieval, allowing to reach processing speeds of hundreds of megabits per second on high-end CPUs and up to one gigabit per second on GPUs [14].”
BackgroundMethodReconstructing curves in three (and higher) dimensional space from noisy data
Coppersmith, D., & Sudan, M. (2003) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/780542.780563 · Cited by 68 · cited 1×
“As number theoretic approaches failed to provide efficient cPIR schemes, some alternatives were explored [6, 7, 8], but all of them were based on non-standard problems and have been broken [9, 10, 11, 12, 13].”
BackgroundPrivacy-Preserving Queries over Relational Databases
Olumofin, F., & Goldberg, I. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14527-8_5 · Cited by 67 · cited 1×
“Second, the NTT and Ring-LWE based private information retrieval scheme and implementation we describe in this paper offer multi-gigabit processing through-put on a commodity CPU, and an optimizer to automatically setup the system for a given setup (hardware/network/application/security).”
MethodPRISM – Privacy-Preserving Search in MapReduce
Blaß, E.-O., Pietro, R. D., Molva, R. A., & Önen, M. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-31680-7_10 · Cited by 66 · cited 1×
“Together, these works total about eighty citations, and have been used as a fundamental building block (or as a benchmark) in major and recent venues such as Usenix Security [15] (2011), NDSS [16, 17] (2013, 2014), and PETs [18, 19, 20, 21] (2010, 2012, 2014).”
BackgroundEfficient Computationally Private Information Retrieval from Anonymity or Trapdoor Groups
Trostle, J. T., & Parrish, A. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-18178-8_10 · Cited by 66 · cited 1×
“First and foremost this paper shows that cPIR is a usable primitive in a large variety of settings, with standard security assumptions and conservative parameter choices.”
BackgroundScalable and private media consumption with Popcorn.Preprint
Gupta, T., Crooks, N., Setty, S., Alvisi, L., & Walfish, M. (2015) · IACR Cryptology ePrint Archive · Cited by 66
Software Speed Records for Lattice-Based Signatures
Güneysu, T. E., Oder, T., Pöppelmann, T., & Schwabe, P. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38616-9_5 · Cited by 60 · cited 2×
“To generate this noise, we use Salsa20/20 [37] (Salsa20/20 is able to provide up to 256 bits of security), and thus even if a set of parameters for Ring-LWE is able to provide theoretically more security, 256 is thus an upper bound (this is the standard maximum security usually considered).”
MethodDevet, C., & Goldberg, I. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-08506-7_4 · Cited by 54 · cited 2×
“A very interesting recent work by Devet and Goldberg[21] has proposed using replicated-database PIR and cPIR jointly to achieve high performance results without compromising security when databases collude.”
BackgroundOne (Block) Size Fits All: PIR and SPIR with Variable-Length Records via Multi-Block Queries.
Henry, R., Huang, Y., & Goldberg, I. (2013) · Network and Distributed System Security Symposium · Cited by 40
Optimal Rate Private Information Retrieval from Homomorphic Encryption
Kiayias, A., Leonardos, N., Lipmaa, H., Pavlyk, K. P., & Tang, Q. (2015) · Proceedings on Privacy Enhancing Technologies · doi:10.1515/popets-2015-0016 · Cited by 37 · cited 1×
“other optimizations, such as those proposed in [32, 36].”
BackgroundSecure Games with Polynomial Expressions
Kiayias, A., & Yung, M. M. (2001) · Lecture notes in computer science · doi:10.1007/3-540-48224-5_76 · Cited by 36 · cited 1×
“As number theoretic approaches failed to provide efficient cPIR schemes, some alternatives were explored [6, 7, 8], but all of them were based on non-standard problems and have been broken [9, 10, 11, 12, 13].”
BackgroundBandwidth Efficient PIR from NTRU
Doröz, Y., Sunar, B., & Hammouri, G. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-44774-1_16 · Cited by 36 · cited 1×
“In [29], an implementation of a fully-homomorphic encryption based scheme is given.”
MethodHigh-Speed Private Information Retrieval Computation on GPU
Melchor, C. A., Crespin, B., Gaborit, P., Jolivet, V., & Rousseau, P. (2008) · International Conference on Emerging Security Information, Systems and Technologies · doi:10.1109/securware.2008.55 · Cited by 32 · cited 1×
“The (broken) schemes of Aguilar et al. [7] and Tros-tle and Parrish [8] represented the state-of-the-art in ef-ficient private information retrieval, allowing to reach processing speeds of hundreds of megabits per second on high-end CPUs and up to one gigabit per second on GPUs [14].”
BackgroundPrivate Stream Search at the same communication cost as a regular search: Role of LDPC codes
Finiasz, M., & Ramchandran, K. (2012) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2012.6283979 · Cited by 20
New lattice based cryptographic constructions
Regev, O. (2003) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/780601.780603 · Cited by 16
Cryptanalysis of a (Somewhat) Additively Homomorphic Encryption Scheme Used in PIR
Lepoint, T., & Tibouchi, M. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-48051-9_14 · Cited by 15 · cited 1×
“As number theoretic approaches failed to provide efficient cPIR schemes, some alternatives were explored [6, 7, 8], but all of them were based on non-standard problems and have been broken [9, 10, 11, 12, 13].”
BackgroundBlake, I. F. (2024) · Cambridge University Press eBooks · doi:10.1017/9781009283403.010 · Cited by 14
Cryptanalysis of a homomorphic encryption scheme from ISIT 2008
Bi, J., Liu, M., & Wang, X. (2012) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2012.6283832 · Cited by 7 · cited 1×
“As number theoretic approaches failed to provide efficient cPIR schemes, some alternatives were explored [6, 7, 8], but all of them were based on non-standard problems and have been broken [9, 10, 11, 12, 13].”
BackgroundReconstructing curves in three (and higher) dimensional space from noisy data
Coppersmith, D., & Sudan, M. (2003) · doi:10.1145/780559.780563 · Cited by 6
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
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.