Prerequisites & Notation

Before You Begin

Shamir's secret sharing is built from finite-field polynomial evaluation and interpolation. The prerequisites are therefore elementary algebra over $\mathbb{F}_q$ . Readers who have not seen finite fields before should spend fifteen minutes with the self-checks below — the subsequent chapters of this book reuse these tools repeatedly.

Finite field $\mathbb{F}_q$ with $q$ a prime or prime power
Self-check: What is $3 \cdot 5 \bmod 7$ ? What is the multiplicative inverse of $3$ in $\mathbb{F}_7$ ?
Polynomial arithmetic in $\mathbb{F}_q[x]$
Self-check: Given $p(x) = x^2 + 2x + 1$ in $\mathbb{F}_7[x]$ , compute $p(3)$ and $p(5)$ .
Lagrange interpolation of a polynomial from its values
Self-check: Can you state the Lagrange interpolation formula for a polynomial of degree $t-1$ given its values at $t$ distinct points?
Entropy and conditional entropy of discrete random variables(Review ch01)
Self-check: If $X$ is uniform on $\{0, 1, \ldots, q-1\}$ , what is $H(X)$ ? What about $H(X \mid Y)$ when $Y$ is independent of $X$ ?
Chapter 2 of this book: distributed-computing framework(Review ch02)
Self-check: Can you state the $(\mu, \Delta, K)$ characterization of a coded-shuffling scheme?

Notation for This Chapter

Secret-sharing notation. We use $n$ for the number of parties (to avoid collision with $N$ = workers in the coded-computing chapters), and $t$ for the reconstruction threshold.

Symbol	Meaning	Introduced
$s$	The secret, an element of $\mathbb{F}_q$	s01
$n$	Number of parties among whom the secret is shared	s01
$t$	Reconstruction threshold (any $t$ shares recover $s$ )	s01
$s_k$	Share held by party $k$	s01
$p(x)$	Shamir polynomial of degree $t-1$ with $p(0) = s$	s02
$\alpha_k$	Evaluation point for party $k$ (distinct nonzero elements)	s02
$\mathbb{F}_q$	Finite field of order $q$ (prime or prime power); need $q > n$	s02
$\ell_k(x)$	Lagrange basis polynomial for evaluation point $\alpha_k$	s02
$g$	Ramp width: secret is split into $g$ chunks (ramp scheme)	s04
$R_{\text{share}} \triangleq \|\text{share}\|/\|\text{secret}\|$	Share-size / secret-size ratio; $R_{\text{share}} = 1$ for Shamir, $1/g$ for $g$ -ramp	s04

← Ch 2 The

(t, n)

-Threshold Problem