Adam J. Aviv
Columbia University
USA

Michael E. Locasto
Columbia University
USA

Shaya Potter
Columbia University
USA

Angelos D. Keromytis
angelos@cs.columbia.edu
USA

The increasing centralization of networked services places users' data
at considerable risk. For example, many users store their email on
remote servers rather than on their own client machine. Doing so
allows users to gain the benefit of regular backups and remote access,
but it also places a great deal of trust in the server. Since most
email is stored in plaintext, a compromise of the server also implies
the loss of confidentiality and integrity of the email stored
therein. Although users could employ an encryption scheme ( e.g.,
PGP), such measures are not widely adopted, require action on behalf
of the sender, and only provide partial protection (the email
headers remain in the clear).

We propose an alternative solution that begins with the server
encrypting newly arriving email, including the headers, body, and
attachments, using a public-key encryption standard. Unfortunately,
this approach also prevents users from remotely searching their
email. To solve this problem, we present Secure Searchable Automated
Remote Email Storage (SSARES), a novel system that offers a practical
approach to securing remotely stored email while allowing privacy
preserving searching. SSARES uses a combination of Identity Based
Encryption and Bloom Filters, revealing little information about
search keywords and queries. SSARES remains largely transparent to
both the email sender and recipient. We present an evaluation of our
system based on our preliminary prototype, and identify areas for
future improvement.

Keywords: Email, Security, Privacy, Secure Searching

Read Paper (in PDF)