Exercises

Perfect secrecy of $F$-bit message requires $F$-bit uniform key. Otherwise leakage exists.

$X$ is independent of $\mathcal{W}$ (secrecy). User $k$ recovers $W_{d_k}$ from $(X, \mathcal{Z}_k)$. Hence $\mathcal{Z}_k$ must contain $\geq F$ bits of key for each file decoded — $M \geq 1$.

$M_\text{eff} = 2$, $\mu_\text{eff} = 0.25$. $R_\text{sec} = 4 \cdot 0.75 / (1 + 1) = 1.5$.

$\mu = 3/8 = 0.375$. $R_\text{MAN} = 4 \cdot 0.625 / (1 + 1.5) = 2.5/2.5 = 1$.

Secure rate (1.5) higher than non-secure (1.0) — secrecy costs 0.5 files/use.

As $N \to \infty$: $\mu = M/N \to \mu_\infty$. Both rates approach $K(1 - \mu_\infty)/(1 + K\mu_\infty)$ since the $-1$ shift becomes negligible.

Secrecy penalty vanishes at library scale. For CDN-scale libraries ($N \sim 10^6$), secure rate is essentially free.

$p(x) = S + a_1 x$ with $a_1$ random over $\mathbb{F}_q$.

User 1: $p(1) = S + a_1$. User 2: $p(2) = S + 2 a_1$. User 3: $p(3) = S + 3 a_1$.

Subtract: $p(2) - p(1) = a_1 \Rightarrow$ recover $a_1$. Then $S = p(1) - a_1$.

Knowing only $p(1) = S + a_1$ with $a_1$ uniform: $S$ remains uniform conditional on this. Zero leakage.

$M = 2 \geq 1 \Rightarrow$ feasible.

$M_\text{eff} = 1$. $\mu_\text{eff} = 0.01$.

$R_\text{sec} = 10 \cdot 0.99 / (1 + 0.1) = 9.9 / 1.1 = 9$ files/channel-use.

$R_\text{MAN} = 10 \cdot 0.98 / 1.2 = 8.17$. Secure rate higher by ~10% — small penalty at this scale.

Each $\mathbf{K}_{\mathcal{S'}}$ uniform on $\{0,1\}^{|X_{\mathcal{S'}}|}$ and independent of $\mathcal{W}$ (by Shamir construction).

