bugtraq - Re: Joint encryption?

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <Pine.LNX.4.58.0502211112590.6014@faust.amtp.cam.ac.uk>
Date: Mon, 21 Feb 2005 11:42:01 +0000 (GMT)
From: "Robert C. Helling" <R.Helling@...tp.cam.ac.uk>
To: John Richard Moser <nigelenki@...cast.net>
Cc: Casper.Dik@....COM, bugtraq@...urityfocus.com
Subject: 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