Multiround Private Information Retrieval: Capacity and Storage Overhead

Understand

The capacity has recently been characterized for the private information retrieval (PIR) problem as well as several of its variants.

• In every case it is assumed that all the queries are generated by the user simultaneously.
• Here we consider multiround PIR, where the queries in each round are allowed to depend on the answers received in previous rounds.
• We show that the capacity of multiround PIR is the same as the capacity of single-round PIR (the result is generalized to also include $T$-privacy constraints).