3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This paper by Andrew Yao apparently describes how the millionaire problem is achieved for more than two parties. $\endgroup$ – AleksanderRas Sep 9 '19 at 12:43
  • $\begingroup$ @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$. $\endgroup$ – Mariuslp Sep 9 '19 at 12:52
  • 1
    $\begingroup$ 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. $\endgroup$ – Mikero Sep 10 '19 at 16:09
  • $\begingroup$ @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. $\endgroup$ – Mariuslp Sep 10 '19 at 16:44
  • 2
    $\begingroup$ 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. $\endgroup$ – Mikero Sep 10 '19 at 17:17
2
$\begingroup$

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.

Old answer:

My best idea to solve the problem is to use YAO's protocol (or any other common MPC protocol), make every party additionally input a random identifier and make the function output the identifier of the richest party. Then the richest party knows being the richest while the other parties don't know who is the richest party.

To avoid the problem that two parties input the same identifier I would think about the following (combining these ideas also makes sense):

  • Make the identifier large enough so that the likelyhood that two parties input the same identifier is negligible.
  • Expand the function such that the function outputs a fixed identifier 0 (which must not be chosen by any party) if two parties input the same identifier. If that happened, repeat the MPC computation with another random identifiers.
|improve this answer|||||
$\endgroup$
  • $\begingroup$ Great answer! I'll see if I can adapt Yao's protocol by myself for this modification, or if I must use generic MPC programming. I'll mark as accepted after that. $\endgroup$ – Mariuslp Sep 10 '19 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.