Welcome to the resource topic for 2024/005
Title:
The Multiple Millionaires’ Problem
Authors: Tamir Tassa, Avishay Yanai
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.
ePrint: https://eprint.iacr.org/2024/005
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .