Eurosys 19 Conclave: secure multi-party computation on big data

摘要

当前的 MPC 算法在大数据上的速度非常的缓慢，而这导致了其在大数据上的应用进展也极其缓慢。许多关系分析查询可以保证 MPC 端到端的安全性，而不需要在所有运算上都使用 MPC。本文所介绍的 Conclave 是一个查询编译器，通过将此类查询转换为数据并行、本地明文处理和小型MPC步骤的组合来加速此类查询。当各参与方都信任彼此的数据集的时候，Conclave 会应用新的混合 MPC 清晰文本协议，在 MPC 之外运行其他步骤，并进一步提高可扩展性。

Conclave 的原型使用 Python 和 Spark 来生成明文代码，使用 Obliv-C 框架编写 MPC 相关的安全代码，并且表现大大优于最相似的系统 SMCQL

1. 介绍

本章主要介绍了 MPC 和 Conclave 的原理

Conclave 是本文提出的一个支持 MPC 查询的编译器，他可以使得 MPC 在大数据上高效地运行。

Conclave 有三个关键的想法。首先，Conclave 会分析查询来应用转换，可以在不损害安全的前提下减少运行的时间；其次，Conclave 在输入关系上使用了可选的，粗粒度的注解来应用新的混合协议，这个协议可以对纯文本和 MPC 进行比较，以获得进一步的加速，尤其是类似 joins 这种众所周知的在 MPC 下非常慢的操作；第三，Conclave 生成的代码将可扩展的、不安全的数据处理系统（如Spark）与安全但缓慢的 MPC 系统相结合。

本文的关键贡献有四点

1. 查询分析技术，可以只通过粗粒度的注解得出在关系查询中哪些部分必须在 MPC 中运行
2. 在保证安全的前提下将一些耗时的操作移出 MPC
3. 在已有的相互信任的参与方之间使用新的MPC-明文混合协议来提升 MPC 中的 joins 和 aggregations 的性能
4. Conclave 原型使用 Python，Spark，Obliv-C 和 Sharemind 来生成高效的用于执行的代码

2. 背景

本文介绍了 MPC 在大数据中的应用，MPC 的安全保障和 MPC 相关的技术和扩展

Conclave 主要使用两种 MPC 技术，一种是混淆电路，另一种是秘密共享，这两种技术在博客中都有文章，不再赘述。

文章还提到了一点就是在实践中的可扩展性。上图在基于秘密共享（Sharemind）和混淆电路（Obliv-C）的MPC框架上对三种关系运算符与不安全明文执行的性能进行了测试评估并得出了以下结论：当前的MPC系统不太可能扩展到中等大小的数据集。特别是联接和聚合的性能较差：60%以上的隐私敏感分析查询使用联接，34%以上包含聚合。由于缺乏新的加密技术，因此在大数据上运行MPC的唯一方法可能是在不需要使用 MPC 的时候避免使用其加密技术。

3. 概述

本章介绍了 Conclave 的一些相关概念和实现。

威胁模型

Conclave 同 SMCQL 一样，是适用于半诚实模型的，要求参与方诚实地执行协议

安全保障和假设

Conclave 是一个为在外部 MPC 系统（后端）中的执行生成代码的查询编译器，所以 Conclave 继承了所使用的 MPC 后端的安全保证和假设，但也必须维护它们。Conclave 还特别隐藏了所有处理过的私有数据以及值频率等元数据。Conclave 针对其 MPC 后端可以容忍的串通敌对各方的相同阈值提供了这些保证。

与 MPC 论文一致，Conclave 将所有输入规模的大小视为 public，并隐藏在 MPC 下处理的中间关系的大小。但是，在 Conclave 重写查询以将操作移出 MPC 后，剩余 MPC 的输入大小可能与原始输入大小不同。根据查询，这可能会泄露信息。如果新的MPC输入关系的大小与数据无关，Conclave 的重写是安全的。对于依赖于数据的大小，Conclave 只有在所有受影响的各方都授权的情况下才会进行重写，否则选择较慢的查询计划。

同时，Conclave 提供的混合协议还可以用一部分安全性来换取性能的提升

4. Conclave 查询规范

Conclave 假设每一方都运行了：

• 一个本地Conclave代理，该代理与其他各方通信并管理本地和MPC作业
• 一个本地MPC端点（例如，Obliv-C 或 Sharemind 节点），所有这些都运行在私有基础设施上
• 可选的并行数据处理系统（例如，Spark），若没有并行数据处理系统，Conclave 将在Python中顺序运行本地计算。

Conclave 还拥有可选的信任方注解，一个参与方如果乐意将隐私数据透露给另一个信任的参与方就可以使用此注解（如银行机构将数据透露给政府监管机构，但不愿意将其泄露给其他竞争对手等），这种注解有助于 Conclave 减少高消耗的 MPC 步骤，从而提高速度。

