How Cryptographic โSecret Sharingโ Can Keep Information Safe
One safe, five sons and betrayal: this principle shows how shared knowledge can protect secretsโwithout having to trust anyone
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.
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.
To understand how AI is contributing to climate change, look at the way itโs being used
Artificial intelligence is not limited to entertaining chatbots: increasingly effective programs trained with machine learning have become integral to uses ranging from smartphone GPS navigators to the algorithms that govern social media. But as AIโs popularity keeps rising, more researchers and experts are noting the environmental cost. Training and running an AI system requires a great deal of computing power and electricity, and the resulting carbon dioxide emissions are one way AI affects the climate. But its environmental impact goes well beyond its carbon footprint.
โIt is important for us to recognize the CO2ย emissions of some of these large AI systems especially,โ says Jesse Dodge, a research scientist at the Allen Institute for AI in Seattle. He adds, however, that โthe impact of AI systems in general is going to be from the applications theyโre built for, not necessarily the cost of training.โ
The exact effect that AI will have on the climate crisis is difficult to calculate, even if experts focus only on the amount of greenhouse gases it emits. Thatโs because different types of AIโsuch as a machine learning model that spots trends in research data, a vision program that helps self-driving cars avoid obstacles or a large language model (LLM) that enables a chatbot to converseโall require different quantities of computing power to train and run. For example, when OpenAI trained its LLM called GPT-3, that work produced the equivalent of around 500 tons of carbon dioxide. Simpler models, though, produce minimal emissions. Further complicating the matter, thereโs a lack of transparency from many AI companies, Dodge says. That makes it even more complicated to understand their modelsโ impactโwhen they are examined only through an emissions lens.
This is one reason experts increasingly recommend treating AIโs emissions as only one aspect of its climate footprint. David Rolnick, a computer scientist at McGill University, likens AI to a hammer: โThe primary impact of a hammer is what is being hammered,โ he says, โnot what is in the hammer.โ Just as the tool can smash things to bits or pound in nails to build a house, artificial intelligence can hurt or help the environment.
Take the fossil-fuel industry. In 2019 Microsoft announced a new partnership with ExxonMobil and stated that the company would use Microsoftโs cloud-computing platform Azure. The oil giant claimed that by using the technologyโwhich relies on AI for certain tasks such as performance analysisโit could optimize mining operations and, by 2025, increase production byย 50,000 oil-equivalent barrels per day. (An oil-equivalent barrel is a term used to compare different fuel sourcesโitโs a unit roughly equal to the energy produced by burning one barrel of crude oil.) In this case, Microsoftโs AI is directly used to add more fossil fuels, which will release greenhouse gases when burned, to the market.
In a statement emailed to Scientific American, a Microsoft spokesperson said the company believes that โtechnology has an important role to play in helping the industry decarbonize, and this work must move forward in a principled mannerโbalancing the energy needs and industry practices of today while inventing and deploying those of tomorrow.โ The spokesperson added that the company sells its technology and cloud services to โall customers, inclusive of energy customers.โ
Fossil-fuel extraction is not the only AI application that could be environmentally harmful. โThereโs examples like this across every sector, like forestry, land management, farming,โ says Emma Strubell, a computer scientist at Carnegie Mellon University.
This can also be seen in the way AI is used in automated advertising. When an eerily specific ad pops up on your Instagram or Facebook news feed, advertising algorithms are the wizard behind the curtain. This practice boosts overall consumptive behavior in society, Rolnick says. For instance, with fast-fashion advertising, targeted ads push a steady rotation of cheap, mass-produced clothes to consumers, who buy the outfits only to replace them as soon as a new trend arrives. That creates a higher demand for fast-fashion companies, and already the fashion industry is collectively estimated toย produce up to eight percentย of global emissions. Fast fashion produces yet more emissions from shipping and causes more discarded clothes to pile up in landfills. Meta, the parent company of Instagram and Facebook, did not respond toย Scientific Americanโs request for comment.
But on the other side of the coin there are AI applications that can help deal with climate change and other environmental problems, such as the destruction wrought by severe heat-fueled hurricanes. One such application is xView2, a program that combines machine-learning models and computer vision with satellite imagery to identify buildings damaged in natural disasters. The program was launched by the Defense Innovation Unit, a U.S. Department of Defense organization. Its models can assess damaged infrastructure, thereby reducing danger and saving time for first responders who would otherwise have to make those assessments themselves. It can also help search-and-rescue teams more quickly identify where to direct their efforts.
Other AI technologies can be applied directly to climate change mitigation by using them to monitor emissions. โIn the majority of the world, for the majority of climate change emissions, itโs very opaque,โ says Gavin McCormick, executive director of WattTime, a company that monitors electricity-related emissions. WattTime is a founding partner of the nonprofit organization Climate TRACE, whose platform combines computer vision and machine learning to flag emissions from global pollution sources. First, scientists identify the emissions coming from monitored facilities. Then they use satellite imagery to pinpoint visual signs of the emission-causing activitiesโsteam plumes from a factory, for example. Next, engineers train algorithms on those data in order to teach the programs to estimate emissions based on visual input alone. The resulting numbers can then help corporations determine to lower their emissions footprint, can inform policymakers and can hold polluters accountable.
As AI becomes more efficient at solving environmental problems, such as by helping to lower emissions, it could prove to be a valuable tool in the fight against climate changeโif the AI industry can reduce its negative climate impacts. โFrom the policy standpoint, both AI policy and climate policy have roles to play,โ Rolnick says. In particular he recommends shaping AI policy in a way that considers all angles of its impact on climate. That means looking at its applications as well as its emissions and other production costs, such as those from water use.
Further, Dodge adds that those with expertise in AI, particularly people in power at tech companies, should establish ethical principles to limit the technologyโs use. The goal should be to avoid climate harm and instead help reduce it. โIt needs to be part of the value system,โ he says.
