Nature does not allow secure computation between rivals

It is impossible to devise a cryptographic system that guarantees secure computation between two rivals. Researchers of Centrum Wiskunde & Informatica (CWI), University of Amsterdam (UvA) and ETH Zürich prove this in an article in Physical Review Letters that appeared on October 17. This was already known for classical communication, but the researchers prove that even with the use of quantum communication, devising a fundamentally secure cryptographic protocol is not possible.

Secure computation between two mutually distrusting parties is a fundamental problem in modern-day cryptography. A famous example is the millionaire problem. Two millionaires want to find out which one of them is the richest, without disclosing their wealth to each other. Is there a secure protocol that they can follow to calculate who is the richest?

Impossible, according to Harry Buhrman (CWI), Christian Schaffner (UvA) and Matthias Christandl (ETH Zürich), one of the parties can always discover the wealth of the other by cheating. The reason lies in the fundamental laws of nature described by quantum mechanics. If the millionaires want to do their computation securely, they must therefore try to prevent this possibility to cheat. This might be done, for instance, by arranging a protocol in which cheating would require extraordinary amounts of time or computer memory.

Quantum cryptography studies the possibilities of secure digital communication by use of quantum mechanical effects. Switzerland is already using quantum cryptographic methods to secure the digital transfer of votes. Other countries are also working on similar systems. CWI is one of the front-runners in quantum cryptographic research worldwide.