> For the complete documentation index, see [llms.txt](https://davidjosearaujo.gitbook.io/notes-mcs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://davidjosearaujo.gitbook.io/notes-mcs/applied-cryptography/rsa-and-related-subjects/secret-sharing.md).
# 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$$
* Lagrange’s interpolation formula:
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.
