Paper 2021/882
Computational Hardness of Optimal FairComputation: Beyond Minicrypt
Hemanta K. Maji and Mingyuan Wang
Abstract
Secure multiparty 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 twoparty cointossing protocols with guaranteed output delivery, a.k.a., fair cointossing. In the informationtheoretic plain model, as in twoparty zerosum games, one of the parties can force an output with certainty. In the commitmenthybrid, any $r$message cointossing 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 (TCC2009) constructed the first $1/r$unfair protocol in the oblivious transferhybrid. No further security improvement is possible because Cleve (STOC1986) proved that $1/r$unfairness is unavoidable. Therefore, Moran, Naor, and Segev's cointossing protocol is optimal. However, is oblivious transfer necessary for optimal fair cointossing? Maji and Wang (CRYPTO2020) proved that any cointossing protocol using oneway functions in a blackbox manner is at least $1/\sqrt r$unfair. That is, optimal fair cointossing is impossible in Minicrypt. Our work focuses on tightly characterizing the hardness of computation assumption necessary and sufficient for optimal fair cointossing within Cryptomania, outside Minicrypt. Haitner, Makriyannia, Nissim, Omri, Shaltiel, and Silbak (FOCS2018 and TCC2018) proved that better than $1/\sqrt r$unfairness, for any constant $r$, implies the existence of a keyagreement protocol. We prove that any cointossing protocol using publickey encryption (or, multiround key agreement protocols) in a blackbox manner must be $1/\sqrt r$unfair. Next, our work entirely characterizes the additional power of secure function evaluation functionalities for optimal fair cointossing. 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 cointossing is also possible in the $f$hybrid. On the other hand, if $f$ is not complete, then a cointossing protocol using publickey encryption in a blackbox manner in the $f$hybrid is at least $1/\sqrt r$unfair.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A minor revision of an IACR publication in Crypto 2021
 Keywords
 Fair computationOptimal fair cointossingCryptomaniaBlackbox separationHardness of computation resultsSecure function evaluation functionalities
 Contact author(s)
 wang1929 @ purdue edu
 History
 20210629: received
 Short URL
 https://ia.cr/2021/882
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/882, author = {Hemanta K. Maji and Mingyuan Wang}, title = {Computational Hardness of Optimal FairComputation: Beyond Minicrypt}, howpublished = {Cryptology ePrint Archive, Paper 2021/882}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/882}}, url = {https://eprint.iacr.org/2021/882} }