$\tilde X_{\mathcal{S'}} = X_{\mathcal{S'}} \oplus \mathbf{K}_{\mathcal{S'}}$. Since $\mathbf{K}_{\mathcal{S'}}$ uniform: $\tilde X_{\mathcal{S'}}$ uniform.

$\tilde X_{\mathcal{S'}}$ uniform $\Rightarrow$ independent of everything, including $\mathcal{W}$. Hence $I(\mathcal{W}; \tilde X_{\mathcal{S'}}) = 0$.

Full $X$ is a concatenation of $\tilde X_{\mathcal{S'}}$; each independent of $\mathcal{W}$ $\Rightarrow I(\mathcal{W}; X) = 0$. $\blacksquare$

$\mathcal{E}$ holds $X$ plus caches of users $\mathcal{T}$ with $|\mathcal{T}| = z$.

$I(\mathcal{W}; X, \mathcal{Z}_\mathcal{T}) = 0$.

Use $(z + t, K)$-threshold sharing instead of $(t, K)$: any $z$ shares still learn nothing; $z + t + 1$ reconstruct. Additional share cost: $z$ shares $\times$ amortization $\Rightarrow$ per-user memory $\geq 1 + z/K$ approximately.

$M \geq 1 + o(1)$ for $z = o(K)$; $M \geq 1 + z/K$ for fixed ratio. Degrades gracefully with $z$.

Perfect secrecy; quantum-safe; 1 file of key material per user; key rotation per delivery.

128-bit security; quantum-vulnerable (Grover's $\sqrt{}$ speedup); 16-byte key + 16-byte nonce per user; key rotation based on sequence number.

STC: $\sim F$ bits per user (large). AES: $\sim 32$ bytes per user (tiny).

STC: high-security applications (government, financial), post-quantum roadmap. AES: general CDN, computational security acceptable.

$M_\text{eff} = 1$, $t = K M_\text{eff}/N = 3/4 \Rightarrow$ non-integer. Use time-sharing or round to $t = 1$.

MAN: each file split into 3 subfiles (for $t = 1$). User $k$ caches $W_{n, \{k\}}$ for all $n$. Shamir keys for each pair. Private permutation $\pi_k$ on $[4]$ per user.

$\tilde{\mathbf{d}} = (\pi_1(d_1), \pi_2(d_2), \pi_3(d_3))$.

$X_{\mathcal{S'}} = \bigoplus_{k \in \mathcal{S'}} W_{\tilde d_k, \mathcal{S'} \setminus \{k\}}$, then $\tilde X_{\mathcal{S'}} = X_{\mathcal{S'}} \oplus \mathbf{K}_{\mathcal{S'}}$.

Each user unmasks its messages using Shamir-reconstructed keys, then decodes via MAN. Privacy: insiders don't know $\pi_j$ for $j \neq k$. Secrecy: eavesdropper sees uniform noise.

Each user caches random bits independently; no combinatorial subset structure to index keys by.

STC's key-per-$(t+1)$-subset structure doesn't translate. Random access to file bits: keys must be indexed by bit position, not subset.

Use random-placement-compatible key derivation (e.g., PRG with position as input). Loses info-theoretic secrecy; gains practicality.

A fully decentralized, info-theoretic secure scheme with the MAN rate is an open problem as of 2024.

For user $k$ decoding $W_{d_k}$: $H(W_{d_k} | \mathcal{Z}_k, X) \leq F \epsilon$.

$I(W_{d_k}; X) = 0 \Rightarrow H(W_{d_k} | X) = H(W_{d_k}) = F$.

$F = H(W_{d_k} | X) = H(W_{d_k} | \mathcal{Z}_k, X) + I(W_{d_k}; \mathcal{Z}_k | X) \leq F\epsilon + M F$.

$M \geq 1 - \epsilon$, so $M \geq 1$ as $\epsilon \to 0$. $\blacksquare$

$M = 0.5 < 1 \Rightarrow$ STC infeasible.

• Hybrid TLS + MAN. TLS encryption (computational secrecy), MAN caching for bandwidth. Loses info-theoretic but works with small cache.
• Downscale security. Accept weak secrecy bound $I(\mathcal{W}; X) \leq \epsilon$ for small $\epsilon$, trading off via weaker key material.
• Larger cache. Add flash storage to sensors.

$M \geq 1$ is fundamental. Small-cache IoT devices cannot use info-theoretic STC; must resort to computational schemes.

If eavesdroppers observe identical $X$: equivalent to single eavesdropper. $M \geq 1$ suffices.

If $Y_i$ are genuinely different (e.g., different channels): more info leaked; stricter bound. But if $X$ is secure individually, it's secure jointly.

Colluding eavesdroppers with MAC-like observations may gain more. STC's construction extends: use larger field / stronger Shamir bounds.

For $e$ colluding eavesdroppers: $M \geq 1$ still sufficient if we use independent keys per channel. Engineering overhead: $e$ fresh keys per round.

Wan-Caire: zero rate cost. Masking permutation $\pi_k$ doesn't change XOR structure.

STC: 1 file of memory. $M_\text{eff} = M - 1$.

Rate = STC rate (only secrecy imposes rate penalty).

Combining two orthogonal security properties: pay only for the one that has cost. Layered security works.

Eavesdropper not only observes but also injects $X'$ hoping users decode it as legitimate.

Add MAC (HMAC-SHA256) per XOR message. Eavesdropper can't forge without key.

Use universal hash functions (Carter-Wegman) for unconditional authentication. Additional key material: $\log N$ bits per message.

Authentication + STC secrecy + privacy: combined overhead dominated by the 1-file STC key. Authentication overhead is lower-order.