Prove that something that can be learned from $S=\sum_{i=1}^n x_i$ is not less than what can be learned from $S+x_{n+1}$

Question

Is there a way to formally prove that whatever can be learned about any $x_i$ from $S=\sum_{i=1}^n x_i$ is certainly not less than what can be learned from $S'=S+x_{n+1}$ where $x_i$s belong to some field $\mathbb{F}$? Here learning is in the adversarial sense for cryptography -- can be any information an adversary can learn about $x_i$ which it could not have without access to $S/S'$ before.

Answer 1

Esentially, we want to prove $I(X_i,S)\ge I(X_i,S')$

Let's prove it (WLOG) for $X_i=X_1$

Let $A=X_1$, $B=X_2 +X_3 + \cdots X_n$ , $C=X_{n+1}$. Assume $X_i$ are independent (hence also $A,B,C$ are).

Let $X=A$, $Y=A+B$ , $Z=A+B+C$

---

Lemma: $X\to Y \to Z$ is a Markov chain.

Proof: $P(Z=z|Y=y,X=x)=P(X_{n+1} + y = z)=P(X_{n+1} = z -y)$

(for the last equation, recall that the variables belong to a field). Hence $P(Z|Y,X)=P(Z|Y)$. QED

---

Then, $I(X;Y)\ge I(X;Z)$ (basic property), that is

$$ I(X_1;X_1 + X_2 + X_n) \ge I(X_1; X_1 +X_2 + \cdots X_{n+1}) $$

as expected.

Or, if you prefer $H(X|Y)\le H(X|Z)$, i.e.

$$ H(X_1 |X_1 + X_2 + X_n) \le H(X_1 | X_1 +X_2 + \cdots X_{n+1}) $$