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. Security is jeopardized if others obtain this information, such as through hacking into the bank’s system.
Imagine I want to prove a mathematical theorem to a colleague. If I show them the steps of the proof, they will be convinced, but then have access to all the information and could easily reproduce the proof.
Professor Nicolas Brunner
Zero-knowledge proof as a solution
To counter this problem, the prover should ideally be able to confirm their identity, without revealing any information at all about their personal data. But is this even possible? Surprisingly the answer is yes, via the concept of a zero-knowledge proof. “Imagine I want to prove a mathematical theorem to a colleague. If I show them the steps of the proof, they will be convinced, but then have access to all the information and could easily reproduce the proof,” explains Nicolas Brunner, a professor in the Department of Applied Physics at the UNIGE Faculty of Science. “On the contrary, with a zero-knowledge proof, I will be able to convince them that I know the proof, without giving away any information about it, thus preventing any possible data recovery.”
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. The Geneva researchers’ protocol therefore offers perfect security and is guaranteed over the long term.
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 distinct 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 over three million times in under three seconds. “The aim would be to allocate a graph to each person or client,” Nicolas Brunner explains. The two prover/verifier pairs in the Geneva researchers’ experiment are separated by 60 meters to ensure that they cannot communicate. “However, this system is already usable, for example, between two bank branches and does not require complex or expensive equipment,” he explains. However, the research team believes that this distance can be reduced to one metre in the very near future. Whenever a data transfer is required, this relativistic zero-knowledge proof system would ensure absolute data processing security and could not be hacked. “In a few seconds, we would guarantee absolute confidentiality,” concludes Hugo Zbinden.
