Private Information Retrieval (PIR)

A 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. This primitive was originally defined in [CGKS98]. It is sometimes referred to as statistical PIR, because this article describes the unconditional primitive, which is based on no computational assumption. See either Single-server PIR or Computational Multi-server PIR for more information about the computational variants.

Formal Definition

Syntax

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

• ${\mathsf {Query}}(i;r)\to (q_{1},\ldots ,q_{k})$, is an algorithm that takes an index $i\in [n]$ parameter and randomness $r\in {\mathcal {R}}$, and queries $q_{1},\ldots ,q_{k}\in \{0,1\}^{u}$,
• ${\mathsf {Ans}}(s,q,D)\to a$, is a deterministic algorithm that takes a server index $s\in [k]$, query $q\in \{0,1\}^{u}$, and array $D\in \{0,1\}^{n}$, and outputs an answer $a\in \{0,1\}^{d}$,
• ${\mathsf {Recon}}(i,a_{1},\ldots ,a_{k};r)\to b$, is an algorithm that takes an array index $i\in [n]$ and answer $a_{1},\ldots ,a_{k}\in \{0,1\}^{d}$ and randomness $r\in {\mathcal {R}}$, and outputs a bit $b\in \{0,1\}$.

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)$. And, a PIR is non-trivial only so long the communication is less than $n$.

This primitive can also be naturally generalized to arrays with word entries longer than a single bit. However, 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.

Correctness

A PRF is correct if for all $D\in \{0,1\}^{n},i\in [n],$ and $r\in {\mathcal {R}}$

${\mathsf {Recon}}(i,a_{1},\ldots ,a_{k};r)=D[i],$

where each $a_{s}\gets {\mathsf {Ans}}(s,q_{s},D)$ and $(q_{1},\ldots ,q_{k})\gets {\mathsf {Query}}(i;r)$.

Privacy

A PRF is private if for every $i,j\in [n]$, $s\in [k]$, and $q\in \{0,1\}^{u}$,

$\Pr _{r}[{\mathsf {Query}}(i;r)[s]=q]=\Pr _{r}[{\mathsf {Query}}(j;r)[s]=q]$

Intuitively, this means that each server observes the same query uploaded with the same probability. Notice that this and correctness are perfect or statistical notions, which have no computationally bounded adversaries.

Constructions

TODO - enumerate best known constructions

Relationship to other primitives

• TODO - lower bound via locally decodable codes

Variations

• Single-server PIR
• Computational Multi-server PIR
• PIR with client-side preprocessing
• Doubly-Efficient PIR (DEPIR)

Other Notes

• Any PIR requires linear total computation across the servers [CGKS98]
• Any (statistical) single-server PIR must have at least $n$ bits of communication