On Sat, 19 Feb 2005, John Richard Moser wrote:

> Yeah I noticed that on the wikipedia :)
>
> http://en.wikipedia.org/wiki/Secret_sharing

I would like to add that both schemes described there are essentially
equal as both make use of the fact that a T dimensional subspace U of an N
dimensional vector space V (for example a vector space of polynomials) is
encoded by giving T linearly independent vectors in U.

Data can now be encoded by thinking of it as a functional

f: T ---> F

that is a linear function that maps T into the field F over which T is a
vector space.

Now for each bearer i of a part of the secret give him a vector b_i in U
(in terms of T coordinates) and his share of the data is e_i = f(b_i).

If T bearers come together, they can combine their T vectors b_i into a
TxT matrix M and compute M^(-1) (if they are linearly independent).
Finally, acting with M^(-1) on the vector of the T e_i's recovers the
original functional f.

Note that if you want to share more data f1...fk you need to compute the
b_i and thus M^(-1) only once and then you pass on the f_n(b_i).

For a practical implementation you could for example use the unique field
F_256 of dimension 256 and do arithmetic using look up tables. See for
example the perl scripts

http://www.damtp.cam.ac.uk/user/rch47/split.pl

for the sharing/combining of the data and

http://www.damtp.cam.ac.uk/user/rch47/gf2.pl

for the finite field arithmetic.

Robert

--
.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo
.oOo.oO
Robert C. Helling School of Science and Engineering
International University Bremen
print "Just another Phone: +49 421-200 3574
stupid .sig\n"; http://www.aei-potsdam.mpg.de/~helling

[ reply ]