Algorithms

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.

Tags: Algorithms, Statistics, Security, All Years

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.

Tags: Data Structures, Algorithms, Security, All Years

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.

Tags:  Algorithms, Cryptography, C/C++, Security, All Years

In this project, students will evaluate a recently proposed CDC algorithm and compare it against state-of-the-art techniques. Working in teams, students will use open-source implementations and real-world datasets to conduct benchmarking experiments and measure metrics such as chunking throughput, chunk-size distributions, and deduplication efficiency. Team members will focus on complementary tasks, including experiment design, dataset preparation, benchmarking, data analysis, and visualization. The primary goal during the program is to evaluate the algorithm and understand its strengths and limitations. Students who continue beyond the program may also explore integrating the algorithm into an open-source benchmarking framework and investigating further improvements to chunking techniques.

Tags: Systems, Algorithms, C/C++, Go, Python, All Years