In this paper we i.ntroduce R, a distributed public key management service for open networks. f'l offers interfaces by which clients can register, retrieve, and revoke public keys, and escrow, use (to decrypt messages), and recover private keys, all of which can be subjected to access con- trol policy. R is built using multiple servers in a way that ensures its correct operation despite the malicious corrup- tion of fewer than one-third of its component servers. We describe the design of R, the protocols underlying its oper- ation, performance in our present implementation, and an experimental application of the service.