You are looking at a specific version 20200210:173452 of this paper. See the latest version.

Paper 2020/131

Coin Tossing with Lazy Defense: Hardness of Computation Results

Hamidreza Amini Khorasgani and Hemanta K. Maji and Mingyuan Wang

Abstract

There is a significant interest in securely computing functionalities with guaranteed output delivery, a.k.a, 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 Eran Omri (2018), and Khorasgani, Maji, and Mukherjee (2019) show that a fail-stop adversary can alter the distribution of the outcome by $\Omega(1/\sqrt{n})$. However, preparing the defense coin is computationally expensive. So, the parties would prefer to update their defense coin only sparingly or when indispensable. Furthermore, if parties delegate their coin-tossing task to an external server, it is even infeasible for the parties to stay abreast of the progress of the protocol and keep their defense coins in sync with the protocol evolution. 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}({1/\sqrt{n}})$ change in their output distribution? This paper proves that being robust to $\mathcal{O}({1/\sqrt{n}})$ 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({1/\sqrt{d}})$, a qualitatively better attack than the previous state-of-the-art when $d=o({n})$. That is, the defense complexity of a coin-tossing protocol, not its round complexity, determines its security. We emphasize that the rounds where parties calculate their defense coins need not be a priori fixed; they can depend on the protocol's evolution itself. Finally, we translate this fail-stop adversarial attack into black-box separation results for lazy coin-tossing protocols. 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Discrete-time MartingaleCoin-tossing ProtocolsFair ComputationDefense ComplexityFail-stop AdversaryBlack-box Separation
Contact author(s)
wang1929 @ purdue edu
History
2021-02-04: last of 3 revisions
2020-02-10: received
See all versions
Short URL
https://ia.cr/2020/131
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.