Yao’s Millionaire Problem
November 18, 2011, 4:27 pm
Filed under: Uncategorized | Tags: , , ,

In this post, I want to talk about a research problem that I think even our new Republican legislatures can get excited about: Yao’s millionaire problem.  In this problem, two millionaires want to determine who is richer, but neither wants to reveal their private net worth.  Can we develop a protocol to help these millionaires?  This problem is important  because it kicked off the the study of secure multiparty computation.

Below is a picture of the protocol originally proposed by Yao.  Alice and Bob are the two millionaires and i and j are the private net worths of Alice and Bob respectively.  The protocol makes use of public key cryptography: Alice is assumed to be able to generate a public encryption key E_a() along with a private decryption key D_a().  To see that the protocol reveals who is richer, note that y_j = D_a(k) = x.  Thus w_j = x if j<= i and w_j = x+1 if j>i.  Showing that the protocol doesn’t reveal any information beyond who is richer is more challenging and is presented in detail in  the paper.



I should point out that this protocol takes exponential time and that this run time has been improved in subsequent papers.  However, there is a question about this problem I haven’t been able to answer.  In the case where there are n players, do we need private channels or cryptographic assumptions to solve the problem?  Are private channels needed even if we’re happy with a Monte Carlo solution?  I’ve seen several papers that remove cryptographic assumptions, but none that seem to remove the need for private channels.  Conversely, I’ve seen no papers that prove that private channels are necessary…


Leave a Comment so far
Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: