An algebraic view of secret sharing

Wildon's Weblog 2019-08-20

As last year I’m lecturing our 3rd year / 4th year / M.Sc. course on cipher systems. As part of the M.Sc. course I cover the Shamir Secret Sharing Scheme. Here is Shamir’s idea generalized to arbitrary commutative rings, with an application to secret sharing in a hierarchical organization. The idea is very obvious, so no originality is expected or claimed.

For a practical example, imagine that I have a critically important 20GB file. Using a secret-sharing scheme with threshold $3$ , I issue shares of the file (each most probably still of size 20GB) to Amazon, Degoo (who promise a ‘top secret cloud drive’) Dropbox and Microsoft. If any single provider goes out of business, or maliciously corrupts the share, the file can still be reconstructed from the remaining three shares. Depending on how much I trust them (and the computational resources available on the various platforms), the reconstruction could be done in the cloud, or on my own machine. In the latter case, a provider can learn the secret only if three of them collude by pooling their shares: this would presumably be a serious breach of all their terms of service.

Mathematical formulation

Fix $n \in \mathbb{N}$ and let $1 \le t \le n$ . Fix a commutative ring $R$ and distinct ideals $I$ , $J_1, \ldots, J_n$ of $R$ . The secret is an element of $R/I$ . We suppose that $R$ has a subset $S$ such that

if $A \subseteq \{1, \ldots, n\}$ is a $t$ -set then the composition $S \hookrightarrow R \rightarrow \prod_{i \in A} R/J_i$ is injective;
if $A \subseteq \{1, \ldots, n\}$ is a $(t-1)$ -set then the composition $S \hookrightarrow R \rightarrow R/I \times \prod_{i \in A} R/J_i$ is surjective.

In particular (2) implies that $S \hookrightarrow R \twoheadrightarrow R/I$ is surjective.

To share a secret $s + I \in R/I$ , pick $r \in S$ such that $r \equiv s$ mod $I$ ; the share for algebraist $i$ is then $r + J_i \in R/J_i$ . By hypothesis, for each $A \subseteq \{1,\ldots, n\}$ such that $|A| = t$ , the unique element of $R$ congruent to $r$ modulo $J_i$ for each $i \in A$ is $r$ itself. Therefore any $t$ (or more) algebraists can pool their shares and determine $r$ , and hence $s = r+I$ .

Shamir’s Scheme

Fix a prime $p$ and distinct $c_1, \ldots, c_n \in \mathbb{F}_p$ . Take $R = \mathbb{F}_p[X]$ , $I = \langle X \rangle$ , and $J_i = \langle X - c_i \rangle$ and $S = \{ r \in R : \mathrm{deg} f < t \}$ . (Thus the secret is $r(0)$ , and the share for algebraist $i$ is $r(c_i)$ .) Property (1) holds because a polynomial of degree $\le t-1$ is uniquely determined by its values at the $t$ distinct points $c_i$ for $i \in A$ . Moreover, since the map

$\displaystyle S \rightarrow R/I \times \prod_{i \in A} R/J_i \cong \mathbb{F}_p \times \mathbb{F}_p^{t-1}$

is a linear isomorphism whenever $|A| = t-1$ , we have (2) in the strongest possible form.

Integer version

For another special case, fix a prime $p$ , a parameter $c \ge 2$ (of which more later) and consecutive primes $q_1 \le \ldots \le q_n$ with $cp \le q_1$ . Let $Q = q_1 \ldots q_t$ . Take $R = \mathbb{Z}$ , $I = p\mathbb{Z}$ , $J_i = q_i \mathbb{Z}$ and

$S = \{0,1,\ldots, Q-1\}.$

Since each $r \in S$ is uniquely determined by its residues modulo any $t$ of the $q_i$ , we have (1). Suppose the $t-1$ algebraists numbered $a_1, \ldots, a_{t-1}$ pool their shares. They can learn $r$ modulo $Q' = q_{a_1} \ldots q_{a_{t-1}}$ . Now $S$ contains $\lfloor Q/Q' \rfloor$ ‘candidate secrets’ of the form $r+ b Q'$ where $b \in \mathbb{Z}$ . Provided $c$ is sufficiently large,

