We continue our series on polynomial secret sharing. In the previous post of this series we discussed secret sharing with a passive adversary. In this post we assume **crash failures** and in later posts we will extend to malicious failures. As before, we must assume parties have **private channels**: the adversary cannot see the content of messages sent between two non-faulty parties.

### What is a Secret Sharing scheme?

An *secret sharing scheme* is composed of two protocols: *Share* and *Reconstruct*. These protocols are run by the $n$ parties. The dealer has a *secret* $s$ in a commonly known finite field $\mathbb{F}_p$ with $p>n$, which is given as *input* to the Share protocol. The two properties are:

**Validity**: If the share protocol completes, the output of the Reconstruct protocol is the dealerâ€™s input value $s$.**Hiding**: If no honest party has begun the Reconstruct protocol, then the adversary can gain no information about $s$.

In later posts we will address the malicious dealer case which will introduce the third property: **Binding**.

We also need termination properties:

**Weak Termination of Share**: if the dealer is non-faulty then all non-faulty parties complete the Share protocol. In some cases a stronger property is needed:**Strong Termination of Share**: if non-faulty completes the Share protocol then all non-faulty parties complete the Share protocol.**Termination of Reconstruct**: if all non-faulty parties complete the share protocol then all non-faulty parties complete the Reconstruct protocol.

See the last section of this post for a discussion on the strong termination property.

### The main idea

TL;DR: **For an adversary controlling $f$ parties, use a degree $f$ polynomial and $n>2f$.**

Parties are enumerated $N={1,2,3,\dots,n}$. Given input $s \in \mathbb{F}_p$, the dealer chooses a uniformly random polynomial $p(x)$, conditioned on $p(0)=s$. The dealer then gives party $i$ the value $p(i)$ which we call its *share*.

The adversary controls $f$ parties, hence gets to see $f$ shares and can also crash these parties. So what degree should $p(x)$ be? and how many parties do we need to tolerate $f$ crash failures?

- For
**Hiding**to hold, we need to share using a polynomial of degree $\geq f$ (otherwise the adversary can learn the secret during the Share protocol simply by interpolating its shares). - Since at least $f+1$ shares are required for unique reconstruction (for a polynomial of degree $\geq f$) and $f$ parties may crash, then we need $n \geq 2f+1$ for
**Validity**.

Hence we choose $p(x)$ from all polynomials of degree at most $f$ and choose $n=2f+1$.

### The Secret Sharing protocol

**Share protocol**:
Given a secret $s$ as input, the dealer *randomly* chooses $f$ values $p_1,\dots,p_{f} \in_R \mathbb{F}_p$ and defines a degree $\le f$ polynomial:

The dealer then sends $p(i)$ to party $i$, for each $i \in N$.

**Reconstruct protocol**:
Each party $i$ sends its share $p(i)$ to all other parties.
Each party receives at least $n-f$ shares. Let $I$ be the subset of the first $f+1$ parties whose shares are received. Note that at most $f$ parties may crash, so at least $n-f \geq f+1$ shares will arrive (here we use $n>2f$).

Each party outputs the dealerâ€™s original secret $s$ as follows:

\[s=p(0)=\sum_{i \in I} \lambda_i p(i)\]Here, $p(i)$ is the share sent by party $i \in I$ and $\lambda_i$ are the Lagrange interpolation coefficients:

\[\lambda_i = \frac{\prod_{j \in I \setminus \{i\}} j}{\prod_{j \in I \setminus \{i\}} (j-i)}\]### Proof of Validity, Hiding, and Weak Termination

Validity follows from the one-to-one mapping of degree at most $f$ polynomials and any $f+1$ shares.

Similarly, Hiding follows since, for any $s$, conditioned on $p(0)=s$, the one-to-one mapping of degree at most $f$ polynomials to any $f$ shares (held by the adversary) implies that the uniform distribution on the coefficients $p_1,\dots,p_f$ induce a uniform distribution on the adversary view. The adversary view is therefore independently and uniformly random, for any value $s$. You can find a more detailed proof in our previous post.

Weak Termination follows since the share is non-blocking and the reconstruct only needs $n-f \geq f+1$ shares.

### Note on strong termination of the share protocol

As written, the dealer may crash in the middle of sending shares and parties have no way of knowing if all non-faulty parties received their phase. So parties need to **reach agreement** on whether the dealer completed or not. In particular all the lower bounds on agreement must hold.

One way to handle this is to abstract it away :-). Simply assume parties have access to **broadcast channel**. So the dealer, after sending all the shares, simply broadcasts `OK`

. If parties dont hear an OK, they know the dealer crashed and use 0 as the reconstruct value.

In this model, the share protocol requires $O(n)$ words to be sent on private channels and $O(1)$ words of broadcast. The reconstruct protocol requires $O(n^2)$ words on private channels.

Comments on Twitter.