SecureCA: Communication- and Round-Efficient Join and Group-By-Aggregation in Secure Database Services

Today, secure collaborative analytics has been a basic functionality of private and distributed database services. Efficiently handling multi-table SQL queries, whose underlying pivotal operators are join and group-by-aggregation, creates particular challenges for building a large-scale service in a practical way. However, previous works fail to implement operators with low communications, as they rely on costly oblivious operators such as sorting and merging. In this work, we propose SecureCA, a series of communication-efficient protocols for unique-key join and group-by-aggregation. Our protocols support semi-honest three-party join queries, as well as common aggregation methods such as Sum, Avg, and Max/Min. In these protocols, we make a trade-off between efficiency and security and design a novel server-aided architecture that breaks the symmetric structure among computation nodes, transforming high-cost multi-party oblivious operators and correlated randomness generation into local computations while also eliminating redundant sorting for join and group-by operations. Compared to state-of-the-art works, when scaled to millions of records, our protocols perform closed-source work,$\text{AHK}^{+}$, by$3 \sim 16 \times$under a wide-area network, and existing open-source work, Secrecy, by$9 \sim 364 \times$.