Re: two of three

From: Bob Harris (plasticnitlion_at_wrappermindspring.com)
Date: 01/28/05 

Date: Fri, 28 Jan 2005 22:11:56 GMT

I wrote:
>> Suppose I have a value x (chosen from some range) and I want to
>> encrypt it with three value a, b, and c (each from the same range as
>> x) such that x can be recovered from any two of those values. In
>> other words, we have functions f, g, and h such that f(a,b) = g(b,c)
>> = h(c,a) = x.

and Michael Brown replied:
> The term to look for is "secret splitting" A primitive approach in this case
> would be encrypt it with a single key, call it K, and let it be n bits long.
> Then, split K into 3 equal portions, called K1, K2, K3. K1 is n/3 bits long,
> etc.
>
> The first "metavalue" a contains K1 and K2, b contains K2 and K3, and c
> contains K3 and K1. From any two of these values, the original key can be
> found. The downside to this approach is that you have dramatically reduced
> the brute-force keyspace if you have only one of the "metavalues", something
> which better methods avoid.

My concern with that is that each of the three parties would have a copy of
the entire ciphertext, which he may be able to brute force.

What I had in mind was giving each party data which is no different
whatsover from randomly generated data. For example a could be chosen
completely at random. b is then chosen to satisfy f(a,b) = x, and if f is
as simple as xor or add, b is just as random as a. The same applies to c.
Thus the three pieces separately do not contain any information whatsoever.
They can't be brute forced-- they are a one-time pad.

What I'm in search of is a set of three functions that could do this.

Bob H