Welcome to the resource topic for 2021/882
Title:
Computational Hardness of Optimal FairComputation: Beyond Minicrypt
Authors: Hemanta K. Maji, 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 r-message coin-tossing protocol is {1/\sqrt r}-unfair, i.e., the adversary can change the honest party’s output distribution by 1/\sqrt r in the statistical distance. Moran, Naor, and Segev (TCC–2009) constructed the first 1/r-unfair protocol in the oblivious transfer-hybrid. No further security improvement is possible because Cleve (STOC–1986) proved that 1/r-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 1/\sqrt r-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 1/\sqrt r-unfairness, for any constant r, 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 1/\sqrt r-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 f, \aka, the f-hybrid. If f is complete, that is, oblivious transfer is possible in the f-hybrid, then optimal fair coin-tossing is also possible in the f-hybrid. On the other hand, if f is not complete, then a coin-tossing protocol using public-key encryption in a black-box manner in the f-hybrid is at least 1/\sqrt r-unfair.
ePrint: https://eprint.iacr.org/2021/882
Talk: https://www.youtube.com/watch?v=Dsy9nYpaplQ
Slides: https://iacr.org/submit/files/slides/2021/crypto/crypto2021/319/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .