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