Uncovering Algebraic Structures in the MPC Landscape.

A fundamental problem in the theory of secure multi-party computation (MPC) is to characterize functions with more than 2 parties which admit MPC protocols with information-theoretic security against passive corruption. This question has seen little progress since the work of Chor and Ishai (1996), which demonstrated difficulties in resolving it. In this work, we make significant progress towards resolving this question in the important case of aggregating functionalities, in which m parties \(P_1,\dots ,P_m\) hold inputs \(x_1,\dots ,x_m\) and an aggregating party \(P_0\) must learn \(f(x_1,\dots ,x_m)\).