  We study the problem of composing and optimizing relational query plans under
secure multi-party computation (MPC). MPC enables mutually distrusting parties
to jointly compute arbitrary functions over private data, while preserving data
privacy from each other and from external entities.
  In this paper, we propose a relational MPC framework based on replicated
secret sharing. We define a set of oblivious operators, explain the secure
primitives they rely on, and provide an analysis of their costs in terms of
operations and inter-party communication. We show how these operators can be
composed to form end-to-end oblivious queries, and we introduce logical and
physical optimizations that dramatically reduce the space and communication
requirements during query execution, in some cases from quadratic to linear
with respect to the cardinality of the input.
  We provide an efficient implementation of our framework, called Secrecy, and
evaluate it using real queries from several MPC application areas. Our results
demonstrate that the optimizations we propose can result in up to 1000x lower
execution times compared to baseline approaches, enabling Secrecy to outperform
state-of-the-art frameworks and compute MPC queries on millions of input rows
with a single thread per party.
