Achtung:

Sie haben Javascript deaktiviert!
Sie haben versucht eine Funktion zu nutzen, die nur mit Javascript möglich ist. Um sämtliche Funktionalitäten unserer Internetseite zu nutzen, aktivieren Sie bitte Javascript in Ihrem Browser.

AG Codes und Kryptographie Bildinformationen anzeigen

AG Codes und Kryptographie

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 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: 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.uni-paderborn.de


References:

github.com/jonaschn/awesome-he good starting point. For papers see resource section.


github.com/morfix-io/node-seal


morfix.io/sandbox


github.com/golemfactory/gMorph


github.com/ldsec/lattigo


github.com/vernamlab/cuFHE


github.com/tfhe/tfhe


github.com/jamespayor/vector-homomorphic-encryption

Signatures with flexible Public Keys vs Key-Homomorphic 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 key-homomorphic 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.uni-paderborn.de

References: 
SFPK

eprint.iacr.org/2018/191


Key-Homomorphic Signatures

eprint.iacr.org/2016/792


Mercurial Signatures

eprint.iacr.org/2018/923

Weighed Global Perfect Coin

One of the central methods for decentralized systems is the so-called 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:

  1. Understand weighted threshold secret sharing based on Benaloh/Leichter (the paper is rather old and could use a more modern writeup)
  2. (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).
  3. Design a weighted threshold signature scheme using the weighted secret sharing as a (black-box) 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 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

Implementation and Overview of Groth-Sahai Non-Interactive Zero-Knowledge Proofs of Knowledge

In the field of zero-knowledge (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 non-interactive, then called NIZK, via the Fiat-Shamir heuristic in the random oracle model (ROM). Besides that there are other NIZK constructions such as the commonly used Groth-Sahai 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 use-cases 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.uni-paderborn.de

References:

https://eprint.iacr.org/2007/155.pdf

Implementation and Overview of Structure-Preserving Signature Schemes

Structure-preserving 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 structure-preserving 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.uni-paderborn.de

References:

https://www.iacr.org/archive/crypto2011/68410646/68410646.pdf

https://eprint.iacr.org/2015/076.pdf

Privacy-Preserving 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.uni-paderborn.de

Weighted Global Perfect Coin

One of the central methods for decentralized systems is the so-called 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:

  1. Understand weighted threshold secret sharing based on Benaloh/Leichter (the paper is rather old and could use a more modern writeup)
  2. (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).
  3. Design a weighted threshold signature scheme using the weighted secret sharing as a (black-box) 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.

Die Universität der Informationsgesellschaft