💻 computer science

ORQ: Complex Analytics on Private Data with Strong Security Guarantees

ORQ 是一个新颖的系统，它通过通过即时聚合消除安全连接的二次方成本，从而实现了在不依赖可信第三方或信息泄露的情况下，在多方计算环境下达到 TPC-H Scale Factor 10 的性能，进而实现对大规模私有数据集高效且具有密码学安全性的协同分析。

原作者： Eli Baum, Sam Buxbaum, Nitin Mathai, Muhammad Faisal, Vasiliki Kalavri, Mayank Varia, John Liagouris

发布于 2026-06-24

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Eli Baum, Sam Buxbaum, Nitin Mathai, Muhammad Faisal, Vasiliki Kalavri, Mayank Varia, John Liagouris

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你是一位船长，手下还有另外三位船长。你们每人都持有一张标有珍贵宝藏位置的秘密地图，但谁也不信任谁，都不愿展示自己的地图。你想通过合作来寻找一条结合了所有人地图的最优路线，但你不想泄露你的宝藏具体在哪里，甚至不想泄露你拥有多少个宝藏。

这就是 Orq 所解决的问题。

问题所在：“二次方爆炸”

在安全计算领域，有一种技术叫做多方计算 (MPC)。它允许人们在不泄露私有数据的情况下共同进行计算。想象一下，一群人正在解决一个数学问题，每个人都在纸上写下数字，但他们传递的是这些数字的“加密/混淆”版本。

然而，这里有一个巨大的瓶颈：连接 (Joins)。
假设你有两份名单。你想找出同时出现在这两份名单中的所有人。

旧方法： 如果你想在不泄露任何信息的情况下安全地进行此操作，计算机必须将列表 A 中的每一个名字都与列表 B 中的每一个名字进行比对。如果列表 A 有 1,000 个名字，列表 B 有 1,000 个名字，计算机就需要进行 1,000,000 次检查（1,000 x 1,000）。
“级联”噩梦： 如果你要合并三份名单，检查次数会爆炸到 1,000,000,000 次。如果是四份，则会达到一万亿次。这被称为“二次方爆炸”。这就像是在草堆里找针，但每当你寻找一次，草堆就会翻倍变大。以前的系统要么为了避免这种爆炸而泄露秘密，要么需要一个“可信”第三方（比如法官）来监督。

解决方案：Orq（“智能分类器”）

研究人员构建了一个名为 Orq 的系统，它改变了游戏规则。Orq 不再是盲目地检查所有组合，而是使用了一个聪明的技巧：先对列表进行排序。

把它想象成整理一个混乱的图书馆。

旧方法： 你走向图书馆里的每一本书并问道：“这本书是关于猫的吗？”你对每一本书都这么问，即使它们都在错误的区域。
Orq 方法： 你首先按字母顺序整理好书籍。现在，如果你想找所有的“猫”类书籍，你只需要去“C”区即可。你不需要去检查“A”区或“Z”区。

Orq 对数据也这样做。它对秘密数据进行排序，使得匹配的项目最终排在一起。这把原本不可能完成的“检查一切”的任务变成了可控的“检查邻居”任务。

核心秘诀：“即时”聚合

论文强调了一个特定的洞察：在大多数现实世界的查询中（例如“我们赚了多少钱？”），我们实际上并不需要看到每一笔交易的最终清单。我们只需要总额。

Orq 使用了一种称为 连接-聚合 (Join-Aggregation) 的技术。

想象一场接力赛： 与其跑完整个赛程，停下来数每一步，然后再跑一遍，Orq 将跑步和计数结合成一个流畅的动作。
当数据在系统中移动时，Orq 在进行表连接的同时，也同步进行加总（聚合）。它永远不会创建那些庞大的、中间状态的组合列表。它能让数据规模保持在受限范围内，就像一个无论倒入多少水都不会溢出的水桶。

结果：速度与规模

研究人员在两种环境下测试了 Orq：

LAN（局域网）： 同一栋建筑内的计算机。
WAN（广域网）： 分布在互联网上的计算机（例如不同的国家）。

他们的发现是：

速度： Orq 比之前的系统快得多。在某些情况下，它快了 800 倍。
规模： 他们能够运行著名的 TPC-H 基准测试（一种衡量数据库性能的标准测试），且“规模因子为 10”。这意味着他们在完全处于安全加密的状态下处理了 5800 万行 数据。
- 背景： 以前的安全系统如果要处理这么多数据，要么必须泄露秘密，要么需要一个可信第三方。Orq 在做到零泄露且无需可信第三方的情况下完成了这项任务。
安全性： 即使某些计算机是“恶意”的（试图作弊）或“半诚实”的（遵守规则但试图窥探），它依然可以正常工作。

