Two shares know nothing

A bank’s vault has one combination, and the bank wants no single employee to be able to open it, yet any three of its eight senior staff must be able to. Giving each employee a piece of the combination does not work. Whoever holds two pieces out of three has learned most of it, and the arrangement needs an enormous number of pieces if every group of three is to succeed. In 1979 Adi Shamir and George Blakley independently published solutions, and Shamir’s fits on a single line. It is exact in a way that is uncommon in security: a group one person short does not have a harder problem to solve, it has no information at all.

That word “no” means something quite specific here, and it can be checked by counting. Everything turns on one elementary fact about polynomials, which the polynomial through the gaps used on the real line: $k$ points determine a polynomial of degree below $k$. What makes the idea work is moving it from the real line to a finite field.

The scheme #

Choose a prime $p$ larger than the secret and larger than the number of people. To protect a secret $s$ so that any $k$ people can recover it, choose $k - 1$ random numbers and form the polynomial

$$q(x) = s + a_1 x + a_2 x^2 + \cdots + a_{k-1} x^{k-1} \pmod p.$$

Person number $i$ receives $q(i)$. That is all. The secret is $q(0)$, and it is handed to no one.

In the picture, $k = 3$, $p = 31$, the secret is 17, and the polynomial is $17 + 9x + 4x^2$. Eight people receive 30, 20, 18, 24, 7, 29, 28 and 4. Modulo a prime the values wander over the whole range, and nothing looks like a parabola. It still behaves like one in the one way that matters. A polynomial of degree two is determined by three of its values, by the same calculation as on the real line, since that calculation needs only addition, multiplication and division. So any three people can write

$$s = q(0) = \sum_{i} y_i \prod_{j \ne i} \frac{-x_j}{x_i - x_j},$$

which is Lagrange’s formula evaluated at nought, and which uses Euclid’s algorithm to perform the divisions modulo $p$. The first three shares, 30, 20, 18, return 17, and so does every other choice of three. The formula was tested for every secret modulo several small primes.

The counting is what makes this remarkable. Suppose only two people meet, holding $q(1) = 5$ and $q(2) = 9$ for a quadratic modulo 13. For any guess $s$ at the secret, there is exactly one quadratic through the three points $(0, s)$, $(1, 5)$ and $(2, 9)$. So every value of the secret corresponds to the same number of polynomials, namely one.

That is not an inference from the formula alone: all 2,197 polynomials were enumerated and tallied. One share leaves 13 polynomials for each of the 13 possible secrets. Two shares leave exactly 1 for each. The third leaves one polynomial in all, which sits at secret 3 in that example, and the secret is known. The transition has no gradual part. If the coefficients were chosen uniformly, then given two shares the secret is still exactly uniform over all thirteen values, with the same distribution as before anything was revealed. That is perfect secrecy, the notion defined in 1949 by Claude Shannon, who also priced a noisy channel, and no amount of computing power can change that, because the two people’s information is literally independent of the secret. Compare a scheme based on factoring or any other hard problem, including those that lean on the arithmetic of primes and their impostors: those would be safe only as long as nobody has a fast enough algorithm. Here there is nothing to compute. The case of two shares with threshold two is just Vernam’s one-time pad: one person holds a random number and the other holds the secret plus that number.

Why the field is not a technicality #

It is natural to wonder why the arithmetic has to be modular at all. Polynomials exist over the whole numbers too, and interpolation works there. So try the same scheme with ordinary integer coefficients, using the same two shares.

Suppose $q$ has whole-number coefficients with $q(1) = 5$ and $q(2) = 9$. Writing out the equations gives $a_1 = 4 - 3a_2$ and $a_0 = 5 - a_1 - a_2 = 1 + 2a_2$. Only odd secrets are possible. So half of all the secrets have been excluded, by two people who were supposed to know nothing. That is the first leak; a further one comes from size, since an integer polynomial’s shares grow and reveal how large the coefficients must be, and with real numbers the values can be bounded by their sizes. In a field neither can happen. Every non-zero difference $x_i - x_j$ can be divided by, and so no value is ever excluded by a divisibility condition. A map from coefficients to shares and a secret, in a finite field, is a square linear system with a Vandermonde determinant that does not vanish, so it is a bijection.

