The laws of physics have been helping to keep sensitive information secret for well over a decade, with banks and other organizations using quantum cryptography to carry out very secure communications. But new research shows that special relativity can also be exploited to guarantee secrecy.
Scientists in Canada and Switzerland have shown that someone can prove their identity without having to provide a personal identification number (PIN) or other information that could potentially be stolen by hackers. They did so using two devices made from off-the-shelf electronics to carry out what is known as a zero-knowledge proof – finding that they could answer each of a series of questions designed to root out imposters in less time than it takes for light to travel between the two devices.
Anyone withdrawing money from a cash machine may think that their PIN ensures the transaction’s security. In reality, however, the PIN itself is vulnerable to fraudsters – who, either by planting a fake machine or tampering with an existing one, can capture the code and use it to remove money from a bank account.
Quantum threat
Zero-knowledge proofs remove this vulnerability by convincing authentication software that a problem can be solved without having to reveal the underlying secret proof. This is currently done by using what are known as one-way functions, such as factoring a huge number into two huge prime numbers, which are assumed to be trivial to evaluate but very hard to solve. While this works very well today, quantum computers could someday solve such problems, raising doubts about the future security of this technique.
The latest research avoids this approach by using multiple physically distant “provers” to independently persuade one or more “verifiers”. This is similar to the police interrogation technique of interviewing several individuals in separate rooms at the same time to make it difficult for the individuals to lie collectively.
First proposed by scientists in the mid-1980s, this approach revolves around graphs – collections of interconnected nodes lying on a plane. The provers’ task is to convince the verifiers without providing proof that a graph with a certain set of nodes and connecting lines is “three-colourable”. This means that when each node can have just one of three colours, no two nodes of the same colour will be connected.
Provers and verifiers
The process involves two pairs of provers and verifiers, with the provers providing the graph and then answering a series of questions simultaneously from their respective verifiers. They can convince the verifiers that the graph is three-colourable only if they always respond with different answers when asked for the colour of nodes at opposite ends of a given line, while always agreeing on the colour of a common node at the intersection of two different lines.
The crucial condition underpinning the protocol is that each question and answer be completed in less time than it would take the two provers to communicate with one another – making them unable, when asked enough questions, to generate the “right” answers in the absence of a three-colourable graph. This time limit is determined by special relativity, which stipulates that no signal can travel faster than the speed of light.
Previous protocols could not meet this requirement over any reasonable distance as they required too much information to be communicated between each prover and verifier. But Claude Crépeau and colleagues at McGill University in Montreal have devised a new, more efficient protocol, which Hugo Zbinden and co-workers at the University of Geneva have now put into practice.
As they report in Nature, the researchers demonstrated their scheme using provers and verifiers made from field-programmable gate-arrays and other commercially available components. They performed two tests, showing that within about a second they could complete the roughly half a million rounds of questions needed to ensure a correct verdict. One test used GPS signals to synchronize the prover-verifier pairs over a distance of 390 m, while the other reduced the separation to just 60 m by employing an optical-fibre link.
Still too far
The researchers acknowledge that 60 m is still too far for many practical applications, but reckon that improved communication and chip technology could reduce the distance to around a metre. At that point, they say, a user could insert a pair of cards into ports on either side of a bank machine, having first activated them via thumbprint recognition. Convinced that the cards – or perhaps ultimately mobile phones – contain data from a three-colourable graph, the machine would then complete the transaction.
Fast quantum random number generator could advance cryptography on the cheap
Gilles Brassard of the University of Montreal, who was not involved in the research, points out in an accompanying “News and views” article in Nature that fraudsters might in future try and breach security by using quantum entanglement – exploiting instantaneous correlations between devices to avoid the three-colour problem. As such, he argues, more research is needed “before these ideas can find their way to your local bank”.
Adrian Kent of the University of Cambridge in the UK agrees that further work is required – both to increase device speed and to guard against powerful quantum computers. But he nevertheless sees the research as “a significant step towards a practical real world application of relativistic cryptography” – adding that plausible future applications of the technology include electronic payments and voting.
