Each of n persons draws a card from a shuffled deck of $k$ cards numbered from $1$ to $k$. There are at least as many cards as persons. The winner is the person who is holding the largest card. If everyone is honest, how can they mutually determine the identity of the winner, without any person learning additional information beyond that which can necessarily be inferred from $n$, $k$, the value of that person's own card, and the identity of the winner? In the general situation with $k \gg n$ for any person this information includes the values of all cards except for the one held by that person, and also the relative value of any two non-winning persons' cards. If this is not possible, in what ways can this information be minimized?
Mental card game
-
0Great answers so far! It will take me some time to research and follow-up. This question is related to another one that I posted on mathoverflow: http://mathoverflow.net/questions/35567/zero-knowledge-proof-of-positivity – 2010-08-26
4 Answers
It seems to me that this puzzle as stated can be resolved by a public counter that counts down from $n$ to $n - k$ in even time steps, each of which is longer than every player's reaction time. Each player intends to stop the counter when it displays a value equal to or lower than the player's own card; whoever first stops the counter is the winner. This does not seem to reveal anything that is not already available from $n$, $k$, and the value of the winner's card.
Obviously this is impracticable when $n \gg k$, but even then one could have the time count down in sufficiently large increments to be physically feasible. When the number of steps is substantially larger than $k$ this would still have a good chance of identifying the winner. Apparent ties in this procedure could be resolved by a quick run-off using the same technology (keeping the players in the runoff anonymous), giving an almost certain procedure to find a unique winner correctly.
-
0I hadn't realized the question can still be read so ambiguiously. – 2010-09-06
If any person pulls the $k$ value card, they immediately identify themselves.
Should this not happen, after a second the individual with the $k-1$ card identifies himself. Similarly, the $k-t$ person identifies himself after $t$ seconds if no one has been identified previously. On this strategy, it would take at most $k-n$ seconds for someone to identify himself as the highest card holder, with no other information being passed besides everyone aware the value of highest card is $k-n$ and who drew it.
-
0I was thinking of the one where a missionary tells them they all have either blue or brown eyes. That solution also involves a protocol where the most common action is to increment a counter and communicate nothing. – 2010-08-22
If I understand your question correctly, your problem can be seen as a multi-party extension of the Millionaires' problem. In the Millionaires' problem problem, two millionaires want to know which of them is richer without revealing their wealth. There is an secure two-party protocol (due to Andy Yao, 1982), and there may be even more sophisticated algorithms around these days. Maybe a simple extension of this protocol will solve your problem (every peer talks to everybody else to lean that the other guy has a higher card). However, I don't know if this simple extension is still secure.
EDIT: After looking over Yao's paper I realize that he is also already addressing the multi-party problem. So you should find your solution in his paper, or follow some of the references given in this article at Wikipedia. Of course, the recent homomorphic encryption scheme will also solve your problem, as has been pointed out by user Moron before. However, since the homomorphic encryption scheme is very general, it might be a little bit too complicated for your problem at hand if you are looking for a practical scheme.
-
0Great answer, I will enjoy trying to implement this scheme. – 2010-08-31
You should be able to use a Fully Homomorphic Encryption Scheme which was recently proved to be possible by Craig Gentry from IBM (and was an important open problem in cryptography till 2009!)
Using a fully homomorphic scheme, any circuit can be evaluated homomorphically, effectively allowing computation on encrypted input without having to decrypt it.
To use it in your case, each can encrypt their card value and do a homomorphic comparison (for instance see this: http://portal.acm.org/citation.cfm?id=1356047, caveat: I have only read the abstract). We can find out the person with the greatest value (or sort them in order) without having to divulge any non-encrypted information.
Of course, this is still theoretical, it might be a while before this becomes practical.
See the wiki page for more details.