MPC protocols for comparisons

Abstract

Multi-party computation allows to compute functions on private inputs without revealing any information about input or output. Secure comparisons are an important building block for many functions and find application in many MPC deployments like secret bidding at auctions, privacy-preserving machine learning, secure linear programming or secure data mining. In recent years, many different MPC protocols for comparisons have been proposed for various different MPC settings. We collect the most promising proposed n-party protocols, compatible with SPDZ or SPDZ2k and evaluate these regarding different MPC settings and cost parameters. The MPC settings include the protocols security model, adversary model, majority model and arithmetic domain, in which computation takes place. The costs are evaluated by determining necessary rounds, communication, computation and precomputation. We provide an overview of the MPC settings and costs for each protocol. Additionally, we contribute implementations in MP-SPDZ and benchmark tests in multiple different MPC settings for most of the chosen protocols. Our results show the advantages and disadvantages of each protocol and enable quick decisions for which protocol to choose for a specific application.

Multiparty Computation (MPC) bietet die Möglichkeit, verschiedene Funktionen auf privaten Eingaben von mehreren Individuen zu berechnen, ohne die privaten Eingaben oder Ausgaben zu veröffentlichen. In den letzten Jahren haben sich verschiedene Forschungsarbeiten mit diesem Thema beschäftigt und dabei vor allem arithmetische Operationen, wie Addition und Multiplikation, untersucht. Allerdings spielen in der Praxis häufig auch andere Funktionen eine wichtige Rolle. Insbesondere die Vergleichsoperation ist von großer Bedeutung für bestimmte Anwendungen, wie zum Beispiel Geheimhaltung bei Data-Mining, geheimes Bieten bei Auktionen, Privatsphäre bewahrendes maschinelles Lernen oder Geheimhaltung bei linearer Programmierung.

In dieser Arbeit werden sieben verschiedene MPC Protokolle für Vergleichsoperationen von verwandten Arbeiten vorgestellt, analysiert und teilweise implementiert und getestet. MPC Protokolle werden meist in unterschiedliche Kategorien unterteilt, welche die Anwendungsumgebung vorgeben, in denen die Protokolle genutzt werden können. Die Anwendungsumgebung stellt verschiedene Sicherheits- und Angreifermodelle dar. Die Analyse bezieht sich auf die in der Theorie anfallenden Kosten, welche meist in anderen MPC Primitiven (z. B. Additionen/Multiplikationen) angegeben werden. In den Tests wird die Anzahl der Vergleichsoperationen pro Sekunde, sowie die Kommunikation zwischen Individuen pro Vergleichsoperation pro Individuum, berechnet. Dabei werden bis zu 500.000 Vergleichsoperationen pro Protokoll pro Anwendungsumgebung ausgeführt. Fünf der sieben MPC Protokolle für Vergleichsoperationen werden in dem Framework MP-SPDZ (Quelle: Data61. MP-SPDZ: Versatile Framework for Multi-party Computation. [Online]. 2019. url: https://github.com/data61/MP-SPDZ (visited on 04/08/2022) (cit. on pp. 11, 13, 19 22, 24, 26, 27, 31, 35, 43).) implementiert und getestet. Das Framework bietet die Möglichkeit, die Performance von MPC Protokollen in verschiedenen Anwendungsumgebungen zu messen.

Während drei der sieben Protokolle bei den Tests besonders gut abschneiden, zeigen die anderen Protokolle besondere Eigenschaften in ihrem Aufbau oder bei den in der Theorie anfallen Kosten. Durch die besonderen Eigenschaften sind die jeweiligen Protokolle ebenfalls interessant für die Praxis. Die Tests werden sowohl für die vollständigen Protokolle für Vergleichsoperationen, wie auch für Protokollversionen, in denen die Vorberechnungen extrahiert wurden, durchgeführt. Es zeigt sich deutlich, dass eine striktere Anwendungsumgebung, mit einem stärkeren Sicherheits- und Angreifermodell, die Vorberechnungen der Protokolle sehr stark verlangsamt, während die Protokollversionen ohne Vorberechnungen nur leicht negativ beeinflusst werden. Eine striktere Anwendungsumgebung sollte also nur in Erwägung gezogen werden, wenn es möglich ist, die Vorberechnungen separat auszuführen.

Die Ergebnisse dieser Arbeit ermöglichen es, schnelle und einfache Entscheidungen bei der Auswahl des zu implementierenden MPC Protokolls für Vergleichsoperationen für bestimmte Programme, unter Berücksichtigung der Anwendungsumgebung, zu treffen.