Re: verifiable Secret sharing implementation in the public domain.

Neo wrote:
> I'm looking for a secret sharing (verifiable preferrably) in the public
> domain. I found one that is a part of a library. Standalone implementations
> would be very helpful.

I don't know about existing implementations, but it's quite easy to
implement this from scratch, provided you're happy with O(nk^2) time to
create k shares of length n (recovery is O(nk)).

What you want to do is, for each byte of the secret, append k-1 random
bytes, then multiply this k-byte vector by the matrix M, where

             / y_j - x_1 \ / y_j - x_k \
      M_ji = | --------- | ... | --------- |
             \ x_i - x_1 / \ x_i - x_k /

and x_1, ..., x_k, y_0, ..., y_k are 2k distinct elements of GF(256), and
the factor with denominator x_j - x_j is excluded from the product. (The
mixed y and x in the numerator is not a typo.) The output vector is your
shares. To recover the secret you multiply the vector of shares by N, which
is the same as M but with x and y exchanged, and then discard all but the
topmost element of the result. (The other elements are the random bytes.)

This algorithm is based on polynomial interpolation, and is pretty easy to
prove correct and secure.

-- Ben
Received on Tue Feb 7 21:00:13 2006