Part1Private Information Retrieval (PIR) scheme

A 1-server private information retrieval (PIR) scheme is a tuple of PPT algorithms with the following syntax:

• takes as input a security parameter in unary, an input size , and an index , and outputs a query along with a trapdoor .
• takes as input a query and a database , and outputs an answer .
• takes as input a trapdoor and an answer , and outputs a plaintext .

These algorithms should satisfy the following properties:

• Correctness: For every and ,

where the probability is over .

• -Privacy: For any -size adversary there exists a negligible function such that for every ,

Kushilevitz and Ostrovsky [KO97] constructed the first sublinear-communication single-server PIR scheme and was followed up by several other works [GR05, Lip05, BV11, DGI+19].

• [CGKS95]: Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan. Private information retrieval.
• [KO97]: Eyal Kushilevitz and Rafail Ostrovsky. Replication is not needed: Single database, computationally-private information retrieval.
• [DGI+19]: Nico Döttling, Sanjam Garg, Yuval Ishai, Giulio Malavolta, Tamer Mour, and Rafail Ostrovsky. Trapdoor hash functions and their applications.

Theorem  ([BV11, DGI+19]). For any function S : N → N, there exists a -private 1-server PIR scheme with query complexity for length- databases, under the -hardness of the LWE, Quadratic Residuosity, or DDH assumptions. Moreover, these schemes are -straight-line secure.

Part2The BMW (Biehl-Meyer-Wetzel) heuristic

The BMW heuristic converts a PCP scheme into a 2-message, succinct, privately verifiable argument.

It does this by allowing one to query a PCP proof using a PIR scheme.

Fix any 1-server PIR scheme and any PCP scheme (II, for a language .

On input and , the 2 -message succinct argument for protocol proceeds as follows:

• Verifier: computes For each , it generates , where is the length of the PCP. It sends to the prover.
• Prover: computes the PCP string , and for each , it computes . It sends to the verifier.
• Verdict: computes for each , and accepts if and only if .

Part3Multi-extractable Somewhere Statistically Binding (meSSB) Hash Family

1Hash Function Families with Local Opening

A hash family is a pair of PPT algorithms , where

• takes as input a security parameter in unary and an input length , and outputs a hash key .
•  takes as input a hash key and an input and outputs an element .

Here, and are parameters associated with the hash family.

A hash family with local opening is a hash family , along with two additional PPT algorithms with the following syntax:

• ) takes as input a hash key , and an index and outputs an opening , where .
• takes as input a hash key , a hash value , an index , a value , and an opening , and outputs 1 or 0 indicating accept or reject, respectively.

These algorithms should satisfy the property:

• Correctness of Opening: For every and ,

where the probability is over .

2Extractable Somewhere Statistically Binding (eSSB) Hash Functions

SSB hash functions are hash functions with local openings that have an additional special property: for any index , one can generate a hash key that guarantees statistical binding for the position . Namely, even an unbounded adversary cannot open the bit at position to two different values.

Furthermore, the hash key should be index-hiding, namely, it should hide the index from all polynomial-time adversaries.

• [HW15]: Pavel Hubácek and Daniel Wichs. On the communication complexity of secure function evaluation with long output.

We augment this notion by requiring that the statistically bound value at position can be recovered from the hash output using a trapdoor underlying the hash key.

A  -hiding extractable somewhere statistically binding (eSSB) hash family is a hash family with local opening , with the following changes:

• takes as additional input an index and outputs a hash key as well as a trapdoor ,

An eSSB hash family also has an additional PPT algorithm .

• takes as input a trapdoor and a hash value , and outputs a value .

These algorithms should satisfy the following properties:

• -Index Hiding: For any poly -size adversary there exists a negligible function such that for any ,

• Correctness of Inversion: For any , and any and ,

where the probability is over .

• Somewhere Statistically Binding: For any and ,

where the probability is over

Hubáček and Wichs constructed SSB hash functions assuming the existence of a leveled homomorphic encryption scheme, and their construction is an extractable SSB hash function as well.

Theorem  ([HW15]). Assuming the sub-exponential hardness of the learning with errors (LWE) problem, there exists a -hiding hash family for some . The -hiding is via a -straight-line reduction from the -hardness of LWE .

3Multi-Extractable SSB (meSSB) Hash Functions

A  -hiding multi-extractable somewhere statistically binding (meSSB) hash family is a hash family with local opening , where

• takes as additional input locations and outputs a hash key as well as a trapdoor ,

along with an additional PPT algorithm which works as follows.

• takes as input a subset of indices as well as a partial trapdoor and a hash value , and outputs . When no subset is provided, takes as input a full trapdoor and a hash value and outputs .

These algorithms should satisfy the following properties:

• -Index Hiding: For any -size adversary , there exists a negligible function such that for any ,

In words, index-hiding requires that even given the trapdoor information for the overlap of the two ordered sets and , the adversary still cannot distinguish whether hk is statistically binding on or .

• Correctness of Inversion: For any , and any , and ,

where the probability is over ( .

• Somewhere Statistically Binding: For any and ,

where the probability is over (hk, td) .

Multi-extractable SSB (meSSB) hash families can be constructed from extractable SSB (eSSB) families by invoking many independent copies.

Part4The BMW Protocol with meSSB Hash Families

Recall that the BMW heuristic is a two message succinct argument, where the verifier queries a PCP via a PCP query consisting of locations by sending parallel independent PIR queries to the prover. The prover computes, under the PIR, the answers and sends them back to the verifier. The verifier then reconstructs the answers and checks them via the PCP verification algorithm.

We note that a eSSB hash family functions as a PIR scheme, as follows:

• calls and outputs , where and .
• takes as input and and produces .
• takes as input and and outputs .

Thus, we can run the BMW heuristic with eSSB hash functions in place of the PIRs. In fact, the notion of these parallel eSSB hash functions is captured by our notion of a meSSB hash function, and thus we can run the BMW heuristic with a single meSSB hash function (binding on the locations of a PCP query) instead of the parallel PIR queries. Indeed, as we formally state below, the BMW heuristic is sound when instantiated with a meSSB hash family and a computationally non-signaling PCP.

Let , Open , Verify , Open be a meSSB hash family. On input and , the 2 message protocol proceeds as follows:

• Verifier: computes He computes and sends to the prover.
• Prover: computes the PCP string , and sends and to the verifier.
• Verdict: computes and accepts if and only if

Theorem. Let be a for a language with adaptive computational non-signaling soundness and locality . Assume that the meSSB hash family is -hiding, where is such that and . Then, for any -size cheating prover , there is a negligible function such that

where and where the probability is over and .

Moreover, this is proven via a -straight-line reduction.