Technologies that enable confidential communication and anonymous authentication are important for providing privacy for users of internet services.Unfortunately, encryption and anonymity, while good for privacy, make it hard to hold bad actors accountable for misbehavior. Internet services rely on seeing message content to detect spam and other harmful content; services must also be able to identify users to attribute and respond to abuse complaints. This tension between privacy and accountability leads to one of two suboptimal outcomes: Services require excessive trust in centralized entities to hold users accountable for misbehavior, or services leave themselves and/or their users open to abuse. In this dissertation, I will examine where this tension arises in our modern private messaging systems and how gaps in accountability can and do lead to real-world attacks.I will discuss how I have addressed this tension through the design of new cryptographic protocols. In particular, I will present new protocols for secure abuse-reporting, anonymous blocklisting, and transparent key infrastructure.