College of LAS Events

Back to Listing

If you need disability-related accommodations in order to participate in a program or event and cannot find an event contact listed, please contact MT Hudson at (217) 333-0885 or mthdson@illinois.edu. Early requests are strongly encouraged to allow sufficient time to meet your access needs.

"Some Complexity Aspects of Secure Multiparty Computation"

Event Type
Other
Sponsor
Coordinated Science Laboratory
Location
141 Coordinated Science Laboratory
Date
Oct 28, 2013   4:00 - 5:00 pm  
Speaker
Professor Manoj Prabhakaran, Computer Science;  University of Illinois
Contact
Peggy Wells
E-Mail
pwells@illinois.edu
Phone
217-244-2646
Views
1049
Originating Calendar
CSL Communications Group Calendar

Abstract:

Secure multiparty computation (MPC) is a well-studied problem in modern cryptography. In this talk, I will survey a collection of results that study qualitative and quantitative complexity of (multi-party) functions, with respect to how "easy" or "hard" they are for MPC.

In particular, we formulate a quantitative notion of "cryptographic complexity" of a (multi-party) function, as the number of "crypto gates" needed to securely evaluate the function (amortized over several evaluations). Due to recent results, we can show that up to constants, this quantity does not depend on the specific choice of crypto gate, as long as it is "complete."

I shall discuss some connections of cryptographic complexity with other notions of complexity of functions, like circuit complexity and communication complexity.

Bio:

Manoj Prabhakaran is an Associate Professor in the Department of Computer Science at the University of Illinois, Urbana-Champaign. Manoj received a Ph.D. in Computer Science from Princeton University in 2005, and a B.Tech in Computer Science and Engineering from the Indian Institute of Technology, Mumbai, in 2000.

link for robots only