Cryptology ePrint Archive: Report 2020/1248

Random-index PIR with Applications to Large-Scale Secure MPC

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 \lneq 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.

Category / Keywords: cryptographic protocols / Private information retrieval, Batch PIR, Random PIR, Large-scale MPC, Secrets on blockchain, Random ORAM

Date: received 8 Oct 2020, last revised 9 Oct 2020

Contact author: craigbgentry at gmail com,shaih@alum mit edu,magri@cs au dk,jbn@cs au dk,sophia yakoubov@gmail com

Available format(s): PDF | BibTeX Citation

Note: updated affiliation

Version: 20201009:144327 (All versions of this report)

Short URL: ia.cr/2020/1248


[ Cryptology ePrint archive ]