Example Shamir's Secret Sharing

1 example

1.1 preparation
1.2 reconstruction
1.3 computationally efficient approach
1.4 problem
1.5 solution
1.6 javascript example

example

the following example illustrates basic idea. note, however, calculations in example done using integer arithmetic rather using finite field arithmetic. therefore example below not provide perfect secrecy , not true example of shamir s scheme. ll explain problem , show right way implement (using finite field arithmetic).

preparation

suppose our secret 1234



(
s
=
1234
)




{\displaystyle (s=1234)\,\!}

.

we wish divide secret 6 parts



(
n
=
6
)




{\displaystyle (n=6)\,\!}

, subset of 3 parts



(
k
=
3
)




{\displaystyle (k=3)\,\!}

sufficient reconstruct secret. @ random obtain 2 (



k
−
1


{\displaystyle k-1}

) numbers: 166 , 94.

(

a

0


=
1234
;

a

1


=
166
;

a

2


=
94
)




{\displaystyle (a_{0}=1234;a_{1}=166;a_{2}=94)\,\!}

our polynomial produce secret shares (points) therefore:

f

(
x
)

=
1234
+
166
x
+
94

x

2






{\displaystyle f\left(x\right)=1234+166x+94x^{2}\,\!}

we construct 6 points




d

x
−
1


=
(
x
,
f
(
x
)
)


{\displaystyle d_{x-1}=(x,f(x))}

polynomial:

d

0


=

(
1
,
1494
)

;

d

1


=

(
2
,
1942
)

;

d

2


=

(
3
,
2578
)

;

d

3


=

(
4
,
3402
)

;

d

4


=

(
5
,
4414
)

;

d

5


=

(
6
,
5614
)





{\displaystyle d_{0}=\left(1,1494\right);d_{1}=\left(2,1942\right);d_{2}=\left(3,2578\right);d_{3}=\left(4,3402\right);d_{4}=\left(5,4414\right);d_{5}=\left(6,5614\right)\,\!}

we give each participant different single point (both



x




{\displaystyle x\,\!}

,



f

(
x
)





{\displaystyle f\left(x\right)\,\!}

). because use




d

x
−
1




{\displaystyle d_{x-1}}

instead of




d

x




{\displaystyle d_{x}}

points start



(
1
,
f
(
1
)
)


{\displaystyle (1,f(1))}

, not



(
0
,
f
(
0
)
)


{\displaystyle (0,f(0))}

. necessary because



f
(
0
)


{\displaystyle f(0)}

secret.

reconstruction

in order reconstruct secret 3 points enough.

let consider




(

x

0


,

y

0


)

=

(
2
,
1942
)

;

(

x

1


,

y

1


)

=

(
4
,
3402
)

;

(

x

2


,

y

2


)

=

(
5
,
4414
)





{\displaystyle \left(x_{0},y_{0}\right)=\left(2,1942\right);\left(x_{1},y_{1}\right)=\left(4,3402\right);\left(x_{2},y_{2}\right)=\left(5,4414\right)\,\!}

.

we compute lagrange basis polynomials:

ℓ

0


=



x
−

x

1





x

0


−

x

1





⋅



x
−

x

2





x

0


−

x

2





=



x
−
4


2
−
4



⋅



x
−
5


2
−
5



=


1
6



x

2


−


3
2


x
+


10
3






{\displaystyle \ell _{0}={\frac {x-x_{1}}{x_{0}-x_{1}}}\cdot {\frac {x-x_{2}}{x_{0}-x_{2}}}={\frac {x-4}{2-4}}\cdot {\frac {x-5}{2-5}}={\frac {1}{6}}x^{2}-{\frac {3}{2}}x+{\frac {10}{3}}\,\!}

ℓ

1


=



x
−

x

0





x

1


−

x

0





⋅



x
−

x

2





x

1


−

x

2





=



x
−
2


4
−
2



⋅



x
−
5


4
−
5



=
−


1
2



x

2


+


7
2


x
−
5




{\displaystyle \ell _{1}={\frac {x-x_{0}}{x_{1}-x_{0}}}\cdot {\frac {x-x_{2}}{x_{1}-x_{2}}}={\frac {x-2}{4-2}}\cdot {\frac {x-5}{4-5}}=-{\frac {1}{2}}x^{2}+{\frac {7}{2}}x-5\,\!}

ℓ

2


=



x
−

x

0





x

2


−

x

0





⋅



x
−

x

1





x

2


−

x

1





=



x
−
2


5
−
2



⋅



x
−
4


5
−
4



=


1
3



x

2


−
2
x
+


8
3






{\displaystyle \ell _{2}={\frac {x-x_{0}}{x_{2}-x_{0}}}\cdot {\frac {x-x_{1}}{x_{2}-x_{1}}}={\frac {x-2}{5-2}}\cdot {\frac {x-4}{5-4}}={\frac {1}{3}}x^{2}-2x+{\frac {8}{3}}\,\!}

therefore

f
(
x
)
=

∑

j
=
0


2



y

j


⋅

ℓ

j


(
x
)




{\displaystyle f(x)=\sum _{j=0}^{2}y_{j}\cdot \ell _{j}(x)\,\!}

=
1234
+
166
x
+
94

x

2






{\displaystyle =1234+166x+94x^{2}\,\!}

recall secret free coefficient, means



s
=
1234




{\displaystyle s=1234\,\!}

, , done.

computationally efficient approach

considering goal of using polynomial interpolation find constant in source polynomial



s
=
f
(
0
)


