Lookup Protocols and Techniques for Anonymity
Lookup Protocols and Techniques for Anonymity
Files
Publication or External Link
Date
2006-08-18
Authors
Morselli, Ruggero
Advisor
Katz, Jonathan
Bhattacharjee, Bobby
Bhattacharjee, Bobby
Citation
DRUM DOI
Abstract
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.