Secure Query Processing with Linear Complexity

arXiv:2403.13492v1 Announce Type: new
Abstract: 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 …

arxiv can class communication complexity computation cs.cr cs.db free large linear mpc party plaintext protocol query result running select support under