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?
$\begingroup$
$\endgroup$
7
asked Aug 21, 2010 at 22:09
-
$\begingroup$ For example, when n = k, the holder of card k simply identifies himself. $\endgroup$– Dan BrumleveCommented Aug 21, 2010 at 22:39
-
$\begingroup$ Is 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. $\endgroup$– Dan BrumleveCommented Aug 22, 2010 at 0:57
-
$\begingroup$ In 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? $\endgroup$– Joshua Shane LibermanCommented Aug 22, 2010 at 1:05
-
$\begingroup$ Yes, 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.) $\endgroup$– Dan BrumleveCommented Aug 22, 2010 at 1:14
-
$\begingroup$ Ahh yes, I see. $\endgroup$– Joshua Shane LibermanCommented Aug 22, 2010 at 1:18
|
Show 2 more comments
4 Answers
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ Great answer, I will enjoy trying to implement this scheme. $\endgroup$ Commented Aug 31, 2010 at 22:19
$\begingroup$
$\endgroup$
7
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.
answered Aug 21, 2010 at 23:45
-
2$\begingroup$ I 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. $\endgroup$ Commented Aug 21, 2010 at 23:53
-
3$\begingroup$ @Dan: you should probably indicate that in the original question, then. $\endgroup$ Commented Aug 21, 2010 at 23:54
-
$\begingroup$ I tried to by qualifying with "additional". What is the best way to say this clearly? $\endgroup$ Commented Aug 21, 2010 at 23:55
-
$\begingroup$ Great answer anyway, it makes me wonder if this can be related to the islander puzzle? $\endgroup$ Commented Aug 22, 2010 at 0:05
-
$\begingroup$ @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. $\endgroup$ Commented Aug 22, 2010 at 0:09
$\begingroup$
$\endgroup$
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.
answered Aug 25, 2010 at 5:09
$\begingroup$
$\endgroup$
3
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.
-
$\begingroup$ I was asking for a method that does not reveal the value of the winner's card. $\endgroup$ Commented Sep 6, 2010 at 2:07
-
1$\begingroup$ @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. $\endgroup$– whuberCommented Sep 6, 2010 at 16:35
-
$\begingroup$ I hadn't realized the question can still be read so ambiguiously. $\endgroup$ Commented Sep 6, 2010 at 18:39