Shamir’s Secret Sharing Scheme is a method used to prevent information from being accessed without the knowledge and consent of a specified number of people. The idea is several people have part of the key needed to reveal the secret but it can’t be accessed by just one person. Often this concept is represented in movies where the codes for a weapon have to be input by three people with high profile positions.
Generating shadows
A “shadow” is part of the key necessary to find the secret. Shamir’s Secret Sharing Scheme can divide the key so that n number of people have a shadow, and k number of shadows are required to find the secret. The shadow is a point on the line which conceals the secret.
In a (2, 3) scheme, there are 3 shadows, 2 are necessary to decipher the secret.
In a (3, 7) scheme, there are 7 shadows and 3 are necessary to decipher the secret.
A polynomial is used where the highest power of x is (k - 1).
If k = 2, y = mx + c
If k = 3, y = ax2 + bx + c
If k = 4, y = ax3 + bx2 + cx + d
The secret K is always the intercept, the number which is not multiplied by x.
A modulus is also necessary for the scheme to be secure, a large prime p.
For example, K = 13 and a (2, 3) scheme is specified.
The polynomial necessary would be y = mx + 13
In this example we will use m = 2 and modulus p = 17
Each of the three entities must have a generated shadow denoted as e
x.
e1 chooses x = 5, and calculates y = 2(5) + 13 = 23 (mod 19) = 4
e2 chooses x = 2, and calculates y = 2(2) + 13 = 17 (mod 17) = 17
e3 chooses x = 8, and calculates y = 2(8) + 13 = 29 (mod 19) = 10
Therefore the shadows are e
1(5, 4), e
2(2, 17) and e
3(8, 10)
Finding the Secret
Continuing from the previous example, two shadows are needed to find the secret. We will use (5, 4) and (8, 10).
As we know two shadows are needed, the polynomial must be in the form of y = mx + c. Therefore we can substitute each point into the equation.
Using (5, 4), 4 = 5m + c
Using (8, 10), 10 = 8m + c
The intercept c can be found using the following formula:
c = {y
1 - x
1[(y2 - y
1)) / (x
2 - x
1)]} mod p
c = 4 - 5[(10 - 4) / (8 - 5)]
= 4 - 5[6 / 3]
= -6 mod 19
= 13
The methods change depending on how many shadows are required. If you want to know more about the method for 3 shadows, look into Cramer’s Rule.
Written by Chelsea
