Welcome to the resource topic for 2021/1208
Title:
On Actively-Secure Elementary MPC Reductions
Authors: Benny Applebaum, Aarushi Goel
Abstract:We introduce the notion of \emph{elementary MPC} reductions that allow us to securely compute a functionality f by making a single call to a constant-degree non-cryptographic'' functionality $g$ without requiring any additional interaction. Roughly speaking, non-cryptographic’’ means that g does not make use of cryptographic primitives, though the parties can locally call such primitives. Classical MPC results yield such elementary reductions in various cases including the setting of passive security with full corruption threshold t<n (Yao, FOCS’86; Beaver, Micali, and Rogaway, STOC’90), the setting of full active security against a corrupted minority t<n/2 (Damgård and Ishai, Crypto’05), and, for NC1 functionalities, even for the setting of full active (information-theoretic) security with full corruption threshold of t<n (Ishai and Kushilevitz, FOCS’00). This leaves open the existence of an elementary reduction that achieves full active security in the dishonest majority setting for all efficiently computable functions. Our main result shows that such a reduction is unlikely to exist. Specifically, the existence of a computationally secure elementary reduction that makes black-box use of a PRG and achieves a very weak form of partial fairness (e.g., that holds only when the first party is not corrupted) would allow us to realize any efficiently-computable function by a \emph{constant-round} protocol that achieves a non-trivial notion of information-theoretic passive security. The existence of the latter is a well-known 3-decade old open problem in information-theoretic cryptography (Beaver, Micali, and Rogaway, STOC’90). On the positive side, we observe that this barrier can be bypassed under any of the following relaxations: (1) non-black-box use of a pseudorandom generator; (2) weaker security guarantees such as security with identifiable abort; or (3) an additional round of communication with the functionality g.
ePrint: https://eprint.iacr.org/2021/1208
Talk: https://www.youtube.com/watch?v=6HtndO3W910
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .