Tata Institute of Fundamental Research
Some Complexity Aspects of Secure Multiparty Computation
Seminar
Speaker:
Manoj M. Prabhakaran (University of Illinois at Urbana-Champaign
Department of Computer Science
1110 West Springfield
Urbana, IL 61801
United States of America)
Organiser:
Vinod M. Prabhakaran
Date:
Wednesday, 1 Jan 2014, 14:30 to 15:30
Venue:
AG-69
(Scan to add to calendar)
Abstract:
Abstract: 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 Secure Multi-party Computation.
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. His primary research interest is in theoretical cryptography. His research has been supported by an NSF CAREER award and a Beckman faculty fellowship.
| Speaker: | Manoj M. Prabhakaran (University of Illinois at Urbana-Champaign Department of Computer Science 1110 West Springfield Urbana, IL 61801 United States of America) |
| Organiser: | Vinod M. Prabhakaran |
| Date: | Wednesday, 1 Jan 2014, 14:30 to 15:30 |
| Venue: | AG-69 |
(Scan to add to calendar)
Abstract:
Abstract: 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 Secure Multi-party Computation.
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. His primary research interest is in theoretical cryptography. His research has been supported by an NSF CAREER award and a Beckman faculty fellowship.
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. His primary research interest is in theoretical cryptography. His research has been supported by an NSF CAREER award and a Beckman faculty fellowship.