Summer 2015

Lower Bounds for Information-Theoretic MPC

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

Add to Calendar

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.