Consider a setting in which you have to share a secret among a group of participants such that a fixed no of participants are needed to recover it. The secret is divided into parts, giving each participant his own unique part.

Objectives

Divide the secret S(for ex Nuclear launch codes) in to n pieces of data s1…. sn such that :

The threshold scheme can be written as (k,n) i.e at least any k pieces out of n are required to reconstruct the secret.

Idea

The solution is a really clever application of properties of polynomials. A polynomial is an equation of the form where exponents are non negative integers.

The degree of a polynomial is the largest degree of any one term with nonzero coefficient.

Property

Given n+1 pairs of points(x,y) where all x are distinct, there is a unique polynomial p(x) of degree n that passes through these points. If we have any less than these n+1 pairs we cannot recover the polynomial for example a line can be uniquely determined by 2 points, we need at least 3 points to uniquely determine a parabola.

Working

Let us choose a1=-6 , a2=1 randomly and secret S(a0) to be shared as -6 so our polynomial p(x)= x²-6x-6.

We want to divide secret in to 4 parts such that at least 3 participants are needed to recover the secret ,our secret threshold scheme is (3,4). Evaluating p(x) at 4 distinct points we get

p(1)=-11

p(2)=-14

p(3)=-15

p(-1)=1

graph of x²-6x-6 from www.desmos.com

let us call the participants as A B C & D the parts given to each individual are A(1,-11) , B(2,-14) , C(3,-15) & D(-1,1). Note we did not evaluate the polynomial at 0 as it would have given out our secret -6.

Recovering the secret

Now suppose A B and C decide to meet and try to recover the polynomial and subsequently the secret using Lagrange Interpolation. Lagrange Interpolation can be defined as given a pair of k points(x,y) such that all x are distinct then L(x) is defined as

where li(x) is defined as

If you are having trouble following calculate lj(x) as product of all (X — xi ) divided by product of (xj - xi) where xi is from 1 to k save xj, and L(x) is calculated as sum of product of value of polynomial at xj and lj(x)

L1=y1*l1 = -11*(x-2)*(x-3)/{(1–2)*(1–3)}

L2=y2*l2 = -14*(x-1)*(x-3)/{(2–1)*(2–3)}

L3=y3*l3 = -15*(x-1)*(x-2)/{(3–1)*(3–2)}

L(x) = L1+L2+L3 , after evaluating we get

L(x)=(2x²-12x-12)/2

L(x)=x²-6x-6

Now to recover the secret simply evaluate the polynomial at x =0 giving L(0) =-6.

This algorithm can be used to share combination to safe or in a doomsday scenario for Nuclear Launch Codes. Shamir’s Algorithm performs the calculations over a finite arithmetic field to counter the attacker’s bruteforce methods that become feasible when more points are compromised, we shall explore it next time.

Happy Hunting

priest

Reach for the sky