Join Log in
Score:1
walcott avatar Crypto

Multi-party Millionaire's variant: how to find the highest number without revealing who holds it?

in flag
walcott

Let's say that $n$ honest-but-curious parties each hold a value $x_i$. The parties want to learn what is the maximum value across the parties $\{x_1...x_n\}$ without sharing their values (unless they hold the maximum), or knowing who holds the maximum (aside from learning that the holder is or is not them). What are some approaches, optimizing for round complexity?

66
1 + 0
Score:2
avatar Crypto
cn flag
lamba

Typically multi-party garbled circuit protocols are the best if you want to optimize for round complexity, since these protocols are constant round. The original protocol that does this is BMR. A more recent protocol in the honest-but-curious setting is this one. To answer your specific problem, the parties basically create a garbled circuit for the max function, this can be done beforehand and without knowing what the input is. The evaluation part is similar to Yao's (2-party) garbled circuit. Both steps are constant round. I suggest reading Section 2 of the second paper to understand the details.

0 + 1
SEJPM avatar
us flag
SEJPM
[MOTION](https://eprint.iacr.org/2020/1137) also has support for garbled circuits and has some improvements over the protocol you suggested.
1
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.