Shamir Secret Share Intros

Shamir Secret Sharing (SSS) is a cryptographic protocol that enables the secure sharing of a secret among a group of participants. It was introduced in 1979 by Adi Shamir, who is credited with its invention. The protocol works by splitting the secret into a number of pieces, each of which is shared among the participants. To reconstruct the original secret, a certain number of participants must share their pieces.

The protocol is based on the mathematical concept of polynomial interpolation. It involves generating a polynomial of a certain degree from a set of given points, which can be used to reconstruct the secret. The protocol is secure as long as the minimum number of required shares is not exceeded, as it would enable an attacker to reconstruct the secret.

Lagrangian interpolation

The point of interpolation is to fit to find the missing points.

The solution is given directly here, the details of which will be covered in a separate article, together with the various interpolation methods.

For a given polynomial function, it is known that there are a given j+1 points, i.e. $(x_0, f(x_0)), ..., (x_j , f(x_j))$

Suppose that any two different xk are not identical to each other, then this polynomial is

$y(x)= \sum _ {k=0}^ {N} l_ {k} (x)f( x_ {k} )$

where each $l_j(x)$ is a Lagrangian fundamental polynomial (or interpolating basis function, as it is called) with the expression:

$l_ {k} (x) \triangleq \frac {(x-x_ {0})\cdots (x-x_ {k-1})(x-x_ {k+1})\cdots (x-x_ {N})}{(x_ {k}-x_ {0})\cdots (x_ {k}-x_ {k-1})(x_ {k}-x_ {k+1})\cdots (x_ {k}-x_ {N})}$

Thresholding Mechanisms

In reality, effective thresholding mechanisms play a key role in the application of key management. Let's take a scenario where a secret is locked in a box and there are 5 people involved. The answer is 10 locks and 6 keys. But if the number of people is increased to 11 and the minimum number of people required to open the box is 6, then the number of locks and keys increases to 462 and 252 respectively. Abstracted to N people, the number of locks is C(N, N/2) and the number of keys is C(N-1, N/2). As the number of people increases, the number of locks and keys will increase exponentially, which will also greatly increase the burden on resources.

We abstract a realistic problem into some data D. Our goal is to partition D into n copies, i.e. D1, D2, ... Dn, satisfying

1. any k or more copies of Di can be easily computed as D

2. any k-1 or fewer copies of Di cannot compute D exactly (all possible values are equal).

Such a mechanism is called a (k, n) threshold mechanism.

Shamir Threshold Scheme

First, we know that in a plane, two points define a line and three points define a 2nd order equation, so we can introduce that given K different points, there is only one K-1th order polynomial q(x) such that q(xi) = yi for all i. We can then, as before, divide D into Di and choose a random k-1th order polynomial as follows.

$q(x)=a_{0}+a_{1} x+\ldots a_{k-1} x^{k-1}$

The advantages of this (k,n) thresholding mechanism are that

1. the size of each piece of information does not exceed the original data

2. if the value of k is fixed, Di can be dynamically added or removed without affecting other pieces of information

3. the pieces of information in Di can be easily changed without changing the original data D. All we need to do is ensure that the pieces can eventually form a polynomial with constant free terms. This variable nature also improves security.

4. We can also use the coefficients of the polynomial as a hierarchical mechanism, with the number of pieces of Di depending on their importance. For example, if we give the chairman of a company 3 values of q(x), each vice-chairman 2 values, and each executive 1 value, then the (3, n) threshold mechanism for checking signatures requires any three executives, or any two executives, one of whom is the vice-chairman, or the chairman himself.

Outros

SSS has a number of applications, including key distribution in distributed systems, secure data transmission, and secure storage. It can also be used to share digital assets or credentials, such as passwords and cryptographic keys. Additionally, it can be used to implement access control mechanisms, such as multi-factor authentication.