Author: Adi Shamir
Note: This note is augmented with paragraphs from Wikipedia.
npieces in such a way that
Dis easily reconstructable from any
kpieces, but even complete knowledge of
k - 1pieces reveals absolutely no information about
D(i.e: all its possible values are equally likely).
(k, n)threshold scheme.
By using a
(k, n)threshold scheme with
n = 2k - 1we get a very robust key management scheme: We can recover the original key even when
[n / 2] = k - 1of the
npieces are destroyed, but our opponents cannot reconstruct the key even when security breaches expose
[n / 2] = k - 1of the remaining
n / 2) pieces are destroyed, the remaining 3 (
k) pieces can be used to recover the key.
n / 2) pieces are exposed, the opponent can’t reconstruct the key.
kpoints in the 2-dimensional plane (
y₁), … ,(
yₖ) with distinct
xᵢ's , there is one and only one polynomial
k - 1such that
q(x) =yᵢfor all
The essential idea of the scheme is based on the Lagrange interpolation theorem , specifically that
kpoints is enough to uniquely determine a polynomial of degree less than or equal to
k − 1. For instance:
1* `2` [points](https://en.m.wikipedia.org/wiki/Point_(geometry)) are sufficient to define a [line](https://en.m.wikipedia.org/wiki/Line_(geometry))2* `3` points are sufficient to define a [parabola](https://en.m.wikipedia.org/wiki/Parabola)3* `4` points to define a [cubic curve](https://en.m.wikipedia.org/wiki/Cubic_function) and4* so forth. — [Wikipedia](https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing)
Dis (or can be made) a number.
k - 1degree polynomial:
q(x) = a₀ + a₁x + ... aₖ₋₁ xᵏ⁻¹in which
D₁= q(1), … ,
Dᵢ= q(i), … ,
Dₙ = q(n).
Dᵢvalues (together with their identifying indices), the coefficients of
q(x)can be found by interpolation, and then evaluate
D = q(O). Knowledge of just
k - 1of these values, on the other hand, does not suffice in order to calculate
D = 1234
n = 6
k = 3
k - 1 = 2numbers are taken at random. Let them be
a₀ = 1234(i.e: the secret)
a₁ = 166
a₂ = 94
q(x) = 1234 + 166x + 94x².
nparticipant in the scheme receives a different point from the polynomial:
Although the simplified version of the method demonstrated above, which uses integer arithmetic rather than finite field arithmetic, works, there is a security problem: An attacker gains information about D with every
p ∈ ℙ : p > D, p > nis used.
pmust be chosen that is bigger than the number of participants and every
a₀ = D).
(x, q(x) mod p)instead of
pis publicly known: Everybody who receives a point must also know its value.