Unlocking Secure Computation: Minimal Complexity Assumptions in Cryptography 🔐

Hemanta Maji (Purdue University)
https://simons.berkeley.edu/talks/hemanta-maji-purdue-university-2023-05-04
Minimal Complexity Assumptions for Cryptography

Reducing the overhead of security solutions increases their adoption. Motivated by such efficiency considerations, characterizing secure computation's round and communication complexity is natural.

The seminal results of Chor-Kushilevitz-Beaver (STOC-1989, FOCS-1989, DIMACS-1989) determine these complexities for deterministic computations. Determining randomized-output functions' round and communication complexity remained open for over three decades. This talk will present how we settled this long-standing open problem.

Our technical innovation is a geometric framework for this research -- opening a wormhole connecting it to geometry research. This framework encodes all candidate secure protocols as points. Studying mathematical properties of novel generalizations of their convex hull implies round and communication complexity results.