Consensus-based information disclosure

Problem description

I am interested in a solution to the following problem:

There is some secret information that a group of n people would like to lock away until some minimum number 1<=m<=n of them agrees to release it. For example, say, the names of all participants in the group.

How can we encrypt this information and distribute n 'keys' to it so that the information remains private forever, unless at some point at least m submit their keys to unlock the information?

Constraints

It is crucial that for any k<m (even m-1), there should be an extremely low probability of successfully retrieving the information with only k keys. Equally crucially, for any k>=m, the probability of success should be extremely high.

And optimally (but not necessarily), I would like a solution that has these properties:

• is functionally scalable 开发者_StackOverflow(solves problem for any m,*n*).
• is speed/memory scalable (takes a reasonable amount of time to encrypt/decrypt).

Initially, I thought that a good solution might involve simply encrypting the information and giving away the (private) key in pieces, but I can't figure out a good way to split up the key.

In particular, the problem seems to get harder when both m and n become really large, since the line between having and not having >=m willing group member becomes thinner and thinner (so to speak).

If you know a solution, a nudge in the right direction would be preferable to a complete answer.

For key splitting, look up Shamir's Secret Sharing. This is a classical method (published in 1979).

You could use the XOR based splitting, here is how it works:

You provide the required number of pieces - n, and the secret key – K. To generate n pieces of your key, you need to create (n – 1) random numbers: R1, R2, R3, . . . , Rn−1. For that you can use a SecureRandom number generator, which will prevent us from duplicates.Then you operate XOR function on these Rn-1 pieces and your key - K:
Rn = R1 ⊕ R2 ⊕ R3 ⊕ . . . ⊕ Rn−1 ⊕ K

Now you have your n pieces: R1, R2, R3, …, Rn-1, Rn and you may destroy the K. Those pieces can be spread in your code or sent to users.

To reassemble the key, we use XOR operation on our Rn pieces:
K = R1 ⊕ R2 ⊕ R3 ⊕ . . . ⊕ Rn−1 ⊕ Rn

With the XOR function (⊕) each piece is inherently important in the reconstruction of the key, if any bits in any of the pieces are changed, then the key is not recoverable.

For more Info you can take a look at the Android Utility I wrote for that purpose:
GitHub Project: https://github.com/aivarsda/Secret-Key-Split-Util

Also you can try the Secret Key Splitter demo app which uses that Utility :
GooglePlay: https://play.google.com/store/apps/details?id=com.aivarsda.keysplitter