{\displaystyle s=f(0)}

using lagrange polynomials not efficient, since unused constants calculated.

an optimized approach use lagrange polynomials find



l
(
0
)


{\displaystyle l(0)}

defined follows:

l
(
0
)
=


∑

j
=
0


k
−
1



f
(

x

j


)


∏



m
=
0


m
≠
j




k
−
1






x

m




x

m


−

x

j







{\displaystyle l(0)={\sum _{j=0}^{k-1}}f(x_{j}){\prod _{\underset {m\neq j}{m=0}}^{k-1}}{\frac {x_{m}}{x_{m}-x_{j}}}}

problem

although simplified version of method demonstrated above, uses integer arithmetic rather finite field arithmetic, works fine, there security problem: eve gains lot of information



s


{\displaystyle s}

every




d

i




{\displaystyle d_{i}}

finds.

suppose finds 2 points




d

0


=
(
1
,
1494
)


{\displaystyle d_{0}=(1,1494)}

,




d

1


=
(
2
,
1942
)


{\displaystyle d_{1}=(2,1942)}

, still doesn t have



k
=
3


{\displaystyle k=3}

points in theory shouldn t have gained more info



s


{\displaystyle s}

. combines info 2 points public info:



n
=
6
,
k
=
3
,
f
(
x
)
=

a

0


+

a

1


x
+
⋯
+

a

k
−
1



x

k
−
1


,

a

0


=
s
,

a

i


∈

n



{\displaystyle n=6,k=3,f(x)=a_{0}+a_{1}x+\dots +a_{k-1}x^{k-1},a_{0}=s,a_{i}\in \mathbb {n} }

, she :

s
∈
[
1046
,
1048
,
…
,
1342
,
1344
]


{\displaystyle s\in [1046,1048,\dots ,1342,1344]}

. has 150 numbers guess instead of infinite number of natural numbers.

solution

this polynomial curve on finite field order of polynomial has seemingly little shape of graph

geometrically attack exploits fact know order of polynomial , gain insight paths may take between known points reduces possible values of unknown points since must lie on smooth curve.

this problem can fixed using finite field arithmetic. field of size



p
∈

p

:
p
>
s
,
p
>
n


{\displaystyle p\in \mathbb {p} :p>s,p>n}

used. graph shows polynomial curve on finite field, in contrast usual smooth curve appears disorganised , disjointed.

in practice small change, means should choose prime



p


{\displaystyle p}

bigger number of participants , every




a

i




{\displaystyle a_{i}}

(including




a

0


=
s


{\displaystyle a_{0}=s}

) , have calculate points



(
x
,
f
(
x
)


(
mod

p
)

)


{\displaystyle (x,f(x){\pmod {p}})}

instead of



(
x
,
f
(
x
)
)


{\displaystyle (x,f(x))}

.

since receives point has know value of



p


{\displaystyle p}

may considered publicly known. therefore, 1 should select value



p


{\displaystyle p}

not low.

low values of



p


{\displaystyle p}

risky because eve knows



p
>
s
⇒



s
∈

[
0
,
1
,
…
,
p
−
2
,
p
−
1
]



{\displaystyle p>s\rightarrow {}s\in {[0,1,\dots ,p-2,p-1]}}

, lower 1 sets



p


{\displaystyle p}

, lower number of possible values eve has guess



s


{\displaystyle s}

.

for example choose



p
=
1613


{\displaystyle p=1613}

, our polynomial becomes



f

(
x
)

=
1234
+
166
x
+
94

x

2



mod


1613


{\displaystyle f\left(x\right)=1234+166x+94x^{2}\mod {1613}}

gives points:




(
1
,
1494
)

;

(
2
,
329
)

;

(
3
,
965
)

;

(
4
,
176
)

;

(
5
,
1188
)

;

(
6
,
775
)



{\displaystyle \left(1,1494\right);\left(2,329\right);\left(3,965\right);\left(4,176\right);\left(5,1188\right);\left(6,775\right)}

this time eve doesn t win info when finds




d

x




{\displaystyle d_{x}}

(until has



k


{\displaystyle k}

points).

suppose again eve finds




d

0


=

(
1
,
1494
)



{\displaystyle d_{0}=\left(1,1494\right)}

,




d

1


=

(
2
,
329
)



{\displaystyle d_{1}=\left(2,329\right)}

, time public info is:



n
=
6
,
k
=
3
,
p
=
1613
,
f
(
x
)
=

a

0


+

a

1


x
+
⋯
+

a

k
−
1



x

k
−
1



mod


p
,

a

0


=
s
,

a

i


∈

n



{\displaystyle n=6,k=3,p=1613,f(x)=a_{0}+a_{1}x+\dots +a_{k-1}x^{k-1}\mod {p},a_{0}=s,a_{i}\in \mathbb {n} }

she:

this time can t stop because



(

m

1


−

m

2


)


{\displaystyle (m_{1}-m_{2})}

integer (even negative if




m

2


>

m

1




{\displaystyle m_{2}>m_{1}}

) there infinite amount of possible values




a

1




{\displaystyle a_{1}}

. knows



[
448
,
445
,
442
,
.
.
.
]


{\displaystyle [448,445,442,...]}

decreases 3 if



1613


{\displaystyle 1613}

divisible



3


{\displaystyle 3}

conclude




a

1


∈
[
1
,
4
,
7
,
…
]


{\displaystyle a_{1}\in [1,4,7,\dots ]}

because s prime can t conclude , didn t win information.

javascript example