CoChat

PIR with Compressed Queries and Amortized Query Processing

Open access
Angel, Sebastian, Chen, Hao, Laine, Kim, Setty, Srinath · 2018 · 2018 IEEE Symposium on Security and Privacy (SP)
Cited by 251

The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.

Abstract

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1109/sp.2018.00062

Cites

3 of 3 references verified0 citation errors · 0 not checkable

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.

A few free checks a day · papers already verified open instantly · results are public

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

Research works printed but not linked: 75

  1. 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)
  2. 10.1109/ISIT.2015.7282815 · doi:10.1109/isit.2015.7282815
  3. silberstein, 2014, Fractional repetition and erasure batch codes, 3rd International Castle Meeting on Coding Theory and Applications
  4. 10.1109/ISIT.2015.7282532 · doi:10.1109/isit.2015.7282532
  5. 10.1109/ISIT.2013.6620388 · doi:10.1109/isit.2013.6620388
  6. 10.1145/1250790.1250829 · doi:10.1145/1250790.1250829
  7. dong, 2014, A fast single server private information retrieval protocol with low communication cost, Proc Ninth European Symp Research Computer Security (ESORICS)
  8. 10.1145/792538.792546 · doi:10.1145/792538.792546
  9. 10.1007/BFb0032018 · doi:10.1007/bfb0032018
  10. 10.1109/TKDE.2012.90 · DOI
  11. 10.1109/SFCS.1995.492461 · DOI · Paper page
  12. chor, 1998, Cryptology ePrint Archive Report 1998/003
  13. cheng, 2016, Talek a private publish-subscribe protocol Technical Report UW-CSE-16–11-01
  14. chen, 1994, Optimal reponse time retrieval of replicated data, Proceedings of the ACM Symposium on Principles of Database Systems (PODS)
  15. devet, 2012, Optimally robust private information retrieval, Proceedings of the USENIX Security Symposium
  16. demmler, 2014, RAID-PIR: Practical multi-server PIR, Proc ACM Cloud Computing Security Workshop (CCSW)
  17. 10.1109/SFCS.1997.646108 · DOI
  18. 10.1145/28395.28396 · DOI · Paper page
  19. lipmaa, 2017, A simpler rate-optimal CPIR protocol, Proc Conf Financial Cryptography
  20. 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
  21. lipmaa, 2014, Linear batch codes, 3rd International Castle Meeting on Coding Theory and Applications
  22. mittal, 2011, PIR - Tor: Scalable anonymous communication using private information retrieval, Proceedings of the USENIX Security Symposium
  23. chen, 2017, Simple encrypted arithmetic library v2 3 0
  24. 10.1109/71.963420 · DOI · Paper page
  25. chang, 2004, Single database private information retrieval with logarithmic communication, Proc 3rd Australasian Conf Inform Security Privacy
  26. 10.1145/2517349.2522716 · DOI · Paper page
  27. pagh, 2001, Cuckoo hashing, Proceedings of the European Symposium on Algorithms (ESA)
  28. 10.1145/3133956.3134061 · DOI · Paper page
  29. 10.3934/amc.2009.3.13 · DOI
  30. 10.1145/3154794 · DOI · Paper page
  31. 10.1109/TIT.2016.2524007 · doi:10.1109/tit.2016.2524007
  32. 2017, OpenSignal State of Mobile Networks USA
  33. 2017, Akamai state of the internet connectivity report
  34. 10.1145/2090236.2090262 · DOI · Paper page
  35. brakerski, 2011, Fully homomorphic encryption from Ring - LWE and security for key dependent messages, Proc Int'l Cryptology Conf (CRYPTO)
  36. 10.1109/FOCS.2011.12 · DOI · Paper page
  37. cachin, 1999, Computationally private information retrieval with polylogarithmic communication, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt)
  38. breslow, 2016, Horton tables: Fast hash tables for in-memory data-intensive computing, Proceedings of the USENIX Annual Technical Conference (ATC)
  39. canetti, 2017, Towards doubly efficient private information retrieval, Proceedings of Theoretical Cryptography Conference (TCC), 10.1007/978-3-319-70503-3_23 · DOI
  40. 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)
  41. 10.1515/popets-2016-0036 · DOI
  42. 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)
  43. lipmaa, 2009, First CPIR protocol with data-dependent computation, Proc Int'l Conf Information Security and Cryptology (ICISC)
  44. 10.1109/SFCS.1997.646125 · DOI · Paper page
  45. 10.1515/popets-2015-0016 · DOI
  46. 10.1007/978-3-642-40450-4_51 · doi:10.1007/978-3-642-40450-4_51
  47. 10.1109/INFCOM.2007.25 · doi:10.1109/infcom.2007.25
  48. 10.1145/258533.258660 · DOI · Paper page
  49. 10.1145/1007352.1007396 · DOI · Paper page
  50. albrecht, 2015, On the concrete hardness of learning with errors, Journal of Mathematical Cryptology, 9, 10.1515/jmc-2015-0016 · DOI · Paper page
  51. angel, 2016, Unobservable communication over fully untrusted infrastructure, Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI)
  52. fan, 2012, Cryptology ePrint Archive Report 2012/144
  53. 10.1109/FOCS.2010.80 · DOI
  54. azar, 1994, Balanced allocations, Proceedings of the ACM Symposium on Theory of Computing (STOC)
  55. 10.1145/2160158.2160159 · DOI · Paper page
  56. 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)
  57. beimel, 2000, Reducing the servers computation in private information retrieval: PIR with preprocessing, Proc Int'l Cryptology Conf (CRYPTO)
  58. 10.1145/362686.362692 · DOI · Paper page
  59. 10.1515/popets-2015-0008 · DOI
  60. 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
  61. 2017, Simple encrypted arithmetic library - SEAL
  62. 2017, Pung Unobservable communication over fully untrusted infrastructure
  63. 2017, XPIR NFLParams
  64. 2017, XPIR NFLLWE security estimator
  65. 2018, Internet providers with data caps
  66. gupta, 2016, Scalable and private media consumption with Popcorn, Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI)
  67. aguilar-melchor, 2016, XPIR Private information retrieval for everyone
  68. 10.1109/SP.2007.23 · DOI · Paper page
  69. 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
  70. groth, 2010, Multi-query computationally-private information retrieval with constant communication rate, International Conference on Practice and Theory in Public-Key Cryptography (PKC)
  71. 10.1145/2976749.2978407 · DOI
  72. 10.1137/090770928 · doi:10.1137/090770928
  73. fernholz, 2007, The k-orientability thresholds for Gn, p, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)
  74. gentry, 2012, Fully homomorphic encryption with polylog overhead, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt)
  75. 10.1007/978-3-662-53644-5_10 · doi:10.1007/978-3-662-53644-5_10

Cited by

See all 251

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

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.