Paper 2021/882

Computational Hardness of Optimal FairComputation: Beyond Minicrypt

Hemanta K. Maji and Mingyuan Wang

Abstract

Secure multi-party computation allows mutually distrusting parties to compute securely over their private data. However, guaranteeing output delivery to honest parties when the adversarial parties may abort the protocol has been a challenging objective. As a representative task, this work considers two-party coin-tossing protocols with guaranteed output delivery, a.k.a., fair coin-tossing. In the information-theoretic plain model, as in two-party zero-sum games, one of the parties can force an output with certainty. In the commitment-hybrid, any $$-message coin-tossing protocol is $$-unfair, i.e., the adversary can change the honest party's output distribution by $$ in the statistical distance. Moran, Naor, and Segev (TCC--2009) constructed the first $$-unfair protocol in the oblivious transfer-hybrid. No further security improvement is possible because Cleve (STOC--1986) proved that $$-unfairness is unavoidable. Therefore, Moran, Naor, and Segev's coin-tossing protocol is optimal. However, is oblivious transfer necessary for optimal fair coin-tossing? Maji and Wang (CRYPTO--2020) proved that any coin-tossing protocol using one-way functions in a black-box manner is at least $$-unfair. That is, optimal fair coin-tossing is impossible in Minicrypt. Our work focuses on tightly characterizing the hardness of computation assumption necessary and sufficient for optimal fair coin-tossing within Cryptomania, outside Minicrypt. Haitner, Makriyannia, Nissim, Omri, Shaltiel, and Silbak (FOCS--2018 and TCC--2018) proved that better than $$-unfairness, for any constant $$, implies the existence of a key-agreement protocol. We prove that any coin-tossing protocol using public-key encryption (or, multi-round key agreement protocols) in a black-box manner must be $$-unfair. Next, our work entirely characterizes the additional power of secure function evaluation functionalities for optimal fair coin-tossing. We augment the model with an idealized secure function evaluation of $$, \aka, the $$-hybrid. If $$ is complete, that is, oblivious transfer is possible in the $$-hybrid, then optimal fair coin-tossing is also possible in the $$-hybrid. On the other hand, if $$ is not complete, then a coin-tossing protocol using public-key encryption in a black-box manner in the $$-hybrid is at least $$-unfair.