How Fair is Your Protocol? A Utility-based Approach to Protocol Optimality

Jul 21, 2015

The security of distributed cryptographic protocols typically requires the following properties: privacy (the inputs of the honest parties remain hidden), correctness (the adversary cannot affect the outcome of the computation any more than choosing the inputs of the corrupt parties), and -- the focus of this paper -- fairness (whenever the adversary gets his output from the computation, all honest parties also do). However, and as implied by Cleve's seminal result [STOC'86], satisfying these properties simultaneously is impossible in the presence of dishonest majorities, leading to a generous number of proposals for relaxed notions of fairness, 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. That is, when presented with a protocol which is not designed to be fair according to their respective notion, they most likely would render it unfair and make no further statement about it. In this work we put forth a comparative approach to fairness. We present 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. To our knowledge, the only other fairness notion providing some sort of comparative statement is that of 1/p-security (aka "partial fairness") by Gordon and Katz [Eurocrypt'10]. We also show in this paper that for a special class of utilities our notion strictly implies 1/p-security. In addition, we fix a shortcoming of the definition which is exposed by our comparison, thus strengthening that result.

  • 34th Annual ACM Symposium on Principles of Distributed Computing -- PODC 2015
  • Conference/Workshop Paper