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.
Many non-private implementations of algorithms often access data structures at indices determined at runtime. Since such indices are determined by the input, revealing such indices would compromise privacy according to our definition. While there are asymptotically efficient solutions to adapt these algorithms to the MPC model, these solutions use generic constructions, and the constant factors make using them impractical.
We observe that many algorithms do not need the full power of random access. In fact, previous work has implemented MPC algorithms that are efficient asymptotically and with much more practical constants by designing oblivious data structures, which are data structures whose access patterns do not reveal what operation is performed on them or the intended target of the operation. Our goal is to design a new oblivious data structure, implement it, and test how it speeds up the implementation of a specific algorithm by comparing it to other MPC implementations of the algorithm. A successful implementation would give us a new way to speed up a class of algorithms that use the same data structure.
A background in algorithms and data structures is necessary. Students will get experience in designing and implementing data structures, along with experiment design when benchmarking their implementation. The main short-term goal would be for students to gain experience designing and implementing oblivious data structures, while a long-term goal would be an oblivious data structure that can be used in a wide range of practical algorithms.