Shamir’s Secret Sharing (SSS) #
SSS has the property of information-theoretic security.
Lagrange interpolation theorem: points on the polynomial uniquely determines a polynomial of degree less than or equal .
Assume secret can be represented as element of finite field and . e.g. a byte Randomly choose elements from and generate polynomial . Compute points of () pair on curve. e.g. Every share gets one point. Obtain by interpolation:
// an input/output pair
type point struct {
x, y byte
}
// Lagrange interpolation
func interpolate(points []point, x byte) (value byte) {
for i, a := range points {
weight := byte(1)
for j, b := range points {
if i != j {
top := x ^ b.x
bottom := a.x ^ b.x
factor := div(top, bottom)
weight = mul(weight, factor)
}
}
value = value ^ mul(weight, a.y)
}
return
}
To verify if out of shares are consistent, we only need to check whether the interpolation of points yields a polynomial with degree or not.
Lagrange Interpolation Newton Polynomial where