This dissertation covers two topics of interest for network applications: lookup protocols, a basic building block for distributed systems, and ring signatures, a powerful primitive for anonymous communication. In the first part of this work, we review lookup protocols, distributed algorithms that allow users to publish a document as well as to look up a published document that matches a given name. Our first major contribution is to design Local Minima Search (LMS), a new efficient lookup protocol for a model in which a node is physically connected to a few other nodes and may only communicate directly with them. Our second major contribution is the formulation of a new model in which we allow an arbitrary number of misbehaving nodes, but we assume a restriction on their network addresses. We then design a new lookup protocol for this setting.

In the second part of this dissertation, we present our work on ring signatures, a variant of digital signatures, which enables a user to sign a message so that a set of possible signers is identified, without revealing which member of that set actually generated the signature. Our first contribution on this topic is new definitions of security which address attacks not taken into account by previous work. As our second contribution, we design the first provably secure ring signature schemes in the standard model.