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:
- 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 (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.