Private Information Retrieval

(Single-server) PIR is the principle variant of PIR that is studied in the literature, introduced by KO97. It is deployed in a setting where a server holds a database (represented as an array) and a client is interested in learning one of the database items. A PIR protocol allows the client to learn the entry without revealing which entry the client is interested in.

The protocol where the client downloads the entire database is known as the trivial PIR.

Syntax

A PIR scheme is a triple of efficient algorithms $\mathsf{PIR}=(\mathsf{Query},\mathsf{Answer},\mathsf{Decode})$ with respect to database size $n$, modeled as a bit-string $D\in \{0,1{\}}^n$:

• $\mathsf{Query}(1^{\lambda },i)\to (q,\mathsf{st}),$ is a randomized algorithm that takes an index $i\in [n]$, outputting a query $q$ to send to the server and a client state $\mathsf{st},$
• $\mathsf{Answer}(D,q)\to a,$ is a deterministic algorithm that takes a database $D\in \{0,1{\}}^n$ and query $q$, outputting an answer $a,$
• $\mathsf{Decode}(\mathsf{st},a)\to x,$ is a deterministic algorithm that takes client state $\mathsf{st}$ and answer $a$, outputting a value $x\in \{0,1\}.$

While PIR is typically represented with data-elements as single bits, most constructions support words from $\{0,1{\}}^w.$ There is also a generic transformation between the two. In particular, on can treat any $w$-width word database as a bit-string and just query for the $w$ consecutive bits the client is interested in.

Properties

Correctness

A PIR $\mathsf{PIR}$ is $(1-\epsilon )$-correct if for all $D\in \{0,1{\}}^n$ and $i\in [n]$,

$$\mathrm{Pr}\left[\mathsf{Decode}(\mathsf{st},\mathsf{Answer}(D,q))=D[i]\right]\ge 1-\epsilon ,$$

where $(q,\mathsf{st})\leftarrow \mathsf{Query}(1^{\lambda },i)$.

Query Privacy

The server’s view — the query $q$ — should reveal nothing about the queried index $i$. The following game captures this: the adversary picks two indices, a challenge bit selects one, and the adversary sees only the resulting query.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{priv}}_{\PIR,\calA}(\secpar)$}
\begin{algorithmic}
\State $(i_0, i_1, \stA) \gets \calA(1^\secpar, 1^n)$
\State $b \getsr \bits$
\State $(q, \st) \gets \Query(1^\secpar, i_b)$
\State $b' \gets \calA(q, \stA)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

A PIR $\mathsf{PIR}$ has query privacy if for all efficient $\mathcal{A}$,

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

is negligible. Here $\mathcal{A}$ is stateful: it runs in two phases, first choosing the challenge indices, then guessing the bit after seeing the query.

Variations

• Multi-server PIR is an information theoretic variant, which requires multiple servers
• Single-server Symmetric PIR (SPIR) additionally protects the server’s data privacy
• PIR with client-side preprocessing
• Keyword PIR

Symmetric private information retrieval (Single-server)

Symmetric private information retrieval is a stronger version of PIR that in addition to protecting the querier’s privacy, also protects the data privacy. The multi-server, information-theoretic version (IT-SPIR) was introduced by GIKM00, but follow-up works showed how to construct computationally secure versions based on assumptions.

Single-server SPIR is equivalent to $1$-out-of-$n$ OT with an additional efficiency requirement.

Other results

• Non-trivial PIR implies OT — DMO00
• Single-round PIR cannot be based on NP-hardness unless PH collapses to the second level — LV15

Constructions

• PIR with $\text{polylog}(n)$ bandwidth can be built from DDH, QR, or LWE — DGI+19
  • This result goes through the use of TDH, which can be used to build PIR generically
• Any PIR requires $\Omega (n)$ public-key operations — DH24