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

Security of distributed cryptographic protocols usually requires privacy (inputs of the honest parties remain hidden), correctness (the adversary cannot improperly affect the outcome), and fairness (if the adversary learns the output, all honest parties do also). Cleve's seminal result (STOC '86) implies that satisfying these properties simultaneously is impossible in the presence of dishonest majorities, and led to several proposals for relaxed notions of fairness. 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 new approach for defining relaxed fairness guarantees that allows for a quantitative comparison between protocols with regard to the level of fairness they achieve. The basic idea is to use an appropriate utility function to express the preferences of an adversary who wants to violate fairness. We also show optimal protocols with respect to our notion, in both the two-party and multi-party settings.