Cryptography

Shamir’s Secret Sharing (SSS) #

SSS has the property of information-theoretic security.

Lagrange interpolation theorem: kk points on the polynomial uniquely determines a polynomial of degree less than or equal k1k-1.

Assume secret ss can be represented as element a0a_0 of finite field GF(q)GF(q) and q>nq>n. e.g. a byte bGF(28)b \in GF(2^8) Randomly choose k1k-1 elements a1ak1a_1…a_{k-1} from GF(q)GF(q) and generate polynomial f(x)=a0+a1x+a2x2++ak1xk1f(x)= a_0 + a_1x + a_2x^2 +…+a_{k-1}x^{k-1}. Compute nn points of (x,f(x)x, f(x)) pair on f(x)f(x) curve. e.g. x=1nx=1…n Every share gets one point. Obtain a0a_0 by interpolation: a0=f(0)=j=0k1yjm=0,mjk1xmxmxja_0 = f(0) = \sum_{j=0}^{k-1} y_j \prod_{m=0,m \neq j}^{k-1} \frac{x_m}{x_m-x_j}

// 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 mm out of nn shares are consistent, we only need to check whether the interpolation of mm points (x1,y1),(xm,ym)(x_1, y_1),…(x_m, y_m) yields a polynomial with degree k1k-1 or not.

Lagrange Interpolation L(x)=j=0kyjm=0,mjkxxmxjxmL(x) = \sum_{j=0}^{k} y_j \prod_{m=0,m\neq j}^{k} \frac{x-x_m}{x_j-x_m} Newton Polynomial N(x)=j=0kaji=0j1(xxi)N(x) = \sum_{j=0}^{k} a_j \prod_{i=0}^{j-1}(x-x_i) where aj=[y0,,yj]a_j = [y_0,…,y_j]

N(x)=i=0k(si)i!hi[y0,yi]N(x) = \sum_{i=0}^{k} \binom{s}{i} i! h^i [y_0,…y_i]