  We present a relational MPC framework for secure collaborative analytics on
private data with no information leakage. Our work targets challenging use
cases where data owners may not have private resources to participate in the
computation, thus, they need to securely outsource the data analysis to
untrusted third parties. We define a set of oblivious operators, explain the
secure primitives they rely on, and analyze 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 or from linear
to logarithmic with respect to the cardinality of the input.
  We implement our framework on top of replicated secret sharing in a system
called Secrecy and evaluate it using real queries from several MPC application
areas. Our experiments demonstrate that the proposed optimizations can result
in over 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.