So the perfect secrecy is exactly a statement about a matrix being invertible, and this is the reason that the proof is three lines long. It is the same bijection in every direction: from $k$ coefficients to any $k$ values. Whichever $k$ positions are chosen, the rest are determined, and that is the defining property of the Reed–Solomon construction described next.

The same thing with planes #

Blakley’s version looks quite different. The secret is a point in $k$-dimensional space over a finite field. Each person is given a hyperplane through it. Two planes in three-dimensional space meet in a line, and three meet in a point.

The counts in this figure are also exact: 169, then 13, then 1, each found by testing all 2,197 points. Blakley’s picture is geometrically transparent, and it shows the idea directly, in that each share cuts the remaining possibilities by one factor of 13. But the figure also shows why it is not quite the same thing as Shamir’s scheme. Each person’s share takes three numbers to specify instead of one. Worse, the possibilities shrink evenly at each step rather than staying flat, so a group one short does know something: the secret lies on one line, not anywhere in the space. If the secret is taken to be just one coordinate of the point, as it must be for secrecy, the problem goes away for random planes, except that a share may happen to rule out some values of that coordinate. Shamir’s construction has no such exception, which is why it became the standard.

There is more unity here than the two pictures suggest. Shamir’s shares are themselves linear functions of the coefficient vector, and each share defines a hyperplane in the space of coefficients. So Shamir’s scheme is Blakley’s scheme with a specific choice of planes, namely those whose normal vectors are $(1, i, i^2, \ldots)$, and with the secret defined as the first coordinate. The reason it has perfect secrecy is that no combination of fewer than $k$ of those normal vectors can produce $(1, 0, 0, \ldots)$, again because of Vandermonde.

Sharing is a code #

If there are more shares than the threshold, the shares form a list with redundancy. The list of values $q(1), \ldots, q(n)$ for all polynomials of degree below $k$ is exactly a Reed–Solomon code, as Robert McEliece and Dilip Sarwate pointed out in 1981. So the theory of error-correcting codes applies directly. Losing shares is an erasure, and the longest code surviving every erasure is the exact statement that any $k$ shares are enough. Secrecy, then, is the mirror image of Reed–Solomon distance. The same algebra that says $k$ positions determine the whole list also says $k - 1$ positions determine nothing about the rest.

That connection has a practical result, because a false share is an error in a codeword.

A group of exactly three cannot tell if one of them is lying, because any three values define a polynomial. The false value simply gives a wrong secret, with no warning. This was tested. With seven shares and the fourth altered by 11, all 35 groups of three compute a secret. The 20 groups avoiding the fourth share agree on 17. The other 15 give other answers, spread over 14 different values. A vote of this kind can pick out the truth, and with more redundancy the same thing can be done efficiently. Decoding beyond half the distance and the older Berlekamp–Welch method find the false shares directly without trying all groups. It works provided that the number of false shares is less than half of the excess over the threshold. A malicious dealer is another matter, since nothing in the basic scheme lets the recipients check that their shares lie on a common polynomial of the right degree. Paul Feldman’s scheme of 1987 adds a verifiable public commitment, at the price of relying on a hard problem.

Who can open it #

Threshold schemes are a small part of a larger family. It is natural to describe who can open by a list of allowed groups.

A scheme with threshold 3 of 8 lets 219 of the 256 possible subsets open it, and it has 56 minimal groups. So a scheme that gave each minimal group its own one-time pad would need 21 separate keys per person, $\binom{n-1}{k-1}$ of them, a number that grows combinatorially. At 6 of 12 there are 924 minimal groups, and a person would be a member of 462 of them. Shamir’s scheme avoids all of it: every person holds one number the size of the secret, however large $n$ becomes, up to the size of the field. And that size is as small as possible. Ehud Karnin, J. W. Greene and Martin Hellman proved in 1983 that any scheme with perfect secrecy must give every necessary person a share at least as long as the secret. The argument is short, as a person with a shorter share would be unable to change the outcome among all secrets when added to a group one short.

For an arbitrary family of allowed groups, the situation is less neat. Any monotone family can be realised, as Mitsuru Ito, Akira Saito and Takao Nishizeki showed in 1987, but the shares may need to be longer than the secret. How much longer is an active open question. The known constructions for general families use shares of exponential size in the number of people, and the lower bounds are very much smaller. Whether some access structures truly need exponential shares is not known. In 2018 Tianren Liu, Vinod Vaikuntanathan and Hoeteck Wee made the first improvement on the old exponential upper bound. Later work, by Benny Applebaum and collaborators among others, has pushed the exponent lower still, without closing the gap. Those improvements are peculiar. They work by sharing a function through its values on a clever encoding, and they say nothing about what the true length is.

