Geometry of Secure Computation
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.
Speaker Biography
Hemanta K. Maji is an Assistant Professor of Computer Science at Purdue University. He received his doctorate in computer science from the University of Illinois at Urbana-Champaign. Maji was a Computing Innovations Fellow from 2011 to 2013 at UCLA. Then, he joined the Center for Encrypted Functionalities at UCLA as a Research Fellow. After that, Maji joined the Purdue faculty. Maji’s primary research interest is cryptography, specializing in secure computation and information-theoretic cryptography.
