Uncovering Algebraic Structures in the MPC Landscape

Abstract: A fundamental open problem in information-theoretically secure multi-party computation (MPC) is to characterize functions which admit MPC protocols (say, secure against passive corruption), when more than 2 parties are involved. This question has seen little progress since the work of Chor and Ishai (1996), who 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 P1, . . . , Pm hold inputs x1, . . . , xm and an aggregating party P0 must learn f(x1,...,xm). We uncover a rich class of algebraic structures that are closely related to secure computability, namely, “Commuting Permutations Systems” (CPS) and its variants. We present a necessary algebraic condition and a slightly stronger sufficient algebraic condition for a function to admit information-theoretically secure MPC protocols. Along the way we introduce and study new models of minimally interactive MPC which help in understanding our positive and negative results better, and may be of independent practical interest.

Based on joint work with Navneet Agarwal and Sanat Anand, to appear at EUROCRYPT'19.