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)
- 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
-
CC BY