Private Information Retrieval in the Shuffle Model

Abstract 
Private information retrieval (PIR) is a powerful cryptographic tool for building many interesting applications, like private search engines, private group chats and more. Although in recent years we have witnessed great strides towards efficient PIR both in theory (e.g., LMW23) and in practice (e.g., SimplePIR), the inherent lower bound of PIR prevents us from going further. 

We consider PIR under "the shuffle model", where queries can be made anonymously by multiple clients. This model can also be viewed as a hybrid between the single-server and the two-server settings: one server holds the database and another server holds a secret permutation. 
- On the theory side, we present the first PIR scheme in this model that has information-theoretic security and sublinear per-client communication. In particular, for every γ > 0, the protocol has O(n^γ) communication and computation costs per (stateless) client, with 1/poly(n) statistical security, assuming that a size-n database is simultaneously accessed by poly(n) clients. 
- On the practice side, we construct concretely efficient PIR in the shuffle model based on computational assumption LPN; even better efficiency follows from conjectured hardness of Multi-Disjoint Syndrome Decoding. In the batched query setting, this PIR scheme has ~20x improvement of throughput over the state-of-the-art single-server PIR schemes. 

Finally, I will discuss a few interesting use cases of the shuffle model in other secure computation tasks. 

This talk is based on joint works with Adrià Gascón, Yuval Ishai, Mahimna Kelkar, Daniel Lee, Baiyu Li, and Mariana Raykova.