**Shamir’s**** Secret sharing**

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 :

- Knowledge of k or more pieces of S allows the secret to be recovered.
- Knowledge of k-1 or fewer pieces of S makes it impossible to recover the secret S.

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

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 l*i*(x) is defined as

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

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

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

L3=y3*l*3* = -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