Doubly-efficient PIR

Doubly efficient PIR is a type of single-server PIR that allows the database to be preprocessed before the client queries the data. A PIR is considered a DEPIR if both the communication and the computation at query time are $o (n)$ , where $n$ is the size of the database. The three main variants of DEPIR are: secret-key, public-key, and unkeyed. Any unkeyed DEPIR is trivially a PK-DEPIR, which is trivially an SK-DEPIR. Secret-key DEPIR was introduced by BIPW17 and CHR17, and public-key DEPIR by BIPW17.

Syntax

A (one-round) doubly-efficient private information retrieval (DEPIR) scheme is a tuple of efficient algorithms $(Setup, Qry, Rsp, Fin)$ with respect to a key space $K$ such that

$Setup (1^{λ}, D B) \to (E D B, k)$ , is a randomized algorithm that takes a security parameter and database $D B \in {0, 1}^{n}$ , and outputs an encoded database $E D B \in {0, 1}^{*}$ and (optionally, see variations) a key $k \in K$ ,
$Qry (k, i) \to (q, h)$ , is a randomized algorithm that takes (optionally) a key $k \in K$ and index $i \in [n]$ , and outputs $q \in {0, 1}^{*}$ and a hint $h \in {0, 1}^{*}$ ,
$Rsp (q, E D B) \to r$ , is a randomized algorithm that takes a query $q \in {0, 1}^{*}$ and database $E D B \in {0, 1}^{*}$ , and outputs a response $r \in {0, 1}^{*}$ ,
$Fin (h, r) \to a$ , is a randomized algorithm that takes a hint $h \in {0, 1}^{*}$ and response $r \in {0, 1}^{*}$ , and outputs an answer $a \in {0, 1}$ .

Properties

Correctness

A DEPIR scheme is correct if for every $λ \in N$ , database $D B \in {0, 1}^{n}$ , and index $i \in [n]$ , $Pr [Fin (h, r) = D B [i] (E D B, k) \leftarrow Setup (1^{λ}, D B) (q, h) \leftarrow Qry (k, i) r \leftarrow Rsp (q, E D B)] = 1.$

Unkeyed DEPIR

By default DEPIR scheme outputs no key i.e. $k = ⊥$ with probability $1$ . The security of this scheme is the same as either game below, which are equivalent when $k$ is set to $⊥$ .

Public-key DEPIR

The privacy advantage of an adversary $A$ that outputs database $D B$ and indices $i_{0}$ and $i_{1}$ is defined as $Adv_{A}^{priv} (λ) := 2 Pr [A (1^{λ}, k, E D B, q) = b] - \frac{1}{2},$ where $(E D B, k) \leftarrow Setup (1^{λ}, D B)$ , $b \leftarrow $ {0, 1}$ , and $(q, h) \leftarrow Qry (k, i_{b})$ . A PK-DEPIR scheme is private if for all efficient $A$ , $Adv_{A}^{priv} (λ)$ is negligible. Because $Qry$ uses only the public $k$ , single-query privacy implies privacy for polynomially many queries by a hybrid argument — folklore.

PK-DEPIR with a sublinear key

A PK-DEPIR scheme has a sublinear key if, on $n$ -bit databases, the key $k$ that $Setup$ outputs and the query-time communication and computation are each at most $p (λ) \cdot n^{c}$ for a polynomial $p$ and a constant $c < 1$ , so below $n$ once $n > p (λ)^{1/ (1 - c)}$ . HPY26’s lower bound for public-key DEPIR is for public keys of length $o (n)$ and does not rule out public keys of length $Ω (n)$ — HPY26.

Secret-key DEPIR

In secret-key DEPIR, $A$ is not given $k$ and makes polynomially many adaptive left-or-right queries, all answered under the same $k$ with no key update — BIPW17, LMW25. A single-query notion is met from one-way functions alone by storing $E D B [π (j)] = D B [j] \oplus F (j)$ for a secret PRP $π$ and PRF $F$ and sending $q = π (i)$ ; this scheme fails the many-query notion, since repeated queries to one index repeat $q$ — folklore.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{sk\text{-}priv}}_{\calA}(\secpar)$}
\begin{algorithmic}
\State $(DB, \stA) \gets \calA(1^\secpar)$
\State $(EDB, k) \gets \Setup(1^\secpar, DB)$; $b \getsr \bits$
\State $b' \gets \calA^{\calO_b}(EDB, \stA)$
\Comment{Polynomially many adaptive queries, all under the same $k$}
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Oracle}
\caption{$\calO_b(i_0, i_1)$}
\begin{algorithmic}
\State $(q, h) \gets \mathsf{Qry}(k, i_b)$
\Return $q$
\end{algorithmic}
\end{algorithm}

