CCSP Seminar: Round and Communication Complexity of Secure Computation

Wednesday, September 28, 2022
4:00 p.m.
Online presentation
Sagnik Bhattacharya

Communication, Control and Signal Processing Seminar
Round and Communication Complexity of Secure Computation
Hemanta Maji
Purdue University

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.

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. 
Join Zoom Meeting

Meeting ID: 986 0336 0883
Passcode: 830016

remind we with google calendar


November 2023

29 30 31 1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 1 2
Submit an Event