Consensus-based information disclosure

Question

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 (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.

Answer 1

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