Practical Private Information Systems

[gpestana]

Practical Private Information Systems

• What are the current production ready computational PIR implementations?
• How do they perform?

Motivation

Project implementations

• XPIR [3] github C++ implementation of a lattice based computational PIR system. Rust bindings for XPIR: github

• mXPIR [4] github Rust implementation of mXPIR, a computational multi-query PIR library for XPIR

• SealPIR [4] github C++ implementation of SealPIR for low communication costs and high performance

• PIR-PSI [5] github C++ implementation of a private set intersection based PIR

Performance and benchmarks

• SealPIR [4]

SealPIR results in queries that are 274× smaller and are 16.4× less expensive for the client to construct. However, SealPIR introduces between 11% and 24% CPU overhead to the server (over XPIR) to obliviously expand queries

Techniques for improving performance and tradeoffs

• dummy queries [1] dummy queries are made alongside with user queries in order to dilute the user's activities. This scheme has been used by databases, DNS queries and web search [2]. Naive schemes based on dummy queries are not secure and may leak information [1].

• anonymous requests: making database queries through anonymous requests systems (such as Tor and mix networks) alone does not provide ε-differential privacy [1].

• composing dummy queries and anonymous requests: [1] shows that composing 2 non ε-differential privacy, provides a scheme which is ε-differential private.

• sparse vectors [1]

• compositions with an anonymity system [1]

• probabilistic batch codes (PBCs) [3]

Conclusions

References

[1] Toledo, R. R., Danezis, G., & Goldberg, I. (2016). Lower-Cost ∈-Private Information Retrieval. Proceedings on Privacy Enhancing Technologies, 2016(4), 184–201. https://doi.org/10.1515/popets-2016-0035

[2] Balsa, E., Troncoso, C., & Diaz, C. (2012). OB-PWS: Obfuscation-based private web search. Proceedings - IEEE Symposium on Security and Privacy, 491–505. https://doi.org/10.1109/SP.2012.36

[3] Carlos Aguilar-Melchor, Joris Barrier, Laurent Fousse, Marc-Olivier Killijian, "XPIR: Private Information Retrieval for Everyone", Proceedings on Privacy Enhancing Technologies. Volume 2016, Issue 2, Pages 155–174, ISSN (Online) 2299-0984, DOI: 10.1515/popets-2016-0010, December 2015.

[4] Angel, S., Chen, H., Laine, K., & Setty, S. (n.d.). PIR with compressed queries and amortized query processing.

[5] Demmler, D., Rindal, P., Rosulek, M., & Trieu, N. (2018). PIR-PSI: Scaling Private Contact Discovery. Proceedings on Privacy Enhancing Technologies, 2018(4), 159–178. https://doi.org/10.1515/popets-2018-0037