# Secret sharing

Problem:

* $$n$$ persons want to share a secret.
* **Any** group of $$t$$ persons can recover the secret.
* Obviously, $$n \ge 1$$ and $$1 \le t \le n$$.
* On a computer program, the secret will ultimately be an integer.

How to do it:

* A trusted central entity prepares and distributes part of the secret (a secret share) to each person.

Hurdles to overcome:

* Knowing $$t - 1$$ shares of the secret **must** not give **any** information about the secret.

Resilience to tampering:

* To destroy the secret $$n - t + 1$$ secret shares have to be corrupted.

## Idea 1 - n = t

Let the secret be the integer $$S$$, and let it have $$k$$ bits.

Let the first $$n-1$$ shares of the secret, $$s_1$$to $$s_{n-1}$$, be random integers with $$k$$ bits.

Let the last share of the secret be the exclusive-or of the secret with all the other shares of the secret ($$\oplus$$donates here the bit-wise exclusive-or binar operator)

$$s_n = S \oplus s_1 \oplus s_2 \oplus ... \oplus s_{n-1}$$

To recover the secret it is only necessary to perform an exclusive-or of all secret shares.

$$s_n = s_1 \oplus s_2 \oplus ... \oplus s_{n}$$

Knowledge of $$n-1$$ secret shares does not give any information about the secret.

It is possible to replace the bit-wise exclusive-or operations with additions and subtractions modulo $$m$$. In this case, the first $$n-1$$ secret shares are random integers from 0 to $$m-1$$, and the last secret share is $$(S-s_1-s_2-...-s_{n-1})mod m$$. To recover the secret it is only necessary to add all secret shares (modulo $$m$$, of course). If $$m$$ is a prime number, we can replace addition by multiplication.

## Idea 2

Blakley's secret sharing scheme:

* The secret is a point a $$P$$ in a $$t$$-dimensional space.
* Each share of the secret is a linear equation (with $$t$$ unkowns) that has $$P$$ has one of its solutions.
* Putting together $$t$$ equations allows us to find $$P$$.
* It is necessary to ensure that the system of equations has a unique solution for all possible $$C^n_t= \frac{n!}{t!(n-t)!}$$ possible combinations of $$t$$ equations chosen from the $$n$$ equations, and that is cumbersome.
* Each share of the secret is composed by $$t + 1$$ numbers.
* Improved security: the secret is kept **only** in one of the coordinates of the point $$P$$.
* Modular arithmetic should be used.

## Idea 3

Shamir’s secret sharing scheme:

* The secret in the independent coefficient $$a_0$$ of a polynomial of degree $$t − 1$$,
* $$A(x) = \sum^{t-1}_{k=0}= a_kx^k$$
* Each secret share in the pair $$(x_k, A(x-k))$$.
* Again, modular arithmetic should be used.
* Each share of the secret is composed by only 2 numbers.

Things to think about:

* Can we do it using square matrices for the $$a^k$$ coefficients?
* And how about for the ak coefficients and the $$x_k$$ values?

## Polynomial Interpolation

Given points $$(x_k,y_k)$$, for $$k = 0, 1, ... , n$$, with $$x_i \ne x_j$$ for $$i \ne j$$ , compute the unique polynomial of degree $$n$$ that passes through these points.

* Newton’s interpolation formula:
  * $$P_0(x) = y_0$$, and for $$k = 1, 2, ..., n$$

<figure><img src="https://3450804385-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FRIg06sTkCh60KyuJiT39%2Fuploads%2F6pG6GYM57welPq82haAt%2FScreenshot%20from%202023-12-29%2017-39-09.png?alt=media&#x26;token=e0802a75-c371-4d4f-b8f5-ec2c05d67f09" alt=""><figcaption></figcaption></figure>

* Lagrange’s interpolation formula:

<figure><img src="https://3450804385-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FRIg06sTkCh60KyuJiT39%2Fuploads%2F8xMngRJzepi5Fi120yLr%2FScreenshot%20from%202023-12-29%2017-39-09.png?alt=media&#x26;token=c7d666f2-f423-454d-8913-8ae2ab7033f6" alt=""><figcaption></figcaption></figure>

If arithmetic modulo $$p$$ is used we must have $$x_i \ne x_j (mod p)$$ for $$i \ne j$$ . If so, all modular inverses needed by Newton’s or Lagrange’s interpolation formulas exist.
