The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
PIR with Compressed Queries and Amortized Query Processing
Open accessAbstract
Private information retrieval (PIR) is a key building block in many privacy-preserving systems. Unfortunately, existing constructions remain very expensive. This paper introduces two techniques that make the computational variant of PIR (CPIR) more efficient in practice. The first technique targets a recent class of CPU-efficient CPIR protocols where the query sent by the client contains a number of ciphertexts proportional to the size of the database. We show how to compresses this query, achieving size reductions of up to 274X. The second technique is a new data encoding called probabilistic batch codes (PBCs). We use PBCs to build a multi query PIR scheme that allows the server to amortize its computational cost when processing a batch of requests from the same client. This technique achieves up to 40× speedup over processing queries one at a time, and is significantly more efficient than related encodings. We apply our techniques to the Pung private communication system, which relies on a custom multi-query CPIR protocol for its privacy guarantees. By porting our techniques to Pung, we find that we can simultaneously reduce network costs by 36× and increase throughput by 3X.
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
Gaussian elimination is not optimal
Strassen, V. (1969) · Numerische Mathematik · doi:10.1007/bf02165411 · Cited by 2,509 · cited 1×
“, [29, 55, 71]) provides amortization over multiple matrix-vector multiplication instances.”
BackgroundXPIR: 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 · cited 1×
“For XPIR, we use the publicly available source code [9] and integrate it into our testing framework using Rust wrappers.”
MethodRiffle: An Efficient Communication System With Strong Anonymity
Kwon, A., Lazar, D., Devadas, S., & Ford, B. (2016) · Proceedings on Privacy Enhancing Technologies · doi:10.1515/popets-2016-0008 · Cited by 84
Research works printed but not linked: 75
- stern, 1998, A new and efficient all-or-nothing disclosure of secrets protocol, Proc Int'l Conf Theory Application of Cryptology and Information Security (ASIACRYPT)
- 10.1109/ISIT.2015.7282815 · doi:10.1109/isit.2015.7282815
- silberstein, 2014, Fractional repetition and erasure batch codes, 3rd International Castle Meeting on Coding Theory and Applications
- 10.1109/ISIT.2015.7282532 · doi:10.1109/isit.2015.7282532
- 10.1109/ISIT.2013.6620388 · doi:10.1109/isit.2013.6620388
- 10.1145/1250790.1250829 · doi:10.1145/1250790.1250829
- dong, 2014, A fast single server private information retrieval protocol with low communication cost, Proc Ninth European Symp Research Computer Security (ESORICS)
- 10.1145/792538.792546 · doi:10.1145/792538.792546
- 10.1007/BFb0032018 · doi:10.1007/bfb0032018
- 10.1109/TKDE.2012.90 · DOI
- 10.1109/SFCS.1995.492461 · DOI · Paper page
- chor, 1998, Cryptology ePrint Archive Report 1998/003
- cheng, 2016, Talek a private publish-subscribe protocol Technical Report UW-CSE-16–11-01
- chen, 1994, Optimal reponse time retrieval of replicated data, Proceedings of the ACM Symposium on Principles of Database Systems (PODS)
- devet, 2012, Optimally robust private information retrieval, Proceedings of the USENIX Security Symposium
- demmler, 2014, RAID-PIR: Practical multi-server PIR, Proc ACM Cloud Computing Security Workshop (CCSW)
- 10.1109/SFCS.1997.646108 · DOI
- 10.1145/28395.28396 · DOI · Paper page
- lipmaa, 2017, A simpler rate-optimal CPIR protocol, Proc Conf Financial Cryptography
- lueks, 2015, Sublinear scaling for multi-client private information retrieval, International Conference on Finance Cryptography and Data Security, 10.1007/978-3-662-47854-7_10 · DOI
- lipmaa, 2014, Linear batch codes, 3rd International Castle Meeting on Coding Theory and Applications
- mittal, 2011, PIR - Tor: Scalable anonymous communication using private information retrieval, Proceedings of the USENIX Security Symposium
- chen, 2017, Simple encrypted arithmetic library v2 3 0
- 10.1109/71.963420 · DOI · Paper page
- chang, 2004, Single database private information retrieval with logarithmic communication, Proc 3rd Australasian Conf Inform Security Privacy
- 10.1145/2517349.2522716 · DOI · Paper page
- pagh, 2001, Cuckoo hashing, Proceedings of the European Symposium on Algorithms (ESA)
- 10.1145/3133956.3134061 · DOI · Paper page
- 10.3934/amc.2009.3.13 · DOI
- 10.1145/3154794 · DOI · Paper page
- 10.1109/TIT.2016.2524007 · doi:10.1109/tit.2016.2524007
- 2017, OpenSignal State of Mobile Networks USA
- 2017, Akamai state of the internet connectivity report
- 10.1145/2090236.2090262 · DOI · Paper page
- brakerski, 2011, Fully homomorphic encryption from Ring - LWE and security for key dependent messages, Proc Int'l Cryptology Conf (CRYPTO)
- 10.1109/FOCS.2011.12 · DOI · Paper page
- cachin, 1999, Computationally private information retrieval with polylogarithmic communication, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt)
- breslow, 2016, Horton tables: Fast hash tables for in-memory data-intensive computing, Proceedings of the USENIX Annual Technical Conference (ATC)
- canetti, 2017, Towards doubly efficient private information retrieval, Proceedings of Theoretical Cryptography Conference (TCC), 10.1007/978-3-319-70503-3_23 · DOI
- cain, 2007, The random graph threshold for k-orientability and a fast algorithm for optimal multiple-choice allocation, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)
- 10.1515/popets-2016-0036 · DOI
- henry, 2013, One (block) size fits all: PIR and SPIR with variable-length records via multi-block queries, Proceedings of the Network and Distributed System Security Symposium (NDSS)
- lipmaa, 2009, First CPIR protocol with data-dependent computation, Proc Int'l Conf Information Security and Cryptology (ICISC)
- 10.1109/SFCS.1997.646125 · DOI · Paper page
- 10.1515/popets-2015-0016 · DOI
- 10.1007/978-3-642-40450-4_51 · doi:10.1007/978-3-642-40450-4_51
- 10.1109/INFCOM.2007.25 · doi:10.1109/infcom.2007.25
- 10.1145/258533.258660 · DOI · Paper page
- 10.1145/1007352.1007396 · DOI · Paper page
- albrecht, 2015, On the concrete hardness of learning with errors, Journal of Mathematical Cryptology, 9, 10.1515/jmc-2015-0016 · DOI · Paper page
- angel, 2016, Unobservable communication over fully untrusted infrastructure, Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI)
- fan, 2012, Cryptology ePrint Archive Report 2012/144
- 10.1109/FOCS.2010.80 · DOI
- azar, 1994, Balanced allocations, Proceedings of the ACM Symposium on Theory of Computing (STOC)
- 10.1145/2160158.2160159 · DOI · Paper page
- beimel, 2002, Breaking the O(n1/(2k-l)) barrier for information-theoretic private information retrieval, Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS)
- beimel, 2000, Reducing the servers computation in private information retrieval: PIR with preprocessing, Proc Int'l Cryptology Conf (CRYPTO)
- 10.1145/362686.362692 · DOI · Paper page
- 10.1515/popets-2015-0008 · DOI
- boyle, 2017, Can we access a database both locally and privately?, Proceedings of Theoretical Cryptography Conference (TCC), 10.1007/978-3-319-70503-3_22 · DOI
- 2017, Simple encrypted arithmetic library - SEAL
- 2017, Pung Unobservable communication over fully untrusted infrastructure
- 2017, XPIR NFLParams
- 2017, XPIR NFLLWE security estimator
- 2018, Internet providers with data caps
- gupta, 2016, Scalable and private media consumption with Popcorn, Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI)
- aguilar-melchor, 2016, XPIR Private information retrieval for everyone
- 10.1109/SP.2007.23 · DOI · Paper page
- gentry, 2005, Single-database private information retrieval with constant communication rate, Proc 29th Int Colloquium Automata Languages Program (ICALP), 10.1007/11523468_65 · DOI · Paper page
- groth, 2010, Multi-query computationally-private information retrieval with constant communication rate, International Conference on Practice and Theory in Public-Key Cryptography (PKC)
- 10.1145/2976749.2978407 · DOI
- 10.1137/090770928 · doi:10.1137/090770928
- fernholz, 2007, The k-orientability thresholds for Gn, p, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)
- gentry, 2012, Fully homomorphic encryption with polylog overhead, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt)
- 10.1007/978-3-662-53644-5_10 · doi:10.1007/978-3-662-53644-5_10
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].”
BackgroundPrivate 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
“Our experimental database contains n = 216, 218, 220 records of 288 bytes and to match the experiments of previous works [7, 8].”
BackgroundMethodResultInfluentialSHECS-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
Secure Federated Submodel Learning
Niu, C., Wu, F., Tang, S., Hua, L., Jia, R., Lv, C., Wu, Z., & Chen, G. (2019) · arXiv · doi:10.48550/arxiv.1911.02254 · Cited by 28
“To avoid downloading the full matrix, Private Information Retrieval (PIR) [13]–[15] can be applied, which exactly matches our problem settings, including the read-only mode and the privacy preservation requirement of the retrieved elements.”
Method
Metadata
- Authors
- Angel, S., Chen, H., Laine, K., & Setty, S.
- Venue
- 2018 IEEE Symposium on Security and Privacy (SP)
- Publisher
- IEEE
- Published
- 2018-05
- Volume
- 2017
- Pages
- 962-979
- ISSN
- 1081-6011 (ISSN-L)
- OpenAlex
- W2883089683
- Cited by
- 251
- References
- 3
- FWCI
- 6.97
- Type
- conference paper
- Language
- en
- Open access
- bronze
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: PIR with Compressed Queries and Amortized Query Processing. https://app.cochat.ai/papers/10.1109/sp.2018.00062
- The paper
- Angel, S., Chen, H., Laine, K., & Setty, S. (2018). PIR with Compressed Queries and Amortized Query Processing. 2018 IEEE Symposium on Security and Privacy (SP). https://doi.org/10.1109/sp.2018.00062
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.