A Math Problem

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.

Image

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:

Image

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)

Advertisements

2 thoughts on “A Math Problem

  1. I obviously know the context of the problem as it applies, but never bothered to work out the math. Interesting though that it essentially becomes a sampling problem (i.e. the polynomials).

    In real life applications though, not all entities are equally (un)trustworthy. What sort of simplification or reduction do we get if one of the entities is trusted by the others (who don’t trust each other)? I’d assume it would be N-1 naively. To be more complicated, we could have a trust network where each entity has a certain level of trust with another, but I assume there’s no closed form solution to that.

  2. The easy solution is to not treat this as a “keys” and “locks” problem, but shares of a secret. Generally trustworthy actors are granted more shares. Of course, that has nothing to do with this specific secret sharing scheme except that it would be difficult to implement since distributing more than 5 shares is extremely data-intensive.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s