Application: Secret sharing

Four of us (Ariel, Amelia, Benjawan, Parinya) are working on the lecture notes for the course. Each person's mood is unpredictable and on a bad day one may decide to erase all the course documents.

To protect the course documents from these unpredictable people, a protocol is created.¹

• Every subset of three persons are given a permission to erase the course documents.
• No subset of two persons can erase any content.

How can we design such a scheme?

Let us consider a more abstract setting. We have $n$ players in a group, and the goal is to make sure that it requires (any combination of) $k$ players to open the document but a group of $(k-1)$ players can never access it. We can protect a document by some secret password $s$ (some integer). Pick a polynomial $p \in {\mathbb F}_q[x]$ of degree $k-1$ such that $p(0)= s$ (where $q$ is a prime larger than $s$ and $n$). Evaluate the polynomial at $1,\ldots, n$, i.e., $c_i = p(i) \pmod{q}$. We give the code $c_i$ to player $i$. The following lemma is a direct application of Theorem 44.

Lemma 16

Any group of $k$ players can access the value of $s$.

Proof:

Let $I \subseteq [n]$ be the set of $k$ players. From Theorem 44, there exists a unique polynomial $f$ of degree $(k-1)$ such that $f(i) = c_i\ (\forall i \in I)$ (the Lagrange polynomial), so it must be the case that $f= p$. We can compute $f(0) = p(0) = s \pmod{q}$ to get the secret password.

Next, we want to argue that any group of $(k-1)$ individuals can "learn nothing" about the secret value $s$. Here, we must first agree on some definition. What does it mean for someone to "learn nothing" in this case? We will go with the following notion.

Let us say that Ariel and Benjawan try to collude to mess up the lecture notes. Combining their information $(x_1,y_1)$ and $(x_2,y_2)$, let us say that $\mathcal{P}$ is the set of polynomials that agree with these points. We say that nothing can be learned if, for all $a \in {\mathbb F}_q$,

${\mathbb P}_{ f\in \mathcal{P}}[f(0) = a] = 1/q$

under a uniform distribution on $\mathcal{P}$. This means that, given the information from Benjawan and Ariel, the secret is equally likely to be any of the numbers in ${\mathbb F}_q$. Another way to view this is that there is no "information leak" from this collusion.

Using probabilistic statements to formulate a concept (e.g., the concept here is information leakage) is ubiquitous in computer science. This happens to be the first example we see in this course, but we are sure you will see many more such examples in the future.

Theorem 46

Let $I \subseteq [n]$ be a subset of collusion of size less than $k$. Then there is no information leak from this collusion.

Proof:

This relies on Exercise 122. Suppose $|I| = \ell < k$ is a subset of players that collude and

$A = \{(x_1,y_1), (x_2, y_2), \ldots, (x_{\ell}, y_{\ell})\}$

be their points that came from the evaluations of the secret polynomial $p$ (where $\deg(p) = k-1$). Let $\mathcal{P}$ be the polynomials that agree with these points, so from Exercise 122, we have that $|\mathcal{P}| = q^{(k-1)-\ell+1} = q^{k-\ell}$. For each $a \in {\mathbb F}_q$, define $A_a = A \cup \{(0,a)\}$, and $\mathcal{P}_a = \{f \in \mathcal{P}: f(0) = a\}$. Again, from Exercise 122, we have $|\mathcal{P}_a|= q^{k-\ell-1}$.

${\mathbb P}_{f \in \mathcal{P}}[f(0) = a] = \frac{|\mathcal{P}_a|}{|\mathcal{P}|} = 1/q$

This implies the desired result.

Exercise 123

Pick a random degree-$d$ polynomial $f \in {\mathbb F}_p[x]$ (with $p$ a prime) using the following random process. For each $i \in \{0,\ldots d\}$, pick a coefficient $c_i \in {\mathbb F}_p$ uniformly at random. Define $f(x) = c_0 + c_1 x + \ldots + c_d x^d$. What is the expected number of roots of $f$?

Footnotes

1. Economic models have long made assumptions about people being rational, until recent decades when this assumption was greatly challenged (e.g., by the late great psychologist Daniel Kahneman whose work was awarded the Nobel Prize in Economics). So, people in fact do not make rational choices in life and they are often not aware when they are not rational. ↩