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].”
BackgroundSPIRAL: Fast, High-Rate Single-Server PIR via FHE Composition
Menon, S. J., & Wu, D. J. (2022) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp46214.2022.9833700 · Cited by 175
“The most efficient single-server PIR protocols [AS16, MBFK16, ACLS18, GH19, PT20, ALP + 21, MCR21] use lattice-based fully homomorphic encryption (FHE) schemes [Gen09, BV11, Bra12, FV12, BGV12, GSW13].”
BackgroundMethodInfluentialPrivate Information Retrieval with Sublinear Online Time
Corrigan-Gibbs, H., & Kogan, D. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-45721-1_3 · Cited by 133
OnionPIR: Response Efficient Single-Server PIR
Mughees, M. H., Chen, H., & Ren, L. (2021) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3460120.3485381 · Cited by 145
Compressible FHE with Applications to PIR
Gentry, C., & Halevi, S. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-36033-7_17 · Cited by 113
“See [KLL + 15,AMBFK16,LP17] for more motivating discussions.”
BackgroundMethodInfluentialPrivacy-Preserving Shortest Path Computation
Wu, D. J., Zimmerman, J., Planul, J., & Mitchell, J. C. (2016) · Network and Distributed System Security Symposium · doi:10.14722/ndss.2016.23052 · Cited by 93
Rethinking Searchable Symmetric Encryption
Gui, Z., Paterson, K. G., & Patranabis, S. (2023) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp46215.2023.10179460 · Cited by 69
“Here, we focus on computational PIR schemes [42], [44] for which there is provably no leakage (per retrieval).”
BackgroundPractical Non-interactive Publicly Verifiable Secret Sharing with Thousands of Parties
Gentry, C., Halevi, S., & Lyubashevsky, V. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-06944-4_16 · Cited by 68
Piano: Extremely Simple, Single-Server PIR with Sublinear Server Computation
Zhou, M., Park, A., Zheng, W., & Shi, E. (2024) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp54263.2024.00055 · Cited by 103
Single-Server Private Information Retrieval with Sublinear Amortized Time
Corrigan-Gibbs, H., Henzinger, A., & Kogan, D. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-07085-3_1 · Cited by 92
“Recent works [1, 5, 7, 53, 83] have used lattice-based encryption schemes to improve the concrete efficiency of single-server PIR, in terms of both communication and computation.”
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
“We construct PSIR using XPIR [5] as well as a PIR construction built from the Paillier cryptosystem [43].”
MethodFrodoPIR: Simple, Scalable, Single-Server Private Information Retrieval
Davidson, A., Pestana, G., & Celi, S. (2023) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2023-0022 · Cited by 84
“PIR schemes are split into those that are information-theoretically secure, but require the database to be shared between multiple non-colluding servers [5, 9–12, 26, 28, 31, 35, 36, 40, 58, 72, 75]; and those that are computationally-secure against a single untrusted server [1, 3, 6, 21, 24, 31, 38, 55, 56, 59, 62, 6…”
BackgroundMethodInfluentialProtocols for Checking Compromised Credentials
Li, L. Q., Pal, B., Ali, J., Sullivan, N., Chatterjee, R., & Ristenpart, T. (2019) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3319535.3354229 · Cited by 66
“orresponding to their password from the server. But in our setting we also want to protect the privacy of the dataset leak. Even if we relaxed that security requirement, the most advanced PIR schemes [17, 39] require exchanging large amounts of information over the network, so they are not useful for checking leaked p…”
BackgroundA Protocol for Privately Reporting Ad Impressions at Scale
Green, M., Ladd, W., & Miers, I. (2016) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2976749.2978407 · Cited by 54
A Privacy-Preserving Framework for Outsourcing Location-Based Services to the Cloud
Zhu, X., Ayday, E., & Vitenberg, R. M. (2019) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2019.2892150 · Cited by 49
“[41] proposes a retrieving mechanism based on Ring-Leaning with error (Ring-LWE) while [9] proposes private query based on quadratic residuosity assumption (QRA).”
SoK: New Insights into Fully Homomorphic Encryption Libraries via Standardized Benchmarks
Gouert, C., Mouris, D., & Tsoutsos, N. G. (2023) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2023-0075 · Cited by 50
“, which element was downloaded) to the server [2, 5].”
Number Theoretic Transforms for Secure Signal Processing
Pedrouzo-Ulloa, A., Troncoso-Pastoriza, J. R., & Pérez‐González, F. (2017) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2016.2647223 · Cited by 46
Vectorized Batch Private Information Retrieval
Mughees, M. H., & Ren, L. (2023) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp46215.2023.10179329 · Cited by 47
“[12] proposed the first such scheme, called XPIR.”
BackgroundPrivate Web Search with Tiptoe
Henzinger, A., Dauterman, E., Corrigan-Gibbs, H., & Zeldovich, N. (2023) · ACM SIGOPS Symposium on Operating Systems Principles (SOSP) · doi:10.1145/3600006.3613134 · Cited by 74
“We use standard linearly homomorphic encryption from ring learning-with-errors [77].”
BackgroundMethodLower-Cost ∈-Private Information Retrieval
Toledo, R. R., Danezis, G., & Goldberg, I. (2016) · Proceedings on Privacy Enhancing Technologies · doi:10.1515/popets-2016-0035 · Cited by 56
Express: Lowering the Cost of Metadata-hiding Communication with Cryptographic PrivacyPreprint
Eskandarian, S., Corrigan-Gibbs, H., Zaharia, M., & Boneh, D. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.09215 · Cited by 57
“private information retrieval techniques [3, 15, 20, 33, 48, 49] to render reads or writes into a database of mailboxes private and target a variety of use cases [4, 13, 19, 22, 24, 39, 40].”
BackgroundEfficient and secure outsourcing of genomic data storage
Sousa, J. S., Lefebvre, C., Huang, Z., Raisaro, J. L., Melchor, C. A., Killijian, M., & Hubaux, J. (2017) · BMC Medical Genomics · doi:10.1186/s12920-017-0275-0 · Cited by 42
“To come up with these values, the XPIR optimizer empirically tests, for a specific file, different combinations of parameters and chooses the ones that provide the better overall PIR performance and guarantee at least 80-bits security.”
MethodInfluentialSelf-citationPrivacy-Enhancing Technologies in Biomedical Data Science
Cho, H., Froelicher, D., Dokmai, N., Nandi, A., Sadhuka, S., Hong, M. M., & Berger, B. (2024) · Annual Review of Biomedical Data Science · doi:10.1146/annurev-biodatasci-120423-120107 · Cited by 48
Fast Additive Partially Homomorphic Encryption From the Approximate Common Divisor Problem
Cominetti, E. L., & Junior, M. A. S. (2020) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2020.2981239 · Cited by 36
“In addition to the comparison with the Paillier cryptosystem, we can evaluate the performance of FAHE1 and FAHE2 with another symmetric additive homomorphic scheme: the solution adopted in XPIR [6], which is based on the ring learning with errors (RLWE) approach introduced in [37].”
MethodPrivacy Techniques for Edge Computing Systems
Rao, F.-Y., & Bertino, E. (2019) · Proceedings of the IEEE · doi:10.1109/jproc.2019.2918749 · Cited by 34
“According to the empirical results collected from a laptop equipped with an Intel Core i7-3630QM CPU [49], the speed of query processing is around 1 Mb/s for a Paillier-based PIR scheme, whereas the speed would be around 20 Gb/s for a PIR scheme based on the FHE scheme.”
BackgroundMethodInfluentialSHECS-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
X-search: revisiting private web search using intel SGX
Mokhtar, S. B., Boutet, A., Felber, P. A., Pasin, M., Pires, R., & Schiavoni, V. (2017) · International Middleware Conference · doi:10.1145/3135974.3135987 · Cited by 31
“These generally rely on heavy and unpractical [2] cryptographic protocols, especially when the accessed data stores contain millions of documents, the normal case for today’s search engines.”
BackgroundHeterogeneous Private Information Retrieval
Mozaffari, H., & Houmansadr, A. (2020) · Network and Distributed System Security Symposium · doi:10.14722/ndss.2020.24363 · Cited by 35
“Existing PIR techniques use two main approaches to obfuscate (cid:126)e j : (a) Homomorphic encryption: In such protocols [50], [36], [2], [1], [4], the client encrypts (cid:126)e j element by element before being sent to the servers.”
BackgroundMethodQuantum Anonymous Private Information Retrieval for Distributed Networks
Khan, A., Khalid, U., Rehman, J. U., & Shin, H. (2022) · IEEE Transactions on Communications · doi:10.1109/tcomm.2022.3168079 · Cited by 30
TreePIR: Sublinear-Time and Polylog-Bandwidth Private Information Retrieval from DDH
Lazzaretti, A., & Papamanthou, C. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-38545-2_10 · Cited by 28
“⋆ arthur.lazzaretti@yale.edu ⋆⋆ charalampos.papamanthou@yale.edu PIR has been studied extensively over the years [2, 6, 9, 10, 14, 26, 34, 39, 40] 1 and unfortunately, all space-efficient PIR protocols are bound to a well-known linear server time lower bound by Beimel et al. [6].”
Revisiting User Privacy for Certificate Transparency
Kales, D., Omolola, O., & Ramacher, S. (2019) · IEEE European Symposium on Security and Privacy · doi:10.1109/eurosp.2019.00039 · Cited by 36
“works have improved the communication and computational complexity of PIR schemes, for example [13, 1, 24, 34, 22, 16, 3, 31].”
BackgroundSWiSSSE: System-Wide Security for Searchable Symmetric Encryption
Gui, Z., Paterson, K. G., Patranabis, S., & Warinschi, B. (2023) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2024-0032 · Cited by 28
“There are many PIR schemes proposed in the single-server single-query (each query retrieves one document) setting [3, 5, 44, 69, 73, 80, 83], single-server batchedquery setting [5, 58, 82], and multi-server setting [30, 38, 46, 48].”
BackgroundMaliciously Secure Multi-Client ORAM
Maffei, M., Malavolta, G., Reinert, M., & Schröder, D. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-61204-1_32 · Cited by 31
“We use XPIR [1], the state of the art in computational PIR.”
MethodPIRANA: Faster Multi-query PIR via Constant-weight Codes
Liu, J., Li, J., Wu, D., & Ren, K. (2024) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp54263.2024.00039 · Cited by 28
Toward a Secure, Rich, and Fair Query Service for Light Clients on Public Blockchains
Cai, C., Xu, L., Zhou, A., & Wang, C. (2021) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2021.3103382 · Cited by 32
“Here, due to the use of heavy homomorphic operations, the first computational PIR scheme falls short in performance and is unpractical for very large database [32], which obviously makes it unfit for public blockchain databases.”
BackgroundINSPIRE: in - s torage p rivate i nformation re trieval via protocol and architecture co-design
Lin, J., Liang, L., Qu, Z., Ahmad, I., Liu, L., Tu, F., Gupta, T., Ding, Y., & Xie, Y. (2022) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1145/3470496.3527433 · Cited by 29
“Stern proposed re-cursion to reorganize the database [53], and this scheme has been broadly used in XPIR [40] and other works [29, 37].”
BackgroundMethodInfluentialWrite-only oblivious RAM-based privacy-preserved access of outsourced data
Li, L., & Datta, A. (2016) · International Journal of Information Security · doi:10.1007/s10207-016-0329-x · Cited by 24
Gupta, T., Fingler, H., Alvisi, L., & Walfish, M. (2017) · ACM SIGCOMM Conference (SIGCOMM) · doi:10.1145/3098822.3098835 · Cited by 23
“The modules, written in 5,300 lines of C++ and 160 lines of Python, glue the code we borrow from existing libraries: GPGME [9] for OpenPGP encryption, Obliv-C [137] for Yao’s 2PC protocol,5 XPIR [20] for the xpir-bv AHE scheme, liblinear [24, 57] to train LR and SVM classifiers, and SQLite FTS4 [10] for the search ind…”
MethodInfluentialLocation Privacy in Cognitive Radios With Multi-Server Private Information Retrieval
Grissa, M., Yavuz, A. A., & Hamdaoui, B. (2019) · IEEE Transactions on Cognitive Communications and Networking · doi:10.1109/tccn.2019.2922300 · Cited by 25
“LP-Chor and LP-Goldberg are more than 3 orders of magnitudes faster than the schemes proposed by Troja and Bakiras [18], [19], and 10 times faster than XPIR [26] and PriSpectrum [2].”
BackgroundMethodInfluentialA privacy-preserving distributed filtering framework for NLP artifacts
Sadat, M. N., Aziz, M. M. A., Mohammed, N., Pakhomov, S., Liu, H., & Jiang, X. (2019) · BMC Medical Informatics and Decision Making · doi:10.1186/s12911-019-0867-z · Cited by 21
“Lately, researchers are adopting lattice cryptosystems, which leverage ring homomorphism (addition and multiplication) [26, 27].”
BackgroundEncELC: Hardening and Enriching Ethereum Light Clients with Trusted Enclaves
Cai, C., Xu, L., Zhou, A., Wang, R., Wang, C., & Wang, Q. (2020) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom41043.2020.9155385 · Cited by 18
“private [26] and authenticated query [13] cannot be easily integrated for guaranteeing security and efficiency at the same time when handling very large databases (see Section VII for more discussions), we resort to the Intel SGX enclave and”
BackgroundLower Bounds for (Batch) PIR with Private Preprocessing
Yeo, K. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-30545-0_18 · Cited by 20
“Recent work has focused on optimizing the concrete efficiency of singleserver schemes using lattice-based homomorphic encryption [2,5,34,58,3,56].”
ConsenSGX: Scaling Anonymous Communications Networks with Trusted Execution Environments
Sasy, S., & Goldberg, I. (2019) · Proceedings on Privacy Enhancing Technologies · doi:10.2478/popets-2019-0050 · Cited by 18
“We allow XPIR’s optimizer module choose the best parameters for d (recursion levels) and α (aggregation factor) in all of our experiments, given the block size and bandwidth constraints.”
MethodInfluentialPROBONITE: PRivate One-Branch-Only Non-Interactive decision Tree Evaluation
Azogagh, S., Delfour, V., Gambs, S., & Killijian, M. (2022) · Workshop on Encrypted Computing & Applied Homomorphic Cryptography (WAHC) · doi:10.1145/3560827.3563377 · Cited by 24
“Several approaches can be used to implement a PIR such as sharing the database among mutually distrustful servers to achieve information-theoretic PIRs [29], using trusted hardware [33] or based on homomorphic cryptography [27].”
MethodSelf-citationEnabling Privacy Preserving Mobile Advertising via Private Information Retrieval
Ullah, I., Sarwar, B. G., Boreli, R., Kanhere, S. S., Katzenbeisser, S., & Hollick, M. (2017) · Conference on Local Computer Networks · doi:10.1109/lcn.2017.63 · Cited by 15
“Recent works focusing on the practicality of PIR schemes include [11] and [13], with [11] evaluating the use of PIR in a privacy preserving web based e-commerce scenario.”
BackgroundMethodResultInfluentialPrivately Connecting Mobility to Infectious Diseases via Applied Cryptography
Bampoulidis, A., Bruni, A., Helminger, L., Kales, D., Rechberger, C., & Walch, R. (2022) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2022-0132 · Cited by 15
SoK: Metadata-Protecting Communication Systems
Sasy, S., & Goldberg, I. (2023) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2024-0030 · Cited by 28
“They treat the problem as a metadata-protected key-value store, and enable clients to privately retrieve messages from this key-value store by leveraging the computational PIR (CPIR) scheme, XPIR [47].”
MethodTowards privacy preserving threat intelligence
Dara, S., Zargar, S. T., & Muralidhara, V. N. (2017) · Journal of Information Security and Applications · doi:10.1016/j.jisa.2017.11.006 · Cited by 14
PURE: A Framework for Analyzing Proximity-based Contact Tracing Protocols
Cicala, F., Wang, W., Wang, T., Li, N., Bertino, E., Liang, F., & Yang, Y. (2021) · ACM Computing Surveys · doi:10.1145/3485131 · Cited by 17
“Then the user runs a Private Information Retrieval (PIR) [5, 11, 24, 34, 38] protocol for each blinded beacon.”
MethodCryptography, Trust and Privacy: It's Complicated
Balsa, E., Nissenbaum, H. F., & Park, S. (2022) · ACM Symposium on Computer Science and Law (CSLAW) · doi:10.1145/3511265.3550443 · Cited by 20
“Cryp-tographers have developed sophisticated techniques for private information retrieval (PIR) [5, 18] that, in theory, provide functionality similar to this.”
BackgroundAhmad, I., Sarker, L., Agrawal, D., Abbadi, A. E., & Gupta, T. (2021) · ACM SIGOPS Symposium on Operating Systems Principles (SOSP) · doi:10.1145/3477132.3483586 · Cited by 11
“Finally, in the third round, the user retrieves a single document that the user wants to view in detail using a single-retrieval PIR [7, 12].”
Grissa, M., Yavuz, A. A., & Hamdaoui, B. (2017) · IEEE Conference on Communications and Network Security · doi:10.1109/cns.2017.8228646 · Cited by 12
“• Low communication overhead: Both approaches provide a reasonable communication overhead that is a middle ground between the fastest computational PIR [24] and the most communication efficient computational PIR [32].”
BackgroundMethodInfluentialA Survey on Anonymous Communication Systems With a Focus on Dining Cryptographers Networks
Shirali, M., Tefke, T., Staudemeyer, R. C., & Pöhls, H. C. (2023) · IEEE Access · doi:10.1109/access.2023.3242870 · Cited by 14
“Pung [7], Private Keyword-Based Push and Pull (P3) [83], and Private Information Retrieval for Everyone (XPIR) [2] are other anonymous communication systems based on PIR, which use a key-value store to allow clients to deposit and retrieve messages without anyone learning the existence of conversation.”
BackgroundPlinko: Single-Server PIR with Efficient Updates via Invertible PRFs
Hoover, A., Patel, S., Persiano, G., & Yeo, K. (2025) · Lecture notes in computer science · doi:10.1007/978-3-031-91095-1_1 · Cited by 10
“More recent works build single-server PIR using lattice-based assumptions such as [2, 5, 28, 58, 3, 55, 52, 39].”
BackgroundWhat Storage Access Privacy is Achievable with Small Overhead?
Patel, S., Persiano, G., & Yeo, K. (2019) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/3294052.3319695 · Cited by 10
“The majority of PIR constructions use homomorphic encryption [2, 4] or other expensive encryptions with useful properties [12, 24, 35].”
BackgroundXSPIR: Efficient Symmetrically Private Information Retrieval from Ring-LWE
Lin, C., Liu, Z., & Malkin, T. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-17140-6_11 · Cited by 10
Privacy preserving substring search protocol with polylogarithmic communication cost
Mainardi, N., Barenghi, A., & Pelosi, G. (2019) · Annual Computer Security Applications Conference · doi:10.1145/3359789.3359842 · Cited by 10
“Indeed, in this work we aimed at minimizing the communication cost of the protocol, while results reported in [21] suggests that in some scenarios the overall query response time is improved by tuning the PIR parameters to tradeoff a low-bandwidth for significant computational savings at server side, and/or to employ…”
MethodFully Malicious Authenticated PIR
Dietz, M., & Tessaro, S. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-68400-5_4 · Cited by 9
“In this paper, we are interested in the more challenging setting of single server PIR [34], for which constructions are known from a variety of assumptions (cf. e.g. [34,11,37,41,20,21,1,3,23,29,18]).”
BackgroundPrivacy preserving data access scheme for IoT devices
Jahan, M., Seneviratne, S., Chu, B., Seneviratne, A. P., & Jha, S. K. (2017) · IEEE International Symposium on Network Computing and Applications (NCA) · doi:10.1109/nca.2017.8171357 · Cited by 9
“Alternatively, CA can utilize private information retrieval (PIR) scheme like XPIR [19] to retrieve membership information for an attribute.”
MethodTowards Practical Doubly-Efficient Private Information Retrieval
Okada, H., Player, R., Pohmann, S., & Weinert, C. (2025) · Lecture notes in computer science · doi:10.1007/978-3-031-78679-2_14 · Cited by 10
“While it is trivial to build PIR from FHE, classical HE-based PIR schemes [MBFK16; ACLS18; MCR21] are built from SHE for performance reasons.”
BackgroundSecure and Anonymous Communications Over Delay Tolerant Networks
Bakiras, S., Troja, E., Xu, X., & Naves, J. F. (2020) · IEEE Access · doi:10.1109/access.2020.2993062 · Cited by 9
Kong, Q., Zhang, S., Lu, R., Bao, H., Chen, B., & Xu, S. (2024) · IEEE Transactions on Services Computing · doi:10.1109/tsc.2024.3377159 · Cited by 8
“Recent PIR protocols also exploit the fully homomorphic encryption (FHE), which are based on the hardness of the lattice and learning with error (LWE) problems [12], [30].”
BackgroundFaster FHE-Based Single-Server Private Information Retrieval
Luo, M., Liu, F.-H., & Wang, H. (2024) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3658644.3690233 · Cited by 13
More is Merrier: Relax the Non-Collusion Assumption in Multi-Server PIR
Gong, T., Henry, R., Psomas, A., & Kate, A. (2024) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp54263.2024.00095 · Cited by 13
“In two efficient single-server cPIR solutions, XPIR [1] and SealPIR [5], it takes a server three orders of magnitude more time to compute the response even for small databases ( N = 2 16 ).”
Zhu, R., Xu, L., Zeng, Y., & Yi, X. (2019) · Security and Communication Networks · doi:10.1155/2019/9126376 · Cited by 9
Optimizing privacy-preserving DSA for mobile clients
Troja, E., & Bakiras, S. (2017) · Ad Hoc Networks · doi:10.1016/j.adhoc.2017.02.001 · Cited by 9
Improving the Privacy of Tor Onion Services
Eaton, E., Sasy, S., & Goldberg, I. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-09234-3_14 · Cited by 7
“This goal can be accomplished either by using encryption with strong mathematical properties like fully homomorphic encryption, as in XPIR [1] or SealPIR [2], or by using secure hardware, as in ZeroTrace [30].”
MethodInfluentialFully Homomorphic Encryption with Table Lookup for Privacy-Preserving Smart Grid
Li, R., Ishimaki, Y., & Yamana, H. (2019) · IEEE International Conference on Smart Computing · doi:10.1109/smartcomp.2019.00023 · Cited by 13
“[10] introduced a PIR scheme with a query compression technique called XPIR.”
MethodOB-WSPES: A Uniform Evaluation System for Obfuscation-based Web Search Privacy
Wei, C., Gu, Q., Ji, S., Chen, W., Wang, Z., & Beyah, R. (2019) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2019.2962440 · Cited by 8
“In cryptography-based solutions [42], [43], [44], [45], also known as system-centric solutions, Private Information Retrieval (PIR) techniques are used to retrieve information from the search engines without revealing queries and search activities.”
MethodUnleashing the Power of Multi-Server PIR for Enabling Private Access to Spectrum Databases
Grissa, M., Hamdaoui, B., & Yavuz, A. A. (2018) · IEEE Communications Magazine · doi:10.1109/mcom.2018.1701341 · Cited by 7
“Despite the wide-spread usage of single-server PIR protocols in the context of database-driven CRN s, these protocols incur very large overhead as they involve highly costly cryptographic operations, such as modular multiplication over large moduli, that need to be executed over the entire database for every query com…”
BackgroundMethodComputational Code-Based Single-Server Private Information Retrieval
Holzbaur, L., Hollanti, C., & Wachter-Zeh, A. (2020) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit44484.2020.9174138 · Cited by 7
“Building on the protocol of [17], a method to significantly decrease the query size was introduced in [20].”
BackgroundMethodOn the privacy of a code-based single-server computational PIR scheme
Bordage, S., & Lavauzelle, J. (2021) · Cryptography and Communications · doi:10.1007/s12095-021-00477-z · Cited by 6
“proved the potential practicality of cPIR [1], but the question of building efficient cPIR protocols remains widely open.”
BackgroundTosun, T., & Savaş, E. (2021) · Journal of Information Security and Applications · doi:10.1016/j.jisa.2021.102830 · Cited by 6
DatashareNetwork: A Decentralized Privacy-Preserving Search Engine for Investigative JournalistsPreprint
EdalatNejad, K., Lueks, W., Martin, J. P., Ledésert, S., L'Hôte, A., Thomas, B., Girod, L., & Troncoso, C. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.14645 · Cited by 6
“Computational PIR protocols [8, 31, 37] (IT-PIR protocols [12, 26] do not apply) place a high computational burden on the database owner.”
BackgroundSPG: Structure-Private Graph Database via SqueezePIR
Liang, L., Lin, J., Qu, Z., Ahmad, I., Tu, F., Gupta, T., Ding, Y., & Xie, Y. (2023) · Proceedings of the VLDB Endowment · doi:10.14778/3587136.3587138 · Cited by 5
“In this work, we focus on the single-server CPIR because it is more practical than deploying non-colluding servers.”
BackgroundInfluentialP3LI5: Practical and confidEntial Lawful Interception on the 5G core
Intoci, F., Sturm, J., Fraunholz, D., Pyrgelis, A., & Barschel, C. (2023) · IEEE Conference on Communications and Network Security · doi:10.1109/cns59707.2023.10288872 · Cited by 9
OnionPIR: Effective Protection of Sensitive Metadata in Online Communication Networks
Demmler, D., Holz, M., & Schneider, T. H. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-61204-1_30 · Cited by 5
Limits of Practical Sublinear Secure Computation
Boyle, E., Ishai, Y., & Polychroniadou, A. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-96878-0_11 · Cited by 6
Privacy Preserving Calculation in Cloud using Fully Homomorphic Encryption with Table Lookup
Li, R., Ishimaki, Y., & Yamana, H. (2020) · IEEE International Conference on Big Data Analytics (ICBDA) · doi:10.1109/icbda49040.2020.9101276 · Cited by 6
“[17] introduced XPIR, a query compression method.”
Security-Enhanced Spatial Range Query Over Large-Scale Encrypted Mobile Cloud Datasets
Miao, Y., Yu, J., Li, J., 李兴华, Feng, J., Liu, Z., & Deng, R. H. (2025) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2025.3599519 · Cited by 4
“BasedonPIR[33],[34]protocol,thequeryingusercanchoose an index i and retrieve the i -th object from an untrusted server without revealing the access pattern.”
A survey on single server private information retrieval in a coding theory perspective
Alfarano, G. N., Khathuria, K., & Weger, V. (2021) · Applicable Algebra in Engineering Communication and Computing · doi:10.1007/s00200-021-00508-5 · Cited by 4
Oblivious Transfer from Rerandomizable PKE
Li, S., Zhang, C., & Lin, D. (2023) · Lecture notes in computer science · doi:10.1007/978-981-99-7356-9_8 · Cited by 4
“To date, the state-of-the-art PIR [16,2,20,18,1,17,14] and SPIR [15] protocols are based on fully-homomorphic encryption (FHE).”
BackgroundRevisiting Multivariate Ring Learning with Errors and Its Applications on Lattice-Based Cryptography
Pedrouzo-Ulloa, A., Troncoso-Pastoriza, J. R., Gama, N., Georgieva, M., & Pérez‐González, F. (2021) · Mathematics · doi:10.3390/math9080858 · Cited by 17
Fast and Accurate Function Evaluation with LUT over Integer-Based Fully Homomorphic Encryption
Li, R., & Yamana, H. (2021) · Lecture notes in networks and systems · doi:10.1007/978-3-030-75075-6_51 · Cited by 4
Pretzel: Email encryption and provider-supplied functions are compatiblePreprint
Gupta, T., Fingler, H., Alvisi, L., & Walfish, M. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1612.04265 · Cited by 7
“The modules, written in 5,300 lines of C++ and 160 lines of Python, glue the code we borrow from existing libraries: GPGME [9] for OpenPGP encryption, Obliv-C [137] for Yao’s 2PC protocol,5 XPIR [20] for the xpir-bv AHE scheme, liblinear [24, 57] to train LR and SVM classifiers, and SQLite FTS4 [10] for the search ind…”
MethodInfluentialPrivateFetch: Scalable Catalog Delivery in Privacy-Preserving AdvertisingPreprint
Mughees, M. H., Pestana, G., Davidson, A., & Livshits, B. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2109.08189 · Cited by 7
“[38] present XPIR with good computation cost.”
SmartPIR: A Private Information Retrieval System using Computational Storage Devices
Chen, Z., You, H., Wei, Q., Lu, H., Ju, L., & Shen, Z. (2025) · IEEE/ACM International Symposium on Microarchitecture (MICRO) · doi:10.1145/3725843.3756060 · Cited by 8
Faster Spiral: Low-Communication, High-Rate Private Information Retrieval
Luo, M., & Wang, M. (2025) · Cryptography · doi:10.3390/cryptography9010013 · Cited by 3
“For example, XPIR [9] instantiates v = 2 to achieve a balance between communication and computation costs.”
Do You Feel a Chill? Using PIR against Chilling Effects for Censorship-resistant Publishing
Mazmudar, M., Gurtler, S., & Goldberg, I. (2021) · ACM Workshop on Privacy in the Electronic Society (WPES) · doi:10.1145/3463676.3485612 · Cited by 7
Private retrieval of location-related content using k-anonymity and application to ICN
Kita, K., Koizumi, Y., & Hasegawa, T. (2022) · Computer Networks · doi:10.1016/j.comnet.2022.108908 · Cited by 4
Research on privacy information retrieval model based on hybrid homomorphic encryption
Song, W., Zeng, G., Zhang, W., & Tang, D. (2023) · Cybersecurity · doi:10.1186/s42400-023-00168-7 · Cited by 3
On Circuit Private, Multikey and Threshold Approximate Homomorphic Encryption
Kluczniak, K., & Santato, G. (2025) · IACR Communications in Cryptology · doi:10.62056/a69qgyl7s · Cited by 3
“We introduce formal models that allow us to reason about circuit privacy.”
Group ORAM for privacy and access control in outsourced personal records
Maffei, M., Malavolta, G., Reinert, M., & Schröder, D. (2018) · Journal of Computer Security · doi:10.3233/jcs-171030 · Cited by 3
From Task Tuning to Task Assignment in Privacy-Preserving Crowdsourcing Platforms
Duguépéroux, J., & Allard, T. (2020) · Lecture notes in computer science · doi:10.1007/978-3-662-62271-1_3 · Cited by 3
Lower-Cost epsilon-Private Information RetrievalPreprint
Toledo, R. R., Danezis, G., & Goldberg, I. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1604.00223 · Cited by 3
“Yet they provide the same functionality and interface, and in many cases can be used as drop-in replacements for traditional PIR.”
LightPIR: Single-Server PIR via FHE without Gaussian Noise
Xia, H., & Wang, M. (2024) · ACM Asia Conference on Computer and Communications Security (ASIA CCS) · doi:10.1145/3634737.3661140 · Cited by 2
“However, lattice-based constructions of single-server PIR [1, 5, 7, 30, 35, 43, 51, 58, 59, 62, 65] have made significant advancements, far surpassing the trivial PIR in terms of efficiency.”
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.