Summer 2015

Lower Bounds for Information-Theoretic MPC

Tuesday, June 9th, 2015 2:00 pm2:25 pm

Add to Calendar


Calvin Lab Auditorium

We present some work in progress on lower bounds for information theoretic MPC. One set of results is about the number of messages required to compute non-trivial functions such the and, we show that a quadratic number of messages in the number of players is required. In the second line of work we show that protocols following  the traditional secret-sharing based design paradigm cannot be significantly improved wrt round and communication complexity, even with preprocessing.