Secure Query Processing with Linear Complexity
<|reference_start|>Secure Query Processing with Linear Complexity: 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.<|reference_end|>
@article{luo2024secure,
    title={Secure Query Processing with Linear Complexity},
    author={Qiyao Luo, Yilei Wang, Wei Dong, Ke Yi},
    journal={arXiv preprint arXiv:2403.13492},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.13492},
    primaryClass={cs.CR cs.DB}
}