  Emails today are often encrypted, but only between mail servers---the vast
majority of emails are exposed in plaintext to the mail servers that handle
them. While better than no encryption, this arrangement leaves open the
possibility of attacks, privacy violations, and other disclosures. Publicly,
email providers have stated that default end-to-end encryption would conflict
with essential functions (spam filtering, etc.), because the latter requires
analyzing email text. The goal of this paper is to demonstrate that there is no
conflict. We do so by designing, implementing, and evaluating Pretzel. Starting
from a cryptographic protocol that enables two parties to jointly perform a
classification task without revealing their inputs to each other, Pretzel
refines and adapts this protocol to the email context. Our experimental
evaluation of a prototype demonstrates that email can be encrypted end-to-end
\emph{and} providers can compute over it, at tolerable cost: clients must
devote some storage and processing, and provider overhead is roughly 5 times
versus the status quo.
