 Main
Towards Optimality in Secure Computation
 Badrinarayanan, Saikrishna
 Advisor(s): Ostrovsky, Rafail;
 Sahai, Amit
Abstract
The need for Cryptography arises out of the following fundamental question: can we perform useful computation while ensuring that an adversary does not learn anything about our private sensitive data? The notion of secure multiparty computation (MPC) \cite{Yao82,GMW87} is a unifying framework for general secure protocols. MPC allows mutually distrusting parties to jointly evaluate any efficiently computable function on their private inputs in such a manner that each party does not learn anything beyond the output of the function. In this thesis, we study the question of building MPC protocols in various security models from standard cryptographic assumptions while minimizing the number of rounds of interaction amongst parties.
In the first part of this thesis, (in a joint work with Vipul Goyal, Abhishek Jain, Yael Kalai, Dakshita Khurana and Amit Sahai, CRYPTO 2018) we construct the first roundoptimal (i.e., four round) MPC protocol for general functions based on polynomially hard DDH (or QR or N$^{th}$Residuosity) in the plain model where parties have access to no trusted setup. We further show how to overcome the fourround barrier for MPC by constructing a threeround protocol for ``list cointossing''  a slight relaxation of cointossing that suffices for most conceivable applications  based on polynomially hard DDH (or QR or N$^{th}$Residuosity). This result generalizes to randomized inputless functionalities. Previously, four round MPC protocols required subexponentialtime hardness assumptions and no multiparty threeround protocols were known for any relaxed security notions with polynomialtime simulation against malicious adversaries. In order to build these protocols, we devise a new {\em partitioned simulation} technique for MPC where the simulator uses different strategies for simulating the view of aborting adversaries and nonaborting adversaries. The protagonist of this technique is a new notion of {\em promise zero knowledge} (ZK) where the ZK property only holds against nonaborting verifiers. We show how to realize promise ZK in three rounds in the simultaneousmessage model assuming polynomially hard DDH (or QR or N$^{th}$Residuosity). We also rely upon a new {\em leveled rewinding security} technique that can be viewed as a polynomialtime alternative to leveled complexity leveraging for achieving ``nonmalleability'' across different primitives. Then, we also we study the round complexity of concurrently secure multiparty computation (MPC) with superpolynomial simulation (SPS) in the plain model (in a joint work with Vipul Goyal, Abhishek Jain, Dakshita Khurana and Amit Sahai, TCC 2017). In the plain model, there are known explicit attacks that show that concurrently secure MPC with polynomial simulation is impossible to achieve; SPS security is the most widely studied model for concurrently secure MPC in the plain model. We construct a threeround concurrent MPC with SPS security against Byzantine adversaries, assuming subexponentially secure DDH and LWE. Prior to our work, the best known round complexity for SPS concurrent MPC was around twenty, although to the best of our knowledge, no previous work even gave an approximation of the constant round complexity that is sufficient for concurrent MPC.
In the second part of the thesis, (in a joint work with Abhishek Jain, Rafail Ostrovsky and Ivan Visconti, ASIACRYPT 2018), we study the problem of noninteractive secure computation in the stateless hardware token model where parties have access to physical hardware as part of a trusted setup phase. The notion of noninteractive secure computation (NISC) first introduced in the work of Ishai et al. [EUROCRYPT 2011] studies the following problem: Suppose a receiver $R$ wishes to publish an encryption of her secret input $y$ so that any sender $S$ with input $x$ can then send a message $m$ that reveals $f(x,y)$ to $R$ (for some function $f$). Here, $m$ can be viewed as an encryption of $f(x,y)$ that can be decrypted by $R$. NISC requires security against both malicious senders and receivers, and also requires the receiver's message to be reusable across multiple computations (w.r.t. a fixed input of the receiver). All previous solutions to this problem necessarily rely upon OT (or specific numbertheoretic assumptions) even in the common reference string model or the random oracle model or to achieve weaker notions of security such as superpolynomialtime simulation. In this work, we construct a NISC protocol based on the minimal assumption of one way functions, in the stateless hardware token model. Our construction achieves UC security and requires a single token sent by the receiver to the sender.
Main Content
Enter the password to open this PDF file:













