ATMs and crypto-asset exchanges are verifying user identities using ID numbers and passwords to protect sensitive customer assets. However, if an ATM is equipped with a skimming device or a corporate server is hacked on a large scale, personal information is leaked and security is compromised. Based on Einstein’s special theory of relativity, a Canadian and Swiss research team has devised a non-hackable method of identity verification without exchanging personal information.
The research team believes that it is effective to verify identity without disclosing personal information at all to combat identity verification security breaches such as ATMs. The idea here is an exchange method called zero-knowledge proof.
Zero-knowledge proof is an exchange method that allows you to prove that a mathematical proposition is true without giving any information other than that the proposition is true. For example, for verifier A, who cannot identify colors, there exists a prover named B, who can identify colors, so that B can identify colors.
In this case, A holds the blue and red cards in both hands and marks the cards on B to see which side is blue and which is red. Then, A hides the card behind B so that B is not visible, replaces it or pretends to replace it, and displays 2 cards to B again. And if you ask him how he changed the card before, B, who can check the color, can answer with 100% probability whether there has been a card change. One or two answers may be an accidental answer, but by repeating this question a huge number of times, it is possible to prove that B can identify colors even in A, which cannot identify colors.
Since the zero-knowledge proof was first formalized in the 1980s, it has been used in fields related to cryptographic assets. However, it is said that there is a problem that some functions cannot be decoded due to the restriction that they are based on mathematical assumptions, or that security is compromised when the mathematical assumptions that are the premises are disproved. Therefore, the research team argues that they made the zero-knowledge proof more robust based on Einstein’s special theory of relativity.
The research team used a mathematical problem called the 3-colorability problem in the zero-knowledge proof. The three-color problem is that in a graph in which one node is connected to another node with two links, each connected node is painted in a different color, such as three colors. A solution to the three-color problem in a specific graph with a large number of nodes and links has not been found and cannot be realistically solved.
The newly verified identity verification method is to give the prover a huge map painted in three colors in advance, and in the identity verification, the verifier asks the prover for the node color. The three-color problem is too complex to solve, but since the prover has the correct map in advance, it can give the correct answer to any node you ask. Also, by regularly changing things like green → blue, blue → red, and red → green, it can make it difficult for hackers to guess the map from the prover answer. In a real-world scene, a prover who wants to withdraw cash can execute this process, such as inserting a device into an ATM machine.
However, the research team points out that there is still a small possibility that the hacker inverted the map in this process, and it is not perfect. It is like adding two large primes to form a large number and decomposing it is difficult but not impossible. Therefore, based on the principle that information cannot travel faster than light in Einstein’s special theory of relativity, a method to further strengthen the zero-knowledge proof was proposed.
The technique devised by the research team is to create two pairs of validators and provers, and the validator randomly selects two adjacent nodes from the map and asks the two provers for different node colors at the same time. In a properly painted map, the color answered by the prover is necessarily different because the colors of adjacent nodes are different. Based on the principle of special relativity that information cannot travel faster than light if there is more than a certain distance between two validators, it becomes impossible to transmit information even to the answer between validators. It is a structure that guarantees the legitimacy of the answer.
The idea behind the technique, the researchers say, is like a policeman technique that interrogates two suspects in different rooms and prevents them from communicating with each other, says the researchers. In actual verification, 3 million questions are asked between the verifier and the prover in less than 3 seconds, so the possibility that the answers of the two provers coincide by chance is also excluded.
In fact, because the research team tested this concept in a state where a pair of validators and provers are more than 60 meters apart, it is said that it is possible to put it into practice without using complicated and expensive technology. In the near future, it is expected that the distance between validators can be reduced to 1m. Related information can be found here.