# Multiparty millionaire problem where members only know if they are the richest one

I'm looking for a generalisation of Yao's millionaire problem: $$N$$ parties want to know whether they are the richest one. If they are not, then they just know they are not the richest party - but do not know the identity of the richest one.

Ideally, in case of equality, all richest members would know they are the richest, but would not know if others are as rich.

Does such a protocol already exist?

Edit: obviously when there are only two users, then everyone knows who is the richest. I guess a formalization would be that not-richest people cannot guess who, amongst remaining users, is richest, with probability better than random.

There exist such constructions, for instance assume a FHE scheme which takes the encrypted values as input, and output for each party $$p_i$$ their result, encrypted with $$p_i$$'s key. While this should work (it may need some work for the encryption of the inputs but anyway), it is also extremely tedious.

• This paper by Andrew Yao apparently describes how the millionaire problem is achieved for more than two parties. Sep 9 '19 at 12:43
• @AleksanderRas yes, but in the classical setting (such as the one described in the paper), all users learn the same data: for instance who is richer. Hence, everyone knows that praty $3$ is the richest. I'd like a protocol in which each party learns something different. Namely, if they are the richest or not. Hence all parties would secretly receive say $0$, one party would secretely receive $1$. Sep 9 '19 at 12:52
• Any function can be computed securely by any MPC protocol, and this function is no exception to that rule. So it's not clear what you're asking. Sep 10 '19 at 16:09
• @Mikero: Not necessarily. Yao's result was that any function $f$ could be coinjointly computed. However, what I want is party A computing $p_A(f(\dots))$, party $B$ computing $p_B(f(\dots))$ and so on. Furthermore from what I know generic constructions are quite slow, if possible I'm interested in an ad-hoc protocol that would be of practical use. Sep 10 '19 at 16:44
• Different outputs to different parties is entirely standard in the modern MPC literature (and it has a simple reduction to identical-output anyway). I'm not aware of special-purpose MPC protocols for comparisons that are better than what you get from general-purpose MPC. Sep 10 '19 at 17:17

Edit:

As the comment of Mikero correctly points out it is quite easy to make the outputs differ for most MPC protocols (for example in the 2PC case at YAO's protocol, you can tell the evaluator that output key X1 means 0 and output Y1 means 1 while you don't say anything about X2 and Y2 and make the evaluator send X2 and Y2 to the garbler, who knows the meanings of them).

In this case you just need to output 0 or 1 to every party if they are the richest or not.