Exercises

$C = (1 + 1/3 + 1/9)^{-1} = (13/9)^{-1} = 9/13 \approx 0.692$.

Compare with $1 - r/N = 1 - 1/3 = 0.667$ (asymptotic limit). At $K = 3$, capacity is slightly above the asymptote.

$C = (1 + 1/2 + 1/4)^{-1} = (7/4)^{-1} = 4/7 \approx 0.571$.

$C_{\text{PIR}}(4, 3, 1) = (1 + 1/4 + 1/16)^{-1} = 16/21 \approx 0.762$. Going from $T = 1$ to $T = 2$ costs $\approx 25\%$ rate.

$C_{\text{SPIR}}(5, 100) = 1 - 1/5 = 0.8$.

SPIR's database-privacy requirement forces the user to learn only $W_\theta$ — regardless of how many other files exist. The other files contribute zero to the achievable rate. Consequently, $K$ doesn't enter the formula — only $N$ matters.

Storage: $4 \cdot 12 = 48$ units. Rate: $C(12, 4, 1) = (1 + 1/12 + 1/144 + 1/1728)^{-1} \approx 0.917$.

Storage: $24$ units. Rate: $(1 + 2/12 + 4/144 + 8/1728)^{-1} \approx 0.838$.

Storage: $16$ units. Rate: $(1 + 3/12 + 9/144 + 27/1728)^{-1} \approx 0.760$.

Storage: $12$ units. Rate: $(1 + 4/12 + 16/144 + 64/1728)^{-1} \approx 0.683$.

Storage: $8$ units. Rate: $(1 + 6/12 + 36/144 + 216/1728)^{-1} \approx 0.533$.

The Pareto frontier is convex (in storage, rate space). The rate/storage efficiency peaks around $r = 3$ — a useful operating point for cost-conscious deployments.

$C(6, 4, 1) = (1 + 1/6 + 1/36 + 1/216)^{-1} = 216/259 \approx 0.834$.

$C(6, 4, 2) = (1 + 2/6 + 4/36 + 8/216)^{-1} = 216/335 \approx 0.645$.

Absolute loss: $0.834 - 0.645 = 0.189$. Relative loss: $0.189 / 0.834 \approx 22.7\%$.

Going from $T = 1$ to $T = 2$ costs $\sim 23\%$ rate. The operator should decide whether the security improvement is worth the bandwidth.

Without shared randomness, the answers $A^{(\theta, n)} = f_n(Q^{(\theta, n)}, W_1, \ldots, W_K)$ are deterministic functions of the query and the files.

For any function $g$ of the user's view, $g(\{Q^{(\theta, n)}, A^{(\theta, n)}\})$ depends deterministically on $W_j$ for $j \neq \theta$. The user can construct a function that equals one bit of $W_j$ — violating database privacy.

Database privacy with deterministic answers and a single query realization is impossible. Therefore positive-rate SPIR requires shared randomness as a masking mechanism.

$r + T - 1 < 8$, i.e., $r + T \leq 8$.

$(r, T)$: $(1, 1), (1, 2), \ldots, (1, 7), (2, 1), (2, 2), \ldots, (2, 6), \ldots, (7, 1)$. Total: $\binom{8}{2}$ feasible pairs (anti-diagonal of the $7 \times 7$ grid below the diagonal $r + T = 8$).

At $N = 8$: can have $(r, T) = (3, 3)$ for $3$x storage savings and $3$-collusion tolerance. Or $(r, T) = (2, 4)$ for $2$x storage and $4$-collusion. Many combinations available.

$C \to 1 - 1/N = 1 - 1/5 = 0.8$.

$C \to 1 - T/N = 1 - 2/5 = 0.6$.

$C \to 1 - r/N = 1 - 2/5 = 0.6$ (same as $T = 2$, by symmetry of the formula — coincidence, not equivalence).

$C = 1 - 1/N = 0.8$ for all $K$. No asymptotic statement needed.

Classical PIR and SPIR have the same asymptotic rate ($1 - 1/N$). For large $K$, the SPIR cost is essentially zero. For small $K$, classical is strictly better (and SPIR is necessary if both sides need privacy).

Each query symbol is constructed as a polynomial $p(x)$ of degree $T$ over $\mathbb{F}_q$, with $T + 1$ coefficients chosen pseudo-randomly. The polynomial is evaluated at $N$ distinct points, with the evaluations sent to the $N$ databases.

Shamir's privacy guarantee: any $T$ evaluations of a degree-$T$ polynomial are statistically independent of the polynomial's secret-encoded coefficient (the desired index $\theta$).

Polynomial of degree $< T$ would not provide $T$-privacy: $T$ evaluations determine the polynomial uniquely, revealing $\theta$.

Higher degree wastes the rate: the polynomial can be reconstructed by the databases jointly, but the user needs to wait for at least $\deg + 1$ evaluations to decode. Excess degree means lower rate. Degree exactly $T$ is the sweet spot.

Let the answers $A^{(\theta, 1)}, \ldots, A^{(\theta, N)}$ each be a function of $(Q^{(\theta, n)}, W_1, \ldots, W_K, S)$.

$H(\{W_{k \neq \theta}\} | A^{(\theta, 1)}, \ldots, A^{(\theta, N)}, Q^{(\theta, *)}) = H(\{W_{k \neq \theta}\})$ by privacy. Equivalently: each answer must be conditionally independent of $W_{k \neq \theta}$ given $S$ and $\{W_\theta\}$.

