Cryptography Reference
In-Depth Information
In 1979, Adi Shamir developed and proposed a perfect
k
-out-of-
n
secret
sharing system based on polynomial interpolation [4]. The scheme employs the fact
that that a polynomial
f
(
x
) of degree
k
1 (over a field) can be uniquely interpolated
from
k
points. This means that a polynomial of degree 1 can be interpolated from 2
points, a polynomial of degree 2 can be interpolated from 3 points, and so on. The
corresponding interpolation algorithm has been around for a long time. It is usually
attributed to Lagrange. Let
−
k−
1
f
(
x
)=
r
0
+
r
1
x
+
...
+
r
k−
1
x
k−
1
=
r
i
x
i
(19.1)
i
=0
be a polynomial of degree
k
−
1 that passes through the
k
points
(
x
1
,f
(
x
1
)=
y
1
)
(
x
2
,f
(
x
2
)=
y
2
)
...
(
x
k
,f
(
x
k
)=
y
k
)
.
The Lagrange interpolating polynomial
P
(
x
) is then given by
k
P
(
x
)=
P
i
(
x
)
,
i
=1
where
k
x
−
x
j
P
i
(
x
)=
y
i
x
j
.
x
i
−
j
=1;
j
=
i
Written explicitly,
P
(
x
)=
P
1
(
x
)+
P
2
(
x
)+
...
+
P
k
(
x
)
(
x
−
x
2
)(
x
−
x
3
)
···
(
x
−
x
k
)
=
y
1
(
x
1
−
x
2
)(
x
1
−
x
3
)
···
(
x
1
−
x
k
)
