Offene Themen für Arbeiten
Wenn Sie eines der hier gelisteten Themen anspricht, melden Sie sich bei Prof. Blömer oder schauen Sie in einem unserer Hangouts vorbei und sprechen informell mit uns. 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.
Masterarbeiten
 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.
Contact: Sascha Brauer
 (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 this thesis there will be enough time to study and discuss FHE in general and to look into the available libraries.Contact: Laurens Porzenheim, laurensp 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
 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.
Bachelorarbeiten
 Analyzing realworld 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 realworld 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 realworld 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  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.