### Quadratic Multiparty Randomized Encodings Beyond Honest Majority and Their Applications

##### 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 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.

Available format(s)
Category
Foundations
Publication info
A major revision of an IACR publication in CRYPTO 2022
Keywords
secure multiparty computation non-interactive reductions information-theoretic security
Contact author(s)
bennyap @ post tau ac il
yuvali @ cs technion ac il
orzkarni @ gmail com
arpita @ iisc ac in
History
2022-06-23: approved
See all versions
Short URL
https://ia.cr/2022/813

CC BY

BibTeX

@misc{cryptoeprint:2022/813,
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{https://eprint.iacr.org/2022/813}},
url = {https://eprint.iacr.org/2022/813}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.