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 possibly randomized 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)$, $(q,\mathsf{st})\leftarrow \mathsf{Query}(\mathsf{pp},i)$ and the probability is also over the coins of $\mathsf{Answer}$.

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.

Several rounds

For a scheme with several rounds, $\mathcal{A}$ also chooses $D$ with $(i_0,i_1)$ and receives, in place of $q$, the server’s view ${\mathsf{V}}_S$ of an honest execution between the client on input $(\mathsf{pp},i_b)$ and the server on input $D$; the scheme has query privacy if this advantage is negligible for all efficient $\mathcal{A}$. It is $(1-\epsilon )$-correct if for all $D\in \{0,1{\}}^n$ and $i\in [n]$ the client on input $(\mathsf{pp},i)$, run with the server on input $D$, outputs $D[i]$ with probability at least $1-\epsilon$ over $\mathsf{pp}\leftarrow \mathsf{Setup}(1^{\lambda },1^n)$ and all coins of the execution, and its server is deterministic if each server message is a function of $D$ and the client’s messages so far. The non-trivial, total-communication and symmetric (SPIR) notions below use this form.

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 retrieves a value by its keyword rather than by its index
• PIR with client preprocessing gives the client a hint before it chooses its indices, for sublinear amortized server computation on an unencoded database
• Batch PIR retrieves several entries at once

Non-trivial PIR

A PIR scheme, of one round or several, is non-trivial if it has query privacy and, for some polynomial $n=n(\lambda )$, it is $(1-1/(8n))$-correct and on every $n$-bit database the server sends fewer than $n$ bits in total. The error bound $1/(8n)$ is the one at which the implication to one-way functions is proved for this communication bound — BIKM99. The communication bound $n$ is where assumptions start: the trivial PIR, which downloads the database, is perfectly correct and perfectly private with no assumption — BIKM99. With one server, a perfectly correct scheme with information-theoretic (perfect) privacy requires $n$ bits of communication on $n$-bit databases, so the trivial scheme is optimal — CGKS98.

PIR with total communication below $n$

A PIR scheme has total communication below $n$ if it has query privacy, is perfectly correct, has a deterministic server and, for some polynomial $n=n(\lambda )$, on every $n$-bit database the client and the server together send fewer than $n$ bits; the communication bound is 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 has query privacy, 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; its $\mathsf{Answer}$ is also deterministic, so that a fixed query defines a function of the database. Perfect correctness makes this free: $\mathsf{Answer}$ with its coins fixed to any value is still perfectly correct and leaves the query and the communication unchanged — folklore.

PIR with polylogarithmic communication

A PIR scheme has polylogarithmic communication if it has query privacy, is $(1-\epsilon )$-correct for a negligible $\epsilon$, consists of the query $q$ and the answer $a$ alone, as in the syntax above, and, for a polynomial $p$ and every $n$, has communication $|q|+|a|\le p(\lambda ,\log n)$ on every $n$-bit database. The first such scheme rests on the Φ-hiding assumption — CMS99. On databases of large polynomial size the error is below $1/(8n)$ and the server sends fewer than $n$ bits, so such a scheme implies one-way functions — BIKM99. Such PIR suffices for non-interactive delegation of all polynomial-time computations with a designated verifier (PIR with polylogarithmic communication ⇒ Designated-verifier delegation for P) — BHK17.

Symmetric private information retrieval (Single-server)

In symmetrically private information retrieval (SPIR) the privacy of the data is guaranteed as well as the privacy of the user: in every invocation the user learns a single physical bit of the database and no other information about it — GIKM00, who introduce the model for several servers (IT-SPIR). OS07 call the single-database definition identical to that of $1$-out-of-$n$ OT — OS07. Single-server SPIR is in addition a PIR scheme, in the form for several rounds, in which on every $n$-bit database the client and the server together send at most $p(\lambda )\cdot n^c$ bits, for a polynomial $p$ and a constant $c<1$, so fewer than $n$ bits once $n>p(\lambda {)}^{1/(1-c)}$. Every PIR protocol with total communication below $n$ yields $1$-out-of-$n$ OT, which DMO00 call SPIR, by a communication-efficient reduction — DMO00. NP05’s computationally secure $1$-out-of-$N$ OT uses only $\log N$ executions of $1$-out-of-$2$ OT; as a corollary, any PIR protocol, combined with that $1$-out-of-$N$ OT, transforms efficiently into one that also has data privacy — NP05. DMO00’s abstract calls the reduction only communication-efficient and does not bound the communication of the resulting protocol.

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.

