Paper 2020/221

Multiparty Reusable Non-Interactive Secure Computation

Fabrice Benhamouda and Huijia Lin

Abstract

Reducing interaction in Multiparty Computation (MPC) is a highly desirable goal in cryptography. It is known that 2-round MPC can be based on the minimal assumption of 2-round Oblivious Transfer (OT) [Benhamouda and Lin, Garg and Srinivasan, EC 2018], and 1-round MPC is impossible in general. In this work, we propose a natural ``hybrid'' model, called \textbf{multiparty reusable Non-Interactive Secure Computation Market (mrNISC)}. In this model, parties publish encodings of their private inputs $x_i$ at the beginning, once and for all. Later, any subset $I$ of them can compute \emph{on-the-fly} a function $f$ on their inputs $\vec x_I = {\{x_i\}}_{i \in I}$ by just sending a single message to a stateless evaluator, conveying the result $f(\vec x_I)$ and nothing else. Importantly, the input encodings can be \emph{reused} in any number of on-the-fly computations, and the same classical simulation security guaranteed by multi-round MPC, is achieved. In short, mrNISC has minimal yet ``tractable'' interaction pattern. We initiate the study of mrNISC on several fronts. First, we formalize the security of mrNISC protocols in both a UC definition and a game-based definition. Second, we construct mrNISC protocols in the plain model with semi-honest and semi-malicious security based on bilinear groups. Third, we demonstrate the power of mrNISC by showing two applications: non-interactive MPC (NIMPC) with reusable setup and a distributed version of program obfuscation. In addition, at the core of our construction of mrNISC is a witness encryption scheme for a special language that verifies Non-Interactive Zero-Knowledge (NIZK) proofs of the validity of computations over committed values, which we believe is of independent interest.

Note: 2021-07-01: various style improvements, comparison to on-the-fly MPC