Paper 2022/813
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.
Note: This version contains better proof of the main result whose complexity scales polynomially with the number of parties.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A major revision of an IACR publication in CRYPTO 2022
- Keywords
- 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 - History
- 2023-01-19: revised
- 2022-06-22: received
- See all versions
- Short URL
- https://ia.cr/2022/813
- License
-
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},
url = {https://eprint.iacr.org/2022/813}
}