Paper 2020/131
Coin Tossing with Lazy Defense: Hardness of Computation Results
Hamidreza Amini Khorasgani, Hemanta K. Maji, and Mingyuan Wang
Abstract
There is a significant interest in securely computing functionalities with guaranteed output delivery, \aka, fair computation. For example, consider a 2party $n$round cointossing protocol in the informationtheoretic setting. Even if one party aborts during the protocol execution, the other party has to receive her outcome. Towards this objective, every round, the sender of that round's message, preemptively prepares a defense coin, which is her output if the other party aborts prematurely. Cleve and Impagliazzo (1993), Beimel, Haitner, Makriyannis, and Omri (2018), and Khorasgani, Maji, and Mukherjee (2019) show that a failstop adversary can alter the distribution of the outcome by $\Omega\left(1/\sqrt n\right)$. This hardness of computation result for the representative cointossing functionality (using a partition argument) extends to the fair evaluation of any functionality whose output is not apriori fixed and honest parties are not in the majority. However, there are natural scenarios in the delegation of computation where it is infeasible for the parties to update their defenses during every round of the protocol evolution. For example, when parties delegate, say, their cointossing task to an external server, due to high network latency, the parties cannot stay abreast of the progress of the fast protocol running on the server and keep their defense coins in sync with that protocol. Therefore, this paper considers lazy cointossing protocols, where parties update their defense coins only a total of $d$ times during the protocol execution. Is it possible that using only $d\ll n$ defense coin updates, a fair cointossing protocol is robust to $\mathcal{O}\left(1/\sqrt n\right)$ change in their output distribution? This paper proves that being robust to $\mathcal{O}\left(1/\sqrt n\right)$ change in the output distribution necessarily requires that the defense complexity $d=\Omega(n)$, thus ruling out the possibility mentioned above. More generally, our work proves that a failstop adversary can bias the outcome distribution of a cointossing protocol by $\Omega\left(1/\sqrt d\right)$, a qualitatively better attack than the previous stateoftheart when $d=o(n)$. This hardness of computation results extends to the fair evaluation of arbitrary functionalities as well. That is, the defense complexity of the protocol, not its round complexity, determines its security. We emphasize that the rounds where parties calculate their defense coins need not be apriori fixed; they may depend on the protocol's evolution itself. Finally, we translate this failstop adversarial attack into new blackbox separation results. The proof relies on an inductive argument using a carefully crafted potential function to precisely account for the quality of the best attack on cointossing protocols. Previous approaches fail when the protocol evolution reveals information about the defense coins of both the parties, which is inevitable in lazy cointossing protocols. Our analysis decouples the defense complexity of cointossing protocols from its round complexity to guarantee failstop attacks whose performance depends only on the defense complexity of the cointossing protocol, irrespective of their round complexity. Our paper, to complement this hardness of computation result, introduces a cointossing protocol with a private defense update strategy, \ie, the defense update round is not publicly measurable, using $d=n^{1\lambda}$ defense updates (in expectation) to achieve $\mathcal{O}\left(1/\sqrt n\right)$ robustness, where $\lambda$ is an appropriate positive constant.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 Discretetime MartingaleCointossing ProtocolsFair ComputationDefense ComplexityFailstop AdversaryBlackbox Separation
 Contact author(s)
 wang1929 @ purdue edu
 History
 20210204: last of 3 revisions
 20200210: received
 See all versions
 Short URL
 https://ia.cr/2020/131
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/131, author = {Hamidreza Amini Khorasgani and Hemanta K. Maji and Mingyuan Wang}, title = {Coin Tossing with Lazy Defense: Hardness of Computation Results}, howpublished = {Cryptology ePrint Archive, Paper 2020/131}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/131}}, url = {https://eprint.iacr.org/2020/131} }