How to encrypt something so that can be decrypted using any two of three keys?

Question

So say I want to encrypt a file and the only way I want it to be read is if two different people enter their keys. So, for instance there are four keys:

key1, key2, key3, key4.

If I encrypt it with key1 then the following combinations will decypt it:

• key2,key3
• key3,key4
• key2,key4

Is this possible using a standard method?

Answer 1

make the fourth key the bitwise checksum of the other three... You could even sequentially increment which key had the checksum value.. so that

1. key 4 bit 1 was a checksum of bit 1 in keys 1-3, and
2. key 1 bit 2 was a checksum of bit 2 in keys 2-4, and
3. key 2 bit 3 was a checksum of bit 3 in keys 1,3,4, and
4. key 3 bit 4 was a checksum of bit 4 in keys 1,2,4, and
5. key 4 bit 5 was a checksum of bit 5 in keys 1,2,3, etc. ...

kinda like striped raid 5 does...

This way, no matter which three of the four keys you had, you could recreate the missing one. use some combination of all four keys to encrypt the message.

Answer 2

Say you're assigning keys x1, x2, .. xN

Encrypt the file with a master symmetric key M. Then store several encrypted copies of M:

• Encrypted with x1 and x2
• Encrypted with x2 and x3
• Encrypted with x1 and x3
• ...

Any two keys will unlock one of the encrypted copies of the master, which will decrypt the file.

Answer 3

Not as you state it, I don't think. But you could get the same effect like this: Use public key crypto; now there are 4 public and 4 private keys. As person #1, encrypt your message with each pairwise combination of the other 3. E.g. encrypt the message with key 2, then encrypt that with key 3. Now encrypt the message with key 2, then encrypt that with key 4. Finally, 3 then 4. Now if any two of the others get together they can recover the original message.

Answer 4

Generate a unique content key to encrypt the message (this is common to many message encryption standards), then apply an erasure code scheme such as Reed-Solomon coding against that content key concatenated with enough additional random data to ensure that any m of n "shards" of the key can be put together to create the final key. Shards are only given out from the random data portion so that none of the shards given out contain actual bits from the content key. This way, any number of collected shards short of m does not give any useful information about the key itself.

EDIT: Reed-Solomon to generate key shards appears to be identical to Shamir's secret-sharing, first published in 1979; thanks to @caf for pointing out the article.

Answer 5

Generate a symmetric key key1 randomly and use it to encrypt the data, then generate key2, key3 and key4 from key1 using Shamir's Secret Sharing protocol.

To securely distribute key2, key3 and key4 you can then use a public key algorithm to encrypt them using the public keys of the recipients.