Keyword PIR

In keyword PIR the server holds $n$ pairs $(w_j,v_j{)}_{j\in [n]}$ with distinct keywords $w_j\in \{0,1{\}}^{\ell }$ and values $v_j\in \{0,1{\}}^m$, and a client holding a keyword $w$ runs a protocol $⟨C(1^{\lambda },w),S((w_j,v_j{)}_{j\in [n]})⟩$, of any number of rounds, at the end of which it outputs $v_j$ if $w=w_j$ and $\perp$ if $w$ is no keyword, except with negligible probability. The communication is at most $p(\lambda ,\ell ,m)\cdot n^c$ for a polynomial $p$ and a constant $c<1$, which rules out sending every pair. The notion is due to CGN98. Below, $(y,V)\leftarrow ⟨C(\cdot ),S(\cdot )⟩$ denotes an execution in which the client outputs $y$ and $V={\mathsf{V}}_S$ is the server’s view.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{kw\text{-}priv}}_{\PIR,\calA}(\secpar)$}
\begin{algorithmic}
\State $((w_j, v_j)_{j \in [n]}, w^0, w^1, \stA) \gets \calA(1^\secpar)$; $b \getsr \bits$
\State $(y, V) \gets \langle C(1^\secpar, w^b), S((w_j, v_j)_{j \in [n]}) \rangle$
\Comment{$\calA$ sees only the server's view}
\State $b' \gets \calA(V, \stA)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

A keyword PIR $\mathsf{PIR}$ is keyword-private if for all efficient $\mathcal{A}$,

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

is negligible.

PIR with client preprocessing

A single-server PIR with client preprocessing (offline/online PIR) is a protocol between a client $C$ and a server $S$ that stores $D\in \{0,1{\}}^n$ unencoded and nothing else. In an offline phase, run before the client chooses any index, the client obtains a hint $h$, written $(h,V)\leftarrow ⟨C(1^{\lambda },1^n),S(D)⟩$ with $V={\mathsf{V}}_S$ the server’s view. In the online phase the client retrieves $D[i_1],D[i_2],\dots$ for adaptively chosen indices, each retrieval an execution $((h^{\prime },x_j),V)\leftarrow ⟨C(h,i_j),S(D)⟩$ that outputs $x_j$ and may update the hint to $h^{\prime }$; after every $Q=Q(\lambda ,n)$ retrievals the offline phase is rerun. The scheme is correct if for every $D$ and every sequence of indices each retrieval outputs $x_j=D[i_j]$ except with negligible probability. It is sublinear if there are a polynomial $p$ and a function $f(n)=o(n)$ such that the client’s storage, and the server’s computation and the communication of one offline phase with its $Q$ retrievals divided by $Q$, are each at most $p(\lambda )\cdot f(n)$. The offline/online model is due to CK20; sublinear amortized server time with adaptive queries is due to CHK22. Every PIR with client preprocessing below is required to be sublinear.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{cp\text{-}priv}}_{\PIR,\calA}(\secpar)$}
\begin{algorithmic}
\State $(D, \stA) \gets \calA(1^\secpar)$; $b \getsr \bits$; $j \gets 0$
\State $(h, V) \gets \langle C(1^\secpar, 1^n), S(D) \rangle$
\Comment{Offline phase, independent of the indices}
\State $b' \gets \calA^{\calO_b}(V, \stA)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Oracle}
\caption{$\calO_b(i_0, i_1)$}
\begin{algorithmic}
\State $j \gets j + 1$
\State $((h, x), V) \gets \langle C(h, i_b), S(D) \rangle$
\If{$j \equiv 0 \pmod{Q}$}
\State $(h, V') \gets \langle C(1^\secpar, 1^n), S(D) \rangle$; $V \gets (V, V')$
\EndIf
\Return $V$
\end{algorithmic}
\end{algorithm}

