Craig Gentry and Shai Halevi and Bernardo Magri and Jesper Buus Nielsen and Sophia Yakoubov

Abstract: Private information retrieval (PIR) lets a client retrieve an entry from a database held by a server, without the server learning which entry was retrieved. Here we study a weaker variant that we call *random-index PIR* (RPIR). It differs from standard PIR in that the retrieved index is an output rather than an input of the protocol, and it is chosen at random.

Our motivation for studying RPIR comes from a recent work of Benhamouda et al. (TCC’20) about maintaining secret values on public blockchains. Their solution involves choosing a small anonymous committee from among a large universe, and here we show that RPIR can be used for that purpose.

The RPIR client must be implemented via secure MPC for this use case, stressing the need to make it as efficient as can be. Combined with recent techniques for secure-MPC with stateless parties, our results yield a new secrets-on-blockchain construction (and more generally large-scale MPC). Our solution tolerates any fraction f⪇1/2 of corrupted parties, solving an open problem left from the work of Benhamouda et al.

Considering RPIR as a primitive, we show that it is in fact equivalent to PIR when there are no restrictions on the number of communication rounds. On the other hand, RPIR can be implemented in a “noninteractive” setting, which is clearly impossible for PIR. We also study batch RPIR, where multiple indexes are retrieved at once. Specifically we consider a weaker security guarantee than full RPIR, which is still good enough for our motivating application. We show that this weaker variant can be realized more efficiently than standard PIR or RPIR, and we discuss one protocol in particular that may be attractive for practical implementations.