DIMACS Theory of Computing Seminar

Title: Lower Bounds for Information-Theoretic Secure Computation

Speaker: Antigoni Polychroniadou, Cornell Tech

Date: Wednesday, April 19, 2017 11:00am-12:00pm

Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ


Information-Theoretic (IT) secure cryptography provides unconditional security without the need for unproven complexity assumptions. The techniques used in IT secure protocols tend to be computationally much more efficient than the cryptographic machinery needed for computational security. Therefore, IT secure protocols are attractive from a practical point of view, however they seem to require a lot of interaction.

In this talk, we will present our recent lower bounds on the communication complexity of secure Multi-Party Computation protocols in the IT setting. In particular, we show that protocols based on the traditional secret-sharing design paradigm cannot be significantly improved with respect to the communication/computational complexity even in the preprocessing model.

See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S17/