Secure Query Processing with Linear Complexity
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911850199777280 |
|---|---|
| author | Luo, Qiyao Wang, Yilei Dong, Wei Yi, Ke |
| author_facet | Luo, Qiyao Wang, Yilei Dong, Wei Yi, Ke |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_13492 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Secure Query Processing with Linear Complexity Luo, Qiyao Wang, Yilei Dong, Wei Yi, Ke Cryptography and Security Databases 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. |
| title | Secure Query Processing with Linear Complexity |
| topic | Cryptography and Security Databases |
| url | https://arxiv.org/abs/2403.13492 |