Abstract
In his seminal result, Cleve [STOC'86] established that secure distributed computation---guaranteeing fairness---is impossible in the presence of dishonest majorities. A generous number of proposals for relaxed notions of fairness ensued, by weakening in various ways the desired security guarantees. While these works also suggest completeness results (i.e., the ability to design protocols which achieve their fairness notion), their assessment is typically of an all-or-nothing nature.
In this work we put forth a comparative approach to fairness. We introduce notions that when presented with two arbitrary protocols, provide the means to answer the question "Which of the protocols is fairer?" The basic idea is that we can use an appropriate utility function to express the preferences of an adversary who wants to break fairness. Thus, we can compare protocols with respect to how fair they are, placing them in a partial order according to this relative-fairness relation.
After formulating such utility-based fairness notions, we turn to the question of finding optimal protocols---i.e., maximal elements in the above partial order. We investigate---and answer---this question for secure function evaluation, both in the two-party and multi-party settings.
Our approach builds on machinery developed in the recently proposed "Rational Protocol Design" framework, by Garay, Katz, Maurer, Tackmann and Zikas [FOCS'13]. The talk will also include a brief introduction to the framework.
This is joint work with Juan Garay (Yahoo Labs), Jon Katz (UMD) and Vassilis Zikas (ETH Zurich).