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.
Abstract: Existing Nakamoto-style blockchains (NSBs) rely on some sort of synchrony assumption to offer any type of safety guarantees. A basic requirement is that when a party produces a new block, then all previously produced blocks should be known to that party, as otherwise the new block might not append the current head of the chain, creating a fork. In practice, however, the network delay for parties to receive messages is not a known constant, but rather varies over time. The consequence is that the parameters of the blockchain need to be set such that the time between the generation of two blocks is typically larger than the network delay (e.g.,minutes in Bitcoin) to guarantee security even under bad network conditions. This results in lost efficiency for two reasons: (1) Since blocks are produced less often, there is low throughput. Furthermore, (2) blocks can only be considered final, and thus the transactions inside confirmed, once they are extended by sufficiently many other blocks, which incurs a waiting time that is a multiple of 10 minutes. This is true even if the actual network delay is only second, meaning that NSBs are slow even under good network conditions. We show how the Bitcoin protocol can be adjusted such that we preserve Bitcoin’s security guarantees in the worst case, and in addition, our protocol can produce blocks arbitrarily fast and achieve optimistic responsiveness. The latter means that in periods without corruption, the confirmation time only depends on the (unknown) actual network delay instead of the known upper bound. Technically, we propose an approach where blocks are treated differently in the “longest chain rule”. The crucial parameter of our protocol is a weight function assigning different weight to blocks according to their hash value. We present a framework for analyzing different weight functions, in which we prove all statements at the appropriate level of abstraction. This allows us to quickly derive protocol guarantees for different weight functions. We exemplify the usefulness of our framework by capturing the classical Bitcoin protocol as well as exponentially growing functions as special cases, where the latter provide the above mentioned guarantees, including optimistic responsivene