Paper 2024/005

The Multiple Millionaires’ Problem

Abstract

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 the very first Multi-Party Computation problem that was presented in Andrew Yao’s seminal work [31]. A closely related problem is MaxP, in which the value of the maximum is sought. We propose several approaches towards the solution of those fundamental problems as well as concrete solutions, and compare their performance. As applications of privacy-preserving computation are more and more commonly implemented in industrial systems, MMP and MaxP become important building blocks in privacy-preserving statistics, machine learning, auctions and other domains. One of the prominent advantages of our novel protocols is their simplicity. As they solve fundamental problems that are essential building blocks in various application scenarios, we believe that our systematic study of solutions to those problems, and the comparison between them, will serve well future researchers and practitioners of secure distributed computing.