Random-Index PIR and Applications

Private information retrieval (PIR) lets a client retrieve an entry from a database without the server learning which entry was retrieved. Here we study a weaker variant that we call random-index PIR (RPIR), where the retrieved index is an output rather than an input of the protocol, and is chosen at random. RPIR is clearly weaker than PIR, but it suffices for some interesting applications and may be realized more efficiently than full-blown PIR.

We report here on two lines of work, both tied to RPIR but otherwise largely unrelated. The first line of work studies RPIR as a primitive on its own. Perhaps surprisingly, we show that RPIR 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 (with pre-processing), which is clearly impossible for PIR. For two-server RPIR we even show a truly noninteractive solution, offering information-theoretic security without any pre-processing.

The other line of work, which was the original motivation for our work, uses RPIR to improve on the recent work of Benhamouda et al. (TCC’20) for maintaining secret values on public blockchains. Their solution depends on a method for selecting many random public keys from a PKI while hiding most of the selected keys from an adversary. However, the method they proposed is vulnerable to a double-dipping attack, limiting its resilience. Here we observe that a RPIR protocol, where the client is implemented via secure MPC, can eliminate that vulnerability. We thus get a secrets-on-blockchain protocol (and more generally large-scale MPC) which is resilient to any fraction \(f < 1/2\) of corrupted parties, resolving the main open problem left from the work of Benhamouda et al.

As the client in this solution is implemented via secure MPC, it really brings home the need to make it as efficient as possible. We thus strive to explore whatever efficiency gains we can get by using RPIR rather than PIR. We achieve more gains by using batch RPIR where multiple indexes are retrieved at once. Lastly, we observe that this application can make do with a weaker security guarantee than full RPIR, and show that this weaker variant can be realized even more efficiently. We discuss one protocol in particular that may be attractive for practical implementations.

1. 1.

   Note that standard PIR does not provide any privacy to the server, hence the functionality lets a corrupted client get the entire database.

2. 2.

   Consider an array of length \(v + d\). Consider placing a 0 in v positions and a 1 in the remaining d positions. Let the degree of \(\mathtt {x}_i\) be the number of 1’s between the i’th occurrence of a 0 and the \((i+1)\)’th occurrence of a 0 (or the end of the array when \(i=v\)). Clearly this gives total degree at most d and there is a one-to-one correspondence between such assignments and monomials of degree at most d. There are \(k = {{v+d} \atopwithdelims ()v}\) ways to place the v entries which are 0.

3. 3.

   For the reader familiar with Reed-Muller based PIR it looks odd to pick a at random. However, this leads up to the non-interactive versions, as detailed below.

4. 4.

   We can assume wlog that the client state does not change throughout the protocol.

5. 5.

   Parties can perform these computations lazily, only when they are selected to a committee, but this does not change the total number of operations that they must perform.

Authors and Affiliations

1. Algorand Foundation, New York, USA

   Craig Gentry & Shai Halevi

2. Concordium Blockchain Research Center, Aarhus University, Aarhus, Denmark

   Bernardo Magri & Jesper Buus Nielsen

3. Aarhus University, Aarhus, Denmark

   Bernardo Magri, Jesper Buus Nielsen & Sophia Yakoubov

Editors and Affiliations

1. Georgetown University, Washington, WA, USA

   Kobbi Nissim

2. The University of Texas at Austin, Austin, TX, USA

   Brent Waters

A Random-Index Oblivious-RAM

In this section we note that a random-index ORAM (RORAM) can be used in our motivating application instead of RPIR, resulting is a somewhat different performance profile. We begin by defining RORAM.

A Random-Index ORAM (RORAM) is a two party protocol between a client and a server similar to Oblivious RAM (ORAM), except that the client does not choose the indexes to read from memory. Instead, these indexes are chosen at random (by the protocol), with the client getting \((i,\mathsf {Mem}_i)\) while hiding them from the server. Similarly to ORAM, we have procedures for \(\mathsf {Init}\), \(\mathsf {Read}\), and \(\mathsf {Write}\), except that the index to be read is not an input to \(\mathsf {Read}\) but an output of it.

Definition 7

(RORAM Syntax). A Random-Index ORAM protocol (RORAM) consists of the following components:

