In the last couple of years, I’ve had a chance to learn cryptography on a very practical level, but I must admit that my background in the actual mathematics is very weak. I’ve never really studied number theory, one-way functions, or modular arithmetic. Still, I have a decent background in probability from my training as an electrical engineer, and this has been my go-to challenge problem:
Eleven scientists are working on a secret project. They wish to lock
up the documents in a cabinet so that the cabinet can be opened if
and only if six or more of the scientists are present. What is the
smallest number of locks needed? What is the smallest number of
keys to the locks each scientist must carry?
This problem and specific answer is presented by Adi Shamir in his paper on sharing secrets.
It is not hard to show that the minimal solution uses 462 locks and 252 keys per scientist.
Not hard, right. But he is talking to professional cryptographers, so it is pretty easy for them.
So, can you figure out the general solution? Let me phrase it for you with some variables:
Given a party of N people that wish to share a safe, any M out of N must be able to unlock it, and at least M are necessary for the task. What is the smallest number of locks L needed and keys K needed? M > N > 0
Apologies for the lack of LaTeX. This is a blog. Stop here to solve the problem, and/or scroll on for my hints and the answer.
An easy (but filled with caveats) way to explain Shamir’s Algorithm is that everyone gets a point that helps to chart a polynomial. The secret is the Y-intercept. In the picture above, you only have 2 points, or parts of the secret, and you need 3, so this is an “any 3 out of N” scheme.
My first hint is obvious if you read the paper’s citation: This is a combinatorial mathematics problem.
My second is this: If you have some idea, but don’t know where to start, try a simpler case and make some observations. Below is the scheme drawn for 2 out of 3 people.
Hold a finger over columns A, B, or C to show that any 2 people can still open the safe. Look at each column to see that at least 2 people are needed.
Some observations about this case, ranging from good to great:
- Tic Tac Toe. X wins.
- There are 3 locks and 2 keys per lock.
- Each lock has a specific purpose; preventing a person (Last hint: or combination of people!) from accessing the safe.
So, ready to solve this? Perhaps you need some time to Google the concepts and formulas from this point, but it should be pretty easy to tackle the problem now. Below is the case for any 3 out of 4, illustrated differently to clarify the last big hint:
See that for all 6 combinations AB, AC, AD, BC, BD, CD, they share a circle in one (and only one) row. See that for all 4 combinations ABC, ABD, ACD, BCD, this is not the case.
The fact that they share a circle in one row means that that combination of 2 out of 4 is denied access and is a solution. They need to find a 3rd person. The fact that they are prevented by just one row is what makes it the minimum solution.
So, to recap our variables:
N = The # of people who share the secret
M = The # of people who can reconstruct the secret
K = The # of keys needed
L = The # of locks needed
So, if you have reworded the problem like I have, we are looking for one or two more intermediate variables. Each lock’s purpose is to prevent a specific combination of people from gaining access. That number of people D in that combination should be one less than the number M needed to open the safe, so that only M people can get at it.
D = M – 1 = The # of people that need to be denied access to a lock.
A = N – D = The # of people that have access to each lock.
And you need one general formula, the one for combinations.
So, the number of locks needed will simplify down to:
Look who found a fancy online LaTeX Editor
The number of keys is easy to find. Just multiple L by A, which also simplifies easily:
And for good measure, the number of keys per person:
X is for the eXtreme keyring they will need
So, some quick specific solutions:
L(2,1) = 1, K(2,1) = 2 (You and your roommate both need to get into your dorm)
L(5,2) = 5, K(5,2) = 20 (Any 2 people on this project can approve a small change)
L(11,6) = 462, K(11,6) = 2772 (Shamir’s example)
L(11,9) = 165, K(11,9) = 495 (And look at what we put up with so Alice and Bob can go on vacation)