Paper 2022/1755

Towards Secure Evaluation of Online Functionalities (Corrected and Extended Version)

Abstract

To date, ideal functionalities securely realized with secure multi-party computation (SMPC) mainly considers functions of the private inputs of a fixed number of a priori known parties. In this paper, we generalize these definitions such that protocols implementing online algorithms in a distributed fashion can be proven to be privacy-preserving. Online algorithms compute online functionalities that allow parties to arrive and leave over time, to provide multiple inputs and to obtain multiple outputs. In particular, the set of parties participating changes over time, i.e., at different points in time different sets of parties evaluate a function over their private inputs. To this end, we propose the notion of an online trusted third party that allows to prove the security of SMPC protocols implementing online functionalities or online algorithms, respectively. We show that any online functionality can be implemented perfectly secure in the presence of a semi-honest adversary, if strictly less than 1/2 of the parties participating are corrupted. We show that the same result holds in the presence of a malicious adversary if it corrupts strictly less than 1/3 of the parties and always allows the corrupted parties to arrive and provide input. Note, this is the corrected and extended version of the work presented in [24].

Note: In the original version [24] we modeled the arrival of parties too abstract, and thus with this corrected version we provide clarification, and model the arrival (and input providing) of parties more explicitly. We also corrected some other minor oversights, and we included additional explanations and details throughout this version. v2: Further clarifications and corrections of wordings.