Shamir's Secret Shring

Introduction:
In the year 1979, an article appeared in the 22nd volume and 11th issue of the journal “Communications of ACM”. The article was written by a person called Adi Shamir from Massachusetts Institute of Technology. The article was called “How to share a secret?”. The article spoke about a secret sharing scheme which divided the secret into parts and distributes these parts to the secret-keepers.
Over the years, this scheme has been the focal point of many cryptographic techniques. Also, many new schemes have been developed based on this idea. This scheme is particularly fascinating because, it opens up a whole new realm of computational hardness problems (such as the RSA encryption scheme).
General idea of Shamir’s secret sharing!
Data security is one of the most important and essential fields today. Why is data security necessary?
Consider this example.
There is a strong room of a bank. It should have some security. Consider that the bank has three managers. The lock of the strong room must be designed such that if any two of the three managers come they must be in a position to open the room.  Here the idea is that the security is more when two keys are required to open the lock rather than just one key.
                                             
What are the possible combinations in which the managers open the room or in other words how many different doors are required for the strong room? There are 3 managers and any two can open the door. Hence there are 3 choose 2 possibilities32. If the number of managers is less then this method can be easily implemented.
In the original article the author used the analogy of 11 scientists working on a science project. They are faced with the problem of placing their findings in a secret cabin. The scheme is such that 6 or more scientists should be able to open the cabin at any given time. It is not hard to show that the minimal solution involves 462 locks and 252 keys per scientist. These numbers are clearly impractical as far as implementation is concerned. What is more intriguing and impossible is that these numbers become exponentially large as the number of participants increases.
Secret sharing principle:

• Let the number of people be n.
• Let the number of people required to open the door be k.
• The idea is to choose a polynomial whose degree is k-1.
• The roots of the equation are distributed as the keys.
• The polynomial is calculated to open the door.
• n keys are generated for the polynomial. Each of the keys is a point on the polynomial.
• For example, consider a straight line ax+b=c . Two points are enough to find the equation of the straight line. However, any point on the straight line can be distributed as a key.
• Generalizing the idea for a k th degree polynomial k keys are sufficient to obtain the polynomial. But any n points on the polynomial can be distributed as keys.
• Lagrange’s interpolation method is used to obtain the polynomial initially.

Mathematical Representation:   
  Formally our goal is to divide D( the secret) into n pieces say D1, D2, D3……….,Dn in such a way that :

1. Knowledge of any k or more Di pieces make D easily computable.
2. Knowledge of any (k-1)  or fewer Di pieces leaves D undetermined.

This scheme is called (k,n) threshold scheme.

Mathematical Representation:   
  Formally our goal is to divide D( the secret) into n pieces say D1, D2, D3……….,Dn in such a way that :

1. Knowledge of any k or more Di pieces make D easily computable.
2. Knowledge of any (k-1)  or fewer Di pieces leaves D undetermined.

This scheme is called (k,n) threshold scheme.

the idea of this secret sharing scheme is that, 2 points are sufficient to define a straight line, 3 points are sufficient for a parabola, 4 points for cubic circle etc…….
That is, it takes k points to define a polynomial of degree (k-1). Say, F is a finite field and say a0,a1,a2,……ak-1are coefficients.
f(x)=a0+a1x+a2x2+……………….ak-1xk-1
Let us construct any n points out of the function f(x). For instance, i=1……..n  to retrieve (i, f(i) ). Every participant is given a point (a pair of input to the polynomial and output). Given any subset of k points, the coefficients of the polynomial can be calculated using interpolation. The secret is the constant term a0.

Shamir’s secret sharing scheme provides are very secure, dynamic, and extensible scheme. Participants can be added or deleted whenever necessary. Thus this secret sharing method is one of the most robust and secure methods available for situations involving many participants and one secret!!