Home > Math News Archive Detail

<< Prev 2/23/2014 Next >>

The Millionaires Problem Plus...

You probably have not heard of Andrew Chi-Chih Yao, a Chinese-born American computer scientist and computational theorist. Currently, Yao at age 66 is the Distinguished Professor-at-Large in the Chinese University of Hong Kong.

In a 1982 paper, Yao created a subfield of cyptography known as "secure computation." Given an arbitrary function, the goal is allow two people to jointly compute a function f(x1, x2) using their respective inputs, but without revealing these inputs.

In his paper, Yao introduced the "millionaire problem," which involves two millionaires who want to know who is the richest without letting the other person know their actual wealth. How would you do this...where having both of them tell their wealth numbers to a third party is not considered "secure"?

Yao's work actually is an extension of another interesting problem: How several people can play poker over a telephone? Important shared-but-trusted information includes shuffling the card deck, dealing a card, revealing cards, and knowing that the other player(s) can be trusted.

This poker problem was solved by Shamir, Rivest, and Adleman in 1981. You may not recognize their names, but may recognize their initials via the valuable RSA algorithm for encypting data with a public key.

Mathematics lies a the base of secure computation. In turn, both mathematics and secure computation become more valuable because the latter has recently moved from "theoretically interesting" to "practical." It is now being used in e-commerce, data mining, remote auction bidding...wherever one needs to compute numbers from diverse "secure" sources, while maintaining the confidentiality and security of the data.

Isn't mathematics great....as new uses of it are constantly being revealed?