Private Information Retrieval

(Single-server) PIR is the principal 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 tuple of efficient algorithms $\mathsf{PIR}=(\mathsf{Setup},\mathsf{Query},\mathsf{Answer},\mathsf{Decode})$ with respect to database size $n$, modeled as a bit-string $D\in \{0,1{\}}^n$:

• $\mathsf{Setup}(1^{\lambda },1^n)\to \mathsf{pp},$ is a randomized algorithm that generates public parameters encoding the database size $n,$
• $\mathsf{Query}(\mathsf{pp},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, one can treat any $w$-width word database as a bit-string and just query for the $w$ consecutive bits the client is interested in.

In general, PIR may be any arbitrary-round two-party protocol. However, most practical schemes to-date require only a single round of interaction, so it is more standard to present the protocol in the 1-round notation with explicit functions.

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 $\mathsf{pp}\leftarrow \mathsf{Setup}(1^{\lambda },1^n)$ and $(q,\mathsf{st})\leftarrow \mathsf{Query}(\mathsf{pp},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 $\pp \gets \Setup(1^\secpar, 1^n)$
\State $(i_0, i_1, \stA) \gets \calA(\pp)$
\State $b \getsr \bits$
\State $(q, \st) \gets \Query(\pp, 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{priv}}(\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
• Symmetric private information retrieval (Single-server) ⇒ cPIR
• Secret-Key PIR (SK-PIR) achieves sublinear online communication using client preprocessing with a secret key
• Keyword PIR

Non-trivial PIR

A PIR scheme is non-trivial if it is perfectly correct ($\epsilon =0$) and, for some polynomial $n=n(\lambda )$, on every $n$-bit database the server sends fewer than $n$ bits in total. The bound is where assumptions start: the trivial PIR, which downloads the database, is perfectly correct and perfectly private with no assumption — BIKM99.

PIR with total communication below $n$

A PIR scheme has total communication below $n$ if it is perfectly correct and, for some polynomial $n=n(\lambda )$, on every $n$-bit database the client and the server together send fewer than $n$ bits, the notion of non-triviality of DMO00. Such a scheme is non-trivial in the sense above.

One-round sublinear PIR

A PIR scheme is one-round sublinear if it is perfectly correct, consists of the query $q$ and the answer $a$ alone, as in the syntax above, and has communication $|q|+|a|\le p(\lambda )\cdot n^c$ for a polynomial $p$ and a constant $c<1$ — IKO05.

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.

Secret-Key PIR (SK-PIR)

In secret-key PIR, the client holds a short secret key $\mathsf{sk}$ derived from an offline encoding of the database. The server holds an encoded database $D^{\prime }$; online queries use only $o(N)$ communication, without requiring sublinear server computation (contrast: SK-DEPIR, which requires both).

Syntax

An SK-PIR scheme is a tuple $(\mathsf{Setup},\mathsf{Query},\mathsf{Answer},\mathsf{Decode})$:

• $\mathsf{Setup}(1^{\lambda },D)\to (\mathsf{sk},D^{\prime })$: randomized; generates secret key $\mathsf{sk}$ and encoded database $D^{\prime }$.
• $\mathsf{Query}(\mathsf{sk},i)\to (q,\mathsf{st})$: randomized; outputs online query $q$ and client state $\mathsf{st}$.
• $\mathsf{Answer}(D^{\prime },q)\to a$: deterministic server response.
• $\mathsf{Decode}(\mathsf{sk},\mathsf{st},a)\to x$: deterministic; recovers $x\in \{0,1\}$.

Correctness

An SK-PIR scheme is $(1-\epsilon )$-correct if for all $D\in \{0,1{\}}^N$ and $i\in [N]$,

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

where $(\mathsf{sk},D^{\prime })\leftarrow \mathsf{Setup}(1^{\lambda },D)$ and $(q,\mathsf{st})\leftarrow \mathsf{Query}(\mathsf{sk},i)$. When $\epsilon =0$, the scheme is perfectly correct.

Security

The adversary acts as the server: it chooses the database, then sees the encoded database $D^{\prime }$ and polynomially many online queries under the same $\mathsf{sk}$, each for index $i_b$ of an adaptively chosen pair $(i_0,i_1)$. $\mathsf{Setup}$ runs once, and neither $\mathsf{sk}$ nor $D^{\prime }$ is updated between queries — CIMR25, BM26. Security requires the queries to reveal nothing about $b$ despite the adversary knowing $D^{\prime }$.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{sk\text{-}priv}}_{\PIR,\calA}(\secpar)$}
\begin{algorithmic}
\State $(D, \stA) \gets \calA(1^\secpar)$
\State $(\sk, D') \gets \Setup(1^\secpar, D)$
\State $b \getsr \bits$
\State $b' \gets \calA^{\calO_b}(D', \stA)$
\Comment{$\calA$ sees $D'$ but not $\sk$}
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Oracle}
\caption{$\calO_b(i_0, i_1)$}
\begin{algorithmic}
\State $(q, \st) \gets \Query(\sk, i_b)$
\Return $q$
\end{algorithmic}
\end{algorithm}

An SK-PIR scheme is secret-key private if for all efficient $\mathcal{A}$,

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

is negligible.

Other results

• Non-trivial cPIR ⇒ OT
• No reduction from NP to one-round sublinear cPIR
• Every single-server PIR without preprocessing in which the server sends fewer than $n$ bits, built from public-key primitives in DH24’s black-box model, performs $\Omega (n)$ public-key operations, however many symmetric-key operations it uses — DH24

Constructions

• TDH ⇒ cPIR
• DDH ⇒ TDH
• QR ⇒ TDH
• LWE with superpolynomial ratio ⇒ TDH
• High-noise LPN ⇒ Secret-Key PIR (SK-PIR)
• OWF ⇒ Secret-Key PIR (SK-PIR)

Participates in

Builds on Private Information Retrieval

• One-round sublinear cPIR ⇒ CRHF (via One-round sublinear PIR)
• Non-trivial cPIR ⇒ OT (via PIR with total communication below $n$)
• Non-trivial cPIR ⇒ OWF (via Non-trivial PIR)
• One-round sublinear cPIR ⇒ cPIR with total communication below n (via One-round sublinear PIR)
• Symmetric private information retrieval (Single-server) ⇒ cPIR (via Symmetric private information retrieval (Single-server))
• Symmetric private information retrieval (Single-server) ⇒ OT (via Symmetric private information retrieval (Single-server))
• cPIR with total communication below n ⇒ Non-trivial cPIR (via PIR with total communication below $n$)

Produces Private Information Retrieval

• Additively homomorphic encryption ⇒ cPIR (via One-round sublinear PIR)
• DCR ⇒ One-round sublinear cPIR (via One-round sublinear PIR)
• Unkeyed DEPIR ⇒ cPIR
• OWF ⇒ Secret-Key PIR (SK-PIR) (via Secret-Key PIR (SK-PIR))
• FHE ⇒ cPIR
• Φ-Hiding ⇒ cPIR
• High-noise LPN ⇒ Secret-Key PIR (SK-PIR) (via Secret-Key PIR (SK-PIR))
• LSN ⇒ Secret-Key PIR (SK-PIR) (via Secret-Key PIR (SK-PIR))
• One-round sublinear cPIR ⇒ cPIR with total communication below n (via PIR with total communication below $n$)
• QR ⇒ cPIR (Kushilevitz–Ostrovsky) (via One-round sublinear PIR)
• Symmetric private information retrieval (Single-server) ⇒ cPIR
• TDH ⇒ cPIR
• TDP ⇒ cPIR with total communication below n (Kushilevitz–Ostrovsky) (via PIR with total communication below $n$)
• cPIR with total communication below n ⇒ Non-trivial cPIR (via Non-trivial PIR)

Barriers

• No fully-black-box reduction from NP to one-round sublinear cPIR (via One-round sublinear PIR)