5. 查询编译

Conclave 的编译阶段分为6步：

1. Conclave 从一个复杂的大型 MPC 查询计划开始，首先将输入关系传到中间关系来确定数据在哪里跨越了各参与方的边界
2. Conclave 使用在第一步的得到的信息将查询重写为更少使用 MPC 的等价查询
3. Conclave 通过 DAG 来传播输入关系的信任注解，并根据推理规则将他们组合起来，以确定应该在何时可以将部分运算符放在 MPC 之外执行
4. 随后 Conclave 在信任注解同意的情况下通过使用混合协议运算符替换一些可以在 MPC 之外运行的运算符来将巨大的内部 MPC 分为多个更小的 MPC 和一些本地步骤
5. 如果有可能，Conclave 通过将一些高消耗的运算符（如排序等）移动到本地或用消耗更低的运算符代替来进一步减少高消耗的不经意协议的使用
6. 最后，Conclave 通过在本地和 MPC 操作之间的每个转换处拆分DAG划分查询来为生成的子 DAG 生成代码，并在各自的后端执行它们。

注解传播

第一次传播以拓扑排序的方式沿着 DAG 从上往下传播，并以反向拓扑顺序遍历的方式将输出位置备份到图中。对于每个中间运算符，传播会派生其结果关系的所有者。如果一方能从其自己的数据导出一个关系，则称此方拥有这个关系。如果有多方拥有这个关系，则此关系没有拥有者，而没有拥有者的关系需要在 MPC 下运行。

第二次传播 Conclave 将会对每个中间关系的列确定一个信任集，如果一方被委托有足够的输入数据来计算该列，则该方被该中间结果列信任。传播这种信任的概念使 Conclave 在确保信息不会泄露给各方明确授权的信任方以外的参与方的同时使用混合协议来计算中间关系成为可能。

每个输入列的信任集合由信任注解来定义。Conclave 通过拓扑排序的方式在 DAG 中传播这些注解，对于每个运算符 $ o $ 的每个结果列 $ c $，Conclave 确定 $ o $ 的哪个操作数列有助于计算 $ c $。Conclave 将 $ c $ 的信任集设置为这些操作数列的信任集的交集。

这种传播算法有助于 Conclave 维护一个重要的安全不变原则：仅当列可从一方被授权的输入列派生的时候才会向另一方揭露此列。这可以保证 Conclave 使用混合协议是安全的。

寻找 MPC 边界

Conclave 从一个在单体巨大的 MPC 里的 DAG 开始计划查询，它可以将可以在 MPC 外本地明文运行的操作符取出，并将其他运算符分为本地预处理运算符和较小的 MPC 步骤。这个转换几乎对 Conclave 后端的安全保证性没有影响。

从输入关系开始，Conclave 将 MPC 边界沿着 DAG 向下推进，在保证正确性和安全性的同时尽量往下推进。当所有关系传播完毕后，每个关系要么是一个拥有唯一所有者的单例关系，要么是一个没有所有者的分区关系。在分区关系中，多方持有关系的一个子集（即分区）。Conclave 从每个单例输入关系中遍历 DAG，并从 MPC 中提取运算符，直到它遇到一个具有分区输出的运算符，它必须在 MPC 下处理该运算符。

查询通常会通过 concat 运算符将来自多方的输入合并到一个单独的分区关系中。这会创建一个“虚拟”输入关系，其中包含来自所有各方的数据，虽然这很方便，但是这回迫使 Conclave 过早的进入 MPC 中。为了避免这种情况的出现，Conclave 将 concat 运算符移动到任何分布在输入分区上的运算符下面，如对于运算符 $ op $ 和由 $ pA $ 到 $ pN $ 拥有的关系 $ R_{pA} $ 到 $ R_{pN} $，有
$$ op(R_{pA} | \dots | R_{pN} \equiv op(R_{pA}) | \dots | op(R_{pN})) $$
虽然二级聚合必须在 MPC 下运行，但是 Conclave 可以将本地预聚合移出 MPC，并显著地减少输入到 MPC 的数据量。

在某些情况下，Conclave可以将 MPC 的边界从输出关系往上推动。有些运算符是可逆的（可从结果推出输入），对于这类运算符，结果就会泄露输入，所以这类运算符就不需要在 MPC 下执行。相反，Conclave 揭示了可逆运算符的输入与最终接收者的关系以进行本地明文乘法，即使输入具有不同的所有者。

安全影响

Conclave 在执行任何的 push-down 操作前都需要得到参与方的确认，因为此操作会改变输入到 MPC 后端的数据长度。

