In this paper, we study the seemingly paradoxical notion of anonymous authentication: authenticating yourself without revealing your identity. Before studying the technical aspects of anonymous Internet connections and anonymous authentication, we begin with a discussion of privacy and why it is important. Although the necessity of privacy is well accepted in the computer security community, the concrete reasons as to why are often not understood. We will demonstrate that such an understanding is crucial for providing technical solutions that solve the real problems at hand. Given this background, we briefly survey the known technologies for constructing anonymous Internet connections. Finally, we study how it is possible to achieve anonymous authentication (on top of anonymous Internet connections). We present definitions and a number of different protocols with different properties. In addition to the basic problem, we also show how it is possible (in a certain model) to achieve revocable anonymity, and explain why this is of importance.