总结

Orq 就像是一个高效的新型安全汽车引擎。以前，试图驾驶一辆载着重物（复杂数据）的安全汽车是非常缓慢且危险的，以至于人们要么选择不驾驶，要么拆掉安全锁（泄露数据）。Orq 重新设计了引擎，让你可以在保持安全锁紧固的同时，既能高速行驶，又能承载重载。

他们甚至已经将代码开源，因此任何人都可以使用这个“引擎”来构建自己的安全数据分析工具。

技术摘要：Orq —— 具有强安全保证的私有数据复杂分析

1. 问题陈述

本文解决了在**外包安全多方计算（MPC）**设置下，对大规模私有数据集进行复杂关系分析（特别是多路连接与聚合）的挑战。在这种设置中，数据所有者将数据的秘密份额分发给一组不可信且互不串通的计算方（服务器）。

现有 MPC 系统的核心瓶颈在于**级联效应（cascading effect）**导致的盲连接（oblivious joins）开销。为了保持盲性（隐藏访问模式和数据分布），对包含 $n$ 条记录的表进行标准的盲连接必须产生规模为 $n^2$ 的最坏情况输出（笛卡尔积）。对于涉及多个连接（ $k$ 个连接）的查询，这会导致 $O(n^{k+1})$ 的时间和空间复杂度，使得复杂的查询在处理大规模数据集时变得难以实现。

现有的解决方案面临着一个三难困境：

二次方成本： 计算完整的笛卡尔积（代价高昂）。
静默丢弃（Silent Dropping）： 通过静默丢弃记录来强制执行亚二次方界限（结果不正确）。
泄露： 向服务器泄露连接结果的大小（不安全）。

先前在委外设置中的工作（如 Secrecy、Scape）要么遭受二次方成本的影响，要么泄露结果大小。此外，许多现有系统依赖于可信计算基（TCB）或特定的数据所有权模型（例如，所有者同时也是计算方的点对点模型），这些模型无法推广到服务器无法查看明文的外包模型中。

2. 方法论

Orq 引入了一个整体的系统运行时，旨在以 $O(n \log n)$ 的复杂度评估复杂查询，从而在不泄露信息的情况下避免二次方膨胀。

2.1 核心洞察：数据无关界限

作者观察到，在许多实际的协作分析场景中，查询结果的大小受输入规模（ $O(n)$ ）的最坏情况约束，且独立于数据分布。即使对于多对多连接，只要查询结构允许可分解聚合（decomposable aggregation），这一结论依然成立。Orq 利用这一观察结果来限制中间结果的大小。

2.2 复合连接-聚合算子（Composite Join-Aggregation Operator）

其核心创新是一个融合的连接-聚合算子，该算子避免了物化笛卡尔积。

机制： Orq 不先进行连接再进行聚合，而是执行一种“类 MapReduce”的评估方式。它首先在输入表上应用预聚合（部分评估）以处理重复项，执行连接，然后应用后聚合。
实现： 该算子将输入表进行拼接，在连接键上进行盲排序，并使用蝴蝶结构的**聚合网络（Aggregation Network, AggNet）**来传播数值并在单一控制流中计算聚合值。
支持： 它支持内连接（inner）、外连接（outer）、半连接（semi-）和反连接（anti-），以及任意用户自定义的聚合函数（sum, count, min, max, avg）。
处理重复项： 对于多对多连接，Orq 通过预聚合其中一个输入来创建唯一键（重数/multiplicity），进行连接，然后通过后聚合来合并重数。这确保了中间表的大小永远不会超过较大输入的基数。

2.3 盲原语与排序

为了支持连接-聚合算子，Orq 实现了一系列最先进的盲原语：

排序： Orq 提供了**快速排序（Quicksort）和基数排序（Radixsort）**的向量化、数据并行实现。
- 快速排序： 使用“先洗牌后排序”的迭代范式，将通信轮数减少至 $O(\log n)$ 。
- 基数排序： 使用结合了积极位置换（eager bit-permutation）与盲洗牌的混合方法。
- TableSort： 一个包装器，用于从填充排序中提取排序置换，并将其应用于表的所有列，从而避免对多个列进行冗余排序。
洗牌（Shuffling）： 与各种 MPC 协议兼容的广义盲洗牌原语。
向量化： 所有算子均采用列式数据格式实现，允许同一阶段内的独立消息被打包并在单轮通信中发送。

