# Secret Sharing Schemes

**Questions to Answer**

- What are Secret Sharing Schemes?
- Why do we need them?
- What are Access Structures?
- How do we define/represent them?
- What types of SSSs are there?
- How can we construct these different LSSS schemes?

## Table of Contents

## 1 Overview

There are times when access to a secret needs to be restricted such that when a pre-defined number of people are present, the secret can be accessed. For example:

- Launch Codes for Nukes
- The recipie for Coca-Cola
- Numbered Bank Account
- Root Login to a Server

*Secret Sharing Schemes* (SSSs) are a tool that provides such access
control. SSSs are used to split the secret value into *shares* that
are then distributed to the concerned parties. It is only when the
concerned parties are together that the secret can be reconstructed.

## 2 Definitions

### 2.1 Secret Sharing Scheme

Given a secret value \(s\) and a set of participants \(\mathcal{P}=\{P_{1},\ldots,P_{l}\}, l > 1\), a SSS \(\Pi\) consists of two algorithms:

- Distribute
- The distribution algorithm takes the secret \(s\) and splits \(s\) into \(P\) shares with each \(P_{i}\) recieving a share \(s_{i}\).
- Reconstruct
- The reconstruction algorithm collects each share \(s_{i}\) from each \(P_{i}\) and uses the shares to reconstruct the secret \(s\).

### 2.2 Threshold Secret Sharing Scheme

A problem with the previous definition of a SSS is that it requires that all participants be available so that *s* can be reconstructed. Threshold SSS are schemes that allows for a qurom of participants to be specified.

Given a secret value *s* and a set of participants
\(\mathcal{P}=\{P_{1},\ldots,P_{l}\}\) a \((t,l)\)-threshold scheme, where
\(1 <= t <= l\), is a method of dividing *s* into an array \(s_{i}\) of
shares such that:

- When given any set
*t*or more of \(s_{i}\), the secret value*s*can be reconstructed. - When given any set fewer than
*t*of \(s_{i}\), the secret value*s*can not be determined.

### 2.3 General Secret Sharing Schemes

With Threshold SSSs there is still the problem that given **any**
\(p\subset\mathcal{P}\) where \(\abs{p} >= t\) will cause the secret to be
reconstructed. A more **general**, fine-grained, means to specify the
distribution of *s* is needed. *General Secret Sharing Schemes*
(GSSSs) are SSSs that distributes the secret *s* among a predefined,
authorised, set of subsets of \(\mathcal{P}\), which is denoted
\(\mathcal{A}\). Such schemes have the advantage that a more precise
distribution of *s* can be specified.

### 2.4 Linear Secret Sharing Schemes

*Linear Secret Sharing Schemes* (LSSSs) are SSSs in which the
distribution and reconstruction of the secret *s* is from a linear
combination of shares.

## 3 Access Structures

First a definition for access structures is given, before two ways in which access structures can be specified are given.

### 3.1 Definition

Given \(\mathcal{P}=\{P_{1},\ldots,P_{l}\}\). Define the pair
\((\mathcal{A}, \mathcal{Z}), \mathcal{A}\cap\mathcal{Z}=\emptyset\)
where \(\mathcal{A}, \mathcal{Z}\subseteq 2^{\mathcal{P}}\). This pair
is called a **monotone access structure** on \(\mathcal{P}\) if:

That is \(\mathcal{A}\) is monotone: if \(X\in\mathcal{A}\) then
\(X\cup\{P_{i}\}\in\mathcal{A}\). The sets in \(\mathcal{A}\) are known as
the **authorised** sets, and the sets in \(\mathcal{Z}\) the
**unauthorised** sets.

### 3.2 Some Example Access Structures.

Let \(\mathcal{P} = \{A,B,C,D\}\). Then some example access structures for P are as follows:

- {{A,B,C},{A,D}}
- {{A,B},{A,C},{B,C}}
- {{A,B,D},{A,C,D},{B,C}}
- {{A,B},{B,C},{C,D}}
- {{A,B,C},{A,B,D}}

### 3.3 From Monotone Circuits

A natural means to specifiy an access structure is as a boolean
formula in *Disjunctive Normal Form* (DNF). Here the interior nodes
are either **AND**, or **OR** gates, and the leaf nodes are the
participants. Such circuits can be written either using:

- Binary Input Gates
- Where each node takes at most two children.
- Multi Input Gates
- Where each node takes many children.

As such standard logic notation can be used in lieu of set notation to denote access structures.

### 3.4 From Threshold Gates

Another way in which access structures can be represented is as a
series of threshold gates. That is, each interior node is a
\((t,l)\)-threshold gate, and the leaf nodes are participants. With
threshold gates one can simulate both **AND** and **OR** gates, as
follows:

Several notational styles exist for threshold operations. For
selecting **any** *t* elements from the set \(\{1,2,3,4\}\) the follwoing
notation can be used:

- \(t\quad\mathsf{of}\quad (1,2,3,4)\)
- \(T_{t}(1,2,3,4)\)

## 4 Shamir's Threshold Scheme

First secret sharing scheme, attributed to **Shamir1979**. Involves the
construction of a random polynomial of degree \(<t\) that evaluates to
the secret being shared when \(x=0\). Each participant is given a share
equated for them. **LaGrange Interpolation** is used to combine the
shares and extract the secret.

### 4.1 Distribution Algorithm

### 4.2 Reconstruction Algorithm

### 4.3 Alternate Views

Shamir's scheme can also be viewed from a linear algebraic view. Again
write \(a(x)=a_{0} + a_{1}x + \ldots + a_{t-1}x^{t-1}\), where
\(s=a_{0}\). When given any *t* shares \(s_{i_{i}},\ldots,s_{i_{t}}\), *s*
is determined by the following matrix equation:

