Yao's Millionaires' problem
Problem in mathematics / From Wikipedia, the free encyclopedia
Yao's Millionaires' problem is a secure multi-party computation problem introduced in 1982 by computer scientist and computational theorist Andrew Yao. The problem discusses two millionaires, Alice and Bob, who are interested in knowing which of them is richer without revealing their actual wealth.
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)
|
This problem is analogous to a more general problem where there are two numbers and and the goal is to determine whether the inequality is true or false without revealing the actual values of and .
The Millionaires' problem is an important problem in cryptography, the solution of which is used in e-commerce and data mining. Commercial applications sometimes have to compare numbers that are confidential and whose security is important.
Many solutions have been introduced for the problem, including physical solutions based on cards.[1] The first solution, presented by Yao, is exponential in time and space.[2]