In this blog article I will show the different types of secret sharing methods especially the common used Shamires secret sharing method. Thereafter I will explain the mathematical background of this procedure.
What is Secret Sharing about?
Let’s start with the following situation. A big heritage should be distributed over 6 heirs. The heritage is stored in a safe with a password. To avoid that only one person opens the safe and takes all the money a so called dealer splits the password into six parts (keys) and gives every part (key) to one of the six heirs (so called players). He also gives them a set of rules on how to recombine these pieces together to reconstitute the former password so that they can open the safe.
“Secret sharing” or secret splitting describes the methodology of distributing secret information among a group of participants in a way that a subset of this group is needed to reconstruct the secret. Whereby a single piece of information cannot be used to reconstruct the secret.
Secret sharing has a wide operation range. It can be used in high security areas for validation reasons e.g. in the military or in the banking area where it might be necessary to have a 4, 6 or 8 eye validation principle. It also can be used to ensure the secure transport of information e.g. transport of a cryptographic key over several channels. Last but not least it can be used in secure access regulation where only a combination of trustworthy people might get access to a secure area.
Different types of secret sharing methods
You can distinguish between two types of secret sharing methods. The ones which needs the partial information of all players to reconstruct the secret called (n,n) schemes (pronounced N out of N scheme). The others need only a sufficient amount of partial information called (k,n) threshold scheme (pronounced K out of N threshold scheme).
(n,n) schemes
The trivial way to share some information (e.g. password) amongst a group of participants is to divide the information into pieces and give every piece to a participant. Like in the following example where each colored number is a piece of the whole.
123 456 789 = 123456789
Other (n,n) schemes include more complex processing than just appending the information pieces. E.g. the concatenation of keys with an xor operator
123 xor 456 xor 789 = 678
These approaches have the same disadvantage they each need all keys to reconstruct the secret. In case one of the keys is lost the secret is lost as well (at least theoretically; depending on the approach it may just need some computational effort to calculate the missing key[1]). Additionally (n,n) schemes are not flexible for key expansion. If further keys are needed all keys have to be recomputed.
(K ,N) threshold schemes
In contrast to the before discussed (n,n) schemes (k,n) threshold schemes are flexible in terms of participant expansion. It is easy to add a new key to the set of the existing keys without recalculating them.
The simple methods are based on reflection about geometrical primitives crossing each other in one point (the secret). E.g. (2,n) threshold scheme: at least two lines in a Euclidean two dimensional space cross each other at one specific point. It is also easy to find another line which cross the crossing point of the first two at the same point.
On the one hand it is easy to get a (k,n) threshold scheme by extending the former method in dimensionality of the space, by k dimensions e.g. (3, n) would be the computation of the intersection point between 3 planes in 3 dimensions. On the other hand the more keys that come together, the more information is known about the secret and the reconstruction of the secret in spite of missing keys becomes easier.
Shamires secret sharing
In 1979 Adi Shamires – the S in RSA – published a paper with the title “How to share a Secret”[2].
Inside this paper he presents a (K,N) threshold scheme which is easy to compute for K out of N keys but gives no information about the secret if less than K keys are known (in the sense that all possible keys are equally likely).
It is based on the fact that every polynomial (q(x) = a0+a1x1 … + ak-1xk-1) is unique determined by the degree of the polynomial and the quantity of given points (which has to be one more than the degree of the polynomial).
Some useful properties of this scheme as being secure, minimal, extensible, dynamic and flexible are good explained in [3].
Before we continue I would recommend you to try it out here[4].
How it works basic concept step by step?
1) k is the least quantity of participants you would like to be able to reconstruct the secret
2) Choose a polynomial of grade k-1
3) Define k random indices (a0…ak-1)
4) Define k points which can be calculated by the polynomial
5) Distribute k points to the participants.
6) To calculate the secret out of the keys use e.g. Lagrange interpolation [5] with x=0 .
Shamires secret sharing graphical explanation
Let’s start with a simple polynomial y = a 0+ a1x1.
a0 is our secret and since the grade of the polynomial is 1 we need at least two points to determine it (see figure 1)
figure 1: graph of a first grade polinomial. a0 is the secret e.g. password. The points are the given keys
If you have only one point given an infinite account of possible solutions can be calculated (see figure 2).
figure 2: graph of a first grade polinomial. a0 is the secret e.g. password. Since there is only one fix point the secret is not reconstructible, because an infinite amount of lines are crossing the point
If K is supposed to be bigger than 2 just take a polynomial with a higher grade e.g. y = a0-a2x2+a0x4 in this case K is equal 5 (see figure 3).
figure 3: graph of a fourth grade polynomial. a0 is the secret e.g. password. The points are the given keys.
Now if you would like to add more participants to have a key you could just create a new key by taking another point of the polynomial (see figure 4).
figure 4: graph of a fourth grade polynomial. a0 is the secret e.g. password. The points are the given keys. The x are additional keys that could be created without interfering with already existing keys.
Summary
In this blog you have learned about different types of secret sharing methods, the possible fields of their usage, the weak points of simple approaches and the benefits of conventional methods. Especially the basics of Shamires secret sharing method has been explained step by step as well as in a comprehensive graphical form.
Yet I did not discuss the possibility of a corrupt key dealer and how to handle this problem.
For detailed explanation please visit the following links or write me a mail.
[1] http://www.gm.fh-koeln.de/~konen/DisMa/secret-sharing.pdf
[2] http://groups.csail.mit.edu/cis/crypto/classes/6.857/papers/secret-shamir.pdf
[3] http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing
[4] http://point-at-infinity.org/ssss/demo.html
[5] http://de.wikipedia.org/wiki/Polynominterpolation#Lagrangesche_Interpolationsformel
http://point-at-infinity.org/ssss/
http://de.wikipedia.org/wiki/Shamir%E2%80%99s_Secret_Sharing