Drunk president and the nuclear launch — Lagrange Decomposition of a function — II
Part 1 — Drunk president and the Nuclear launch — Shamir Secret Sharing
You might have landed here because of the above-linked article to go deeper into the rabbit hole. If not, I am impressed by your perseverance, either you are stuck with math homework and looking desperately for help or just have too much time on your hands to have landed here.
Oh wait, medium.com tags are good too, and search engines these days are running tags on steroids with the ML hype. Crunch everything you can and raise prices for Nvidia RTX 2080 Ti and Titan X. No, I am not a sales rep from Nvidia.
So, coming back to our problem, given N+1 points (x,y) where for a Nth degree function, how do I determine a particular co-efficient without wasting the precious compute power of my Raspberry pi zero.
By now, you would have realized that you can’t calculate a single coefficient ai individually. You get all or none, just like my jokes. We will consider the secret at the first constant a0 because it provides computational feasibility without losing any information.
How to construct the polynomial
We want to find a polynomial such that,
Assume that you have a polynomial such that,
Now what good does this do. We can construct p(x) from those polynomials given xi, yi . How ?
If you substitute x = x0 all polynomials except y0 will vanish. That’s the case will all values of x and y. This means, with whatever information we have, we simulated the original polynomial used to derive the shared keys. All we need to find out now are those smaller polynomials.
Let’s try to fulfil the first condition of each pi(x) .
- Function must return 0 on all values except one
This is the simplest polynomial that fulfills the first condition, It’s trivial, as they say.
2. It must return 1 for the one missed value xi . If we solve the above equation with x=xi and pi(xi) = 1 we can see that:
making the smaller polynomial
Now let’s look what do we need to find actually. That was a Lagrange decomposition of the function by the way.
Since we modeled our function p(x) as the key generating function, the same polynomial that we discarded after generating the key, and we agreed to making the Secret as a0 which is conveniently equal to f(0) thus equal to p(0) .
So all we need to find is p(0)
Let’s construct the condensed form of the equation, trust me, that will help.
Again, replace the smaller polynomials pi(x) with the condensed product form.
Now putting this all together, we come with the below form.
Now, we are ready to get the value of p(0)
Now this, we can calculate easily and in O(N²) time complexity.
A simple implementation: Basic Shamir
$ python shamir_simple.py gen
86, 5004526649
55, 839710439
4, 26141
42, 286285385
76, 3054424829
7, 233255
89, 5739193331$ python shamir_simple.py get
X: 86 4 89 76 42
Y: 5004526649 26141 5739193331 3054424829 286285385
28.9999959767
If you check the implementation, you’ll see that the secret is 29 but we get a value close to 29. This happens because there is a division aka floating point operation in the solution.
There is an element of information leak here. Let’s go back to the original straight line equation that we had seeing how a line can’t be fixed with just 1 point. Assume m is 1 to make things simpler. Also, we are trying to leak some info, so it is ok to assume that we have a subset of required keys. In this case assume we own the key (2, 4)
We have assumed that all coefficients are integers, so with the below equation after substituting the keys known to us,
we can derive that a0 needs to be an even number to make a1 an integer which reduces the search space.
A small comment on the explanation on Wiki
Wiki assumes that all coefficients are Natural numbers that leak even more information, in our case that assumption will lead to a solution with only one point.
In our case, we have assumed that the numbers belong to Integers except 0, so we only have one information leak (still not desired), that the number is even.
To solve this issue (check the next part for this) and the above precision issue we move all the calculations to a Finite Field.
Ok, that’s something which is generally not taught in schools. Certainly, asking the drunk president to deal with Finite field math, he would prefer launching the missile.
Oh, by the way, did you notice, the above method has a fail safe as well, that relies on traditional key management. Just let one person have the Secret, like the head of an Org. In case of his losing the key, or some mercenaries overthrowing the head, the secret is lost, it can always be regenerated using the keys and passed on to the new head. I would refrain to let the drunk president have it though, just sayin’.
There is still more to it, check out the third part for getting over the precision problem.
Part 3 — Drunk president and the nuclear launch — Shamir and the duel guy, Galois — III