plus/minus epsilon

In Adi Shamir's paper titled How to Share a Secret, he quotes this problem from a combinatorics textbook:

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?

The scientists are building what's called a 6-out-of-11 threshold gate, and the combinatorial solution that they use can be easily converted to use encryption instead of physical locks to achieve the same goal with digital secrets. The problem with this scheme is the same for locking up cabinets as well as bytes: the number of keys and locks required grows very quickly as the number of scientists increases. The minimal solution to the problem just quoted uses 462 locks and 252 keys per scientist.

Shamir's paper goes on to describe what's now known as Shamir's Secret Sharing scheme, which only ever uses one lock and one key per scientist, at the expense of some slightly complicated math. To summarize, it works by having the sharer choose a k-degree polynomial where all the coefficients are random, except one which is the secret. The sharer then evaluates the polynomial at a different point for each person that wants a share of the secret. To recover the secret, you take k different shares and interpolate the polynomial that goes through them -- this gives you all the coefficients, including the secret.

(Note: You can also think about share distribution in Shamir's scheme as multiplying a coefficient vector by a Vandermonde matrix, and secret recovery as multiplying a share vector by the inverse of a subset of the Vandermonde matrix. I remember this made implementing it a lot easier for me.)

Moving on from just threshold schemes, there's a concept in computer science called a monotone predicate which is essentially any boolean formula constructed exclusively of AND and OR gates (with no negations). These formulas are 'monotone' because once the output is true, turning any more of the inputs to true will never make the output go back to false.

An interesting but simple observation is that any monotone predicate can be represented by nested threshold gates. AND gates are constructed as a 2-out-of-2 threshold, and OR gates are a 1-out-of-2 threshold. This means you can recursively apply Shamir's Secret Sharing scheme to share a secret according to any monotone predicate. The easiest example being:

$$(\texttt{user1}\ &&\ \texttt{user2})\ ||\ \texttt{admin}$$

A system of nested instances of Shamir's scheme designed to implement access control according to some boolean formula like this, is called a monotone span program. Or MSP for short.

Fig. Clothesline tied around two padlocks, such that unlocking one frees the clothesline from both.