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.
One primitive used to implement MPC algorithms is function secret sharing, which is a way to split a function f among multiple parties such that each party can evaluate f on a common input x and obtain shares of the output f(x). We investigate the use of function secret sharing to implement sorting algorithms in MPC since sorting is a common subroutine in many algorithms. We then benchmark these implementations against state-of-the-art private sorting algorithms.
Basic backgrounds in cryptography and c or c++ are appreciated, and a background in algorithm design is necessary. Students will get hands on experience designing algorithms, comparing different implementations, and using (and possibly extending) a secure computation library. The main short-term goal would be for students to familiarize themselves with function secret sharing, along with implementing sorting algorithms using function secret sharing. Our longer-term goal would be to eventually beat the state-of-the-art sorting algorithm at communication cost by using function secret sharing.