Shamir's secret sharing scheme
Shamir's secret sharing is a threshold secret sharing
scheme invented by Adi Shamir in his paper "How to share a secret" in
1979. In this scheme, a secret S is divided into n pieces in such a way that S
is easily reconstructed from any k pieces (k < n) but even complete
knowledge of k - 1 pieces reveals absolutely no information about S. Shamir
secret sharing scheme is used in ad-hoc networks where there is no centralized
infrastructure to distribute a Certificate Authority into several secured nodes
in the network. This non-centralized approach have the advantages that there is
no single point of security compromise and increase the virtual Certificate
Authority's availability.
In this post I will explain how Shamir's
secret sharing works and how to apply it into mobile ad-hoc network to form a
virtual Certificate Authority.
Definition
The goal is to divide
secret S into n pieces S1, S2, ... in such a way that:
- Knowing any k or more Si pieces can easily reconstruct the secret S.
- Knowing less than k pieces Si will not able to reconstruct the secret S.
This scheme is called
(k, n ) threshold secret sharing scheme. if k = n, then every pieces of Si
are required to reconstruct S.
Shamir secret sharing
The essential idea of Shamir
secret sharing are from below comments:
- Given f(x) = ax + b
- Knowing more than 2 points on the graph of the function f(x) will reveal f(x) therefore reveal f(0)
- Knowing less than 2 points on the group of the function f(x) will not reveal f(x) therefore not reveal f(0)
- Given f(x) = ax2 + bx + c
- Knowing more than 3 points on the graph of the function f(x) will reveal f(0)
- Knowing less than 3 points on the group of the function f(x) will not reveal f(0)
…
- Given f(x) = ak-1xk-1 + … + a2x2 + a1x + a0
- Knowing more than k points on the graph of the function f(x) will reveal f(0)
- Knowing less than k points on the group of the function f(x) will not reveal f(0)
From above comments,
if S is f(0) we can divide S into n pieces by calculating n points on the graph
of the function f(x). Each point is a sharing piece Si
Knowing more than k
points will reveal S but knowing less than k point will not reveal S.
Example of Shamir's secret sharing
Suppose we have a secret S = 6 and
want to divide the secret into 6 parts (n = 6) where any 3 parts can easily
reconstruct the secret (k = 3)
Division process
Since the threshold is k = 3, we will
generate a function f(x) = a0 + a1x + a2x2
which f(0) = S
Therefore, a0 = S and at
random we obtain a1 = 166, a2 = 94
Our
polynomial to produce secret shares (points) is therefore:
f(x) = 1234 + 166x + 94x2
In order to have 6 parts of
the secret, we calculate 6 points on the graph of the function f(x).
D0 = (1, 1494)
D1 = (2, 1942)
D2 = (3, 2578)
D3 = (4, 3402)
D4 = (5, 4414)
D5 = (6, 5614)
D1 = (2, 1942)
D2 = (3, 2578)
D3 = (4, 3402)
D4 = (5, 4414)
D5 = (6, 5614)
Each point is a sharing
secret
Reconstruction process
In order to reconstruct
the secret any 3 points will be enough.
Let us consider (x0, y0) = (2, 1942), (x1, y1)
= (4, 3402), (x2, y2) = (5, 4414)
We will compute Lagrange
basic polynomials:
How to apply it to form a virtual Certificate Authority
By using Shamir’s
secret sharing, the system secret or private key of the Certificate Authority
is divided into n parts such that any k parts can perform as a Certificate
Authority. Each part is given to a node in the network. The term server is
used to refer to a node which keeps a part of a secret to participate in
forming the virtual Certificate Authority. A server’s properties can be
summarized as below:
- A server can be initialized securely with its share of the secret which allows it to act as a server.
- A server knows the public keys of all nodes in the network including ones will join the network after initiation.
Now consider an
example when A need to find out the public key of B.
A
sends out a broadcast message to its neighbors requesting a certificate for B.
- Each server which hears this message generates a partial certificate with its partial system
- secret and sends it to a combiner.
- A combiner combine partial certificates and generates a complete certificate and send to A.
