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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
1