Computing without opening #

The most far-reaching use came after 1979. If each of several people holds a share of $s$ and also a share of $t$, then adding their shares pointwise gives shares of $s + t$, since adding polynomials adds their constant terms. So a group can add secrets without anyone seeing them. Multiplication is almost as easy: the pointwise product of two shares is a value of the product polynomial, whose constant term is $st$. The degree has doubled, but it can be brought back down by a short interactive step. Since any computation is made of additions and multiplications, Michael Ben-Or, Shafi Goldwasser and Avi Wigderson showed in 1988 that a group can evaluate any function of its members’ private inputs, with no participant learning more than the output, provided that fewer than a third of them are dishonest. David Chaum, Claude Crépeau and Ivan Damgård showed the same thing that year.

The surprise is how little structure has been used. There is no cryptographic assumption in that theorem at all, and its security is the same information-theoretic statement as the flat rows in the census above. An idea for locking up a vault’s combination turned out, once the polynomials were added and multiplied, to allow an arbitrary computation on hidden data. It is the same algebra that makes Hamming’s and Reed’s codes work, doing an unrelated job, and it is what lets the counts in a field carry a guarantee that no probability calculation could.

What the counts do not cover #

Perfect secrecy assumes that the coefficients are chosen uniformly at random. The enumeration above treats every polynomial as equally likely, and it says nothing about a real dealer’s random numbers, which come from some generator. If the coefficients are predictable, the flat rows are irrelevant. Producing randomness of that quality is a separate problem. A figure of a uniform count cannot show that one dealer’s choice was actually uniform. Nor does anything here model a group that combines partial information with knowledge of what kind of secret it is. If the secret is known to be a printable word, the group always had that knowledge, and the shares add none. That is exactly what the flat count means, but it does not mean that the secret was safe from guessing.

The counts are also finite examples in small fields. The general theorem is short and does not depend on them, but the figures show only the particular prime 13 with the particular shares used.

What was computed and what was quoted #

The interpolation formula was tested for every secret modulo 7, 11 and 13 on one polynomial shape. The census of 2,197 polynomials and that of 2,197 points are exact enumerations. The integer example is an exact calculation, and it was checked over a range of the free coefficient. The experiment with seven shares went through all 35 groups. The access-structure counts are binomial sums.

The theorems of Shamir and Blakley on secrecy are simple and are proved above in outline. The results of McEliece and Sarwate, Karnin, Greene and Hellman, Ito, Saito and Nishizeki, Feldman, Ben-Or, Goldwasser and Wigderson, and Chaum, Crépeau and Damgård, and the recent bounds on general access structures, are quoted and were not verified here.

Still open: how long a share must be #

For the hardest monotone access structure on $n$ people, what share length is necessary? The best constructions known use about $2^{0.64n}$ bits per person, down from the old $2^{n}$ order, and the best lower bound, due to László Csirmaz in the 1990s, is only about $n / \log n$. It is one of the widest gaps in the theory of cryptography. It is not known whether some function requires an exponential share, or if a small polynomial length always suffices.

For threshold schemes, everything needed is known, and the theory is finished. That makes the contrast sharper. A threshold is so simple that a polynomial handles it perfectly and optimally. A mild change in who is allowed to open might require a share longer than the observable universe, or might not. Nobody knows. There is a related open question on the linear case, since Shamir’s scheme is linear and most efficient schemes are too. Linear schemes correspond to monotone span programs, and bounds for those are better understood, while those for general schemes are not.

A flat row and a spike #

Modulo a prime, $k$ values determine a polynomial of degree below $k$, and $k - 1$ values are consistent with every constant term, by the same number of polynomials for each. So a group of $k$ knows everything and a group of $k - 1$ knows nothing, with no intermediate state, and this was verified by listing all 2,197 quadratics modulo 13.

The strength of the result comes from the field. Over the whole numbers, two shares leak the secret’s parity, because not every number can be divided by. In a field every number can, the map between coefficients and shares is a bijection, and each row of the census is flat. An ordinary fact about parabolas, that three points fix one, has turned into a guarantee that no future mathematics can undermine.