Thesis Defense: Srinivasan Raghuraman: Infrastructures for Secure Multiparty Computation

Abstract:  Motivated by the goal of improving the concrete efficiency of secure multiparty computation (MPC), we study the possibility of implementing an infrastructure for MPC. We consider the various (cryptographic) components of an infrastructure for MPC. The first, communication. We study the problem of almost-everywhere reliable message transmission. The goal is to design low-degree networks which allow a large fraction of honest nodes to communicate reliably even while linearly many nodes can experience byzantine corruption and deviate arbitrarily from the assigned protocol. We achieve a log-degree network with a polylogarithmic work complexity protocol, thereby improving over the state-of-the-art result of Chandran et al. (ICALP 2010) who required a polylogarithmic-degree network and had a linear work complexity. In addition, we also achieve a work efficient version of Dwork et. al.'s (STOC 1986) butterfly network and an improvement upon the state of the art protocol of Ben-or and Ron (Information Processing Letters 1996) in the randomized corruption model – both in work-efficiency and in resilience.

Next, we propose an infrastructure for oblivious transfer (OT), which would consist of OT channels between some pairs of parties in the network. We devise information-theoretically secure protocols that allow additional pairs of parties to establish secure OT correlations using the help of other parties in the network in the presence of a dishonest majority. Our main technical contribution is an upper bound that matches a lower bound of Harnik, Ishai, and Kushilevitz (Crypto 2007), who studied the number of OT channels necessary and sufficient for MPC. In particular, we characterize which n-party OT graphs G allow t-secure computation of OT correlations between all pairs of parties, showing that this is possible if and only if the complement of G does not contain the complete bipartite graph on n – t nodes as a subgraph.

Finally, we study the problem of building an infrastructure for fair secure computation. Fitzi, Garay, Maurer, and Ostrovsky (Journal of Cryptology 2005) showed that in the presence of a dishonest majority, no primitive of cardinality n – 1 is complete for realizing an arbitrary n-party functionality with guaranteed output delivery. In this work, we introduce a new 2-party primitive called “synchronizable fair exchange” (SyX) and show that it is complete for realizing any n-party functionality with fairness in a setting where all n parties are pairwise connected by independent instances of SyX. In the SyX-hybrid model, the two parties load SyX with some input, and following this, either party can trigger SyX with a suitable “witness” at a later time to receive the output from SyX. Crucially the other party also receives output from SyX when SyX is triggered. The trigger witnesses allow us to synchronize the trigger phases of multiple instances of SyX, thereby aiding in the design of fair multiparty protocols. Additionally, a pair of parties may reuse a single a priori loaded instance of SyX in any number of multiparty protocols (possibly involving different sets of parties).

Committee:  Shafi Goldwasser, Mike Sipser and Vinod Vaikuntanathan