The Multiple Millionaires’ Problem

ePrint Report: The Multiple Millionaires’ Problem

Tamir Tassa, Avishay Yanai

We study a fundamental problem in Multi-Party Computation, which we call the Multiple Millionaires’ Problem (MMP). Given a set of private integer inputs, the problem is to identify the subset of inputs that equal the maximum (or minimum) of that set, without revealing any further information on the inputs beyond what is implied by the desired output.
Such a problem is a natural extension of the Millionaires’ Problem, which is …

call computation eprint report identify information inputs integer party private problem report study