Graduate mentor's supervisor: Prof. Florian Kerschbaum
For secure multiparty computation (MPC), our goal is for parties 1 to n to securely compute f(x1, …, xn) where xi is the private input of party i. Our security condition is for the messages each party sends and receives during the computation of f to reveal no more information than its input and output. This allows the parties to collaboratively compute a function over their private inputs while maintaining privacy.
Traditionally, MPC algorithms have a fixed runtime that depends only on input size rather than the specific input since otherwise the runtime would leak information about the private input. However, for non-private algorithms, there are practical algorithms with a runtime that is both random and low in expectation. One example that has been successfully adapted to the MPC setting is quicksort, which is an algorithm whose random runtime is independent of the input list. Our goal in this project is to adapt another algorithm with random runtime that is independent of the specific input and benchmark it against private deterministic versions of the same algorithm. A successful implementation could enable adaptation of richer algorithm classes to the private setting.
An introductory background in algorithms and statistics is necessary since we analyze the runtime of randomized algorithms. Students will get experience with the design and analysis of randomized algorithms, along with experiment design when benchmarking the implementation. Our main short-term goal is to adapt randomized algorithms to the MPC setting using the template provided by the quicksort implementation, while the long-term goal is to develop techniques to implement a wider class of randomized algorithms in MPC.