1
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ MOTION also has support for garbled circuits and has some improvements over the protocol you suggested. $\endgroup$
    – SEJPM
    Aug 13, 2021 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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