混合运算符

Conclave 将工作密集型运算符（如连接和聚合）分为多个混合运算符。Conclave 通过向 STP（selectively-trusted party，选择性信任方）揭露一些输入列来将一些高消耗的部分外包给其计算，因此混合运算符会涉及到 STP 的本地计算和 MPC 的多方计算。Conclave 只有在查询的信任注解中放松了输入列的隐私限制时才会应用此转换。Conclave 目前支持 hybrid join, public join 和 hybrid aggregation 三种混合运算符。

• hybrid join
  当双方数据有一个相交的信任集时（即共享一个STP），Conclave 可以将 MPC join 转换为 Hybrid join
  
  协议如下处理：

  1. 参与方在 MPC 下输入关系
  2. 各方将除连接键列之外的所有列投影出去，并向STP显示生成的仅有键列的关系
  3. 对每一个键列关系，STP 枚举所有行，并为所有输入行分配一个唯一的标识符，Conclave 之后会用这个标识符来将聚合的结果链接回在秘密共享中的行
  4. STP对枚举的键列关系执行明文连接
  5. STP将左右关系的行标识符列投射为两个新关系，并秘密分享给不受信任的各方
  6. 各方对每个被打乱的输入关系执行一个类似 Laud 的不经意索引协议，对给定的秘密索引的集合，索引协议不经意选择在关系对应位置的列。通过使用索引关系和打乱的输入，各方选择包含结果的左右行，产生两个关系 left_rows 和 right_rows
  7. 双方将这两种关系连接起来，并将结果重新打乱

• public join
  如果 MPC 连接双方的连接键列都是 public（列的信任注解包括所有参与方） 的，则 Conclave 可以使用 public join。各方将连接键列发送给随机选择的一方；该方枚举并连接行，最后将连接的索引关系发送给各方，各方计算连接结果。

• hybrid aggregation
  如果在 group-by 列上的信任集包含一个 STP，Conclave 可以将 MPC aggregation 转为 hybrid aggregation
  协议如下处理：

  1. 参与方不经意打乱输入并向 STP 揭露打乱过的 group-by 列
  2. STP 在本地枚举被揭露的键，产生键列与索引列的关系，并在键列上对其进行排序
  3. STP 扫描关系并为每一行都计算出一个等价的标志来表示此行的键是否与上一行相同
  4. STP 从已排序的关系中将键列投影，只留下索引，并将此索引发送给其他参与方
  5. STP 秘密共享等价标志
  6. 相互不信任的各方根据明文排序信息对打乱的关系行进行重新排序，这样行就以分组列的值为顺序排序了
  7. 在 MPC 中，各方对结果进行扫描。对于每个条目，如果相应的秘密等价标志是1就将之前的值聚合到当前的值中。各方也会储存秘密等价标志以便于进行最后的比较
  8. 各方打乱结果并揭露等价标志，并移除所有设置标志的条目

减少不经意操作

对于排序这种高消耗的 MPC 操作，Conclave 通过遍历 DAG 来查看有无冗余排序并消除他们。

6. 实现

Conclave 使用 Python 和 Spark 实现明文前端，使用 Obliv-C 和 Sharemind 实现 MPC 后端。

7. 评估

本章对 Conclave 进行了测试。

8. 相关工作

本章对之前的一些相关工作作了介绍，并将 Conclave 与之前已有的一些框架进行了对比。

• 混合模式下的 MPC
  本段将 Conclave 与 Wysteria 进行了对比，相比于 Wysteria 的细粒度注释，对数据分析师有着更高的 MPC 知识要求，Conclave 的目标人群是不太具有 MPC 知识的数据分析师，并专注于自动化。Conclave 还支持在已有的框架中（如 Spark）进行明文并行计算

• 查询重写和 MPC 替代方案
  本段将 Conclave 与 许多其他框架如 Kerschbaum、SMCQL、Opaque 等进行了对比。Conclave 与 SMCQL 相同，使用列层级的注解，但是 Conclave 的注解表现力更强，混合协议也允许额外的性能提升。

• 受保护的数据库和可扩展性
  与之前数据库保护社区多年所研究的对单数据库的大数据量安全查询相反，Conclave 的应用场景是分布式的

• 推断和隐私
  MPC 提供对运算中敏感状态的保护，但是不限制从输出中推断出敏感输入的可能性。之前的许多框架都利用了查分隐私（Different privacy, DP），Conclave 并没有使用 DP，但是添加它并不需要对查询编译做根本性的更改。

9. 总结和展望

Conclave 通过重写查询来减小在 MPC 中的高消耗操作来加速了在大数据上的安全多方计算。

参考文献

Eurosys 19 Conclave: secure multi-party computation on big data