  Encryption provides a method to protect data outsourced to a DBMS provider,
e.g., in the cloud. However, performing database operations over encrypted data
requires specialized encryption schemes that carefully balance security and
performance. In this paper, we present a new encryption scheme that can
efficiently perform equi-joins over encrypted data with better security than
the state-of-the-art. In particular, our encryption scheme reduces the leakage
to equality of rows that match a selection criterion and only reveals the
transitive closure of the sum of the leakages of each query in a series of
queries. Our encryption scheme is provable secure. We implemented our
encryption scheme and evaluated it over a dataset from the TPC-H benchmark.
