UC Irvine

This dissertation addresses "distributed cryptography" in the presence of "almost" asynchrony. Many machines collaborate to accomplish some goal -- whether agreeing on a bit, secure group messaging, or computing a function of their inputs -- over a network that is not guaranteed to deliver messages within a known time constraint. The applications in this dissertation explore new tradeoffs on the spectrum of synchronous to asynchronous executions, adversarial advantages, and efficiency.

First, we explore consensus protocols in both a poorly-studied permissioned model and a novel permissionless model. Consensus protocols require that all parties agree on the same output bit, and that the output is constrained by their inputs. In the permissioned model, we study optimal constraints on highly efficient, sublinear-round protocols, where somewhat faulty but otherwise correct parties must produce outputs consistent with fully functional, honest parties. In the permissionless model we ask under what synchronization conditions consensus is possible at all, and illustrate the power of a technique common to most Proof-of-X primitives to achieve consensus in a very weakly synchronized model.

We then explore asynchronous, concurrent group messaging and provide a framework for reasoning about group keys that simplifies their security proofs. In concurrent group messaging, parties send application messages while also continuously updating the group key; in an asynchronous network, there may be many simultaneous latest group keys due to concurrent evolutions by different parties. Using our framework, we prove security of a novel protocol that achieves better security properties in asynchronous networks than any previous protocol.

Finally, we analyze timed cryptographic primitives and introduce a novel model for proving security of arbitrarily composed timed primitives. The model permits an adversary to operate an asynchronous network, but the adversary is bounded in depth to model realistic passage of time.

For each application, we discuss or prove how the constraints applied to the asynchronous model make the problem tractable, and explain how the resulting models represent progress towards cryptography that could be deployed.