Offene Themen für Arbeiten
Neben den hier gelisteten Themen können wir auf Anfrage auch kurzfristig, auf die eigenen Interessen angepasste, Themen finden. Für eine Orientierung, was euch interessieren könnte, empfehlen wir die Forschungsschwerpunkte der Arbeitsgruppe anzuschauen.
Wenn Sie eines der hier gelisteten Themen anspricht, melden Sie sich bei Prof. Blömer. Auch wenn die hier gelisteten Themen Sie nicht ansprechen melden Sie sich gerne und wir finden gemeinsam ein passendes Thema. Wenn Sie allgemein auf der Suche nach Abschlussarbeitsthemen sind dann empfehlen wir zusätzlich diese Übersichtsseite.
- Fuzzy Clustering using mu-similar Bregman Divergences
Fuzzy k-Means is a popular generalization of the classical k-Means problem to soft clusterings. From an algorithmic perspective however, it is much more difficult to compute provably good solutions. Typically, these problems use the squared Euclidean distance to measure how far data points are apart. The squared Euclidean distance is part of the mu-similar Bregman divergences, a large class of dissimilarity measures sharing desirable characteristics.
Using sampling techniques to find good approximations of optimal centroids has proven to work for both, the k-Means problem using mu-similar Bregman divergences and also for the Fuzzy k-Means problem using the squared Euclidean distance. The goal of this thesis is to explore whether this can actually be combined to obtain a good approximation algorithm for the Fuzzy k-Means problem using mu-similar Bregman divergences.
Contact: Johannes Blömer
- Analyzing real-world applications of secure multiparty computation protocols
A recent case study ( https://eprint.iacr.org/2018/450.pdf ) considers the usage of secure multiparty computation (MPC) protocols in real-world applications. MPC protocols, in short, aim at enabling several parties to jointly evaluate a given function based on their private input data. In cryptography, such protocols are usually considered secure when nothing beyond the evaluated function's results is leaked during an execution. Security models vary in the abilities of adversaries, e.g. ranging from eavesdropping to adaptively corrupting and controlling a certain number or fraction of protocol participants. There exist several fundamental protocols which are applicable to any given (computable) function achieving different levels of security. However, their efficiency is often too low for practical applications.
To match real-world constraints, specialized MPC protocols and compositions thereof have been designed for certain use cases. The paper's authors, which also participated in the construction of the 4 considered products, only sketch their used techniques, matched (or at least desired) security properties and achieved performance. Interesting questions to be answered within a thesis, for example, are:
- Which security models underly the products?
- How do two similar products compare to each other (in terms of performance, functionality, security properties, ...)?
- Have security properties been weakened for the sake of efficiency? If yes, where and why?
- How applicable are these products in reality, e.g. considering performance and usability? Are there other interesting products based on MPC protocols used in the wild?
- ...? (Further suggestions)
Contact: Henrik Bröcher, henrik.broecher at upb.de
- (Stable) Matching using Secure Multiparty Computation
The goal of secure multiparty computation protocols is, in general, to allow multiple parties to jointly perform a certain computation using their private inputs, without leaking these inputs to other participants. Existing protocols allow the joint evaluation of arbitrary functions. This generality, however, comes at the cost of efficiency. Therefore, for certain applications, specialized protocols were proposed.
One application is to securely realize matching algorithms. A matching algorithm is used to create a mapping between two disjoint sets of parties, where each party has a (potentially partial) preference order over the parties from the other set, such that the result provides some form of stability. An exemplary algorithm used to solve the so-called “Stable Marriage” problem is the Gale-Shapley algorithm. The goal of this thesis is to (find and) compare existing secure MPC implementations for matching scenarios.
While traditional implementations usually reveal the parties’ preferences either to some trusted third party, the matched partner, or even every participant, secure multiparty computation hides these. This thesis focusses on 1) finding such protocols (e.g. https://shelat.khoury.neu.edu/dl/stable-matching-ccs.pdf, https://crypto.stanford.edu/~pgolle/papers/stable.pdf, https://eprint.iacr.org/2006/332.pdf) and 2) compare these, for example based upon their targeted model of security (active, passive, ...), efficiency, complexity,...
Supervisor: Henrik Bröcher (Maill)
- Threshold Signature Schemes using Multiparty Computation
Threshold signature schemes enhance “normal” digital signature schemes in the sense that from n parties a fraction k<n is (at least) required to create a valid signature with respect to a jointly computed public key. This is a special use case for secure multiparty computation protocols where n parties jointly compute a given function (here, for example, the signing algorithm) without revealing their private data (here, their “shares” of a private key). Typically, this privacy of inputs is only guaranteed when a threshold k of all n parties honestly runs a given code.
This topic aims to give an overview on existing threshold signature solutions, underlying assumptions, their security properties, and further features we/you identify as meaningful. A very recent publication concerning threshold signatures and MPC is, for example, https://eprint.iacr.org/2022/374.pdf.
Supervisor: Henrik Bröcher (Maill)
- Parameters in Lattices: Bounds and Heuristics
In lattice cryptography there are many parameters. Many, if not all useful theorems require certain bounds on these parameters. Examples for these parameters are the length of some vectors under the L2 norm or the infinity norm, the spectral norm of matrices of certain distributions, or the so-called smoothing parameter.
When instantiating cryptographic schemes based on lattices, one has to decide on values for these parameters, such that security still holds. However, theoretical bounds can often be quite conservative, leading to not-so efficient schemes.
The question now is whether there are heuristics with which one could choose values for the parameters and how much these heuristics could improve the efficiency of the cryptographic schemes.
Your task is to identify interesting parameters, to create and implement heuristic tests for bounds and to compare the heuristics to the theoretical bounds. Afterwards you compare the efficiency of instantiations of some cryptographic schemes based on your heuristics and theoretical bounds.
A Decade of Lattice Cryptography: https://eprint.iacr.org/2015/939.pdf A good starting point to learn about lattices.
Supervisor: Laurens Porzenheim Mail