Securing Data Transfers with Relativity

Today, the Geneva team is demonstrating a radically different system in practice: a relativistic zero-knowledge proof. Security is based here on a physics concept, the principle of relativity, rather than on a mathematical hypothesis. The principle of relativity – that information does not travel faster than light – is a pillar of modern physics, unlikely to be ever challenged. The Geneva researchers’ protocol therefore offers perfect security and is guaranteed over the long term.

Dual Verification Based on a Three-Colorability Problem
Implementing a relativistic zero-knowledge proof involves two distant verifier/prover pairs and a challenging mathematical problem. “We use a three-colorability problem. This type of problem consists of a graph made up of a set of nodes connected or not by links”, explains Hugo Zbinden, professor in the Department of Applied Physics at the UNIGE. Each node is given one out of three possible colours – green, blue or red – and two nodes that are linked together must be of different colours. These three-colouring problems, here featuring 5,000 nodes and 10,000 links, are in practice impossible to solve, as all possibilities must be tried. So why do we need two pairs of checker/prover?

“To confirm their identity, the provers will no longer have to provide a code, but demonstrate to the verifier that they know a way to three-colour a certain graph”, continues Nicolas Brunner. To be sure, the verifiers will randomly choose a large number of pairs of nodes on the graph connected by a link, then ask their respective prover what colour the node is. Since this verification is done almost simultaneously, the provers cannot communicate with each other during the test, and therefore cannot cheat. Thus, if the two colours announced are always different, the verifiers are convinced of the identity of the provers, because they actually know a three-colouring of this graph. “It’s like when the police interrogates two criminals at the same time in separate offices: it’s a matter of checking that their answers match, without allowing them to communicate with each other”, says Hugo Zbinden. In this case, the questions are almost simultaneous, so the provers cannot communicate with each other, as this information would have to travel faster than light, which is of course impossible. Finally, to prevent the verifiers from reproducing the graph, the two provers constantly change the colour code in a correlated manner: what was green becomes blue, blue becomes red, etc. “In this way, the proof is made and verified, without revealing any information about it”, says the Geneva-based physicist.

A Reliable and Ultra-Fast System
In practice, this verification is carried out more than three million times, all in less than three seconds. “The idea would be to assign a graph to each person or client”, continues Nicolas Brunner. In the Geneva researchers’ experiment, the two prover/verifier pairs are 60 metres apart, to ensure that they cannot communicate. “But this system can already be used, for example, between two branches of a bank and does not require complex or expensive technology”, he says. However, the research team believes that in the very near future this distance can be reduced to one metre. Whenever a data transfer has to be made, this relativistic zero-knowledge proof system would guarantee absolute security of data processing and could not be hacked. “In a few seconds, we would guarantee absolute confidentiality”, concludes Hugo Zbinden.