Trust and verification. This expression summarizes the tension between relying on others and the desire to maintain a level of control over the situation. Athlete Adi Shamir must have thought about this challenge when he developed what is now known as the “Adi Shamir Secret Sharing” algorithm, which bears his name.
Adi Shamir Secret Sharing Principle
To understand it, the following puzzle can help: suppose an elderly woman wants to bequeath the contents of her safe, which is protected by a complex lock, to her five children, but she is suspicious of each one. She fears that if she reveals the code to one of them, he will take the contents and flee with them. Thus, she wants to give each child a clue that only the five can work together to unlock the safe. How should the woman act?
Adi Shamir Secret Sharing Solution
The task may seem simple. For example, if the complex lock requires a five-digit code, she could give each child a number so they can unlock it together. But in this scenario, if three of the children cooperate, they can outsmart the other two siblings. Three allies only lack two numbers from the complete code, so they can quickly test possible combinations of the numbers to access the desired contents.
Therefore, the woman is looking for a way to distribute the information that can only be used if all five work together. If two, three, or four of the children gather, the content of the combined information should be useless. This requirement makes the task more complicated.
Application of Adi Shamir Secret Sharing
To understand the Adi Shamir Secret Sharing method, it helps to look at a specific numerical example. Suppose the woman’s secret code is 43953, and for simplicity, let’s assume she has only two children. If the woman assigns one child the code “439” and the other “953,” she has given them the same amount of information. Now, as explained above, the children could try to guess the missing two numbers. They would only need to try a maximum of 100 combinations each to unlock the safe.
Thus, Adi Shamir needed a different solution. It would be better if each child received a piece of information that does not initially appear to relate to the solution. But when the pieces of information are combined, they should be able to deduce the number combination 43953. There is a neat and simple way to do this with the help of a linear equation.
Every straight line is uniquely defined by two points. Adi Shamir realized that the secret number could be encoded in a straight line: for instance, as a height that intersects the y-axis. If he gives the children the coordinates of one point on the line, they can determine the number 43953 together. No one child can do anything with just one point alone: there are infinitely many lines that can pass through a single point.
The woman, for example, could choose the line equation y = 5x + 43953 and give the elder child the coordinates for point P1 (33503, 211468) and the other child the coordinates for a second point, P2 (85395, 470928). Even if the two children are bad at math, they can simply mark the two points on a surface, connect them with a ruler, and then read the point where the straight line intersects the y-axis to get the solution for the safe.
So, the problem is solved for the two children. If the woman has three children, she can proceed in the same way. In this case, she would not choose a straight line but instead would select a quadratic piece to conceal the code.
On
For example, a woman can choose the quadratic function y = 5×2 + 10x + 43953 and give each of her children a point on the semicircular plot. Again, the intersection point with the y-axis corresponds to the required solution: 43953. Two sons cannot conspire against the third because there are infinitely many semicircular curves that can pass through two points; the sons need their brother’s help to find the intersection point with the y-axis and thus the code for the vault.
The principle can be generalized to any number of parties: a woman with four sons can solve an equation of the type y = ax3 + bx2 + cx + 43953. (Since 3 is the highest coefficient in this equation, it is called a third-degree polynomial equation.) A woman with five sons uses a fourth-degree polynomial equation (such as y = ax4 + bx3 + cx2 + dx + 43953), and so on. The principle is based on what is called polynomial interpolation: in general, it requires n + 1 points to determine a polynomial of degree two. There are infinitely many semicircular curves that pass through two points.
Involving the Sons in the Vault
A woman can also grant her sons access to the vault in pairs. In this case, she relies on the sons controlling each other so that two out of the five need to be present to open the vault. To do this, the woman can again choose a straight line as a base and randomly place five specific points on it. By giving each son a point, she ensures that two of them can determine the code – regardless of which sons meet.
But there is a problem. Let’s return to the scenario with the five sons. If four of them conspire against their brother, they can use the four points to solve the fourth-degree equation as best as they can. Of course, they cannot read the code directly from it. In the end, they are left with an equation with two unknowns: coefficient a and code c (which in our example is 43953, but the sons do not know that).
The four sons know that c must be an integer, however. And if, for example, the woman always gives them integer coordinates for the points on the curve, they can assume that a also has an integer value. This greatly restricts the range of possibilities. The siblings can use a computer program to try different solutions – and thus they might identify the correct code.
Entering a Different Number Field
To avoid such a scenario, Shamir had another trick: instead of calculating with regular real numbers, he confined himself to a smaller range of numbers: a finite field. In this numerical system, the four basic arithmetic operations (addition, multiplication, subtraction, and division) can be applied as usual. Instead of an infinite number of numbers, this numeric range contains only a limited number of them.
Although it may seem unfamiliar, we use finite fields every day – for example, when we look at the clock. If you only look at the hours, the range of numbers consists of either 12 or 24 digits. But we still calculate in this limited range: if it is 11 PM and someone says the bakery opens in seven hours, it is clear that they mean 6 AM.
In Shamir’s secret splitting, a limited numeric range is also chosen, but the upper limit is usually a large prime number. If the numeric range is chosen in this way, the graph of the polynomial equation no longer corresponds to a continuous curve but to points randomly distributed on the surface. When defining a polynomial equation in a finite field, the smooth curve becomes a set of points.
From
During the restriction of women’s accounts in such a numerical range, it is nearly impossible to conspire against each other. To know the correct numerical code, they must work together.
This article originally appeared in Spektrum der Wissenschaft and has been reproduced with permission.
Source: Manon Bischoff
Leave a Reply