Event

 

Purdue University

Abstract

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. This talk presents our recent work that proves the first such results for the randomized output case.

We study the problem of realizing a two-party secure function evaluation in a given round or communication constraint. We prove the decidability of this problem. We construct one such protocol if it exists; otherwise, we present an obstruction to achieving security.

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 imply round and communication complexity results.

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, he joined the Purdue faculty. Maji's primary research interest is cryptography, specializing in secure computation and information-theoretic cryptography.