$\displaystyle \frac{Q}{Q'} = \frac{q_1 \ldots q_t}{q_{a_1} \ldots q_{a_{t-1}}} \ge cp\frac{q_2 \ldots q_t}{q_{n-t+2} \ldots q_n} \ge p$ .

Therefore the ‘candidate secrets’ cover all residue classes modulo $p$ , and so (2) holds. Moreover, the sizes of the fibres over each $(r^\star + I, r + J_{a_1}, \ldots, r+J_{a_{t-1}})$ vary by at most $1$ with $r^\star$ , and have mean size $Q / p q_{a_1} \ldots q_{a_{t-1}}$ . Provided $c$ is large, all the primes $q_i$ have about the same size, and the mean fibre size is approximately $c$ .

Example

Provided $c$ is large, this variation in the fibre leaks very little information. For small $c$ is it a problem. For example, take $n=4$ , $t=3$ , $c = 2$ , $p = 11$ and $q_1 = 23$ , $q_2 = 29$ , $q_3 = 31$ , $q_4 = 37$ . Thus $Q = q_1q_2q_3 = 20677$ . For the secret $s$ we choose $7$ , lifting it to

$r = 11161 \in \{0,\ldots, Q-1\}.$

The shares are then $6, 25, 1, 24$ . If algebraists $3$ and $4$ cooperate they can learn $r$ modulo $31 \times 27$ . This leaves

$\lfloor \frac{Q}{31 \times 37} \rfloor = 18$

possibilities for $r$ . The mean fibre size is $18 / 11$ and since $18 = 2 \times 7 + 1 \times 4$ , there are $7$ fibres of size $2$ and $4$ of size $1$ (namely those for $1 + 11\mathbb{Z}$ , $4 + 11\mathbb{Z}$ , $7 + 11\mathbb{Z}$ and $10 + 11\mathbb{Z}$ ). Choosing one of these at random gives them a $1/4$ chance of guessing the secret.

Choosing a small fibre is a good heuristic, but not infallible: it is possible that the secret corresponds to a large fibre—for example if algebraists $1$ and $2$ pool their shares then the fibres for $2 + 11 \mathbb{Z}$ and $9 + 11\mathbb{Z}$ have size $2$ , and the rest have size $3$ .

Question

What other rings are amenable to the generalized Shamir scheme?

Secret sharing in a hierarchy

One possible answer to this question is ‘multivariable polynomial rings’. Here is an idea along these lines.

Let $R = \mathbb{F}_p[X,Y]$ . Fix $m, n \in \mathbb{N}$ and thresholds $t$ , $u$ with $t \le m$ and $u \le n$ . Let $S$ be the set of polynomials $f \in R$ with $\mathrm{deg}_X f < t$ and $\mathrm{deg}_Y f < u$ . Fix distinct non-zero $c_1, \ldots, c_m \in \mathbb{F}_p$ and distinct $d_1, \ldots, d_n \in \mathbb{F}_p$ . The aim is to share a secret $s \in \mathbb{F}_p$ between teams $T_1, \ldots, T_n$ where team $T_j$ consists of people $P_{1j}, \ldots, p_{mj}$ . For this, choose $f \in S$ such that $f(0,0) = s$ . For each $j \in \{1,\ldots, n\}$ , let $f_j(X) = f(X, d_j)$ . For each $j \in \{1,\ldots, n\}$ and each $i \in \{1,\ldots, m\}$ , let $s_{ij} = f_j(c_i) = f(c_i,d_j)$ . Issue $s_{ij}$ as the share to person $P_{ij}$ .

The shares $s_{ij}$ are the shares in a normal Shamir Secret Sharing Scheme for $f_j(0)$ . By the linear isomorphism in the first example above, when $t$ people in the team cooperate to learn $f_j(0)$ , they in fact learn $f_j$ itself. Suppose that $u$ teams learn $f_{b_1}, \ldots, f_{b_u}$ . Then since $\mathrm{deg}_Y f < u$ , they can cooperate to learn $f$ , and hence $f(0,0)$ . Given a $(u-1)$ -subset $B$ of $\{1,\ldots, n\}$ , when the teams numbered in $B$ pool their shares they learn nothing useful, since for each $h^\star \in \mathbb{F}[X]$ , there is a unique polynomial $f^\star$ with $\mathrm{deg}_Y < u$ such that $f(X, 0) = h^\star(X)$ and $f(X, d_j) = f_j(X)$ for each $j \in B$ . Explicitly,

$\displaystyle f^\star = h^\star(X) \prod_{j \in B} \frac{Y-d_k}{-d_k}+ \sum_{j \in B}Y \prod_{k \in B \atop k \not=j}\frac{Y-d_k}{d_j-d_k} f_j(X).$

This polynomial is consistent with the secret being $h^\star (0)$ ; since $h^\star(0)$ takes each value in $\mathbb{F}_p$ equally often as $h^\star(X)$ varies over the polynomials in $\mathbb{F}_p[X]$ of degree at most $t-1$ no useful information is learned.

It should be admitted that one can arrive at essentially the same situation, more simply, by sharing the secret between $n$ teams, and then sharing each 'team-share' between the $m$ people in each team, each time using the normal Shamir Scheme.