To combat hacking, researchers created a new system based on the concept of ‘zero-knowledge proofs,’ the security of which is based on the physical principle of relativity, which states that information cannot move faster than the speed of light. As a result, one of the fundamental principles of contemporary physics enables secure data transit.
The amount of data sent is increasing all the time, but the absolute security of these exchanges cannot be guaranteed, as evidenced by hacking cases that are routinely reported in the news. To combat hacking, a team from Switzerland’s University of Geneva (UNIGE) devised a novel system based on the notion of “zero-knowledge proofs,” the security of which is based on the physical theory of relativity: information cannot move faster than the speed of light.
As a result, one of the fundamental principles of contemporary physics enables secure data transit. This technology enables users to identify themselves in total privacy without giving any personal information, and it has promising applications in the world of cryptocurrency and blockchain. These findings can be found in the journal Nature.
When a person – the so-called ‘prover’ – wants to confirm their identity, such as when withdrawing money from an ATM, they must present their personal information to the verifier, in this case, the bank, which processes this information (e.g. the identification number and the pin code). Confidentiality is guaranteed as long as only the prover and the verifier have access to this information. If others get hold of this information, for example by hacking into the bank’s server, security is compromised.
The aim is to allocate a graph to each person or client. The two prover/verifier pairings in the Geneva researchers’ experiment are separated by 60 meters to ensure they cannot communicate. However, this method may currently be utilized, for example, between two bank branches and does not require complex or costly equipment.
Nicolas Brunner
Zero-knowledge proof as a solution
To address this issue, the prover should ideally be able to validate their identity without disclosing any personal information. Is this, however, even possible? Surprisingly, the answer is affirmative, thanks to the zero-knowledge proof notion. “Assume I want to demonstrate a mathematical theorem to a coworker. If I show them the steps of the proof, they will be persuaded, but they will then have access to all of the information and will be able to easily reproduce the proof “explains Nicolas Brunner, a professor at the UNIGE Faculty of Science’s Department of Applied Physics.
“On the contrary, with a zero-knowledge proof, I will be able to convince them that I am aware of the proof without divulging any information about it, so prohibiting any conceivable data retrieval.”
The zero-knowledge proof principle, established in the mid-1980s, has been used in recent years, most notably for cryptocurrencies. However, their implementations have a flaw because they are based on a mathematical assumption (that a specific encoding function is difficult to decode). If this assumption is proven incorrect – which cannot be ruled out right now – security is jeopardized since the data becomes available.
Today, the Geneva team is presenting in practice a radically different system: a relativistic zero-knowledge proof. Instead of a mathematical hypothesis, security is founded on a physics idea, the principle of relativity. The principle of relativity, which states that information cannot move faster than the speed of light, is a pillar of modern physics that is unlikely to be disputed. As a result, the Geneva researchers’ protocol provides complete security and is assured in the long run.
Dual verification based on a three-colorability problem
A relativistic zero-knowledge proof requires two distant verifier/prover pairings and a difficult mathematical issue to implement. “A three-colorability issue is used. This type of problem is represented by a graph, which is made up of a set of nodes that are connected or not by links” Hugo Zbinden, professor at UNIGE’s Department of Applied Physics, explains. Each node is assigned one of three colors: green, blue, or red, and nodes that are linked together must be of different colors. These three-coloring issues, with 5,000 nodes and 10,000 linkages, are practically hard to solve because all alternatives must be explored. So why do we need two checker/prover pairs?
“To authenticate their identification, the provers will no longer have to supply a code, but will have to demonstrate to the verifier that they know how to three-color a specific graph,” Nicolas Brunner says. To be sure, the verifiers will select a large number of pairs of nodes connected by a link at random, then ask their respective prover what color the node is. Because this verification is done virtually simultaneously, the provers are unable to communicate with one another during the test and hence cannot cheat.
As a result, if the two colors disclosed are always different, the verifiers are sure of the provers’ identity, because they are aware of a three-coloring of this graph. “It’s like when the police interview two criminals in separate offices at the same time: it’s a matter of confirming that their answers match, without enabling them to contact with each other,” Hugo Zbinden explains. Because the inquiries are virtually simultaneous in this situation, the provers are unable to interact with one another because this information would have to travel faster than light, which is obviously impossible.
Finally, to prevent the verifiers from reproducing the graph, the two provers constantly change the color code in a correlated manner: what was green turns blue, blue turns red, and so forth. “In this way, the evidence is made and validated without giving any knowledge about it,” says the physicist from Geneva.
A reliable and ultra-fast system
In practice, this verification is performed millions of times in less than three seconds. “The aim is to allocate a graph to each person or client,” Nicolas Brunner explains. The two prover/verifier pairings in the Geneva researchers’ experiment are separated by 60 meters to ensure they cannot communicate. “However, this method may currently be utilized, for example, between two bank branches and does not require complex or costly equipment,” he explains.
However, the research team predicts that this distance will be lowered to one metre in the very near future. This relativistic zero-knowledge proof system would guarantee total data processing security and could not be compromised whenever a data transfer was required. “In a few seconds, we would guarantee absolute confidentiality,” concludes Hugo Zbinden.
