My PhD Thesis

Distributed Key Generation and Its Applications

Layman Abstract.
A trusted authority, in some form, is essential for many secure systems. However, this requirement always leads to the problem of single point of failure and sometimes to the more undesirable problem of key escrow. Solving these problems is of paramount importance while designing systems over the Internet where denial-of-service attacks and malicious entities are widespread. A distributed key generation (DKG) protocol overcomes these problems using a complete distribution of the trust among a set of servers such that subsets of size greater than a threshold can reveal or use the shared secret, while smaller subsets cannot. In this thesis, we make contributions to the concept of DKG and propose three applications.

The existing DKG protocols do not provide a completion guarantee over the networks such as the Internet having unbounded transmission delays. Observing this, we design the first DKG protocol for use over the Internet, and demonstrate its practicality with experiments over PlanetLab, a global network that supports planetary-scale services. On the theoretical front, we reduce the size of broadcasts required by DKG protocols by a linear factor by proposing a constant-size cryptographic commitment scheme for univariate polynomials.

Identity-based cryptography (IBC) greatly simplifies public-key management in cryptographic infrastructures. However, IBC has an authority, private-key generator (PKG), that can decrypt encrypted messages in the system without any detection. This asks for the ultimate trust in a PKG. As our first application, we use our DKG protocol to define distributed PKGs in all important identity-based encryption (IBE) frameworks. Our second application lies in the area of onion routing (, which is the most prominent mechanism for anonymous web browsing. We use one of our distributed PKGs to define a protocol that solves the scalability problem in single-pass onion routing. In a peer-to-peer network structured as a distributed hash table (DHT), quorums are small groups of nodes that annihilate malicious behaviors with a majority effect. As our third application, we design a distributed signature architecture in quorum-based DHTs, and use it to define two robust communication protocols that simultaneously solve the conflicting problems of obtaining reliability and avoiding spamming.

Thesis Committee.
Prof. Ian Goldberg (Supervisor), Prof. Urs Hengartner, Prof. Alfred Menezes, Prof. Michael Reiter and Prof. Douglas R. Stinson
Thesis WebPage at UWaterloo Library: follow
Theis in PDF form: follow

Back to to my Academic webpage.
Copyright © 2011 Aniket Kate, MPI-SWS, Germany.