Each answer carries information about the structure (depending on $\theta$) but must be statistically masked from $W_{k \neq \theta}$. The masking requires entropy from $S$ proportional to the file content $L$ — at minimum $L/(N-1)$ bits.

Sun-Jafar's SPIR construction achieves exactly $H(S) = L/(N-1)$, proving the bound is tight.

$C(10, 5, 1) = (1 + 0.1 + 0.01 + 0.001 + 0.0001)^{-1} = 1/1.1111 \approx 0.900$.

$C(10, 5, 3) = (1 + 0.3 + 0.09 + 0.027 + 0.0081)^{-1} = 1/1.4251 \approx 0.702$.

$C(10, 5, 3) = (1 + 0.3 + 0.09 + 0.027 + 0.0081)^{-1} \approx 0.702$ (same as (b) by formula coincidence).

$r + T - 1 = 5$. $R = (10 - 5)/10 \cdot (1 - (5/10)^5)^{-1} = 0.5 \cdot (1 - 0.03125)^{-1} = 0.5 \cdot 1.0323 \approx 0.516$.

$(0.702)(0.702) / 0.900 \approx 0.548$. Predicted by naive product rule.

Joint actual: $0.516$. Naive composition: $0.548$. Naive composition overestimates the joint rate by $\sim 6\%$. The actual joint rate is harder to achieve than the product rule suggests.

SPIR: $0.75$ for all $K$. Classical: $C(4, K) = 4/(4 \cdot \sum_{i=0}^{K-1} (1/4)^i) = (1 - 1/4)/(1 - (1/4)^K) = 0.75 / (1 - 4^{-K})$.

$\text{Gap}(K) = 0.75 / (1 - 4^{-K}) - 0.75 = 0.75 \cdot 4^{-K} / (1 - 4^{-K}) \approx 0.75 \cdot 4^{-K}$ for large $K$.

$0.75 \cdot 4^{-K} = 0.001 \Rightarrow 4^{-K} = 4/3 \cdot 10^{-3} \Rightarrow -K \log 4 = \log(4/3) - 3 \Rightarrow K \approx 4.7$. So at $K = 5$ the gap drops below $0.001$.

$K = 5$: gap $= 0.75 \cdot 4^{-5}/(1 - 4^{-5}) = 0.75 / 1023 \approx 0.000733$. Confirms $K = 5$ is the crossover.

For any library with $\geq 5$ files at $N = 4$ databases, SPIR's rate cost over classical PIR is below $0.1\%$ — essentially free.

• User privacy: yes (PIR baseline).
• Database privacy: yes (HIPAA-style).
• Collusion tolerance: $T = 2$.
• Storage: replicated (no constraint mentioned).

SPIR + $T = 2$-colluding. Combines two of the §14.4 extensions.

SPIR with $T$-colluding: outer bound is $1 - T/N = 1 - 2/5 = 0.6$ (the $K$-independent SPIR-style limit adjusted for collusion). Achievable rate is $\leq 0.6$.

Classical Sun-Jafar at $K = 1000, N = 5$: $C \approx 0.8$ (asymptotic). Loss from full requirement set: $\sim 25\%$ rate.

Acceptable for medical applications — the $0.6$ rate corresponds to downloading $\sim 1.67\times$ the target file. Acceptable bandwidth cost for HIPAA compliance.

Per-file: $L/3 = 1\text{ MB}/3 \approx 333\text{ kB}$. Across $10000$ files: $\sim 3.33\text{ GB}$ of shared randomness needed.

• Generate master seed $K \in \{0, 1\}^{256}$.
• Distribute $K$ via $(N-1, N)$-Shamir secret sharing across the $N$ databases. Each database gets a share that, combined with $N-1$ others, reconstructs $K$.
• Each database derives per-file masks via $\text{PRG}(K, \text{file\_id})$.
• For each PIR query, the databases use the corresponding pseudo-random masks (deterministic given $K$ and query parameters).
• The user never learns $K$.

Storage: $N \cdot 256$ bits for the shares — negligible. Compute: $O(L)$ PRG evaluations per query. Avoids distributing $3.33$ GB of true randomness.

With a PRG, the SPIR is now computationally secure, not information-theoretically secure. For IT-secure SPIR, true randomness must be distributed (e.g., via OTP- like setup).

Choose any subset $\mathcal{S} \subseteq [N]$ of size $r + T - 1$ databases.

• From the MDS structure: the entropy of their joint storage is $\geq L \cdot (r + T - 1)/r$.
• From the $T$-collusion privacy: the entropy of the queries to $\mathcal{S}$ is $\geq H(\theta)$ if $|\mathcal{S}| \geq T$.
• Symmetrize, normalize, recurse.

The cut-set converse uses one cut at a time. For finite $K$, the joint constraint may be tighter when applied across multiple cuts simultaneously — but this is not captured by single- cut techniques.

The achievable rate ($\sim$ Freij-Hollanti) is conjectured to be optimal, but no matching converse is known. Closing this gap requires either: (i) a tighter outer bound (multi-cut) or (ii) a tighter achievable scheme.

$K = 2$: capacity is settled. $K \geq 3$: gap remains open. Recent work (e.g., Jia-Sun-Jafar 2019) has narrowed the gap but not closed it.

Connection to coded-computing capacity (Chapters 5, 8) might offer new techniques. The structure of the joint problem resembles a coded secret-sharing instance — known to have rate $\sim 1 - r/N$ in similar contexts.