Applications in Secure and Distributed Computing

In secure coded matrix multiplication (the topic of Chapter 5 with a privacy extension), the dataset rows $\mathbf{a}_i$ are sensitive: we want workers to compute $\mathbf{A}^T \mathbf{B}$ without any single worker learning any row of $\mathbf{A}$ (or the corresponding row of $\mathbf{B}$).

Construction. Split each row $\mathbf{a}_i$ via a $(t, N)$-Shamir scheme before distributing to $N$ workers. Each worker computes its polynomial-coded product of the share; the master reconstructs the sum via Lagrange interpolation from any $K \geq t$ responses. No single worker, and no coalition of fewer than $t$ workers, learns any row of $\mathbf{A}$.

The privacy parameter $t$ interacts with the recovery threshold $K$ of the coded-computing scheme: privacy costs $t - 1$ "extra" redundant workers, which the recovery threshold inherits.

Secure aggregation (Chapter 10) lets a server compute $\sum_k \mathbf{g}_k$ over $n$ users' gradients without learning any individual gradient. The essential primitive is the additive $(n, n)$-scheme from Section 3.1: each user adds pairwise random masks to its gradient, and all masks cancel in the aggregate.

More precisely, for each pair $(i, j)$ of users, let $\mathbf{r}_{ij} = -\mathbf{r}_{ji}$ be a symmetric random mask drawn from a fresh per-round pseudorandom generator seeded by a Diffie-Hellman key exchange. User $k$ uploads $$\tilde{\mathbf{g}}_k \;=\; \mathbf{g}_k + \sum_{j \neq k} \mathbf{r}_{kj}.$$ The server sums: $\sum_k \tilde{\mathbf{g}}_k = \sum_k \mathbf{g}_k + \sum_{i < j} (\mathbf{r}_{ij} + \mathbf{r}_{ji}) = \sum_k \mathbf{g}_k + 0 = \sum_k \mathbf{g}_k$. No subset of the users can break the aggregate's privacy because the sum of masks is zero only when all are combined.

In private information retrieval (Chapter 13), a user wants to retrieve file $W_{\theta}$ from $N$ databases without revealing the index $\theta$ to any single database. The user constructs $N$ queries $Q_1, \ldots, Q_N$, one per database, such that:

• The joint of $(Q_1, \ldots, Q_N)$ depends on $\theta$;
• Each individual $Q_k$ is information-theoretically independent of $\theta$ (or, in the $T$-colluding variant, any $T$-subset is independent).

The Sun–Jafar protocol implements this using linear secret sharing: each query is a Shamir-like evaluation of a carefully- constructed polynomial whose coefficients encode the query index. Secret sharing is the primitive that hides the query from individual databases; coding theory is the primitive that keeps the download rate as close to the PIR capacity as possible.