2.4 系统架构

数据流 API： 用户使用类似于 Apache Spark 的数据流风格 API 来定义查询，而非 SQL，从而能够简洁地表达复杂的流水线。
协议无关性： 算子被构建为基于 MPC 原语（ $+$ $+$ , $\times$ $\times$ , $\oplus$ $\oplus$ , $\land$ $\land$ ）的黑盒抽象。Orq 支持三种协议：
1. 半诚实、非诚实多数派（ABY, 2-party）。
2. 半诚实、诚实多数派（Araki 等人, 3-party）。
3. 恶意安全、诚实多数派（Fantastic Four, 4-party）。
通信层： 一个基于 TCP 的自定义层，使用无锁环形缓冲区来摊销网络成本，特别是在广域网（WAN）环境下。

3. 主要贡献

Orq 系统： 一个用于外包 MPC 环境下复杂关系分析的完整系统，支持具有强安全保证（不泄露结果大小）的多路连接与聚合。
新型连接-聚合算子： 一种通过分解并积极应用聚合来限制中间结果大小的技术，为以往需要 $O(n^2)$ 复杂度的连接实现了 $O(n \log n)$ 的复杂度。
协议无关的原语： 一套统一的盲算子实现（连接、排序、聚合），可以实例化为半诚实或恶意 MPC 协议。
可扩展排序： 数据并行的向量化盲排序实现，可处理高达 5.37 亿行数据，性能显著优于现有技术。
全面的评估： 首次在不依赖泄露或可信计算的情况下，对完整的 TPC-H 基准测试（规模因子 10）进行了端到端的 MPC 执行。

4. 实验结果

作者在 LAN 和 WAN 部署环境下，针对包括完整的 TPC-H 基准测试和来自先前工作的查询在内的多样化工作负载对 Orq 进行了评估。

对比现有技术性能：
- 对比 Secrecy： Orq 的延迟降低了高达 827 $\times$ 。Secrecy 使用 $O(n^2)$ 连接和单线程执行；Orq 使用 $O(n \log n)$ 和向量化。
- 对比 SecretFlow： 在连接查询方面，Orq 比 SecretFlow 快 1.1 $\times$ 至 1.5 $\times$ ；在非连接查询方面快 58 $\times$ 至 85 $\times$ ，尽管 SecretFlow 会泄露连接结果的大小，而 Orq 在实现更高性能的同时完全没有泄露。
- 对比 MP-SPDZ： 由于采用了数据并行化，Orq 的排序速度比其快达 189 $\times$ 。
可扩展性：
- Orq 在整个 MPC 环境下处理 Scale Factor 10 的 TPC-H 查询（平均 5800 万行）。
- 最昂贵的查询（Q21）在 LAN（恶意安全）环境下耗时 42 分钟，在 WAN（恶意安全）环境下耗时 18 小时。
- 排序协议可扩展至 5.37 亿行（Quicksort, SH-HM）和 1.34 亿行（Radixsort, Mal-HM）。
带宽： 由于渐进复杂度的改进，Orq 的带宽消耗比 Secrecy 低至两个数量级。
预处理： 论文对 Beaver 三元组生成进行了基准测试，结果显示，尽管计算开销较高，但亚二次方协议（Doerner 等人）相比传统方法提供了显著的带宽节省。

5. 重要性与主张

本文声称 Orq 代表了使大规模协作数据分析中的安全分析走向实用化的重要一步。

打破二次方壁垒： Orq 证明了在不泄露结果大小或不依赖可信硬件的情况下，实现高效、完全盲性的复杂多路连接评估是可能的。
大规模实用性： 通过成功运行完整的 TPC-H 基准测试（规模因子 10，此前仅能通过泄露或可信计算实现），Orq 证明了 MPC 可以处理企业级的工作负载。
通用性： 该系统并不局限于特定的数据所有权模型或威胁模型，支持外包环境下的半诚实和恶意攻击者。
开源： 作者已发布 Orq 开源版本，以促进进一步的研究与应用。

作者指出，虽然目前仍需使用数据流 API（而非自动 SQL 规划器），但该系统的性能和安全特性为安全关系分析建立了新的基准。未来的工作包括集成自动查询规划器，并进一步优化 WAN 环境下的恶意检查。