Geometry of Secure Two-party Computation

Characterizing the optimal round and communication complexity of secure computation is essential to minimize the overhead of security when computing over distributed data. In this context, the seminal results of Chor-Kushilevitz-Beaver (STOC-1989, FOCS-1989, DIMACS-1989) characterize all two-party computations with deterministic output that admit secure protocols, namely, the decomposable functions. However, the precise round and communication complexity have essentially remained unexplored for secure protocols of computations with randomized output. The space of all candidate private-coin secure protocols has an intricate structure that confounds intuition and has been challenging to reason.

Our work resolves this problem for two-party secure function evaluation functionalities with randomized output. We introduce an innovative geometric encoding of all candidate secure protocols for a given computation as points in a high-dimensional space. Next, we analyze the properties of these geometric sets of points using a real algebraic geometry toolkit and demonstrate their tameness. Consequently, the following decidability, search, and optimization results follow.

1. Determining whether a given computation admits a secure protocol within round or communication constraints is decidable.

2. If there is such a protocol, we can construct one such protocol.

3. Otherwise, we present a geometric obstruction to achieving security.

Tight new information complexity bounds for secure computation follow as corollaries of our technical contributions. We demonstrate the expressive power of our results by unifying the current state-of-the-art. The geometric sets that we study are new and natural generalizations of the convex hull of points, motivating exciting new foundational research in real algebraic geometry and topology.