Resource-restricted cryptography: revisiting MPC bounds in the proof-of-work era (Q2119009)

The authors study the question of how bounds for synchronous Byzantine agreement (BA) and secure multi-party computation (MPC) change when instead of the number of corrupted parties the majority of the computational resources are considered as a foundation. In doing so, the authors show that the bound of \(t < n/3\) malicious parties can be lifted to \(t < n/2\) in this setting. The proof is based on a wrapper-based abstraction of the resource-restricted paradigm. The wrapper is first theoretically analyzed and it is shown that the bounds of \(t < n/3\) are invalid. Then the communication-restricted network is implemented and the correctness is proven. Afterward, it is shown how certified digital signatures and MPC can be obtained. The paper concludes by removing the previously-used freshness assumption. The considered question is interesting, and most of the paper is well-written, so it's worth reading. In particular, the proofs are well-written and clear. The constructions can be improved. On several occasions in the paper, variable symbols are not properly introduced and some variable typos are annoying but not critical. The reader should be familiar with MPC and Canetti's universal composition framework. For the entire collection see [Zbl 1482.94003].