Re: Joint encryption?

["Robert C. Helling" <R.Helling@xxxxxxxxxxxxxxx>]

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