What are the millionaire problems of math

Researchers at ETH Zurich have shown that there is no absolutely secure exchange of data in procedures such as online auctions. Not even if one uses the ingenious means of quantum physics to help. The scientists are thus answering an old question and pointing the way that their discipline should follow in the future.

Anyone who has ever participated in an online auction knows from their own experience: You submit your bid, whereby the amount offered and the details of yourself should remain anonymous. The question that arises is: is absolute confidentiality possible in such an exchange of information? After all, you can't completely trust the auction house's servers. Therefore, an auction, in the simplest case between only two bidders without the auction house as a counterpart, would be fundamentally more secure. But how can you even guarantee the secure exchange of data between the bidders?

The Chinese computer scientist Andrew Yao asked himself this question 30 years ago. Since then, researchers have summarized this type of question under the concept of the millionaire problem: Two wealthy people want to compare their possessions without the other party knowing how much they own. In the jargon of mathematics, one speaks in this context of the reliable two-party calculation of a function. The function would use the inputs of the two bidders to perform a calculation and output the result to both parties. In the case of the online auction, the calculation is simply to compare the two bids and return the higher bid as the result.

Quantum encryption

With the means that classical physics provides for the encryption of information, the secure exchange of information is already hopeless. With a sufficiently sophisticated decryption process it will always be possible to steal the data. It is different when one uses quantum mechanics. With their help, eavesdropping attacks can be detected in certain situations. With so-called quantum cryptography, for example, it is possible for two parties to exchange a code for encrypting and decrypting a message without a third party being able to overhear it unnoticed. This is possible, for example, if you send the code via light quanta (photons).

Millionaires with exchange problems

Can quantum physics also help to reliably calculate which of two millionaires earns more or which auction bid is the highest? To illustrate the thought experiment, we introduce two virtual millionaires: Alice and Bob. Both want to find out who is richer. Bob could tell Alice how much money he has in his account. Alice checks to see if Bob's fortune is greater than her own and answers him by only disclosing whether she has more or less money than Bob. Only then did Bob reveal how much he owned.

"This approach is admittedly quite naive," says Matthias Christandl, professor of quantum information theory and co-author of a new study that was published in the journal Physical Review Letters. The question now is, is there any other, smarter way to solve this problem without Bob having to reveal everything about his possessions. "We have now been able to provide mathematical proof that this is not the case - not even with the help of quantum mechanics, even if Alice and Bob can send each other photons."

For the special case of an online auction, this means that there cannot be one hundred percent security when exchanging data. A party interested in our data is in any case not prevented by the laws of physics from "looking into our cards" unnoticed.

Limits and new horizons

The present result for secure computation thus shows the limits of communication with quanta, but it also shows the path that future investigations in quantum cryptography should take. The work shows that every promising exchange protocol between two untrustworthy communication partners must be at least partially dependent on quantum mechanical coincidence. This important role of chance is also suggested by other recently published work.

A typical problem that occurs in this context is the quantum mechanical generation of random numbers. Many computer simulation methods that are essential for science, such as the Monte Carlo method, are based on the generation of real random numbers. “Our work confirms that quantum cryptography can show its strengths precisely when it comes to these coin tossing tasks, i.e. when it comes to generating random numbers. In this direction, a further field of research for quantum cryptography will open up in the future, ”emphasizes Christandl.


Buhrman H, Christandl M, Schaffner C: Complete Insecurity of Quantum Protocols for Classical Two-Party Computation. Physical Review Letters, 2012, 109: 160501, DOI: 10.1103 / physrevlett.109.160501