Abstract

Can we securely compute a two-party function?

This question went unanswered for nearly 40 years in the information-theoretic setting. In 1989, Beaver, Chor, and Kushilevitz characterized securely computable functions with deterministic output. But, in general, functions have randomized output. For them, we present a finite procedure to answer this question.

We geometrically approach this foundational question in information complexity. We prove specific lamination hulls are semi-algebraic, which was an open problem in geometry. Lamination hulls generalize convex hulls and are motivated by the hydrodynamics literature.

Paper links:
1. https://www.cs.purdue.edu/homes/hmaji/papers/BKMN22.pdf
2. https://www.cs.purdue.edu/homes/hmaji/papers/BKMN23.pdf
3. https://www.cs.purdue.edu/homes/hmaji/papers/BKMN24.pdf