Secure multiparty cryptography for the Archistar secure multi-cloud Prototype.
- RabinIDS
- Shamir's Secret Sharing
- Krawczyk Secret Sharing Made Short
- Rabin-Ben-Or Verifiable Secret Sharing
Disclaimer: I'm a software developer and this should be seen as an very simplistic introduction to the used algorithms.
The goal of secret sharing is to split up a secret text into multiple parts so that a subset of those parts (called shares) can be used to reconstruct the original secret. The minimum amount of shares needed to reconstruct the secret should be configurable at 'split-up' time, i.e. it should be possible to split up a secret into 8 parts (shares) of which any 5 are needed to reconstruct the original data.
A basic example of Shamir's Secret Sharing should illustrate a possible contruction technique: let's assume that we want to split up '42' (the secret) into 5 parts, 3 of which are needed to reconstruct the original data ('42'). We will be using polynomials: to solve a polynomial of the third degree three points (x|y) are needed. So if we calculate 5 solutions for a polynomial of the third degree and distribute one solution to each participant each, any subset larger than 3 can solve the polynomial (and thus reconstruct the secret).
The generic form of a polynomial of the third degree is:
y = a_0 * x^0 + a_1 * x^1 + a_2 * x^2
We choose a_1 and a_2 randomly (i.e. 1 and 2) and substitute a_0 with our secret (42), thus creating the following equation:
y = 42 + 1 * x + 2 * x^2
Now we calculate 5 x|y pairs, for example:
| x | y | y |
+---+---------------+----+
| 1 | 42 + 1 + 2*1 | 45 |
| 2 | 42 + 2 + 2*4 | 52 |
| 3 | 42 + 3 + 2*9 | 63 |
| 4 | 42 + 4 + 2*16 | 76 |
| 5 | 42 + 5 + 2*25 | 97 |
and distribute one point to each participant. For example User 1 retrieves x=1|y=45, User 2 retrieves x=2,y=52 and so on. No user can tell anything about the original secret.
To reconstruct the secret 3 participant have to exchange their information, in case of User 1, 2 and 3 this would yield the following equations:
45 = a_0 + a_1 * 1 + a_2 * 1^2
52 = a_0 + a_1 * 2+ a_2 * 2^2
63 = a_0 + a_1 * 3 + a_2 * 3^2
We can use sage to solve this solution:
a0, a1, a2 = var("a0 a1 a2")
eq1 = 45 == a0 + a1 + a2
eq2 = 52 == a0 + 2*a1 + 4*a2
eq3 = 63 == a0 + 3*a1 + 9*a2
solve([eq1, eq2, eq3], a0, a1, a2)
-> [[a0 == 42, a1 == 1, a2 == 2]]
Through solving this a_0 can be calculated to be '42'. Voila, secret restored!
- fork it
- work on your new feature
- run the testcases with
mvn test
- send me a pull request