  We present LINQ, the first join protocol with linear complexity (in both
running time and communication) under the secure multi-party computation model
(MPC). It can also be extended to support all free-connex queries, a large
class of select-join-aggregate queries, still with linear complexity. This
matches the plaintext result for the query processing problem, as free-connex
queries are the largest class of queries known to be solvable in linear time in
plaintext. We have then built a query processing system based on LINQ, and the
experimental results show that LINQ significantly outperforms the state of the
art. For example, it can finish a query on three relations with an output size
of 1 million tuples in around 100s in the LAN setting, while existing protocols
that support the query cannot finish in an hour. Thus LINQ brings MPC query
processing closer to practicality.
