Secret Sharing Schemes

Questions to Answer

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:

The distribution algorithm takes the secret \(s\) and splits \(s\) into \(P\) shares with each \(P_{i}\) recieving a share \(s_{i}\).
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:

  1. When given any set t or more of \(s_{i}\), the secret value s can be reconstructed.
  2. 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:

\begin{align*} X\in\mathcal{A}, X\subseteq Y&\implies Y\in\mathcal{A}\\ B\in\mathcal{Z}, X\subseteq Y&\implies A\in\mathcal{Z} \end{align*}

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:

  1. {{A,B,C},{A,D}}
  2. {{A,B},{A,C},{B,C}}
  3. {{A,B,D},{A,C,D},{B,C}}
  4. {{A,B},{B,C},{C,D}}
  5. {{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:

\begin{equation*} t= \begin{cases} 1 & \text{Node is OR-Gate} \\ [1,t] & \text{Node is a Threshold-Gate} \\ l & \text{Node is a AND-Gate} \end{cases} \end{equation*}

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:

  1. \(t\quad\mathsf{of}\quad (1,2,3,4)\)
  2. \(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:

\begin{equation*} \begin{pmatrix} 1 & i_{i} & i_{1}^{2} & \cdots & i_{1}^{t-1} \\ \vdots & \vdots & \vdots & & \vdots \\ 1 & i_{t} & i_{t}^{2} & \cdots & i_{t}^{t-1} \end{pmatrix} \begin{pmatrix} a_{0}\\ \vdots\\ a_{t-1} \end{pmatrix} = \begin{pmatrix} s_{i_{1}}\\ \vdots\\ s_{i_{t}} \end{pmatrix} \end{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 ij'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:

  1. Assign \(s\) to 'root' OR gate.
  2. For AND gate with input \(\{1,2,4\}\):
    1. Construct random values \(a_{1}, a_{2}\).
    2. \(P_{1}\gets a_{1}\)
    3. \(P_{2}\gets a_{2}\)
    4. \(P_{4}\gets s-a_{1}-a_{2}\).
  3. For AND gate with input \(\{1,3,4\}\):
    1. Construct random values \(b_{1}, b_{2}\).
    2. \(P_{1}\gets b_{1}\)
    3. \(P_{3}\gets b_{2}\)
    4. \(P_{4}\gets s-b_{1}-b_{2}\).
  4. For AND gate with input \(\{2,3\}\)
    1. Construct random value \(c_{1}\)
    2. \(P_{2}\gets c_{1}\)
    3. \(P_{3}\gets s-c_{1}\)
  5. 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.

8 References

Date: 2012-03-13 10:51:58 GMT

Author: Jan de Muijnck-Hughes

Org version 7.8.03 with Emacs version 24

Validate XHTML 1.0