Solution Shamir's Secret Sharing

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.