[proofplan] Fix $k - 1$ distinct indices and their share values. We count the pairs $(S, a_1, \dots, a_{k-1}) \in \mathbb{F}_p^k$ — the full randomness of the scheme — that produce those shares. For each candidate secret $S \in \mathbb{F}_p$, Lagrange interpolation over $\mathbb{F}_p$ produces exactly one polynomial of degree at most $k - 1$ that takes the value $S$ at $0$ and the values $y_j$ at $i_j$; this uses that $i_1, \dots, i_{k-1}, 0$ are $k$ distinct points in $\mathbb{F}_p$, guaranteed by $p > n$. Thus every $S$ admits exactly one completion to a full assignment, so every $S$ is equally likely under the uniform prior on the coefficients. [/proofplan] [step:Fix the conditioning event and parametrise the sample space] Let $i_1, \dots, i_{k-1} \in \{1, \dots, n\}$ be distinct and let $y_1, \dots, y_{k-1} \in \mathbb{F}_p$ be arbitrary. The randomness of the scheme lies in the coefficient vector \begin{align*} (a_1, \dots, a_{k-1}) \in \mathbb{F}_p^{k-1}, \end{align*} chosen uniformly from $\mathbb{F}_p^{k-1}$. The secret $S$ is fixed by the dealer; the distribution we analyse is the conditional law of $S$ given the shares. To talk about $S$ as a random variable we let $S$ range over $\mathbb{F}_p$ uniformly as well and consider the full random vector \begin{align*} (S, a_1, \dots, a_{k-1}) \in \mathbb{F}_p^k, \end{align*} distributed uniformly on $\mathbb{F}_p^k$. (This uniform prior on $S$ is the standard adversarial model: it represents maximum uncertainty about the secret.) The conditioning event is \begin{align*} E := \{f(i_1) = y_1, \dots, f(i_{k-1}) = y_{k-1}\}, \end{align*} where $f(t) = S + a_1 t + \dots + a_{k-1} t^{k-1}$. [/step] [step:Invoke Lagrange interpolation to count consistent polynomials] Let $S \in \mathbb{F}_p$ be fixed. Consider the $k$ points \begin{align*} (0, S), \; (i_1, y_1), \; \dots, \; (i_{k-1}, y_{k-1}) \in \mathbb{F}_p \times \mathbb{F}_p. \end{align*} The $x$-coordinates $0, i_1, \dots, i_{k-1}$ are $k$ distinct elements of $\mathbb{F}_p$: they are pairwise distinct by hypothesis, and $0 \notin \{i_1, \dots, i_{k-1}\}$ because the $i_j$ lie in $\{1, \dots, n\}$. Since $p > n$, none of $0, 1, \dots, n$ collapse under reduction modulo $p$, so the $k$ points are genuinely distinct in $\mathbb{F}_p$. We apply [Lagrange interpolation over a field](/theorems/???), which states: given $k$ distinct points $x_0, \dots, x_{k-1} \in \mathbb{F}_p$ and arbitrary values $v_0, \dots, v_{k-1} \in \mathbb{F}_p$, there exists a unique polynomial $g \in \mathbb{F}_p[t]$ of degree at most $k - 1$ with $g(x_j) = v_j$ for $j = 0, \dots, k - 1$. With $(x_0, v_0) = (0, S)$ and $(x_j, v_j) = (i_j, y_j)$ for $j \ge 1$, this gives a unique polynomial $f_S \in \mathbb{F}_p[t]$ of degree at most $k - 1$ satisfying \begin{align*} f_S(0) = S \quad \text{and} \quad f_S(i_j) = y_j \text{ for } j = 1, \dots, k - 1. \end{align*} [guided] Why does Lagrange interpolation apply over $\mathbb{F}_p$? The theorem requires that the $k$ interpolation nodes be distinct elements of the ground field. We verify: - The nodes $i_1, \dots, i_{k-1}$ are pairwise distinct in $\{1, \dots, n\}$ by hypothesis. - The node $0$ does not coincide with any $i_j$ because $i_j \ge 1$. - All of $0, 1, \dots, n$ remain distinct when reduced modulo $p$, because the hypothesis $p > n$ guarantees that the map $\{0, 1, \dots, n\} \to \mathbb{F}_p$ is injective. With distinctness established, Lagrange's construction is explicit: \begin{align*} f_S(t) = S \cdot \ell_0(t) + \sum_{j=1}^{k-1} y_j \cdot \ell_j(t), \end{align*} where $\ell_0, \ell_1, \dots, \ell_{k-1}$ are the Lagrange basis polynomials for the nodes $0, i_1, \dots, i_{k-1}$. Explicitly, \begin{align*} \ell_0(t) &= \prod_{m=1}^{k-1} \frac{t - i_m}{0 - i_m}, \\ \ell_j(t) &= \frac{t}{i_j} \prod_{m \ne j, \, m \ge 1} \frac{t - i_m}{i_j - i_m} \quad (j \ge 1). \end{align*} Each denominator is a product of non-zero elements of $\mathbb{F}_p$ — the differences of distinct interpolation nodes — and is therefore invertible in $\mathbb{F}_p$. (This is the step that would fail in $\mathbb{Z}/m\mathbb{Z}$ for composite $m$, and it is precisely why Shamir's scheme requires a prime modulus $p > n$.) Uniqueness follows because two interpolating polynomials of degree at most $k - 1$ that agree at $k$ distinct points differ by a polynomial of degree at most $k - 1$ with $k$ roots, which must be identically zero. [/guided] [/step] [step:Translate polynomials into coefficient vectors bijectively] Define the evaluation map \begin{align*} \Phi: \mathbb{F}_p^k &\to \{g \in \mathbb{F}_p[t] : \deg g \le k - 1\} \\ (S, a_1, \dots, a_{k-1}) &\mapsto S + a_1 t + \dots + a_{k-1} t^{k-1}. \end{align*} $\Phi$ is a bijection: the coefficients of a polynomial of degree at most $k - 1$ are uniquely determined by the polynomial, and conversely every such polynomial arises from its coefficient vector. Hence for every candidate secret $S \in \mathbb{F}_p$, the unique polynomial $f_S$ from the previous step corresponds under $\Phi^{-1}$ to exactly one coefficient vector $(S, a_1^{(S)}, \dots, a_{k-1}^{(S)}) \in \mathbb{F}_p^k$. Consequently the conditioning event $E = \{f(i_1) = y_1, \dots, f(i_{k-1}) = y_{k-1}\}$ decomposes as a disjoint union over candidate secrets: \begin{align*} E = \bigsqcup_{S \in \mathbb{F}_p} \{(S, a_1^{(S)}, \dots, a_{k-1}^{(S)})\}, \end{align*} and in particular $|E| = |\mathbb{F}_p| = p$: each secret contributes exactly one sample point to $E$. [/step] [step:Compute the conditional distribution of $S$ given the observed shares] Under the uniform prior on $\mathbb{F}_p^k$, every singleton $\{(S, a_1, \dots, a_{k-1})\} \subset \mathbb{F}_p^k$ has probability $p^{-k}$. By the previous step, $E$ contains exactly one sample point per value of $S$, so \begin{align*} \mathbb{P}(E \cap \{S = s\}) = p^{-k} \quad \text{for every } s \in \mathbb{F}_p, \end{align*} and consequently $\mathbb{P}(E) = p \cdot p^{-k} = p^{1-k}$. By definition of conditional probability, \begin{align*} \mathbb{P}(S = s \mid E) = \frac{\mathbb{P}(S = s, E)}{\mathbb{P}(E)} = \frac{p^{-k}}{p^{1-k}} = \frac{1}{p}. \end{align*} This holds for every $s \in \mathbb{F}_p$, so the conditional law of $S$ given $E$ is the uniform distribution on $\mathbb{F}_p$. In particular, for any $S, S' \in \mathbb{F}_p$, \begin{align*} \mathbb{P}(S \mid E) = \mathbb{P}(S' \mid E) = \frac{1}{p}, \end{align*} so both candidate secrets are equally consistent with the $k - 1$ observed shares. The conditional entropy $H(S \mid E) = \log_2 p$ equals the unconditional entropy $H(S) = \log_2 p$, i.e., the shares convey zero bits of information about $S$. [guided] The conclusion expresses **information-theoretic security**: the mutual information $I(S; (f(i_1), \dots, f(i_{k-1})))$ between the secret and any $k - 1$ shares is zero. No adversary, however computationally powerful, can distinguish between candidate secrets given fewer than $k$ shares, because the observation is statistically independent of the secret. Contrast this with the computational security of RSA, where security rests on the conjectured hardness of factoring: an adversary with a factoring oracle breaks RSA completely. Shamir's scheme admits no such attack because the secret simply is not a function of fewer than $k$ shares — a $k$th share is required to pin down $f$, and until one is supplied every completion of the observed $k - 1$ shares to a full polynomial remains in play. The role of the hypothesis $p > n$ is now visible: it ensures that $1, 2, \dots, n$ are distinct non-zero elements of $\mathbb{F}_p$, so each share index $i_j$ produces a valid, non-degenerate Lagrange node. Without $p > n$, two of the $i_j$ could collapse modulo $p$, destroying the interpolation argument. [/guided] [/step]