Staircase-PIR: Universally Robust Private Information Retrieval
By Rawad Bitar, Salim el Rouayheb. 2018
29 citations recorded by the source corpus.
We consider the problem of designing private information retrieval (PIR) schemes on data of m files replicated on n servers that can possibly collude. We focus on devising robust PIR schemes that can tolerate stragglers, i.e., slow or unresponsive servers. In many settings, the number of stragglers is not known a priori or may change with time. We define universally robust PIR as schemes that achieve PIR capacity asymptotically in m and simultaneously for any number of stragglers up to a given threshold. We introduce Staircase-PIR schemes and prove that they are universally robust. Towards that end, we establish an equivalence between robust PIR and communication efficient secret sharing.
Subfields: Artificial Intelligence, Computer Networks and Communications, Privacy & Security
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Martin Jaggi
- Qiang Yang
- Jakub Konecný
- Peter Kairouz
- Peter Richtárik
- Ananda Theertha Suresh
- Jianyu Wang
- Sebastian U. Stich
In Computer Networks and Communications
- Sebastian U. Stich
- Martin Jaggi
- Jianyu Wang
- Aurélien Bellet
- Prateek Mittal
- Gauri Joshi
- Peter Kairouz
- Lie He
In Privacy & Security
- Peter Kairouz
- Badih Ghazi
- Rasmus Pagh
- Qiang Yang
- Ziteng Sun
- Adrià Gascón
- H. Brendan McMahan
- Aurélien Bellet
Citations in the corpus
- Advances and Open Problems in Federated Learning (2019, background): “[280] A. Ali, T. Lepoint, S. Patel, M. Raykova, P. Schoppmann, K. Seth, and K. Yeo, “Communication-computation trade-offs in PIR,” IACR Cryptol. ePrint Arch., vol. 2019, p. 1483, 2019.”