Load-Balanced Server-Aided MPC in Heterogeneous Computing

Most existing MPC protocols consider the homogeneous setting, where all the MPC players are assumed to have identical communication and computation resources. In practice, the player with the least resources often becomes the bottleneck of the entire MPC protocol execution. In this work, we initiate the study of so-called <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">load-balanced MPC</i> in heterogeneous computing. A load-balanced MPC protocol can adjust the workload of each player accordingly to maximize the overall resource utilization. In particular, we propose new notions called <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">composite circuit</i> and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">composite garbling scheme</i>, and construct two efficient server-aided protocols with malicious security and semi-honest security, respectively. Our maliciously secure protocol is over <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$400\times $ </tex-math></inline-formula> faster than the authenticated garbling protocol (CCS ’17) and up to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$4.3\times $ </tex-math></inline-formula> faster than the state-of-the-art server-aided MPC protocol of Lu et al. (TDSC ’23); our semi-honest protocol is up to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$173\times $ </tex-math></inline-formula> faster than the optimized BMR protocol (CCS ’16) and is up to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$3.8\times $ </tex-math></inline-formula> faster than the protocol of Lu et al.