Anonymous Webs of Trust

Abstract. Webs of trust constitute a decentralized infrastructure for es-tablishing the authenticity of the binding between public keys and users and, more generally, trust relationships among users. This paper intro-duces the concept of anonymous webs of trust – an extension of webs of trust where users can authenticate messages and determine each other’s trust level without compromising their anonymity. Our framework com-prises a novel cryptographic protocol based on zero-knowledge proofs, a symbolic abstraction and formal verification of our protocol, and a proto-typical implementation based on the OpenPGP standard. The framework is capable of dealing with various core and optional features of common webs of trust, such as key attributes, key expiration dates, existence of multiple certificate chains, and trust measures between different users.