Revolutionary identity verification technique offers robust solution to hacking

"Current identification schemes that use personal identification numbers (PINs) are incredibly insecure faced with a fake teller machine that stores the PINs of users," says Crépeau, a professor in the School of Computer Science at McGill. "Our research found and implemented a secure mechanism to prove someone's identity that cannot be replicated by the verifier of this identity."

How to prove you know something without revealing what it is you know

The new method, published in Nature, is an advance on a concept known as zero-knowledge proof, whereby one party (a 'prover') can demonstrate to another (the 'verifier') that they possess a certain piece of information without actually revealing that information.

The idea of zero-knowledge proof began to take hold in the field of data encryption in the 1980s. Today, many encryption systems rely on mathematical statements which the prover can show to be valid without giving away clues to the verifier as to how to prove the validity of the statement. Underlying the effectiveness of these systems is an assumption that there is no practical way for the verifier to work backwards from the information they do receive from the prover to figure out a general solution to the problem. The theory goes that there is a certain class of mathematical problem, known as one-way functions, that are easy for computers to evaluate but not easy for them to solve. However, with the development of quantum computing, scientists are beginning to question this assumption and are growing wary of the possibility that the supposed one-way functions underlying today's encryption systems may be undone by an emerging generation of quantum computers.

Separating witnesses to get the story straight

The McGill-Geneva research team have reframed the zero-knowledge proof idea by creating a system involving two physically separated prover-verifier pairs. To confirm their bona fides, the two provers must demonstrate to the verifiers that they have a shared knowledge of a solution to a notoriously difficult mathematical problem: how to use only three colours to colour in an image made up of thousands of interconnected shapes such that no two adjacent shapes are of the same colour.

"The verifiers randomly choose a large number of pairs of adjacent shapes in the image and then ask each of the two provers for the colour of one or the other shape in each pair," explains co-author Hugo Zbinden, an associate professor of applied physics at the University of Geneva.

If the two provers consistently name different colours in response, the verifiers can be assured that both provers do indeed know the three-colour solution. By separating the two provers physically and questioning them simultaneously, the system eliminates the possibility of collusion between the provers, because to do so they would have to transmit information to each other faster than the speed of light -- a scenario ruled out by the principle of special relativity.

"It's like when the police interrogate two suspects at the same time in separate offices," Zbinden says. "It's a matter of checking their answers are consistent, without allowing them to communicate with each other."