International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Quadratic Multiparty Randomized Encodings Beyond Honest Majority and Their Applications

Authors:
Benny Applebaum , Tel-Aviv University
Yuval Ishai , Technion
Or Karni , Tel-Aviv University
Arpita Patra , Indian Institute of Science, Bangalore
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2022
Abstract: 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 {\em 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=⌊2n/3⌋ 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.
Video from CRYPTO 2022
BibTeX
@inproceedings{crypto-2022-32149,
  title={Quadratic Multiparty Randomized Encodings Beyond Honest Majority and Their Applications},
  publisher={Springer-Verlag},
  author={Benny Applebaum and Yuval Ishai and Or Karni and Arpita Patra},
  year=2022
}