An SK-DEPIR scheme is secret-key private if for all efficient $A$ ,

Adv_{A}^{sk - priv} (λ) := 2 Pr [G_{A}^{sk - priv} (λ) = 1] - 1

is negligible.

Passive-server SK-DEPIR

An SK-DEPIR scheme in the syntax above, one query and one response (two rounds in the count of LMW25), has a passive server if every query $q$ is a list of positions in $E D B$ and $Rsp (q, E D B)$ returns the entries of $E D B$ at those positions — LMW25.

Passive-server SK-DEPIR with a database-independent key

A passive-server SK-DEPIR scheme has a database-independent key if $Setup (1^{λ}, D B)$ first samples $k \leftarrow KeyGen (1^{λ})$ , without access to $D B$ , and then computes $E D B \leftarrow Prep (1^{λ}, k, D B)$ , for efficient algorithms $KeyGen$ and $Prep$ , so that the client holds only $(n, k, i)$ — LMW25 (Definition 2.1). The variant recorded here also bounds the query-time communication and computation by $p (λ) \cdot n^{c}$ for a polynomial $p$ and a constant $c < 1$ , so below $n$ once $n > p (λ)^{1/ (1 - c)}$ . A passive-server SK-DEPIR whose key may depend on $D B$ exists with no assumption: $Setup$ outputs $k = D B$ and an empty $E D B$ , $Qry (k, i)$ outputs the empty list of positions and the hint $h = k [i]$ , and $Fin$ returns $h$ — folklore.

Variations

Multi-server DEPIR

In $k$ -server PIR with preprocessing, each of $k$ non-colluding servers stores, besides $D$ , polynomially many bits precomputed from it. When the servers hold only the database and the client keeps no state between queries, the servers of a perfectly private, perfectly correct scheme together read at least $n$ database bits per query in expectation, for every $k$ and whatever the communication; with preprocessing there are, for every constant $k \geq 2$ , information-theoretic $k$ -server schemes with $O (n^{1/ (2 k - 1)})$ communication and $O (n / lo g^{2 k - 2} n)$ server work, and, for every constant $ε > 0$ , schemes with $O (n^{1/ k + ε})$ communication and server work — BIM00. See doubly-efficient multi-server PIR.

Other results

Ring-LWE ⇒ Unkeyed DEPIR — LMW23
Many cryptographic primitives cannot be used to construct SK-DEPIR in a black-box way, unless OWF can be used to construct SK-DEPIR in a black-box way, and black-box one-way functions give no passive-server SK-DEPIR with a database-independent key (No fully-black-box reduction from OWF to passive-server SK-DEPIR with a database-independent key) — LMW25
For single-server computationally private PIR with public preprocessing, whose $r$ -bit hint is available to everyone including the adversary, and expected query time $t$ , $t \cdot r = Ω (n lo g n)$ when $r = Ω (lo g n)$ and $t = Ω (n)$ when $r = O (lo g n)$ , even with error $1/ n^{2}$ and distinguishing advantage $1/ n$ — PY22. Public-key DEPIR with a sublinear key, whose key and query-time cost are at most $p (λ) \cdot n^{c}$ ( $c < 1$ ), and hence unkeyed DEPIR with such query-time cost, cannot be built from cryptography used only as a black box, random oracles and VBB obfuscation included, when key generation and the database encoding make no queries to the cryptographic oracle (No oracle-free-encoding reduction from ROM to public-key DEPIR with a sublinear key); HPY26 state it for public keys of length $o (n)$ and sublinear query computation; the bound does not cover secret-key DEPIR, whose encoding may depend on client-private state, and it is incomparable with the passive-server SK-DEPIR bound (no fully-black-box passive-server SK-DEPIR with a database-independent key from OWF) — HPY26.
Permuted puzzles ⇒ SK-DEPIR
Secret-key DEPIR in which the server and the client each do polylogarithmic work per query after preprocessing follows from one-way functions for a bounded number of queries, with server storage linear in the number of queries plus the database size, and for an unbounded number from new assumptions related to the hardness of solving a system of noisy linear equations; a natural and general approach towards public preprocessing is doomed to fail — CHR17. HPY26 list CHR17 among the secret-key DEPIR schemes — HPY26.

Participates in

Builds on Doubly-efficient PIR

Produces Doubly-efficient PIR

Barriers

Cryptology City

Explorer