Trust but verify. That expression captures the tension between relying on others while still wanting to keep some level of control over a situation. Mathematician Adi Shamir must have thought about this challenge when he developed what is now known as “Shamir’s secret sharing,” an algorithm named after him.
To understand it, the following puzzle can help: Suppose an elderly woman wants to bequeath the contents of her safe, which is secured with a combination lock, to her five sons, but she is suspicious of each of them. She fears that if she reveals the code to just one, he will make off with the contents. So she wants to give each son a clue such that only the five working together can open the safe. How should the woman proceed?
The task may seem simple. For example, if the combination lock required a five-digit code, she could give each son a number so that they could open it together. But in that scenario, if three sons teamed up, they could likely bypass their two other brothers. Three allies are only two numbers short of the entire code, so they could quickly try out the possible number combinations to get to the coveted contents.
The woman is therefore looking for a way to distribute information that can only be used if all five work together. If two, three or four of the five sons get together, the combined information content must be useless. And that requirement makes the task much more complex.
But in 1979 this challenge did not discourage Shamir. Two years earlier he had developed the so-called “RSA algorithm” together with Ron Rivest and Leonard Adleman. It was the first asymmetric encryption algorithm to be widely adopted, and it is still used today.
[Read more about encryption]
Shamir’s Secret Sharing in Action
To understand the Shamir secret-sharing method, it helps to look at a concrete numerical example. Suppose the woman’s secret code is 43953, and, for the sake of simplicity, let’s assume she only has two sons. (We’ll work our way up to the situation with five sons later.)
If the woman were to entrust one son with “439” and the other with “953,” she would have given the two of them the same amount of information. Now, as explained above, the sons could each try to guess the missing two digits. They would only have to try a maximum of 100 combinations each to open the safe.
Shamir therefore needed a different solution. It would be best if each sons received a piece of information that at first glance had nothing to do with the solution. But if you put the two pieces of information together, you should be able to deduce the number combination 43953. And there is an elegant, simple way to do this with the help of a linear equation.
Each straight line is uniquely defined by two points. Shamir realized that the secret number can be encoded in a straight line: for example, as the height at which it intersects the y axis. If you give the two sons the coordinates of one point each on the straight line, they can only determine the number 43953 together. One of the sons cannot do anything with a single point alone: there are an infinite number of straight lines that run through a single point.
The woman could, for example, choose the equation of the line y = 5x + 43953 and give the eldest son the coordinates for a point P1 (33503, 211468) and the other son the coordinates for a second point, P2 (85395, 470928). Even if the two sons are bad at math, they can simply mark the two points in the plane, connect them with a ruler and then read off the point at which the straight line intersects the y axis for the solution to the safe.
So the problem is solved for two sons. If the woman has three sons, she could proceed in a similar way. In this case, however, she would not choose a straight line but rather a parabola to hide the code.
For example, the woman can choose the quadratic function y = 5x2 + 10x + 43953 and give each of her sons a point on the parabola. Again, the point of intersection with the y axis corresponds to the desired solution: 43953. Two of the sons can’t conspire against the third because an infinite number of parabolas can run through two points; the two sons need the help of their brother to find the point of intersection with the y axis and thus the code to the safe.
The principle can be generalized for any number of parties: A woman with four sons can solve an equation of the type y = ax3 + bx2 + cx + 43953. (Because 3 is the highest exponent in this equation, it is called a polynomial equation of the third degree.) A woman with five sons uses a polynomial equation of the fourth degree (such as y = ax4 + bx3 + cx2 + dx + 43953), and so on. The principle is based on so-called polynomial interpolation: in general, n + 1 points are required to uniquely determine a polynomial of the nth degree.
The woman can also give her sons access to the safe in pairs. In this case she relies on the sons controlling each other such that two out of five people need to be present to open the safe. To do this, the woman can again choose a straight line as a base and mark five randomly selected points on it. By giving each son a point, she ensures that two of them can determine the code—regardless of which two of the sons meet.
But there’s a catch. Let’s return to the scenario with the five sons. If four of them conspire against a brother, they can use the four points to solve the fourth-degree equation as far as possible. Of course, they can’t read the code directly from it. In the end they are left with an equation with two unknowns: a parameter a and the code c (which in our example is 43953, but the sons don’t know that).
The four sons know that c must be an integer, however. And if, for example, the woman has always given them integer coordinates for the points on the curve, then they can assume that a probably also has an integer value. This considerably restricts the range of possibilities. The brothers can use a computer program to try out different solutions—and might then determine the correct code.
Into a Different Number Range
To avoid such a scenario, Shamir had another trick up his sleeve: instead of calculating with the usual real numbers, he restricted himself to a smaller number space: a finite field. In this number system, the four basic arithmetic operations (addition, multiplication, subtraction and division) can be applied as usual. Instead of an infinite number of numbers, however, this number space only contains a finite number of them.
Though that may sound unfamiliar, we use finite fields every day—for example, whenever we look at the clock. If you only look at the hours, the number range comprises either 12 or 24 numbers. But we still calculate in this limited space: if it’s 11 P.M. and someone says that the bakery opens in seven hours, then it’s clear that they mean six o’clock.
In Shamir’s secret sharing, a restricted number range is also chosen, but the upper limit is usually a large prime number. If the number space is chosen in this way, the graph of a polynomial no longer corresponds to a continuous curve but to randomly distributed points in the plane.
By limiting the woman’s calculations to such a number range, it is practically impossible for the brothers to conspire against each other. To find out the correct numerical code, they have to work together.
This article originally appeared in Spektrum der Wissenschaft and was reproduced with permission.
