Theory and Practice of Deploying Anonymous Credential Schemes

Anonymous credentials are a complex and versatile primitive designed to provide users with tight and fine-grained control over the information they disclose while securely authenticating themselves to digital services and organisations. This thesis explores the theory and practice of anonymous credential schemes, describing their features and variants, explaining the challenges they face, and proposing solutions and improvements.
In the theoretical portion of the thesis, we formally define anonymous credentials and identify different methods and approaches to constructing them, yielding a framework that can be used to categorise and compare credential schemes. Using this framework, we summarise the existing anonymous credential literature, sorting credential schemes into a loose taxonomy and identifying notable trends and innovations. We then explore one such innovation, looking in detail at the recent development of mercurial signatures, a new primitive capable of functioning as an anonymous credential without the need for extensive zero-knowledge protocols. We recount the development of this family of credentials and then provide and prove our own novel extension to them, showing how they can be made to include selectively-disclosed attributes, a feature that is central to most anonymous credential schemes.
The latter chapters of the thesis address the more practical concerns facing anonymous credential development, investigating issues that have made it difficult for them to gain a foothold in real-world use cases. We analyse the efficiency of existing anonymous credentials, noting the differences between older, more established credential schemes and newer, more innovative ones, and the ways in which efficiency is impacted by different design approaches. We also highlight other challenges that arise in implementation, such as the problem of how to revoke credentials that are lost or abused, and how to prevent the illicit sharing of credentials. We then explore the broader field of identity management, compare the ways in which some identity management systems apply anonymous credentials, and see how they address the implementation challenges they face. Finally, we point to the open areas for future research that this work helps to identify.