My PhD Thesis

Distributed Key Generation and Its 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 (www.torproject.org), 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.