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
-
0For example, when n = k, the holder of card k simply identifies himself. – 2010-08-21
-
0Is there any such thing as a one-way-function F which is also an order-preserving mapping? If so then everyone can compute F(x_i), and then use Joshua's method with that value instead of x_i itself. But I do not know of any such one-way function. – 2010-08-22
-
0In this instance, your example does not satisfy the entire criterion either as the holder of card k simply identifying himself reveals information. Are we interested in pursuing a statistical strategy where the individual with the highest card value is identified with high probability? – 2010-08-22
-
0Yes, my example is trivial because when n = k everyone already knows that the highest dealt card has value k, even before any are dealt. Also yes I am interested in average-case solutions as well as worst-case ones, and I am also allowing that there is a time constraint which makes sufficiently hard problems equivalent to unsolvable ones. (Suppose that after a certain amount of time all cards are to be revealed anyway. We wish to know the winner before this time, without knowing anything else before this time.) – 2010-08-22
-
0Ahh yes, I see. – 2010-08-22
-
0There is no one-way function like I described because it could be inverted in a logarithmic number of comparison queries using binary search. So that idea is wrong but could there be some other cryptographic solution? – 2010-08-22
-
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 was asking for a method that does not reveal the value of the winner's card. – 2010-09-06
-
1@Dan: I simply did not interpret the problem the way you apparently intended, due to an ambiguity in English. Where you wrote "without any person learning additional information beyond that which can necessarily be inferred from n, k, the identity of the winner, and the value of that person's own card," I understood "that person" to refer to the *immediately preceding* person, namely the "winner." I hope you weren't the one who downvoted my response, which was offered in a constructive spirit and--whether wrong or right--suggests alternative approaches to analyzing the problem. – 2010-09-06
-
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.
-
2I am asking for a solution where the value of the highest card (as well as all other cards) remains unknown to the maximum extent permitted. All that should become known when k >> n is the identity of the person who holds it. – 2010-08-21
-
3@Dan: you should probably indicate that in the original question, then. – 2010-08-21
-
0I tried to by qualifying with "additional". What is the best way to say this clearly? – 2010-08-21
-
0Great answer anyway, it makes me wonder if this can be related to the islander puzzle? – 2010-08-22
-
0@Dan: the problematic word for me in the question is "others," which I take to mean the value of the cards held by anyone other than who holds the highest card. But you don't want any additional information about _anyone's_ card to be known, including the holder of the highest card. – 2010-08-22
-
0It is the same solution as to the island puzzle where at least one husband has been unfaithful. – 2010-08-22
-
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.