CCSP Seminar: Round and Communication Complexity of Secure Computation

Wednesday, September 28, 2022
4:00 p.m.
Online presentation
Sagnik Bhattacharya
Sagnikb@umd.edu

Communication, Control and Signal Processing Seminar
Round and Communication Complexity of Secure Computation
 
Hemanta Maji
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. 
 
Join Zoom Meeting
https://umd.zoom.us/j/98603360883?pwd=WTBFbURLeU0wUGdSQTg4bFB4Nk5KZz09

Meeting ID: 986 0336 0883
Passcode: 830016

remind we with google calendar

 

October 2022

SU MO TU WE TH FR SA
25 26 27 28 29 30 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 31 1 2 3 4 5
Submit an Event