Secure multi-party computation (SMPC) enables multiple parties to evaluate functions of their private inputs, in a way such that none of the parties can learn anything about the other parties' private input but what can be learned from their own input and its output of the function evaluation. There are various practical applications for SMPC with runtimes ranging from a few seconds to multiple days. The performance of a protocol typically depends on the number of parties, the problem size, and the network setting. Thus, evaluating the applicability and performance of an SMPC protocol requires extensive benchmarking in varying settings, which can be very time and resource consuming, especially in slow network settings.

In secure multi-party computation (SMPC), it is considered that multiple parties that are known to each other evaluate a function over their private inputs in a secure fashion. The participating parties do not learn anything about each other's private inputs beyond what can be deduced from their own input and output. The assumption that the parties know each other, however, does not seem suitable for all potential applications of SMPC. In some applications participants may not only want to hide their private inputs and outputs, but may also want to hide the fact that they are participating in a given function evaluation in the first place. We therefore propose an anonymous system for SMPC that allows parties to anonymously evaluate a function of their private inputs in a fully distributed and secure fashion. The proposed system allows authorized parties to execute an SMPC protocol robust with penalty against a dishonest majority in the presence of a malicious adversary. During the protocol execution, the system guarantees that all participating parties stay anonymous w. r. t. each other as well as any third parties. In addition, it guarantees that in each function evaluation all participating parties are unique, i. e., no party can participate as more than one entity.

In classical secure multi-party computation (SMPC) it is assumed that a fixed and a priori known set of parties wants to securely evaluate a function of their private inputs. This assumption implies that online problems, in which the set of parties that arrive and leave over time are not a priori known, are not covered by the classical setting. Therefore, the notion of online SMPC has been introduced, and a general feasibility result has been proven that shows that any online algorithm can be implemented as a distributed protocol that is secure in this setting [22, 23]. However, so far, no online SMPC protocol that implements a concrete online algorithm has been proposed and evaluated such that the practicality of the constructive proof is an open question.

To date, ideal functionalities securely realized with secure multi-party computation (SMPC) mainly considers functions of the private input 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 join 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.