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
Practical Private Information Systems
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
Performance and benchmarks
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