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 2-party $n$-round coin-tossing protocol in the information-theoretic 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 fail-stop adversary can alter the distribution of the outcome by $\Omega\left(1/\sqrt n\right)$. This hardness of computation result for the representative coin-tossing 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 coin-tossing 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 coin-tossing 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 coin-tossing 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 fail-stop adversary can bias the outcome distribution of a coin-tossing protocol by $\Omega\left(1/\sqrt d\right)$, a qualitatively better attack than the previous state-of-the-art 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 fail-stop adversarial attack into new black-box 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 coin-tossing protocols. Previous approaches fail when the protocol evolution reveals information about the defense coins of both the parties, which is inevitable in lazy coin-tossing protocols. Our analysis decouples the defense complexity of coin-tossing protocols from its round complexity to guarantee fail-stop attacks whose performance depends only on the defense complexity of the coin-tossing protocol, irrespective of their round complexity. Our paper, to complement this hardness of computation result, introduces a coin-tossing 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.