Phd in COMPUTER SCIENCE

Thesis title: New Perspectives in Multi-Party Computation: Low Round Complexity from New Assumptions, Financial Fairness and Public Verifiability

Research in Multi-Party Computation is constantly evolving over the years. Starting from the very first result by Yao in 1982, to serve new and more practical scenarios, a lot of different protocols with stronger security properties have been introduced and proven for several assumptions. For some functionalities, properties like public verifiability, fairness and round-optimality can be considered nowadays a minimal set of assumption to consider an MPC protocol practical. Asynchrony, in the sense that different parties should be able to join a protocol at different times, is fundamental for applications like decentralized lotteries, where the protocol execution can last even days. In such case, due to the involvement of monetary payments, parties must also be aware of what happens to their pockets when such protocols are run. In particular, they must be sure that the execution of a certain class of protocols is financially sustainable. We list below our three contributions to the thesis. We firstly introduce a new theoretical result, showing how to achieve low round MPC from new assumptions. In particular, we show how to construct maliciously secure oblivious transfer (M-OT) from a mild strengthening of key agreement (KA) which we call {\em strongly uniform} KA (SU-KA), where the latter roughly means that the messages sent by one party are computationally close to uniform, even if the other party is malicious. Our transformation is black-box, almost round preserving (adding only a constant overhead of two rounds), and achieves standard simulation-based security in the plain model. As we show, 2-round SU-KA can be realized from cryptographic assumptions such as low-noise LPN, high-noise LWE, Subset Sum, DDH, CDH and RSA---all with polynomial hardness---thus yielding a black-box construction of fully-simulatable, round-optimal, M-OT from the same set of assumptions (some of which were not known before). By invoking a recent result of Benhamouda and Lin (EUROCRYPT 2017), we also obtain (non-black-box) 5-round maliciously secure MPC in the plain model, from the same assumptions. Our second and third contributions are focused on the concrete application of MPC protocols achieving the aforementioned properties in real-world scenarios. In applications like decentralized lotteries, decentralized payment mechanisms like blockchains relying on smart contracts can be considered a powerful tool to enforce the correct behavior of cheating players with the aid of monetary incentives or punishments. In facts, a weaker version of fairness called fairness with penalties, firstly introduced in the lottery protocol of Andrychowicz et al. (S&P '14) and then formally defined by Bentov et al. (CRYPTO'14), can be used to ensure that corrupted players are incentivized to reveal the output to honest players. This can be done successfully through Bitcoin scripts or Ethereum smart contracts. In our second contribution, we consider executions of smart contracts on forking blockchains (e.g., Ethereum) and study security and delay issues due to forks. As security notion for modeling executions of smart contracts, we focus on MPC. In particular, we consider on-chain MPC executions with the aid of smart contracts. The classical double-spending problem tells us that messages of the MPC protocol should be confirmed on-chain before playing the next ones, thus slowing down the entire execution. This contribution consists of two results: - For the concrete case of fairly tossing multiple coins with penalties, we notice that the lottery protocol of Andrychowicz et al. becomes insecure if players do not wait for the confirmations of several transactions. In addition, we present a smart contract that instead retains security even when all honest players immediately answer to transactions appearing on-chain. We analyze the performance using Ethereum as testbed. - We design a compiler that takes any ``digital and universally composable'' MPC protocol (with or without honest majority), and transforms it into another one (for the same task and same setup) which maintains security even if all messages are played on-chain without delays. The special requirements on the starting protocol mean that messages consists only of bits (e.g., no hardware token is sent) and security holds also in the presence of other protocols. We further show that our compiler satisfies fairness with penalties as long as honest players only wait for confirmations once. By reducing the number of confirmations, our protocols can be significantly faster than natural constructions, maintaining at the same time public verifiability, asynchrony (obtained by making the parties posting messages to the blockchain via smart contracts), and fairness with penalties. As a third contribution, we survey the state-of-the-art blockchain based penalty protocols (i.e achieving fairness with penalties) and pioneer another type of fairness, financial fairness, that is closer to the real-world valuation of financial transactions. Intuitively, a penalty protocol is financially fair if the net present cost of participation of honest parties---i.e., the difference between the total value of cash inflows and the total value of cash outflows at the end of the protocol, weighted by the relative discount rate---is the same, even when some parties cheat. Then, we show that the ladder protocol (CRYPTO'14), and its variants (CCS'15 and CCS'16), fail to achieve financial fairness both in theory and in practice, while the penalty protocols of Kumaresan and Bentov (CCS'14) and Baum, David and Dowsley (FC'20) are financially fair. Moreover, It can be inferred that the fair with penalties extension of the generic compiler presented in our second contribution, based on CCS'14, is financially fair. Hence, our compiler is also financially sustainable.