A PIR with client preprocessing $\mathsf{PIR}$ is private if for all efficient $\mathcal{A}$,

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

is negligible.

Constructions and lower bounds

• Constructions exist from one-way functions (OWF ⇒ PIR with client preprocessing (Piano)) — ZPZS24 — and, through linearly homomorphic encryption, from DDH (DDH ⇒ PIR with client preprocessing) and QR (QR ⇒ PIR with client preprocessing), among other assumptions — CHK22.
• Under decision LWE, a hint computed by the server gives single-server PIR whose server performs fewer than one 32-bit multiplication and one 32-bit addition per database byte, about 10 GB/s per core: for a 1 GB database the client downloads a 121 MB hint once and then makes any number of queries of 242 KB each; DoublePIR shrinks the hint to 16 MB at 345 KB per query and 7.4 GB/s per core — HHCMV23. In SimplePIR the hint is the database, arranged as a matrix, times the public LWE matrix, so it depends on no client secret; for $N$ entries and LWE secret dimension $\ell$ it has about $\ell \sqrt{N}$ elements of ${\mathbb{Z}}_q$ and each query and answer about $\sqrt{N}$, while DoublePIR’s hint is independent of $N$. The concrete parameters take $q=2^{32}$ and a discrete Gaussian error — HHCMV23. Online server time stays linear in the database size, so these schemes are not sublinear in the sense above.
• For databases stored unencoded, the offline/online protocols of CK20 are optimal for the trade-off between communication and online running time — CK20.
• Under LWE, a single-server scheme with client preprocessing has amortized bandwidth ${\tilde{O}}_{\lambda }(1)$ per query, server and client computation ${\tilde{O}}_{\lambda }(\sqrt{n})$ per query and client storage ${\tilde{O}}_{\lambda }(\sqrt{n})$, optimal up to polylogarithmic factors in server computation and bandwidth — ZLTS23.
• An $r$-bit hint and $t$ entries accessed per retrieval require $t\cdot r=\Omega (n)$, which is tight and closes a logarithmic gap; the bound holds for error at most $1/15$, against efficient adversaries corrupting one of $\ell =O(1)$ servers, when entries are stored unmodified though possibly replicated — Yeo23. Proving such lower bounds for two-server PIR in general computational models would imply the online matrix-vector conjecture — Yeo23.
• Information-theoretic single-server schemes exist, with non-trivial trade-offs between server computation, client space and bandwidth; they obey a nearly tight lower bound on the trade-off between client space and bandwidth, and a computational scheme beating it that meets a natural syntactic requirement implies a hard problem in $\mathbf{SZK}$ — ISW24. Among them is a single-server scheme with sublinear server computation (their Theorem 1.4) — ISW24.
• With cryptography used only as a black box, random oracles and VBB obfuscation included, a client storing $s$ bits needs $\Omega (n/s)$ amortized online computation over $k=\Omega (s)$ queries: either $\Omega (n/s)$ amortized online communication or $\Omega (n/s)$ cryptographic operations by the server, and each alternative is tight — HPY26.

Batch PIR

A batch code encodes a string into $m$ buckets so that any $k$ of its bits can be decoded by reading at most one bit, or more generally $t$ bits, from each bucket; batch codes amortize the computational cost of retrieving $k$ entries by PIR — IKOS04. Probabilistic batch codes trade a small probability that some queries of a batch fail, about one in a trillion multi-queries, for far fewer buckets, which cuts the network cost of batch-code-based multi-query PIR — ACLS18; with vectorized homomorphic encryption, batch PIR can be efficient in both computation and communication, with $7.5$ to $98.5$ times less communication than earlier schemes in the paper’s benchmark configuration — MR23. With an $r$-bit client hint, batch retrieval of $k$ entries accessing $t$ entries needs $t\cdot r=\Omega (nk)$ when $r\ge k$, and $t=\Omega (n)$ when $r<k$ — Yeo23.

