Paper 2015/574

Fair and Robust Multi-Party Computation using a Global Transaction Ledger

Aggelos Kiayias, Hong-Sheng Zhou, and Vassilis Zikas

Abstract

Classical results on secure multi-party computation (MPC) imply that fully secure computation, including fairness (either all parties get output or none) and robustness (output delivery is guaranteed), is impossible unless a majority of the parties is honest. Recently, cryptocurrencies like Bitcoin where utilized to leverage the fairness loss in MPC against a dishonest majority. The idea is that when the protocol aborts in an unfair manner (i.e., after the adversary receives output) then honest parties get compensated by the adversarially controlled parties. Our contribution is three-fold. First, we put forth a new formal model of secure MPC with compensation and we show how the introduction of suitable ledger and synchronization functionalities makes it possible to express completely such protocols using standard interactive Turing machines (ITM) circumventing the need for the use of extra features that are outside the standard model as in previous works. Second, our model, is expressed in the universal composition setting with global setup and is equipped with a composition theorem that enables the design of protocols that compose safely with each other and within larger environments where other protocols with compensation take place; a composition theorem for MPC protocols with compensation was not known before. Third, we introduce the first robust MPC protocol with compensation, i.e., an MPC protocol where not only fairness is guaranteed (via compensation) but additionally the protocol is guaranteed to deliver output to the parties that get engaged and therefore the adversary, after an initial round of deposits, is not even able to mount a denial of service attack without having to suffer a monetary penalty. Importantly, our robust MPC protocol requires only a {\em constant } number of (coin-transfer and communication) rounds.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Contact author(s)
aggelos @ di uoa gr
hszhou @ vcu edu
vzikas @ inf ethz ch
History
2015-10-29: revised
2015-06-17: received
See all versions
Short URL
https://ia.cr/2015/574
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/574,
      author = {Aggelos Kiayias and Hong-Sheng Zhou and Vassilis Zikas},
      title = {Fair and Robust Multi-Party Computation using a Global Transaction Ledger},
      howpublished = {Cryptology ePrint Archive, Paper 2015/574},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/574}},
      url = {https://eprint.iacr.org/2015/574}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.