An Overview of Fairness Notions in Multi-Party Computation

Die sichere Mehrparteienberechnung (``Multi-party Computation'', MPC) ist eine kryptografische Technik, die es mehreren Parteien, die sich gegenseitig misstrauen, ermöglicht, gemeinsam eine Funktion über ihre privaten Eingaben zu berechnen. Fairness in MPC ist definiert als die Eigenschaft, dass, wenn eine Partei die Ausgabe erhält, alle ehrlichen Parteien diese erhalten. Diese Arbeit befasst sich mit dem Defizit an umfassenden Übersichten über verschiedene Fairnessbegriffe in MPC.

Vollständige Fairness (``complete fairness''), die oft als Ideal angesehen wird, garantiert, dass entweder alle ehrlichen Parteien ein Ergebnis erhalten oder keine. ... mehrDieses Ideal ist jedoch aufgrund theoretischer und kontextbezogener Beschränkungen im Allgemeinen nicht zu erreichen. Infolgedessen haben sich alternative Begriffe herausgebildet, um diese Einschränkungen zu überwinden.

In dieser Arbeit werden verschiedene Fairnessbegriffe in MPC untersucht, darunter vollständige Fairness, partielle Fairness (``Partial Fairness''), Delta-Fairness, graduelle Freigabe, Fairness mit Strafen und probabilistische Fairness. Jedes Konzept stellt unterschiedliche Anforderungen und Einschränkungen für reale Szenarien dar. Wir stellen fest, dass vollständige Fairness eine ehrliche Mehrheit erfordert, um für allgemeine Funktionen ohne stärkere Annahmen, wie z. B. den Zugang zu öffentlichen Ledgern, erreicht zu werden, während bestimmte Funktionen auch ohne diese Annahmen mit vollständiger Fairness berechnet werden können. Andere Begriffe, wie Delta-Fairness, erfordern sichere Hardwarekomponenten. Wir geben einen Überblick über die Begriffe, ihre Zusammenhänge, Kompromisse und praktischen Implikationen dieser Begriffe. Darüber hinaus fassen wir die Ergebnisse in einer vergleichenden Tabelle zusammen, die einen kompakten Überblick über die Protokolle bietet, die diese Fairnessbegriffe erfüllen, und die Kompromisse zwischen Sicherheit, Effizienz und Anwendbarkeit aufzeigt.

In der Arbeit werden Annahmen und Einschränkungen im Zusammenhang mit verschiedenen Fairnessbegriffe aufgezeigt und Protokolle aus grundlegenden Arbeiten auf diesem Gebiet zitiert. Es werden auch mehrere Unmöglichkeitsergebnisse vorgestellt, die die inhärenten Herausforderungen beim Erreichen von Fairness im MPC aufzeigen. Die praktischen Implikationen dieser Fairnesskonzepte werden untersucht und geben Einblicke in ihre Anwendbarkeit und Grenzen in realen Szenarien.

Multi-party Computation (MPC) is a cryptographic technique that enables multiple mutually distrusting parties to jointly compute a function over their private inputs. Fairness in MPC is defined as ensuring that if one party receives the output, all honest parties do. This thesis addresses the lack of comprehensive overviews on different fairness notions in MPC.

Complete fairness, often considered the ideal, guarantees that either all parties receive an outcome or none do. However, this ideal is not generally achievable due to theoretical and contextual constraints. As a result, alternative notions have emerged to address these limitations.
... mehr

In this thesis, we review different notions of fairness in MPC, including complete fairness, partial fairness, Delta-fairness, gradual release, fairness with penalties, and probabilistic fairness. Each notion approaches different requirements and limitations to real-world scenarios. We find that complete fairness requires an honest majority to be achieved for general functions without stronger assumptions, such as access to public ledgers, while specific functions can be computed with complete fairness even without these assumptions. Other notions, such as Delta-fairness, require secure hardware components. We provide an overview of the notions, their interrelations, trade-offs, and practical implications of these notions. In addition, we summarize the findings in a comparative table that provides a compact overview of the protocols that achieve these notions of fairness, showing the trade-offs between security, efficiency, and applicability.

The thesis identifies assumptions and constraints associated with various notions of fairness, citing protocols from seminal works in the field. Several impossibility results are also presented, demonstrating the inherent challenges in achieving fairness in MPC. The practical implications of these fairness notions are explored, providing insights into their applicability and limitations in real-world scenarios.