Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / Multiparty Secure Computation, Non Interactive, Witness Encryption

Date: received 19 Feb 2020

Contact author: rachel at cs washington edu,fabrice benhamouda@normalesup org

Available format(s): PDF | BibTeX Citation

Version: 20200221:120046 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]