Paper 2020/221

Multiparty Reusable Non-Interactive Secure Computation

Fabrice Benhamouda and Huijia Lin


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

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in TCC 2020
Multiparty Secure ComputationNon InteractiveWitness Encryption
Contact author(s)
rachel @ cs washington edu
fabrice benhamouda @ normalesup org
2021-07-01: revised
2020-02-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Fabrice Benhamouda and Huijia Lin},
      title = {Multiparty Reusable Non-Interactive Secure Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2020/221},
      year = {2020},
      doi = {10.1007/978-3-030-64378-2_13},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.