Other results

• cPIR with total communication below n ⇒ 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
• In every perfectly private, perfectly correct PIR whose servers store only the database and whose client keeps no state between queries, for any number $k$ of servers and whatever its communication, the servers together read at least $n$ database bits per query in expectation — BIM00. The $\Omega (n)$ bound on server time holds with computational privacy too, but for a client that keeps state it bounds only the first query — CHK22. Doubly-efficient PIR stores an encoding of the database instead, and PIR with client preprocessing moves the linear server work into an offline phase run before the client chooses its index — CK20.

Practical single-server schemes

• SealPIR compresses the client’s query vector into a single ciphertext — ACLS18.
• OnionPIR composes two lattice-based somewhat homomorphic schemes, for a response overhead of $4.2$ times the insecure baseline against $100$ times for earlier schemes — MCR21.
• Spiral composes the Regev and Gentry–Sahai–Waters schemes; its streaming variant SpiralStreamPack, on databases with over a million records, reaches a server throughput of $1.9$ GB/s at rate $0.81$, against $200$ MB/s and $0.24$ for earlier protocols — MW22.
• YPIR combines LWE with ring-LWE response compression and needs no offline communication: for a 1-bit or 1-byte record of a 32 GB database it achieves $12.1$ GB/s/core with $2.5$ MB of total communication, where SimplePIR achieves $12.5$ GB/s/core with $1.5$ MB but first downloads a $724$ MB hint — MW24.
• FrodoPIR reports a server cost of about $1 for answering $100,000$ client queries in its benchmark — DPC23.

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)
• cPIR with total communication below n ⇒ OT (via PIR with total communication below $n$)
• Non-trivial cPIR ⇒ OWF (via Non-trivial PIR)
• One-round sublinear cPIR ⇒ Keyword PIR (via One-round sublinear PIR)
• One-round sublinear cPIR ⇒ cPIR with total communication below n (via One-round sublinear PIR)
• PIR with polylogarithmic communication ⇒ cPIR (via PIR with polylogarithmic communication)
• PIR with polylogarithmic communication ⇒ Designated-verifier delegation for P (via PIR with polylogarithmic communication)
• PIR with polylogarithmic communication ⇒ Non-trivial cPIR (via PIR with polylogarithmic communication)
• 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)
• DDH ⇒ PIR with client preprocessing (CHK22) (via PIR with client preprocessing)
• Unkeyed DEPIR ⇒ cPIR
• OWF ⇒ Secret-Key PIR (SK-PIR) (via Secret-Key PIR (SK-PIR))
• Φ-Hiding ⇒ cPIR (via PIR with polylogarithmic communication)
• Length-flexible additively homomorphic encryption ⇒ PIR with polylogarithmic communication (Lipmaa) (via PIR with polylogarithmic communication)
• 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 ⇒ Keyword PIR (via Keyword PIR)
• One-round sublinear cPIR ⇒ cPIR with total communication below n (via PIR with total communication below $n$)
• OWF ⇒ PIR with client preprocessing (Piano) (via PIR with client preprocessing)
• PIR with polylogarithmic communication ⇒ cPIR
• PIR with polylogarithmic communication ⇒ Non-trivial cPIR (via Non-trivial PIR)
• QR ⇒ PIR with client preprocessing (CHK22) (via PIR with client preprocessing)
• 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 polynomially-preserving fully-black-box reduction from enhanced TDP to one-round sublinear cPIR (via One-round sublinear PIR)
• No fully-black-box reduction from NP to one-round sublinear cPIR (via One-round sublinear PIR)
• No polynomially-preserving fully-black-box reduction from TDP to one-round sublinear cPIR (via One-round sublinear PIR)