The \(t\times t\) matrix is a *Vandermonde* matrix with determinant:
\(\prod_{1\geq j<k\geq t}(i_{k}-i_{j})\). Hence the equation has a
unique solution provided all i_{j}'s are distinct.

## 5 Brickell's Vector Space Construction

Brickell's *Vector Space* construction applies to a certain class of
access structure. When using this construction, a share generating
matrix must first be defined. This matrix is used to distributed the
secret according to a predefined distribution.

### 5.1 Share Generating Matrix

Given an access structure \(\mathcal{A}\), and a set of participants
\(\mathcal{P}=\{P_{1},\ldots,P_{l}\}\), the vector space construction
applies whenever it is possible to construct a *suitable* \(l\times m\)
matrix *M*, where *m* is to be determined. The Matrix *M* associated a
public vector of length *m* with each \(p\in\mathcal{P}\). The public
vector is linked to an access structure \(\mathcal{A}\) if given *any*
set \(x\subset\mathcal{A}\) the vector \((1,0,\ldots,0)\) is contained
within the *linear span* of \(M_{x}\). Here \((1,0,\ldots,0)\) is the unit
vector of length *m*, and \(M_{x}\) denotes the submatrix whose rows are
indexed by *x*.

### 5.2 Distribution Algorithm

### 5.3 Reconstruction Algorithm.

### 5.4 Example

Define \(\mathcal{A}= (1\land 2\land 3) \lor (1\land 4)\). A suitable matrix \(M\) is:

\[ \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & -1 \\ 1 & 1 & 0 \end{pmatrix} \]Each \(M_{i,j}\in\mathbb{F}_{q}\). When presented with both \(M_{\{1,2,3\}}\) or \(M_{\{1,4\}}\) both the linear spans will result in \((1,0,0)\). For example:

\begin{align*} (1,0,0) =&(1,0,1) + (0,1,-1) - (0,1,0) \\ (1,0,0) =&(1,1,0) - (0,1,0) \end{align*}Using \(M\) a secret value \(s\in\mathbb{F}_{q}\) can be shared as follows. First two random values \(r_{1}, r_{2}\in_{R}\mathbb{F}_{q}\) are chosen. The shares are constructed as follows, from matrix vector product:

- \(P_{1}\gets s_{1} = r_{1}\)
- \(P_{2}\gets s_{2} = s + r_{2}\)
- \(P_{3}\gets s_{3} = r_{1} - r_{2}\)
- \(P_{4}\gets s_{4} = s + r_{1}\)

## 6 Monotone Circuit Construction

The *Monotone Circuit* construction is attributed to Benaloh and
Leichter. This construction takes as input a boolean circuit. Working
backwards from the output to the input, the algorithm assigns shares
to the participants.

### 6.1 Distribution Algorithm

### 6.2 Reconstruction Algorithm

### 6.3 Example

- Given participants \(\mathcal{P}=\{P_{1}, P_{2}, P_{3}, P_{4}\}\)
- Let our access structure be \(\mathcal{A}=\{\{1,2,4\},\{1,3,4\},\{2,3\}\}\)

\(\mathcal{A}\) represents a monotone circuit comprising of three *AND*
gates with three and two inputs respectively, whose outputs are
combined using a three input *OR* gate. The secret \(s\) is distributed
as follows:

- Assign \(s\) to 'root'
*OR*gate. - For
*AND*gate with input \(\{1,2,4\}\):- Construct random values \(a_{1}, a_{2}\).
- \(P_{1}\gets a_{1}\)
- \(P_{2}\gets a_{2}\)
- \(P_{4}\gets s-a_{1}-a_{2}\).

- For
*AND*gate with input \(\{1,3,4\}\):- Construct random values \(b_{1}, b_{2}\).
- \(P_{1}\gets b_{1}\)
- \(P_{3}\gets b_{2}\)
- \(P_{4}\gets s-b_{1}-b_{2}\).

- For
*AND*gate with input \(\{2,3\}\)- Construct random value \(c_{1}\)
- \(P_{2}\gets c_{1}\)
- \(P_{3}\gets s-c_{1}\)

- Send following piece vectors to each \(P_{i}\):
- \(P_{1}: a_{1}, b_{1}\)
- \(P_{2}: a_{2}, c_{1}\)
- \(P_{3}: b_{2}, s-c_{1}\)
- \(P_{4}: s-a_{1}-a_{2}, s-b_{1}-b_{2}\)

## 7 Monotone Span Program Construction

Brickell's vector space construction will always result in a sharing
scheme in which each participant gets one share. However, not every
access structure allows for this. To combat this *Monotone Span Programs* (MSPs) can be used to describe a LSSS for **any** access
structure. This is a result of **Beimel1997**. Given the similarities
between the two constructions the secret sharing algorithms for MSPs
shall be omitted.

### 7.1 Definition of a Span Program

From **Karchmer1993**: Fix a field \(K\). A span program over \(K\) is a
labelled matrix \(\hat{M}(\mathcal{M},\rho)\) where \(\mathcal{M}\) is a
matrix over \(K\) and
\(\rho:rows(\mathcal{M})\rightarrow\{x_{i}^{\varepsilon}\mid
i\in[n],\varepsilon=0,1\}\). The size of \(\hat{M}\) is the number of
rows in \(\mathcal{M}\).

### 7.2 Definition of Monotone Span Program

Adapted from **Karchmer1993**: A span program
\(\hat{M}(\mathcal{M},\rho)\) is called monotone, if the image of \(\rho\)
is only the positive literals \(\{x_1,\ldots,x_n\}\). Such span programs
can also compute monotone functions.