Shamir's secret sharing scheme

Shamir's secret sharing scheme

  5:54 AM    Unknown

---

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 S₁, S₂, ... in such a way that:

• Knowing any k or more S_i 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 S_i 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) = ax² + 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) = a_k-1x^k-1 + … + a₂x² +  a₁x + a₀
• 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 S_i

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) = a₀ + a₁x + a₂x² which f(0) = S

Therefore, a₀ = S and at random we obtain a₁ = 166, a₂ = 94

Our polynomial to produce secret shares (points) is therefore:

f(x) = 1234 + 166x + 94x²

In order to have 6 parts of the secret, we calculate 6 points on the graph of the function f(x).

D₀ = (1, 1494)
D₁ = (2, 1942)
D₂ = (3, 2578)
D₃ = (4, 3402)
D₄ = (5, 4414)
D₅ = (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 (x₀, y₀) = (2, 1942), (x₁, y₁) = (4, 3402), (x₂, y₂) = (5, 4414)

We will compute Lagrange basic polynomials:

Secret S is the free coefficient, which means S = 1234

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:

1. A server can be initialized securely with its share of the secret which allows it to act as a server.
2. 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.

1. Each server which hears this message generates a partial certificate with its partial system
2. secret and sends it to a combiner.
3. A combiner combine partial certificates and generates a complete certificate and send to A. 

A combiner is just a server which takes on the responsibility of combining S partial certificates and generates a complete certificate. Any server can take on the role of a combiner. A server does not require any extra capabilities to be a combiner. Conversely, a server does not gain any extra information about the system secret by being a combiner