You are looking at a specific version 20201009:144327 of this paper. See the latest version.

Paper 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.

Note: updated affiliation

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Private information retrievalBatch PIRRandom PIRLarge-scale MPCSecrets on blockchainRandom ORAM
Contact author(s)
craigbgentry @ gmail com,shaih @ alum mit edu,magri @ cs au dk,jbn @ cs au dk,sophia yakoubov @ gmail com
History
2021-06-12: last of 4 revisions
2020-10-09: received
See all versions
Short URL
https://ia.cr/2020/1248
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.