Drunk president and the Nuclear launch — Shamir Secret Sharing — I

Suppose you work for a president who likes to flaunt their nuclear strength, but you understand the responsibility of owning a nuclear weapon. So you need to save the world from the drunk president. One thing you could do is break up the key into multiple pieces and let the drunk fella have only 1 of the pieces.

The formal problem statement

Given a secret S, divide it into k pieces such that any combination of N+1 pieces can recover the secret. It must be computationally easy to compute and If you have the number of pieces less than k it should be computationally infeasible to calculate the secret.

So, now you know it’s a terribly simple (spoiler alert) method called Shamir’s Secret Sharing. Given that wiki has a complete explanation to it, you have 2 choices left, abandon reading this and jump to the provided link or continue having fun over my discreet way of writing.

So, you are still here, guess you’ll get a tickle or two.

Let’s go back to grade school and re-visit straight lines. Given a point in 2D space, how many straight lines can you draw passing through the point?

multiple lines through 1 point

There can be infinitely many lines that pass through a single point which in this case is (2, 4) .The general equation of lines passing through this is:

Suppose we fix another point, then we can draw a fixed line. The above line is rotating around the point (2,4), probably high on some spiral, let’s leave it at that. Fix another point, say (0, 2) and we can solve for m in the above equation.

Let’s generalize this now, as every math text says,…

Given a function f of degree N such that:

To uniquely identify the above curve, you need N+1 parameters, which are all the constant terms in the equation. If you know same number of relations between unknowns as there are number of unknowns, all of them can be solved for. Which implies,

You would need at least N+1 points (x, y) to fix the curve where all values of x are distinct.

Substitute all the points in the above equation and you’ll get a set of N+1 equations with N+1 variables.

If you have any less than N+1 equations, you won’t be able to solve for all variables and you’ll get a family of curves, which will do no good. (If you are not careful, it might hurt you)

Note: The degree N is also an important aspect, when defining a function, because you can plot a fixed line through 2 points although you cannot define a fixed parabola using just 2 points. Our requirement is to get a fixed curve. So if we want to derive a fixed curve of degree N we would need N+1 points exactly.

So, you would now ask, where is the safeguard I promised, sharing a key between multiple people. So let’s begin with deriving the shared keys.

Note: Generating exactly N + 1 keys would not be fault tolerant one of the applications of Shamir secret sharing is that you can lose a certain number of keys before making it irrecoverable.

• Choose k such that k > N + 1
• Generate k unique random numbers x0, x1, .. x(k-1) and corresponding values of y using the curve f(x)
• We have derived k keys now, and each key is represented as

ith key

• Distribute the keys to k people and throw away the constants in the original equation, purge it, have no trace of it, and I don’t mean trace but trace

Wait, is that it…

Yes, that’s it. All you need is any N + 1 points from the set of keys and would be able to solve the curve. In this process, you can use any of the values a0, a1, a2, ..., an as your secret that you want to share. Unless you have atleast N + 1 points you can not solve for all values of a.

To get the feel of it, try solving this (the above equation for m=1 ) with the substitution of the point (2, 4).

destroying all coefficients

Not possible right, to pin-point the curve, you get a family of curves with the variable m.

Either you can believe me, it’s true for the above-generalized equation too, anything less than N+1 equations, and you are in for a ride, or I am going to use the strongest weapon, Proof is left as an exercise to the reader .

Let’s go through an example.

Let 7 be the secret we need to share

and we derive keys from it which are (1, 6), (2, 7), (3, 10), (4, 15)

Let’s forget the equation and only remember that we need 3 keys to unlock whatever is locked by the shared keys.

by solving this, we get a2=1, a1=-2, a0=7 which tells us the exact curve and we get our value 7 to unlock. Okay, but how did we solve this and how can we make it easier, as solving a set of linear equations is not easy at all. Some ways that you can solve are Cramer’s Rule and Gauss Jordan Elimination (When the prince has a way, you oblige)

But the thing is that we don’t need all the constants, we only need one of them, so why find all of them.

Enter Joseph-Louis Lagrange and his weird enough intuition. But sad enough, we are exiting now. I don’t intend to make this too long because

source: Pinterest

Need more, look up the second part, deeper down the rabbit hole, more towards the real world.

Part 2 — Drunk president and the nuclear launch — Lagrange Decomposition of a function — II

Part 3 — Drunk president and the nuclear launch — Shamir and the duel guy, Galois — III