Cryptology ePrint Archive: Report 2019/1264

Resource-Restricted Cryptography: Honest-Majority MPC from a CRS (and No Broadcast)

Juan Garay and Aggelos Kiayias and Rafail Ostrovsky and Giorgos Panagiotakos and Vassilis Zikas

Abstract: Traditional bounds on synchronous Byzantine agreement (BA) and secure multi-party computation (MPC) establish that in absence of a private-coin 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 *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.

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, but merely a *fresh* Common Reference String (CRS)---i.e., a CRS which becomes available to the parties at the same time as to the adversary. We also show how to remove this freshness assumption 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.

Category / Keywords: cryptographic protocols / MPC, broadcast, consensus, proof of work, blockchain

Date: received 30 Oct 2019, last revised 31 Oct 2019

Contact author: juan a garay at gmail com,akiayias@inf ed ac uk,pagio91i@gmail com,rafail@cs ucla edu,vassilis zikas@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20191105:080542 (All versions of this report)

Short URL: ia.cr/2019/1264


[ Cryptology ePrint archive ]