• \(\mathsf {Init}(1^\kappa ,\mathsf {Mem}) \rightarrow (\mathsf {cst};\mathsf {SST})\): The initialization algorithm takes as input the security parameter and initial memory \(\mathsf {Mem}\in \{0,1\}^*\) (that could be empty), and generates an initial secret client state \(\mathsf {cst}\) and a public server state \(\mathsf {SST}\).

• \(\mathsf {Read}(\mathsf {cst},\mathsf {SST}) \rightarrow (i,x,\mathsf {SST}')\): The client fetches \((i,\mathsf {Mem}_i)\) (presumably for a random index \(i\in |\mathsf {Mem}|\)), and the server state is updated to \(\mathsf {SST}'\).^{Footnote 4}

• \(\mathsf {Write}(\mathsf {cst},i,x,\mathsf {SST}) \rightarrow \mathsf {SST}'\): The content of the memory is modified by setting \(\mathsf {Mem}[i] := x\) and the server state is updated to \(\mathsf {SST}'\).

A RORAM protocol is nontrivial if the communication in each of \(\mathsf {Read}\) and \(\mathsf {Write}\) operations is \(o(|\mathsf {Mem}|)\).

Desired Properties: The security notion for (computational) ORAM from [18] intuitively says that the server should not learn anything about which data and in what order it is being accessed. (We may also require that the server cannot learn if the operation is read or write.) As for RPIR, here too it is convenient to define security by means of an ideal functionality.

RORAM Functionality. The functionality \(\mathcal {F}_{\mathsf {RORAM}}\) takes as input a (possibly empty) initial \(\mathsf {Mem}\in \{0,1\}^*\) from the client. It stores \(\mathsf {Mem}\) internally and gives the size of the memory \(|\mathsf {Mem}|\) to the server.

Thereafter, on input \(\mathsf {Read}\) from the client it sets \(n:=|\mathsf {Mem}|\), chooses at random an index \(i\leftarrow [n]\), returns \((i,\mathsf {Mem}[i])\) to the client, and outputs n to the server. On input \(\mathsf {Write}(i,x)\) from the client (i in unary) it modifies \(\mathsf {Mem}[i]:=x\) (extending the memory if needed), and outputs the new \(|\mathsf {Mem}|\) to the server.

Definition 8

(RORAM). A two-party protocol \(\varPi \) is a Random ORAM if it realizes the functionality \(\mathcal {F}_{\mathsf {RORAM}}\) above.

1.1 A.1 Target Anonymous Channels from RORAM

One can use (batch) RORAM as an almost “drop-in” replacement for (batch) RPIR to establish target-anonymous channels. Here too we have previous committees playing the part of the RORAM client, where the server state is publicly known so every committee member can simulate the server in its head. However, there are a few differences.

In the RPIR-based solution, the server state only changes when the database contents change; that is, when public keys are added or removed due to a party joining or leaving the pool of participants (or parties changing their keys). When this happens, no additional communication is needed to run the RPIR server, since all parties can update the server state locally. In contrast, the RORAM server state is evolving dynamically with each read/write operation, and the state depends on the client secret. This has several consequences. First, setting up the server state takes O(n) communication (where n is the number of parties in the pool of participants), since communication with the client (played by the committees) is necessary for every write. Second, every party in the pool of participants must continuously update the server state and keep a local copy of it, so that it can simulate the server for itself if it gets selected to one of these committees. Namely, whenever a client-simulating committee broadcasts an RORAM-client message, every party in the universe must update its local copy of the RORAM-server state accordingly.

The rest of the construction works just like the RPIR-based solution, with the committees implementing the RORAM client and any secrets that the client requires passed from committee to committee using the proactive secret sharing technique of Benhamouda et al. [2]. The result is summarized by the following informal theorem:

Theorem 7

In the model of Benhamouda et al. [2] with a broadcast channel and mobile adversary, given anonymous PKE (for the target-anonymous channels) and a nontrivial RORAM protocol satisfying Definition 8, there exists a scalable ECPSS scheme as per [2, Def 2.3], tolerating any fraction \(f<1/2\) of corrupt parties.

We remark that there is an interesting trade-off between the RPIR-based and the RORAM-based solutions: While both tools can provide a scalable solution (in that the amount of communication in each step is independent of the universe size n), they differ in how many parties need to perform local computation, and how much local computation each of them must do.

• When using RPIR, the only parties that need to perform local computations in each step are the current committee members (so only \(O(\kappa )\) of them). However, each one of them must play the RPIR server, so it must do at least \(\varOmega (n)\) operations.

• When using RORAM, every party in the universe must keep up to date with the evolving server state, so every party must perform some computation in every step.^{Footnote 5} On the other hand, the computational complexity of one server-step is typically just polylog(n) (depending on the underlying RORAM protocol).

Hence we have a choice between \(O(\kappa )\) parties performing \(\varOmega (n)\) operations each for RPIR, or all n parties performing only polylog(n) operations each for RORAM. It is an interesting open problem to find a solution where both the number of computing parties and the complexity of operations is sublinear in n (possibly using some combination of RPIR and RORAM).

B Target Anonymous Channels from Mix-Nets

A different approach to setting up target anonymous communication channels is using Mix-Nets [5], i.e., by repeatedly shuffling and re-randomizing all the keys. This solution can be implemented simply by having individual parties self-select to shuffle and re-randomize all parties’ public keys, then proves in zero knowledge that they did so correctly. Since the shuffling parties do not need any secret state, they can self-select using VRFs or by solving moderately-hard puzzles. There is no need to establish target-anonymous channels with these parties as recipients.

Notice that this setting is slightly different than traditional use of Mix-Nets, in that the shuffled and re-randomized entities are themselves public keys, with the corresponding secret keys held by individual parties. This means in particular that the adversary can always recognize its own keys in the shuffled list; only the honest parties’ keys are hidden. Therefore, even after all the shuffling is done, we still require fresh public randomness—unpredictable by the adversary—to select the rerandomized keys from the shuffled database. (Otherwise a malicious last shuffler can plant keys belonging to corrupt parties in the positions from which keys are to be selected.)

This solution uses \(\kappa \) (security parameter) shuffles, so that at least one of the shufflers will be honest with overwhelming probability. As usual with Mix-Nets, all we need is one honest shuffler, as biased shuffles do no harm as long as at least one shuffle along the way is uniform. Also, we assume a synchronous model, so if one or more shufflers do not show up to play their roles, we simply skip their turns.

The major drawback here is communication; each of the \(\kappa \) shufflers needs to broadcast \(n\) public keys, or \(O(n\kappa )\) bits. This gives us a total communication complexity of \(O(n\kappa ^2)\). On the other hand, this solution is very simple and requires no evolving secret state to be passed among the parties, making it appealing in some practical settings where the number of parties is not so large.

The solution can be optimized further, along somewhat similar lines to the batch-RPIR construction from Sect. 5.2: We divide the database of public keys into m bins each containing \(\frac{n}{m}\) public keys. We then run the Mix-Net solution above on each bin separately, using independently-chosen set of shufflers for each bin. Finally we use fresh public randomness to select k/m committee members from each bin. Note that we can now use only \(s\ll \kappa \) shuffling steps, maybe as little as \(s=\varTheta (1)\). Each bin has \(2^{-s}\) probability of having all corrupt shufflers, hence starting from an f-fraction of corrupt parties the expected fraction of corrupt committee members per bin is \(f'=2^{-s}+f(1-2^{-s})\), and setting m large enough we can ensure that the actual fraction is very close to \(f'\) whp.

The total communication complexity of this modified scheme becomes \(O(n\kappa s)\). For comparison, the FHE-based batch RPIR approach (Sect. 3) in combination with YOSO MPC gives total communication complexity of \(\tilde{O}(\kappa ^3)\), where both the size of a YOSO MPC committee and the number of keys being selected (for communication channels to the next committee) is \(O(\kappa )\), and the length of an FHE decryption share is \(\tilde{O}(\kappa )\). While the dependence of the communication complexity on \(n\) in the Mix-Nets solution may appear crippling, in practice the term \(\tilde{O}(\kappa ^3)\) may dwarf the number of participants n.

Reprints and permissions

© 2021 International Association for Cryptologic Research

Policies and ethics