Secure Query Processing with Linear Online Cost

Query processing under the secure multi-party computation (MPC) model has received increasing attention in recent years. However, all existing MPC query processing algorithms incur a cost of $\Omega(n \log n)$, due to the use of secure sorting. While secure sorting is believed to be inevitable, we observe that it can be moved to a one-time preprocessing stage. By doing so, we manage to reduce the online cost of each subsequent query to linear for free-connex queries, a large class of select-project-joinaggregation queries. This matches the plaintext result for query processing, as free-connex queries are the largest class of queries known to be solvable in linear time on plaintext. We have then built SLOOP, a Secure Linear Online cOst query Processing system. Experimental results show that SLOOP significantly outperforms state-of-the-art methods, while supporting a much broader class of queries.