摘要
在数据量不断膨胀的今天，但是因为隐私问题，在科学研究等方面的数据共享工作仍然进展缓慢。
本文提出了一种名为 PDN（Private Data Network）的用于多个互不信任的参与方之间的联邦数据库形式。在PDN中，用户将查询请求发送给一个名为诚实代理（Honest Broker）的中间人，由诚实代理通过SMC（Secure Multiparty Compute）协调各方进行计算并最终将结果返回给用户。
本文还提出了一个用于实现PDN的框架——SMCQL，SMCQL可以根据SQL语义将SQL语句转换为SMC原语，并且在不向同级别数据提供者揭露隐私信息的情况下完成查询。只有诚实代理和查询者可以获得PDN的查询结果。同时为了提高速度，SMCQL还使用了启发式算法优化了PDN对SMC的使用（SMC会消耗大量的资源）
1. 介绍
本章详细介绍了联邦数据库和PDN的工作方式，以及SMCQL的一些特性
用户向诚实代理提交查询，所有参与方根据诚实代理提供的安全协议进行计算，由诚实代理将多方的结果整合并返回给用户，从用户的角度看PDN与传统的数据库是完全一样的，提交查询，得到结果。
PDN使用SMC（Secure Multiparty Compute）完成多个不信任的参与方之间的计算和查询，因为SMC需要满足安全传输 ，所以他消耗的计算资源会非常的庞大，通常是明文查询的数倍。所以SMCQL通过将SQL语句转化为SMC原语，确定需要使用SMC的部分，并通过启发式算法优化，大大降低的SMC的使用，提高了计算速度。
SQMQL是适用于半诚实模型的数据库框架，它假设各参与方都诚实地执行诚实代理提供的安全协议，并使用了差分隐私通过在查询中注入噪声等来对个人信息进行保护以防有恶意查询者想要获取到隐私信息。在系统建立时，整个PDN会对表的内容进行统一定义，并且为不同的属性设定不同的安全级别，诚实代理会和所有参与者一起在安全的前提下完成这个表的链接。同时，各参与方可以制定一个策略用于定义其所允许执行的请求类型。
不同于采用同态加密的outsourced computation，PDN是将数据保留给其持有者，利用SMC来隐藏具体的计算过程而不是隐藏具体的数据。PDN将安全计算分摊给所有参与者，并只采用一个轻量级的诚实代理来协调请求处理过程。
本篇论文的主要贡献有如下几点：
- 一个用于有多个彼此不信任的数据提供商参与的联邦数据库（PDN）
- 一个可以将SQL语句转换为安全计算原语的生成器
- 基于启发式的PDN查询执行优化器
- 对该系统基于现实中的医疗数据进行了深入测试评估
2. 背景
本章主要介绍了SMCQL是如何实现SMC的。
SMCQL主要采用混淆电路（Garbled Circuits）和ORAM（Oblivious RAM）来实现SMC运算，主要是因为这两者都比较成熟，优化比较好。SMCQL利用混淆电路来计算在多方数据上的操作，利用ORAM来保护数据在执行者间的传输（在每次读写时都打乱包含数据的tuple，从而使得数据的访问细节对于被访问者来说是未知的）。SMCQL可以为每个数据库操作单独设计一个混淆电路，利用ORAM完成操作间的数据传递，从而避免了设计一个复杂的臃肿的大型混淆电路来执行一系列的操作。
3. 系统概述
本章主要介绍了SMCQL是如何将SQL语句转换为SMC原语的。
- 首先，诚实代理在收到查询的SQL语句后，首先将其转换为一个有向无环图（DAG），也就是语法树，诚实代理对其进行检查，以确保其在PDN的安全策略下是可以运行的。
- 诚实代理生成一个安全计划，标识语法树中的需要使用安全计算的最小子树，该安全计划是由诚实代理自下往上对树进行遍历，对敏感数据的数据流进行建模生成的
- SMCQL使用启发式方法将该语法树优化为多个小的SMC单元，并对SMC的数量进行优化
- 诚实代理通过优化后的plan生成一系列的SMC代码用于协调各个参与者完成请求
- 每个参与者各自按照其自身的协议执行SQL请求，并在诚实代理提供的SMC代码下进行协作
当前该系统支持多种SQL操作，包括selection、projection、aggregation、limit、some window aggregates，对于join操作目前仅支持equi-join、theta-join、cross products。
4. 安全查询执行器
本章主要介绍了SMCQL是如何将PDN计划中的物理运算符转换为可执行的安全的代码
首先将一些组合多方数据的步骤加入计划中，随后对运算符树中所有的运算符生成一个安全的代码
安全代码使用混淆电路在多个参与方上联合计算，并将结果存入ORAM（Oblivious RAM）中。引擎使用这种安全的结构在操作符两边的节点间传递数据。
SMCQL使用ObliVM——一个拥有类似C语言语法的语言来创建混淆电路和ORAM。首先它将代码转换为一组逻辑门和ORAM的集合，然后在执行阶段再生成混淆电路。这个语言与底层的混淆电路协议相互解耦，使得使用不同的协议时对于编程者可以无缝切换。
每个操作在转换成安全代码时，都需要一个对应的模板函数，这个模板函数接受过滤器谓词（filter predicates）、输入的大小作为输入，其为一种操作定义了安全代码的具体工作流程。模板和逻辑门、ORAM共同构成了PDN的低级表示，并在执行阶段编译出混淆电路。
5. 安全模型
本章主要介绍了SMCQL面向用户提供的协议，同时还介绍了SMCQL的安全类型系统
面向用户的安全协议
SMCQL提供了以下三个数据保护级别：
- public：该数据对所有参与方都可见
- protected：该数据仅对数据源，诚实代理和用户可见，使用k匿名（k-anonymity）来描述一个protected属性的安全度，指该属性的一条记录至少和k-1个记录不可区分。在这种情况下，用户和诚实代理是可以通过协调多个参与者来获取这些数据的。
- private：该数据仅对数据源可见
隐私数据流
上图为安全系统的语法树，其中 phrase 可以是一个 expression、一个 set 或是一个 operator，expression 表示属性的引用、常量、算数与比较运算符、逻辑连接符，set 表示expression的集合，operator 表示以一个运算，输入一个 set，输出一个 set
该系统还定义了high和low两个安全级别，分别对应public和private类型（之后将protected视作private），一个expression是low的，当且仅当其中引用的所有属性都不是high的；一个set是low的，当且仅当其中所有的expression都是low的。
上图描述了operator中的low和high的定义。其中R-NEST描述了一个操作的安全等级应当高于其子结点；R-NEST-BIN针对二元操作，如果一个子结点的安全等级为high，则该结点也为high。
本文基于这套形式系统来描述其operator-tree的结构，并从而通过安全等级的传递来描述敏感数据在树结构中的流动。
SMC优化
本章主要介绍了对SMC的优化。
对于树上的每一个运算符都有以下三种执行模式：
- Plain：运算符被标记为低，并在源数据库中进行评估
- Sliced：被标记为高的运算符安全地运行在由公共表达式水平分区的元组上。
- Secure：被标记为高的运算符使用一个单独的SMC程序在所有的数据提供方上执行。
每个Sliced的operator在接受明文输入后，需要利用slice key对输入进行二进制化加密。具有相同slice key的不同值被独立计算。Slice 可以显著减少 SMC 的使用。
上图为SMCQL用于确定执行模式的算法。扫描从plain模式开始对树进行扫描，当碰到了高运算符时，引擎会切换为 sliced 或 secure 模式。如果运算符为 sliced 模式，则其祖先都要运行在 sliced/secure 模式中以保证数据安全。
比如COUNT(*)在涉及private attribute时，我们可将其分为两步，第一步在各个参与者中各自计算相应的数量，第二步利用SMC方法进行求和。可见第一步是low的，而第二步是high的，我们称这样的operator是splittable operator。每个splitable operator能够被分为两个安全等级不同的phrase，将其视作两个等级不同的子句而不是一个high的整体，能够进一步减小SMC开销。
再进一步，我们可以仅在涉及多方的情况下才使用SMC方法，称为semi-join。理由和上面的一样，我们可以将请求执行分为两个部分，在仅涉及自身一个参与者的情况下，可以采用明文计算而无需SMC方法；在涉及发送和传递数据时才使用SMC方法。
测试
本章对SMCQL的性能进行了测试。
其中 Baseline 对应所有属性都被视作 private 的，从而不进行任何优化；SMC Minimization对应通过分析high和low而减少了对于SMC的使用，包括splittable operators；Fully Optimized对应继续采用slice execution的方法进行优化，可以看到优化后的执行时间大大降低。
随后本文以recurrent c. diff场景为例，进一步测试了不同条件对于每个operator的性能影响：
同时本文还在comorbidity情景下使用不同的输入大小，测试了Secure状态和明文状态下的性能差异。本文将Secure在Scale增大时的性能降低主要归结于不经意传输时需要传输和打乱的数据的规模增大。
