ORQ: Complex Analytics on Private Data with Strong Security Guarantees

Computer Science > Cryptography and Security [Submitted on 13 Sep 2025 (v1), last revised 23 Jun 2026 (this version, v2)] ORQ: Complex Analytics on Private Data with Strong Security Guarantees Eli Baum, Sam Buxbaum, Nitin Mathai, Muhammad Faisal, Vasiliki Kalavri, Mayank Varia, John Liagouris We present ORQ, a system that enables collaborative analysis of large private datasets using cryptographically secure multi-party computation (MPC). ORQ protects data against semi-honest or malicious parties and can efficiently evaluate relational queries with multi-way joins and aggregations that have been considered notoriously expensive under MPC. To do so, ORQ eliminates the quadratic cost of secure joins by leveraging the fact that, in practice, the structure of many real queries allows us to join records and apply the aggregations "on the fly" while keeping the result size bounded. On the system side, ORQ contributes generic oblivious operators, a data-parallel vectorized query engine, a communication layer that amortizes MPC network costs, and a dataflow API for expressing relational analytics -- all built from the ground up. We evaluate ORQ in LAN and WAN deployments on a diverse set of workloads, including complex queries with multiple joins and custom aggregations. When compared to state-of-the-art solutions, ORQ significantly reduces MPC execution times and can process one order of magnitude larger datasets. For our most challenging workload, the full TPC-H benchmark, we report results entirely under MPC with Scale Factor 10 -- a scale that had previously been achieved only with information leakage or the use of trusted third parties. Comments: Extended version, appeared at SOSP 2025. Code available at this https URL Subjects: Cryptography and Security (cs.CR); Databases (cs.DB) Cite as: arXiv:2509.10793 [cs.CR]   (or arXiv:2509.10793v2 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2509.10793 Focus to learn more Related DOI: https://doi.org/10.1145/3731569.3764833 Focus to learn more Submission history From: Eli Baum [view email] [v1] Sat, 13 Sep 2025 03:19:01 UTC (1,869 KB) [v2] Tue, 23 Jun 2026 13:17:51 UTC (4,300 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2025-09 Change to browse by: cs cs.DB References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)