We study oblivious storage (OS), a natural way to model privacy-preserving
data outsourcing where a client, Alice, stores sensitive data at an
honest-but-curious server, Bob. We show that Alice can hide both the content of
her data and the pattern in which she accesses her data, with high probability,
using a method that achieves O(1) amortized rounds of communication between her
and Bob for each data access.

Oblivious RAM simulation is a method for achieving confidentiality and
privacy in cloud computing environments. It involves obscuring the access
patterns to a remote storage so that the manager of that storage cannot infer
information about its contents. Existing solutions typically involve small
amortized overheads for achieving this goal, but nevertheless involve
potentially huge variations in access times, depending on when they occur. In
this paper, we show how to de-amortize oblivious RAM simulations, so that each
access takes a worst-case bounded amount of time.

In this paper, we study methods for improving the efficiency and privacy of
compressed DNA sequence comparison computations, under various querying
scenarios. For instance, one scenario involves a querier, Bob, who wants to
test if his DNA string, $Q$, is close to a DNA string, $Y$, owned by a data
owner, Alice, but Bob does not want to reveal $Q$ to Alice and Alice is willing
to reveal $Y$ to Bob \emph{only if} it is close to $Q$. We describe a
privacy-enhanced method for comparing two compressed DNA sequences, which can
be used to achieve the goals of such a scenario.

We give efficient data-oblivious algorithms for several fundamental geometric
problems that are relevant to geographic information systems, including planar
convex hulls and all-nearest neighbors. Our methods are "data-oblivious" in
that they don't perform any data-dependent operations, with the exception of
operations performed inside low-level blackbox circuits having a constant
number of inputs and outputs.

We study the classic graph drawing problem of drawing a planar graph using
straight-line edges with a prescribed convex polygon as the outer face. Unlike
previous algorithms for this problem, which may produce drawings with
exponential area, our method produces drawings with polynomial area. In
addition, we allow for collinear points on the boundary, provided such vertices
do not create overlapping edges.

The round-trip distance function on a geographic network (such as a road
network, flight network, or utility distribution grid) defines the "distance"
from a single vertex to a pair of vertices as the minimum length tour visiting
all three vertices and ending at the starting vertex. Given a geographic
network and a subset of its vertices called "sites" (for example a road network
with a list of grocery stores), a two-site round-trip Voronoi diagram labels
each vertex in the network with the pair of sites that minimizes the round-trip
distance from that vertex.

We introduce the straggler identification problem, in which an algorithm must
determine the identities of the remaining members of a set after it has had a
large number of insertion and deletion operations performed on it, and now has
relatively few remaining members. The goal is to do this in o(n) space, where n
is the total number of identities. The straggler identification problem has
applications, for example, in determining the set of unacknowledged packets in
a high-bandwidth multicast data stream.