Andreas Klinger: Privacy Preserving Online Algorithms

 

Introduction:

Secure multi-party computation (SMPC) allows parties to evaluate a function over their private inputs in a distributed fashion so that each party only learns its prescribed output and anything it can deduce from combining its prescribed output with its own private input. An SMPC protocol describes the individual communication and computation steps each party follows during the distributed evaluation of the function it implements. Informally speaking, such a protocol is said to securely evaluate the function if it correctly computes the prescribed output of the function and if during the evaluation, the parties do not learn anything that goes beyond what they would learn if the function was evaluated centrally by a trusted third party (TTP) - even in the presence of an adversary. However, the general assumption underlying SMPC is that such a TTP that is incorruptable and trusted by everyone does not exist. Therefore, the parties execute an SMPC protocol to simulate the behavior of a TTP.

Secure function evaluation (SFE), a special case of SMPC, considers functions that could - if they were evaluated by a TTP - be evaluated by a single run of an (offline) algorithm that takes the inputs of a fixed number of parties and computes the desired output for each party. The security notions of SFE can also be extended to reactive SMPC to cover reactive algorithms [Gol04] which allow an a priori known fixed number of parties to provide input over multiple rounds and obtain output in each round. In addition, the output can depend on a state, which itself depends on all previous inputs and outputs.

However, the prominent set of functions or problems that can be solved with the help of online algorithms [FW98] has not yet been considered in SMPC: Online algorithms receive events one after another and for each event they have to decide immediately how to deal with it. The main difference between offline/reactive and online algorithms is that whereas the participating parties are fixed for offline/reactive algorithms, parties can dynamically join and leave in online algorithms.

Secure and privacy preserving protocols for offline (bipartite) matching is an important research field [Gol06, BS14, AC17, WVMW17]. However, using online matching algorithms instead has the added benefit of not requiring to restart the complete computation as soon as a new party joins and thus reducing waiting times. Such online matching problems naturally arise for example when open job positions are to be filled by applicants, or students apply for internship offers and need to be told immediately whether or not they are accepted.

The aim of this dissertation project is to analyze how to securely evaluate online algorithms in a privacy-preserving fashion. We want to model the problem in a general fashion and find its limitations in regard to securely realizing such online functionalities. The main research questions are: How to provide privacy and security for online matching algorithms? What are the limitations? To what degree can privacy be provided?

Model:

Ideally evaluating an online functionality such as online matching in a privacy-preserving way does not only entail protecting the inputs and outputs of all parties involved, and securely keeping a state over a changing set of parties, but also hiding the arrival and departure of parties from the other participating parties. This includes hiding the point in time when a party provides input. We therefore propose several new models for online TTPs that can evaluate online functionalities, i. e., the mapping of inputs and outputs of online algorithms.

References:

• [AC17] B. Anandan and C. Clifton. Secure minimum weighted bipartite matching. In 2017 IEEE Conference on Dependable and Secure Computing, pages 60–67, 2017.
• [BS14] Marina Blanton and Siddharth Saraph. Secure and Oblivious Maximum Bipartite Matching Size Algorithm with Applications to Secure Fingerprint Identification, 2014.
• [FW98] Amos Fiat and Gerhard Woeginger, editors. Online Algorithms: The State of the Art. Springer, 1998.
• [Gol04] Oded Goldreich. Foundations of Cryptography: Basic Applications. Cambridge University Press, 2004.
• [Gol06] Philippe Golle. A Private Stable Matching Algorithm. In International Conference on Financial Cryptography and Data Security, pages 65–80. Springer, 2006.
• [WVMW17] Stefan Wüller, Michael Vu, Ulrike Meyer, and Susanne Wetzel. Using Secure Graph Algorithms for the Privacy-Preserving Identification of Optimal Bartering Opportunities. In Proceedings of the 2017 on Workshop on Privacy in the Electronic Society, WPES ’17, pages 123–132. Association for Computing Machinery, 2017