Quadratic Multiparty Randomized Encodings Beyond Honest Majority and Their Applications
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 work, 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 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.
Based on a joint work with Benny Applebaum, Yuval Ishai, and Or Karni, at CRYPTO’22.
Speaker Biography
Arpita Patra is presently an Associate Professor at Indian Institute of Science. Her area of interest is Cryptography, focusing on theoretical and practical aspects of secure multiparty computation protocols. She received her PhD from Indian Institute of Technology (IIT), Madras and held post-doctoral positions at University of Bristol, UK, ETH Zurich, Switzerland, and Aarhus University, Denmark. Her research has been recognized with J. P. Morgan Chase Faculty Award, SONY Faculty Innovation Award, Google Research Award, NASI Young Scientist Platinum Jubilee Award, SERB Women Excellence award, INAE Young Engineer award and associateships with various scientific bodies such as Indian Academy of Sciences (IAS), National Academy of Engineering (INAE ), The World Academy of Sciences (TWAS), Indian Association for Research in Computing Science (IARCS).
