Open Theses
If you are interested in writing a thesis with us, please contact Prof. Blömer or come by one of our hangouts and talk to us informally. Even if none of the listed topics below interests you, still feel free to contact us and we'll try to find a good topic together. If you are looking for a general overview of open topics including other working groups, then please see this overview.
Master's theses
 Fuzzy Clustering using musimilar Bregman Divergences

Fuzzy kMeans is a popular generalization of the classical kMeans 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 musimilar 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 kMeans problem using musimilar Bregman divergences and also for the Fuzzy kMeans 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 kMeans problem using musimilar Bregman divergences.
 (Fully) Homomorphic Encryption in practice

The goal of this thesis is to research what the real world performance for (fully) homomorphic encryption FHE is nowadays.
Depending on the supported functions what are the real world running times achieved by different libraries.
For this topic one has to be proficient using and understanding programming APIs (not limited to one programming language).
Additionally the theory behind FHE has to be studied (not in detail, but on a basic level).
During the proposal time and the first month of the BA thesis there will be enough time to study and discuss FHE in general and to look into the available libraries.Contact: Fabian Eidens feidens at mail.unipaderborn.de
References:github.com/jonaschn/awesomehe good starting point. For papers see resource section.
github.com/morfixio/nodeseal
github.com/golemfactory/gMorph
github.com/jamespayor/vectorhomomorphicencryption
 Signatures with flexible Public Keys vs KeyHomomorphic Signatures vs Mercurial Signatures

Clarify the relation between the three signature types and what each of them offers.
Are there any equivalences between the definitions, e.g. SFPK does not imply keyhomomorphic signatures?
For this topic one has to first study the three signature types and then try to prove a relation based on the definitions.
Each of the types define a homomorphism on some of the elements of the signature, e.g. public and secret key homomorphism.
Contact: Fabian Eidens, feidens at mail.unipaderborn.deReferences:
SFPK
KeyHomomorphic Signatures
Mercurial Signatures
 Weighed Global Perfect Coin

One of the central methods for decentralized systems is the socalled leader election, where a bunch of nodes must agree on a leader. One nice way to implement this with cryptography is through threshold signatures: every node gets a special key that is useless on its own, but when at least k nodes come together, they can generate a unique certificate for the leader, i.e. everyone can check that the decision was made correctly (and dishonest nodes cannot influence the election).
Our colleagues at Prof. Scheideler's group need a weighted leader election. In their scenario, some nodes may be more trustworthy than others. Each node has a trustworthiness score attached. Leader election should now be possible when the sum of trust scores is large enough (previously: any k nodes could elect a leader). Our goal is to design an efficient leader election system that works with weights. The trivial version would be to assign w many keys to a weight w node, but for large weights, this is clearly not feasible.
The roadmap for this project is as follows:
 Understand weighted threshold secret sharing based on Benaloh/Leichter (the paper is rather old and could use a more modern writeup)
 (optional) understand more efficient threshold secret sharing (which only works under some conditions, we would like to understand how realistic those are in our scenario).
 Design a weighted threshold signature scheme using the weighted secret sharing as a (blackbox) subroutine (this can be complex or very easy, depending on how many nice security properties the construction shall have).
For a Master's thesis, the whole project could potentially be accomplished (we can negotiate the details for this during the proposal phase of the work and you can set a focus on specific subtopics as you prefer).
This is a pretty cool project (elegant methods, useful outcome), so if you're interested (or you have informal questions), contact Jan.
Bachelor's theses
 Analyzing realworld applications of secure MPC protocols

