Linear SS ⇒ IT-PIR

Standard model · CGKS98 · security loss: none: privacy is perfect, each server’s view being independent of $i$

Statement

For a database $D\in \{0,1{\}}^n$, the client secret-shares its index $i$: with two servers it picks a uniformly random $S\subseteq [n]$ and sends $S$ to one and $S△\{i\}$ to the other — an additive $(2,2)$ linear secret sharing of the characteristic vector of $i$ over ${\mathbb{F}}_2$ — and each server returns the XOR of the database bits it indexes, so the XOR of the two answers is $D[i]$. Each server’s view is a uniformly random subset independent of $i$, so privacy against each non-colluding server is perfect; this is information-theoretic two-server PIR with $O(n)$ communication. Arranging $D$ as a $d$-dimensional cube and sharing each coordinate separately gives $2^d$ servers with $O(n^{1/d})$ communication for constant $d$, and a covering-code argument lets two servers simulate the $d=3$ scheme with $O(n^{1/3})$ communication — CGKS98.

Sketch

Linearity keeps the answers short: a server holding a share $q$ of the characteristic vector $e_i$ returns $⟨q,D⟩$, and linear reconstruction applied to the answers gives $⟨e_i,D⟩=D[i]$; XOR sharing is the ${\mathbb{F}}_2$ case.