Doubly-efficient PIR

Double 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 computation at query time is $o(n)$, where $n$ is the size of the database. The three main variants of DEPIR are: secret-key, public-key, and unkeyed. Note that any unkeyed DEPIR is trivially a PK-DEPIR which is trivially an SK-DEPIR. The latter keyed variants of DEPIR were introduced by BIPW17.

Syntax

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

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

Properties

Correctness

A DEPIR scheme is correct if for every $\lambda \in \mathbb{N}$, database $DB\in \{0,1{\}}^n$, and index $i\in [n]$, $\mathrm{Pr}[\mathsf{Fin}(h,r)=DB[i]|\begin{array}{c}(EDB,k)\leftarrow \mathsf{Setup}(1^{\lambda },DB)\\ (q,h)\leftarrow \mathsf{Qry}(k,i)\\ r\leftarrow \mathsf{Rsp}(q,EDB)\end{array}]=1.$

Unkeyed DEPIR

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

Public-key DEPIR

The privacy advantage of an adversary $\mathcal{A}$ that outputs database $DB$ and indices $i_0$ and $i_1$ is defined as ${\mathbf{Adv}}_{\mathcal{A}}^{\mathrm{priv}}(\lambda ):=2\left|\mathrm{Pr}[\mathcal{A}(1^{\lambda },k,EDB,q)=b]-\frac{1}{2}\right|,$ where $(EDB,k)\leftarrow \mathsf{Setup}(1^{\lambda },DB)$, $b\stackrel{\$}{\leftarrow }\{0,1\}$, and $(q,h)\leftarrow \mathsf{Qry}(k,i_b)$. A PK-DEPIR scheme is private if for all efficient $\mathcal{A}$, ${\mathbf{Adv}}_{\mathcal{A}}^{\mathrm{priv}}(\lambda )$ is negligible. Because $\mathsf{Qry}$ uses only the public $k$, single-query privacy implies privacy for polynomially many queries by a hybrid argument — folklore.

Secret-key DEPIR

In secret-key DEPIR, $\mathcal{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 $EDB[\pi (j)]=DB[j]\oplus F(j)$ for a secret PRP $\pi$ and PRF $F$ and sending $q=\pi (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 $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathcal{A}}^{\mathrm{sk}\text{-}\mathrm{priv}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathcal{A}}^{\mathrm{sk}\text{-}\mathrm{priv}}(\lambda )=1\right]-1\right|$$

is negligible.

Variations

Multi-server DEPIR

TODO

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 — LMW25
• Permuted puzzles ⇒ SK-DEPIR

Participates in

Builds on Doubly-efficient PIR

• Unkeyed DEPIR ⇒ cPIR (via Unkeyed DEPIR)
• PK-DEPIR ⇒ SK-DEPIR (via Public-key DEPIR)
• Unkeyed DEPIR ⇒ PK-DEPIR (via Unkeyed DEPIR)

Produces Doubly-efficient PIR

• Ring-LWE ⇒ Unkeyed DEPIR (via Unkeyed DEPIR)
• High-noise LPN ⇒ SK-DEPIR (via Secret-key DEPIR)
• Permuted puzzles ⇒ SK-DEPIR (via Secret-key DEPIR)
• PK-DEPIR ⇒ SK-DEPIR (via Secret-key DEPIR)
• Unkeyed DEPIR ⇒ PK-DEPIR (via Public-key DEPIR)