A recent case study ( https://eprint.iacr.org/2018/450.pdf ) considers the usage of multiparty computation (MPC) protocols in realworld applications. In short, MPC protocols aim at enabling several parties to jointly evaluate a given function based on their private input data. In cryptography, protocols are usually considered secure when nothing beyond the function's results is leaked during an execution. Security models vary in the capacities of adversaries, e.g. ranging from eavesdropping to completely corrupting and controlling a certain number or fraction of the executing parties. There exist several fundamental protocols which are applicable to any given (computable) function achieving different levels of security. However, their efficiency is too low for realworld applications.
To match the realworld constraints, special MPC protocols and compositions thereof have been designed for certain use cases. The 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 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", ...)?
 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?
 ...
 Implementation and Overview of GrothSahai NonInteractive ZeroKnowledge Proofs of Knowledge

In the field of zeroknowledge (security for the prover P) proofs of knowledge (security for the verifier V of the proof) there is the interactive Schnorr protocol between P and V that one might know from a bachelor's course. Such a protocol can be turned noninteractive, then called NIZK, via the FiatShamir heuristic in the random oracle model (ROM). Besides that there are other NIZK constructions such as the commonly used GrothSahai NIZK (GS NIZK). GS NIZK is specifically tailored for proving relations over bilinear groups (groups equipped with a pairing).
Understanding the variants of GS NIZK the features, advantages and common usecases is are the first steps in this thesis. The goal at the end is to have an implementation of GS NIZK in our library Cryptimeleon. For this, one first has to research GS NIZK, its variants, related constructions, and the security. This topic allows us to move the focus either to the theoretical part or more to the practical part.
Contact: Fabian Eidens, feidens at mail.unipaderborn.de
References:
 Implementation and Overview of StructurePreserving Signature Schemes

Structurepreserving signatures (SPS) are a variant of digital signatures where public key, message and the signature itself is from the same structure, e.g. they are group elements. This might sound uninteresting at first glance, but the feature called structurepreserving comes in handy in situations where you just want to sign a group element, e.g. a public key of a user.
The goal of this thesis is to give an overview of existing SPS schemes and their efficiency. The most promising schemes should then be implemented using our Cryptimeleon library. This topic allows us to focus more on the theoretical part or more on the practical part.
Contact: Fabian Eidens, feidens at mail.unipaderborn.de
References:
https://www.iacr.org/archive/crypto2011/68410646/68410646.pdf
 PrivacyPreserving Collection and Evaluation of Log Files

In real world scenarios log files are maintained for several reasons, e.g. to trace misbehavior or some regulations enforce some collection of data. One example is a company's network where one wants to trace users that use the network for things that are not permitted, e.g. visiting malware infected websites. These log files are in general an infringement of privacy. They collect all kinds of data not limited to such misbehaviors.
In this thesis the goal is to develop and analyze a theoretical concept of a data collection system that on the one side protects user's privacy and on the other side allows tracing of misbehaving users. More general speaking, a company that deploys such a system should still be able to evaluate some functions over the collected data, e.g. average bytes downloaded by a user, top ten domains visited. The thesis should also answer which functions are viable while ensuring privacy, where the kind of privacy is also an open question. While answering these questions one has to keep the tradeoff between evaluations of collected data and privacy in mind. Simply put, collecting the name of the employe in clear leaves no room for privacy, where not collecting the name in any form (e.g. encrypted) erases the possibility to trace the user.
We envision that the thesis first looks into a simple scenario (with equality as the evaluation function) and solutions based on hash function and deterministic encryption. Afterwards we want to take a look at more advanced scenarios and solutions.
Supervisor: Fabian Eidens, feidens at mail.unipaderborn.de
 Weighted Global Perfect Coin

One of the central methods for decentralized systems is the socalled leader election, where a bunch of nodes must agree on a leader. One nice way to implement this with cryptography is through threshold signatures: every node gets a special key that is useless on its own, but when at least k nodes come together, they can generate a unique certificate for the leader, i.e. everyone can check that the decision was made correctly (and dishonest nodes cannot influence the election).
Our colleagues at Prof. Scheideler's group need a weighted leader election. In their scenario, some nodes may be more trustworthy than others. Each node has a trustworthiness score attached. Leader election should now be possible when the sum of trust scores is large enough (previously: any k nodes could elect a leader). Our goal is to design an efficient leader election system that works with weights. The trivial version would be to assign w many keys to a weight w node, but for large weights, this is clearly not feasible.
The roadmap for this project is as follows:
 Understand weighted threshold secret sharing based on Benaloh/Leichter (the paper is rather old and could use a more modern writeup)
 (optional) understand more efficient threshold secret sharing (which only works under some conditions, we would like to understand how realistic those are in our scenario).
 Design a weighted threshold signature scheme using the weighted secret sharing as a (blackbox) subroutine (this can be complex or very easy, depending on how many nice security properties the construction shall have).
For a Bachelor's thesis, we'd suggest to concentrate on (1) or (3) depending on your interests. We can talk about the details.
This is a pretty cool project (elegant methods, useful outcome), so if you're interested (or you have informal questions), contact Jan.