Multi-server Private Information Retrieval

Private Information Retrieval (PIR) is a primitive that allows a client to access a specific element from a public array without revealing which array element was accessed, introduced by CGKS98.

Syntax

A $k$-server Private Information Retrieval (PIR) for a database of size $n$ is a tuple of efficient functions $(\mathsf{Query},\mathsf{Answer},\mathsf{Compute})$, with respect to randomness space $R$ such that:

• Generally, we consider the size of the initial queries to be $u$ bits each and the answers to be $d$ bits each.
• In general, we can consider the total communication of a PIR as $k(u+d)$.
• A PIR is non-trivial only so long as the communication is less than $n$.

Properties

Correctness

A PIR is correct if for all $D\in \{0,1{\}}^n$, $i\in [n]$, and $r\in R$ $\mathsf{Recon}(i,a_1,\dots ,a_k;r)=D[i]$ where each $a_s\leftarrow \mathsf{Answer}(s,q_s,D)$ and $(q_1,\dots ,q_k)\leftarrow \mathsf{Query}(i;r)$.

Privacy

A PIR is private if for every $i,j\in [n]$, $s\in [k]$, and $q\in \{0,1{\}}^u$, ${\mathrm{Pr}}_r[\mathsf{Query}(i;r)[s]=q]={\mathrm{Pr}}_r[\mathsf{Query}(j;r)[s]=q].$

Intuitively, this means that each server observes the same query uploaded with the same probability.

Variations

Computational Multi-server PIR

Similar to the PIR, one can weaken the notion of multi-server PIR to only be private against polynomial-time non-colluding servers. In this setting, the syntax remains the same, but now the query distribution is only required to be computationally indistinguishable for any two index pairs.

• PRG ⇒ DPF
• DPF ⇒ Computational Multi-server PIR

For every constant $\epsilon >0$ there is a one-round two-server computational PIR with communication $O(n^{\epsilon })$, built from pseudorandom generators and storing the database unencoded — CG97. With one-bit answers its queries have length $2^{O(\sqrt{\log n})}$, which distributed point functions reduce to polylogarithmic — GI14. Two-server information-theoretic PIR has communication $n^{O(\sqrt{\log \log n/\log n})}=n^{o(1)}$ — DG15 — so the $O(n^{\epsilon })$ bound no longer needs an assumption.

Doubly-efficient Multi-server PIR

In $k$-server PIR with preprocessing, each server 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\ge 2$, information-theoretic $k$-server schemes with $O(n^{1/(2k-1)})$ communication and $O(n/{\log }^{2k-2}n)$ server work, and, for every constant $\epsilon >0$, schemes with $O(n^{1/k+\epsilon })$ communication and server work — BIM00.

Other results

• The typical setting is the 1-bit array (also called database), since you can build a $w$-bit PIR using just $w$ copies of a 1-bit PIR.
• With one server, perfect privacy requires $n$ bits of communication; with two non-colluding servers, $O(n^{1/3})$ bits suffice — CGKS98.
• For every constant $k\ge 2$ there is a $k$-server information-theoretic PIR with communication $O(n^{1/(2k-1)})$, generalizing the two-server $O(n^{1/3})$ of CGKS98 — Amb97. BIKR02 lower this to $n^{O(\log \log k/(k\log k))}$, below $O(n^{1/(2k-1)})$ for every $k\ge 3$ ($O(n^{1/5.25})$ for three servers), and obtain $k$-query binary locally decodable codes of length $\exp (n^{O(\log \log k/(k\log k))})$, shorter than earlier ones for every $k\ge 4$ — BIKR02.
• There is a two-server information-theoretic PIR with total communication $n^{O(\sqrt{\log \log n/\log n})}$, improving the $O(n^{1/3})$ of earlier two-server schemes and matching the known three-server schemes; it reduces matching-vector PIR from 3 or 4 servers to 2 by recasting it as polynomial interpolation and adding partial derivatives — DG15.
• For every Mersenne prime $2^t-1$ there are 3-query locally decodable codes of length $\exp (n^{1/t})$; with the largest Mersenne prime known in 2007 this gives length below $\exp (n^{10^{-7}})$ and 3-server information-theoretic PIR with communication $O(n^{10^{-7}})$, and if there are infinitely many Mersenne primes the codes have length $\exp (n^{O(1/\log \log n)})$ for infinitely many $n$ — Yek07. Unconditionally, 3-query locally decodable codes of length $\exp (\exp (O(\sqrt{\log n\log \log n})))$ exist, with $2^r$-query analogues, and give 3-server PIR with communication $2^{\tilde{O}(\sqrt{\log n})}$ — Efr09; 3-server PIR with communication $2^{\tilde{O}((\log n{)}^{1/3})}$ follows from matching vectors and derivatives — GKS25.
• Locally decodable codes are related to smooth codes, whose decoder queries no codeword position much more often than uniformly — KT00. A perfectly smooth non-adaptive $q$-query code of length $N$ over $\Sigma$, whose decoder is always correct on an uncorrupted codeword and whose every query is uniform on $[N]$, gives $q$-server PIR with $q(\log N+\log |\Sigma |)$ bits of communication: server $j$ stores the encoded database and returns the symbol at the decoder’s $j$-th query — standard. In the other direction, one-round two-server information-theoretic PIR reduces to 2-query locally decodable codes; binary linear 2-query codes have length $2^{\Omega (n)}$, so a two-server scheme whose answers are linear combinations of the database, with $t$-bit queries and $a$-bit answers, has $t=\Omega (n/2^a)$ — GKST06. Every binary 2-query locally decodable code has length $2^{\Omega (n)}$, linear or not — KdW03 — and one-round two-server PIR with one-bit answers needs queries of at least $n-2$ bits, against the upper bound $n-1$, improving the roughly $0.25n$ of KdW03 — BFG06.
• In the offline/online model the client fetches a hint before choosing its index, and the online phase then runs in time sublinear in $n$ without extra server storage; the protocols can be statistically secure with two servers and are computationally secure with one, and both are optimal for the trade-off between communication and running time in this model — CK20. From one-way functions, two servers reach $\tilde{O}(n^{1/4})$ bandwidth with $\tilde{O}(n^{1/2})$ computation per query and $\tilde{O}(n^{1/2})$ client storage — GZS24 — and polylogarithmic bandwidth with ${\tilde{O}}_{\lambda }(n^{1/2+\epsilon })$ client space and $n^{1+\epsilon }$ server space — GZSP25.

Participates in

Builds on Multi-server Private Information Retrieval

• IT-PIR ⇒ Computational Multi-server PIR

Produces Multi-server Private Information Retrieval

• DPF ⇒ Computational Multi-server PIR (via Computational Multi-server PIR)
• IT-PIR ⇒ Computational Multi-server PIR (via Computational Multi-server PIR)
• SPIR ⇒ IT-PIR
• Linear SS ⇒ IT-PIR