Privacy Preserving Online Algorithms
In secure multi-party computation a number of parties wants to compute a function over their inputs such that their inputs are kept private. The participating parties shall only learn their prescribed output without learning anything beyond that. The output can be either the same for all parties or each party obtains a different output. A trusted third party can be used to perform these computations. However, in some settings the parties want to keep their inputs private, e.g., if it is confidential or private information the parties are not willing to share with anyone. In order to keep the inputs private the parties avoid the trusted third party by computing the function in a distributed fashion, i.e., they jointly execute a secure protocol to simulate the trusted third party. In addition, such a protocol shall provide privacy and security in the presence of adversaries, i.e., a malicious party that wants to learn more than intended or deviates from the protocol specification arbitrarily.
For the most common secure multi-party computation settings it is assumed that everything is known prior to the protocol execution, i.e., the parties know their personal input and the set of parties participating in the protocol execution is somehow known. For such a determined setting there exist already a variety of protocols for different requirements. However, there are cases where the scenario is more uncertain and might change over time.
The aim of this dissertation project is to analyze these scenarios in more detail and provide a framework to define security and privacy in these settings. We will focus our research on online algorithms and develop protocols that can deal with different types of uncertainty.