摘要
本篇论文提出了 Adore：一组差分不经意关系型数据库运算符的实现（A set of Differentially Oblivious RElational database operators），包括带投影的选择、带聚合分组和外键连接。这组运算符降低了缓存复杂度、运行时复杂度和输出大小，并且比目前最先进的完全不经意算子（ObliDB）快7.4倍。
介绍
本章介绍了一些硬件加密方法（Intel SGX、RISC-V Sanctum），介绍了差分隐私技术在增强数据隐私方面的应用，提出了differential obliviousness，并从缓存复杂度、时间复杂度和输出大小三个方面进行了评估（如下图）
本篇论文贡献如下：
- 将差分不经意性应用到数据库运算符中，设计了三种不经意运算符
- 形式化证明了这些运算符满足差分不经意性，并且降低了缓存复杂度和输出虎大小
- 通过实验证明了这些运算符相对于当前最先进的完全不经意运算符有性能提升（7.4×）
背景
威胁模型
以 Intel SGX 为例，数据存储在 enclave（被隔离的内存区域，不能被os等访问）中并加密，用户通过一个不可信的 I/O 组件与其沟通，用户将加密查询发送给不可信组件后，不可信组件再将加密查询发送给 enclave，相同的，enclave 也会将输出的加密数据经由不可信组件发送给用户。同时 enclave 可能会将一些加密数据写入内/外存，因为预留的内存空间（enclave）是有上限的，而攻击者通过观察 enclave 如何读写加密数据和中间结果可以推测出一些信息。
内存访问模式（Memory access patterns）
内存访问模式可以反映数据的访问模式，如顺序访问、随机访问、局部性访问等。如果某些程序的内存访问模式包含了某些敏感数据的特定访问模式，那么攻击者可能会根据这些内存访问模式来推断出这些敏感数据的存在和内容，从而造成数据隐私泄露。
其次，内存访问模式和数据隐私还存在着一定的信号侦听风险。攻击者可以通过监视内存访问模式来获取机密数据的信息。例如，在一些侧信道攻击中，攻击者可以通过监视程序或系统的内存访问模式，可以推断出正在执行的代码或访问的数据是什么，从而进一步获取敏感数据。
差分不经意性（Differential Obliviousness）
与标准的差分隐私不同，本文并不要求数据计算的输出是私有的，但是要求计算的过程、数据库系统的可观测运行时候的行为，即访问模式是差分私有的，而这一概念被称为差分不经意性。
一个算法 $ \mathcal{A} $ 满足 $ (\epsilon, \delta)-\operatorname{differentially Obliviousness} $，如果对任意两个相邻数据库 $ D_1 $，$ D_2 $ 和任意内存访问模式 $ S $ 的子集，有：
$$ \operatorname{Pr}\left[\mathcal{M}\left(\mathcal{A}, D_1\right) \in S\right] \leq e^\epsilon \cdot \operatorname{Pr}\left[\mathcal{M}\left(\mathcal{A}, D_2\right) \in S\right]+\delta $$
完全不经意性（Full Oblivious）
一个算法 $ \mathcal{A} $ 是不经意的，如果对任意两个大小相同的数据库 $ D_1 $，$ D_2 $ 和任意可能的内存访问模式 $ S $ 的子集，有
$$ \operatorname{Pr}\left[\mathcal{M}\left(\mathcal{A}, D_1\right) \in S\right] \leq \operatorname{Pr}\left[\mathcal{M}\left(\mathcal{A}, D_2\right) \in S\right]+\delta $$
差分不经意运算符
本章用到的符号解释如下表：
带投影的选择（selection with projection）$ (\sigma, \prod) $
select column_name1, column_name2
from table_name
where conditionselect 运算符得到一个关系，并根据给出的条件输出一个子集，在关系代数中写作 $ \sigma_{\phi}(R) $，其中 $ \phi $ 是过滤谓词，$ R $ 是输入表（table_name）
projection 运算符将一个关系转换为另一个，在关系代数中写作 $ \prod_{a_1, \dots, a_n}(R) $，其中 $ a_1, \dots, a_n $ 是一系列属性的集合，在结果中保留了 $ a_1, \dots, a_n $ 这些属性而舍弃掉了其他的
简单非不经意算法（Naïve non-oblivious algorithm）
时间是线性的，但是攻击者可以通过读写指针前进的频率来判断出哪些属性被保留哪些则被舍弃，所以本文差分不经意过滤算法的主要思想就是混淆每个指针的前进速度，使其刚好足以实现差分不经意
差分私有前缀和（Differentially Private prefix-sum）
对于一个只包含0和1的长度为 $ n $ 的数据流 $ D \in \{0, 1 \}^n $，它的前缀和 $ Y_c $ 代表在前 $ c $ 个元素中有多少个1出现。假设有一个 $ (\epsilon, \delta) $ - differentially private prefix sum 算法可以回答至多 $ n $ 个答案，每个答案 $ \widetilde{Y}_c $ 有很高的可能性在 $ \left[Y_c-s, Y_c+s\right] $。为了使写入指针的轨迹差分私有，我们可以将输出指针移动到 $ Y_c - s $，并将已经扫描还未输出的元祖储存在私有缓冲区中（enclave），只需要 $ 2s $ 大小的私有缓冲区就可以保证该算法只有很小的概率才会出错。本文使用 Chan 提出的二进制机制作为 DP 前缀和预言机，该机制本质上是建立一个二进制区间树来储存局部噪声和以实现最优近似隐私权衡。对每个 $ c \in [n] $，估计的前缀和 $ \widetilde{Y}_c $ 有 $ O\left(\epsilon^{-1} \cdot(\log T) \cdot \sqrt{\log t} \cdot \log (1 / \delta)\right. $ 的误差的概率至少为$ 1 - \delta $
差分不经意过滤（Differentially Oblivious Filtering, DoFilter）
设 $ I $ 是长为 $ N $ 的输入表，$ s $ 为 DP 前缀和预言机的近似误差（每个查询的概率至少为 $ 1 - \delta $）。在私有内存中创建一个长度为 $ 2s $ 的缓冲区 $ P $，$ I \prime $ 为在虚拟内存外的输出表，和一个用于指示目前读取元组数目的计数器 $ c $。随后重复以下操作直至 $ I $ 结束：
- 读取接下来 $ s $ 个元组并更新计数器 $ c $
- 对每个元组 $ t $，当谓词赋值为 TRUE 时将其推入 P 中
- 从 P 弹出元组直至输出表 $ I\prime $ 达到长度 $ \widetilde{Y}_c - s $
当读到 $ I $ 的末尾后，将所有 $ P $ 中的元组弹出，并在 $ I \prime $ 上添加必要的填充元组直至其长度到达 $ \widetilde{Y}_N $，其中 $ N = \left| I \right| $
该算法描述如下：
带聚合的分组（Grouping with Aggregation）$ (\gamma, \alpha) $
select count(*)
from table_name
group by grouping_attributegrouping 运算符对一个关系分组和/或聚合一些列，通常记为 $ \gamma_L(R) $，其中 $ L $ 为由分组属性（将要对 $ R $ 进行分组的 $ R $ 所拥有的属性）和应用于 $ R $ 的 aggragation 运算符（如 $ \gamma_{c_1, c_2, \alpha_1(c_3)} $ 将会将 $ R $ 根据属性 $ \{c_1, c_2\} $ 进行分组，并输出 $ \alpha_1 $ 应用于 $ c_3 $ 上的聚合值）
本文提出了一种基于分组属性随机划分的非不经意哈希分组算法，可以通过在分组属性 $ L $ 上应用伪随机函数（pseudorandom function, PRF）来实现。为了让每个分区都适应私有内存的大小（$ M $），本段应用了一种预处理步骤来获取正确的随机划分算法参数 $ s $，使用随机流不同计数算法（randomized streaming distinct count algorithm）来得到一个查询产生分组数的估计值 $ \widetilde{G} $，大约需要 $ k=\lceil\widetilde{G} / M\rceil $ 次扫描来找到所有的分组。
本文提出的差分隐私不同计数流算法（Differentially Private Distinct Count）如下（Algorithm 5）：
本文提出的差分不经意分组（Differentially Oblivious Grouping）算法如下（Algorithm 2）：
其中 $ I $ 是输入表，$ L $ 是由分组属性和聚合属性组合而成的列表。
外键连接（Foreign Key Join）$ (\bowtie) $
select * from table_1
join table_2
on table_1.primary_key = table_2.foreign_key;使用 $ R \bowtie S^2 $ 来表示关系 $ R $ 的主键和 $ S $ 的外键上的一个连接。
典型的不经意连接算法有如下几个步骤：
- 填充：将两个表中的元组填充到相同的大小，并为每个元组添加一个“标记”列以标记该元组来自哪个表
- 排序：通过执行oblivious sort将来自两个表的元组路由到同一组
- 顺序扫描：通过对排序后的表进行顺序扫描来生成结果表
- 去除填充：最后，使用另一个oblivious sort去除所有填充元素
本文提出了差分不经意外键连接算法（Differentially Oblivious Foreign Key Join Algorithm）DoJoin，在 DoJoin 中，两个相邻数据集应该包含同一主键，并且它们的外键表具有相同长度的记录，但是其中有一条数据不同。DoJoin 从以下三个方面改进了典型的不经意连接算法：
- 使用更高效的桶不经意排序（$ O(nlogn) $）（Bucket Oblivious Sort）代替了 ObliDB 中使用的双调排序（$ O(nlog^2n) $）（Bitonic Sort）
- 移除了去除填充这一步（已在Algorithm 1中进行），只对输入进行一次排序
- 将输出中的填充元组填充到差分不经意性要求的大小，而不是更坏的情况，在实际中填充量可能很小
DoJoin 算法描述如下：
其中 $ R $ 为主键表，$ S $ 为外键表，$ k_R $ 是 $ R $ 的主键， $ k_S $ 是 $ S $ 中连接 $ R $ 的外键。DoJoin 算法首先将双方的元组填充到相同的大小，并在每个元组中添加一个标记列来表明它来自哪个关系。随后将得到的元组进行拼接，并将其先按键列再按标记列进行排序。对于有相同键的元组，来自 $ R $ 的元组总是先被读取。随后算法顺序扫描表，当扫描到一个元组时，如果它来自于关系$ R^\prime $ （填充后的 $ R $），则将其赋值给工作元组；如果它来自于关系$ S^\prime $ （填充后的 $ S $），则将其与工作元组进行连接操作，并将结果输出到结果集中。
差分私有区分计数（Differentially Private Distinct Count）
本章描述了一个基于差分隐私的分区计数算法，介绍了随机抽样的顺序统计量性质，$ (\epsilon, \delta) \text {-Sensitivity } $，并对其的进行了证明和分析，DISTINCT COUNT算法描述如下，DPDistinctCount 如上 Algorithm 5 所示：
性能评估
本章对 DO 运算符在 Big Data Benchmark 上进行了测试，并与 ObliDB 和 Spark SQL 进行了对比。隐私参数 $ eplsilon = 1 $，$ \delta = 2^{-30} $。
在 Benchmark #1: Selection with projection 中，相比没有加密的非不经意 spark SQL，有 7.8 - 26.0 倍的开销，开销主要来自于在 SGX enclave 内存中移动数据时的加密和解密；相比 ObliDB 有 1.5-3.7 倍的速度提升，这种性能增益来自更高效的算法和差分不经意性带来的更小的填充大小。
在 Benchmark #2: Grouping with aggregation 中，在中等数据集上（300k-300M）相比没有加密的非不经意 spark SQL，有 12.4 - 105.7 倍的开销；对于300K行的UserVisits表进行分组聚合，DO 运算符与 ObliDB 具有类似的性能，但 ObliDB 无法在3000万行的 User Visits 表上运行聚合分组。
在 Benchmark #3: Foreign Key Join 中，相比没有加密的非不经意 spark SQL，有 98.1 - 182.1 倍的开销，但相比 ObliDB 有 4.8-7.4 倍的速度提升。
下面是对 DO 运算符不同阶段耗时的拆分图，各部分说明如下：
- Encrypt：在 enclave 中加密
- Decrypt：在 enclave 中解密
- Read：将数据从不受信任的内存读入 enclave
- Write：将数据从 enclave 写入不受信任的内存
- Compute：在 enclave 中计算
