Electrical and Computer Engineering, Carnegie Mellon University

Real-World Threshold Keys

Let’s say that you’ve been tasked with locking away a stash of treasure in a safe. There is a group of 6 people, each of whom wants access to the safe, but since they don’t trust each other, they decide that in order to open the safe, at least 4 of them need to come together. You can put as many locks as you want on the safe, and for each lock you can distribute as many keys as you want to the participants. How many locks do you put on the safe and how do you distribute the keys?

(If you don’t know the answer and don’t want to spoil the fun, stop reading now.)

What we want in solving this problem is to distribute the keys among the participants in such a way that (1) any group of 4 or more participants collectively own keys for each lock on the safe (and of course the group can have more than one key for the same lock), and (2) any group of 3 or fewer participants will be missing a key for at least one lock on the safe. It’s actually this second property that gives us the insight to solve this problem. The idea is that we select every possible subgroup of three people in the group, and for each subgroup we put a lock on the safe and give keys for the lock to everyone else in the group except for those three. So in this case we would need 6 choose 3 locks, which equals 20 locks. Then we give every subgroup of three people keys to a lock, so for example the first key would be given to participants 1, 2, and 3, the second key would be given to participants 1, 2, and 4, and so on.

Why does this work? Consider participants 1, 2, and 3. There is one key that they don’t have, namely the key given to participants 4, 5, and 6. We also know that they have all of the other keys except this one, since the only way to not give a key to any of 1, 2, or 3 would be to give the key to 4, 5, and 6. We also know that adding any participant to this subgroup would give them all the keys, because 4, 5, and 6 all have the one key that they’re missing. We can substitute any 3 different numbers above, and get the same result. So any group of 4 people are required to unlock the safe!

Now let’s see what happens when we generalize the problem. We have n participants, at least t of whom are needed to open the safe. We can use a similar approach as earlier. For every subgroup of t-1 participants there should be a key that nobody in the subgroup has. So we can make one lock for each of these subgroups (and there are n choose t-1 of these subgroups) and for each lock give keys to all participants not in this subgroup. Thus in total we distribute (n choose t-1) * (n-t+1) keys. So now we can do this for all kinds of groups and thresholds!

In cryptography, secret sharing allows a secret to be split among n people in such a way that at least t of them need to agree to unlock the secret. This is a nice mathematical equivalent of solving the above problem without having to deal with lots of separate locks and keys. Shamir’s secret sharing is a particularly elegant solution: since t points are sufficient to define a polynomial of degree t-1, we can define such a polynomial P(x) with P(0) equal to the secret and distribute one point of the polynomial (1 and P(1) for example) to each participant. Then, any t of them can reconstruct the polynomial using Lagrange interpolation to find the secret.

Tag Cloud