International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Resource-Restricted Cryptography: Revisiting MPC Bounds in the Proof-of-Work Era

Juan A. Garay , Department of Computer Science and Engineering, Texas A&M University
Aggelos Kiayias , School of Informatics, University of Edinburgh & IOHK
Rafail M. Ostrovsky , UCLA Department of Computer Science and Department of Mathematics
Giorgos Panagiotakos , School of Informatics, University of Edinburgh
Vassilis Zikas , School of Informatics, University of Edinburgh & IOHK
DOI: 10.1007/978-3-030-45724-2_5 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2020
Abstract: Traditional bounds on synchronous Byzantine agreement (BA) and secure multi-party computation (MPC) establish that in absence of a private correlated-randomness setup, such as a PKI, protocols can tolerate up to $t<n/3$ of the parties being malicious. The introduction of ``Nakamoto style'' consensus, based on Proof-of-Work (PoW) blockchains, put forth a somewhat different flavor of BA, showing that even a majority of corrupted parties can be tolerated as long as the majority of the computation resources remain at honest hands. This assumption on honest majority of some resource was also extended to other resources such as stake, space, etc., upon which blockchains achieving Nakamoto-style consensus were built that violated the $t<n/3$ bound in terms of number of party corruptions. The above state of affairs begs the question of whether the seeming mismatch is due to different goals and models, or whether the resource-restricting paradigm can be generically used to circumvent the $n/3$ lower bound. In this work we study this question and formally demonstrate how the above paradigm changes the rules of the game in cryptographic definitions. First, we abstract the core properties that the resource-restricting paradigm offers by means of a functionality {\em wrapper}, in the UC framework, which when applied to a standard point-to-point network restricts the ability (of the adversary) to send new messages. We show that such a wrapped network can be implemented using the resource-restricting paradigm---concretely, using PoWs and honest majority of computing power---and that the traditional $t<n/3$ impossibility results fail when the parties have access to such a network. Our construction is in the {\em fresh} Common Reference String (CRS) model---i.e., it assumes a CRS which becomes available to the parties at the same time as to the adversary. We then present constructions for BA and MPC, which given access to such a network tolerate $t<n/2$ corruptions without assuming a private correlated randomness setup. We also show how to remove the freshness assumption from the CRS by leveraging the power of a random oracle. Our MPC protocol achieves the standard notion of MPC security, where parties might have dedicated roles, as is for example the case in Oblivious Transfer protocols. This is in contrast to existing solutions basing MPC on PoWs, which associate roles to pseudonyms but do not link these pseudonyms with the actual parties.
Video from EUROCRYPT 2020
  title={Resource-Restricted Cryptography: Revisiting MPC Bounds in the Proof-of-Work Era},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  keywords={Byzantine agreement;MPC;resource-restricted cryptography},
  author={Juan A. Garay and Aggelos Kiayias and Rafail M. Ostrovsky and Giorgos Panagiotakos and Vassilis Zikas},