Re: Joint encryption?
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