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.