Re: two of three

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

Date: Sat, 29 Jan 2005 03:15:29 GMT

I wrote:
> 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.

Actually, I have one simple solution. Sort of.

X is my plaintext.

I create A = some truly random text, same size as X.
I create B = A + X modulo whatever M makes sense
I create C = A - X modulo the same thing

Given A and B, X is recovered from B-A
Given A and C, X is recovered from A-C
Given B and C, X is recovered from (B-C)/2

The trick is that 2 has to have an inverse modulo M.

Bob H