Paper 2022/813

Quadratic Multiparty Randomized Encodings Beyond Honest Majority and Their Applications

Benny Applebaum, Tel Aviv University
Yuval Ishai, Technion – Israel Institute of Technology
Or Karni, Tel Aviv University
Arpita Patra, Indian Institute of Science, Bangalore

Multiparty randomized encodings (Applebaum, Brakerski, and Tsabary, SICOMP 2021) reduce the task of securely computing a complicated multiparty functionality $f$ to the task of securely computing a simpler functionality $g$. The reduction is non-interactive and preserves information-theoretic security against a passive (semi-honest) adversary, also referred to as privacy. The special case of a degree-2 encoding $g$ (2MPRE) has recently found several applications to secure multiparty computation (MPC) with either information-theoretic security or making black-box access to cryptographic primitives. Unfortunately, as all known constructions are based on information-theoretic MPC protocols in the plain model, they can only be private with an honest majority. In this paper, we break the honest-majority barrier and present the first construction of general 2MPRE that remains secure in the presence of a dishonest majority. Our construction encodes every $n$-party functionality $f$ by a 2MPRE that tolerates at most $t=\lfloor 2n/3\rfloor$ passive corruptions. We derive several applications including: (1) The first non-interactive client-server MPC protocol with perfect privacy against any coalition of a minority of the servers and up to $t$ of the $n$ clients; (2) Completeness of 3-party functionalities under non-interactive $t$-private reductions; and (3) A single-round $t$-private reduction from general-MPC to an ideal oblivious transfer (OT). These positive results partially resolve open questions that were posed in several previous works. We also show that $t$-private 2MPREs are necessary for solving (2) and (3), thus establishing new equivalence theorems between these three notions. Finally, we present a new approach for constructing fully-private 2MPREs based on multi-round protocols in the OT-hybrid model that achieve \emph{perfect privacy} against active attacks. Moreover, by slightly restricting the power of the active adversary, we derive an equivalence between these notions. This forms a surprising, and quite unique, connection between a non-interactive passively-private primitive to an interactive actively-private primitive.

Note: This version contains better proof of the main result whose complexity scales polynomially with the number of parties.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2022
secure multiparty computationnon-interactive reductionsinformation-theoretic security
Contact author(s)
bennyap @ post tau ac il
yuvali @ cs technion ac il
orzkarni @ gmail com
arpita @ iisc ac in
2023-01-19: revised
2022-06-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benny Applebaum and Yuval Ishai and Or Karni and Arpita Patra},
      title = {Quadratic Multiparty Randomized Encodings Beyond Honest Majority and Their Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2022/813},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.