SAGIRI'S BLOG - VLDB
type: channel
link: http://blog.sagiri.tech/index.php/category/VLDB/
description: Very Large Data Bases
items: VLDB 22 Adore: Differentially Oblivious Relational Database Operators
items: VLDB 23 OpBoost: A Vertical Federated Tree Boosting Framework Based on Order-Preserving Desensitization
items: VLDB 22 Privacy-preserving Cooperative Online Matching over Spatial Crowdsourcing Platforms
items: VLDB22 Federated Matrix Factorization with Privacy Guarantee
items: VLDB 22 Hu-Fu: Efficient and Secure Spatial Queries over Data Federation
items: VLDB17 SMCQL: Secure Querying for Federated Databases

VLDB 22 Adore: Differentially Oblivious Relational Database Operators
type: item
date: 2023-05-07T20:13:00+08:00
description: 摘要 本篇论文提出了 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 condition select 运算符得到一个关系，并根据给出的条件输出一个子集，在关系代数中写作 $ \sigma_{\phi}(R) $，其中 $ \phi $ 是过滤谓词，$ R $ 是输入表（table_name） projection 运算符将一个关系转换为另一个，在关系代数中写作 $ \prod_{a_1, \dots, a_n}(R) $，其中 $ a_1, \dots,…

VLDB 23 OpBoost: A Vertical Federated Tree Boosting Framework Based on Order-Preserving Desensitization
type: item
date: 2023-03-26T21:38:00+08:00
description: 摘要 本文引入了 OpBoost 框架，提出了三种在垂直联邦学习下的满足基于距离的 LDP（dLDP）的保序脱敏提升树算法用于对训练数据进行脱敏，优化了 dLDP 定义，并研究了有效的采样分布进一步提高了算法的精度和效率。 介绍 本章介绍了一些基础概念，如联邦学习，HFL，VFL，提升树等 提升树算法是一种流行的监督机器学习算法，有着高效性和可解释性的特点，被广泛应用于基于异构特征的预测任务中，但是当前现有的大多数提升树算法都是在集中式设置下提升的，直接访问整个数据集，在当前人们越来越注重隐私的环境下集中式的设置限制了提升树算法的广泛部署，所以设计一个使用的隐私保护VFL提升树算法成为一个重要问题。 本文贡献如下： 提出了新的隐私保护垂直联合提升树框架 OpBoost 设计了三种保序脱敏算法 优化 dLDP 定义 引入新的保序度量用于量化保序脱敏算法的隐私性，并使用此度量对 OpBoost 进行了综合评估 一些知识 基于距离的本地差分隐私（Distance-based Local Differential Privacy, dLDP） 对任意输入 $ x, x^\prime \in \mathbb{D} $ 和 $ \left| x - x^\prime \right| \leq t $，对所有 $ y \in \operatorname{Range} (\mathcal{M}) $ 有 $$ \operatorname{Pr}[\mathcal{M}(x)=y] \leq e^{t \epsilon} \cdot \operatorname{Pr}\left[\mathcal{M}\left(x^{\prime}\right)=y\right] $$ 保序脱敏算法（Order-Preserving Desensitization Algorithm） 保序脱敏算法（Order-Preserving Desensitization Algorithm） 令 $ X = x_1, x_2, \dots, x_n (\forall i.x_i \in \mathbb{N}) $ 为敏感序列，$ Y = y_1, y_2, \dots, y_n (\forall i.y_i \in \mathbb{N}) $ 为由脱敏算法 $ \mathcal{R} $ 生成的噪声序列。脱敏算法 $ \mathcal{R} $ 为保序的当且仅当 $$ \begin{aligned} & \forall i, j . x_i>x_j \Rightarrow y_i>y_j, \quad \text { and } \\ & \forall i, j \cdot y_i>y_j \Rightarrow x_i \geq x_j . \end{aligned} $$ 概率保序脱敏算法（Probabilistic Order-Preserving Desensitization Algorithm） 令 $ X = x_1, x_2, \dots, x_n (\forall i.x_i \in \mathbb{N}) $ 为敏感序列，$ Y = y_1, y_2, \dots, y_n (\forall i.y_i \in \mathbb{N}) $ 为由脱敏算法 $ \mathcal{R} $ 生成的噪声序列。脱敏算法 $ \mathcal{R} $ 为概率保序的当且仅当 $$ \forall i, j . x_i>x_j \Rightarrow \operatorname{Pr}\left[y_i>y_j\right] \geq \gamma(t) $$ 其中 $ \gamma(t) \in [0, 1] $，$ \left| x_i - x_j \right| \leq t $。在这里 $ \gamma(t) $ 是与 $ x_i $ 到 $ x_j $ 之间的距离有关的函数，当 $ \gamma(t) = 1 $ 时则为保序脱敏算法。 梯度提升树（Gradient Tree Boosting） GBDT (Gradient Boosting Decision Tree），中文名为梯度提升决策树，是一种基于决策树的增强学习算法，它被广泛地应用于回归、分类以及排序等问题。XGBoost 是一种 GBDT 的高效实现。 在梯度提升树的过程中，只有特征值的顺序是必要的。该算法（XGBoost）持续寻找分裂点并计算其增益。我们设 $ I_L $ 和 $ I_R $ 分别为样本集分裂（split）后的左右节点，$ g_i $ 和 $ h_i $ 为梯度，$ \lambda $ 和 $ \omega $ 为正则化参数，分裂的增益如下： $$ G_{split}=…

VLDB 22 Privacy-preserving Cooperative Online Matching over Spatial Crowdsourcing Platforms
type: item
date: 2023-02-24T21:38:08+08:00
description: 摘要 本文提出了一种名为隐私保护的协作在线匹配（Privacy-preserving Cooperative Online Matching(PCOM)）的框架，可以保护用户和工人在各自平台上的隐，并基于两种不同的隐私保护策略提出了两种不同的 PCOM 算法。 本文主要贡献如下： 制定了 PCOM，并提出了 PCOM 框架，在考虑敏感数据隐私的情况下将各平台收益最大化 证明了 PCOM 框架满足差分隐私性质，并提出了两种求解 PCOM 的算法 基于平台历史数据对请求的收益进行定价 综合考虑收益和请求被接受的概率进行定价 在真实和合成数据集上验证了算法的有效和高效性 问题说明 问题定义 请求（Request） 一个空间众包平台上的请求 $ r $ 定义如下：$ r = \langle t_r, l_r, d_r, \nu_r \rangle $，其中 $ t_r $ 为请求发出的时间，$ l_r $ 是在二维地图上请求发出的地点，$ d_r $ 是完成请求所需要的距离，$ \nu_r $ 是完成请求可以获得的收益 工人（Worker） 一个空间众包平台上的工人 $ w $ 定义如下：$ w = \langle t_w, l_w, rad_w \rangle $，其中 $ t_w $ 为工人出现的时间，$ l_w $ 为在二维地图上工人出现的地点，$ rad_w $ 为二维空间上工人服务的半径 本地/合作平台（Local/Cooperative Platform） 一个平台的描述如下：$ p = \langle R, W \rangle $，其中 $ R $ 是平台 $ p $ 上请求的集合，$ W $ 是在平台 $ p $ 上注册的工人集合。对于一个给定的请求 $ r $，请求发出的平台称为请求 $ r $ 的本地平台（Local Platform），相反，合作平台（Cooperative Platform）是合作中除了本地平台以外的任意平台。在本地平台上的工人称为本地工人（local worker），记为 $ w_{loc} $，在合作平台上的工人称为合作工人（cooperative worker），记为 $ w_{cop} $ 对外支付（Outer Payment） 当一个合作工人需要服务一个请求 $ r $，他想获得一笔报酬 $ \nu_r^\prime \in (0, \nu_r] $，其中 $ \nu_r^\prime $ 称为对外支付 收入（Revenue） 当请求 $ r $ 由本地工人服务时，平台将收到 $ \nu_r $ 的报酬，当请求 $ r $ 由合作工人服务时，平台将收到 $ \nu_{r_i} - \nu_{r_i}^\prime $ 的报酬。假设有一个可行匹配 $ M $，$ M_{loc} $ 为满足本地工人服务的匹配，$ M_{cop} $ 为满足合作工人服务的匹配，则平台的总收入定义如下： $$ \operatorname{Rev}=\sum_{i=1}^{\left|M_{l o c}\right|} v_{r_i}+\sum_{i=1}^{\left|M_{c o p}\right|}\left(v_{r_i}-v_{r_i}^{\prime}\right) $$ 隐私保护协作在线匹配（Privacy-preserving Cooperative Online Matching）（PCOM） 给定一组愿意参与合作的空间众包平台 $ P $，每个平台 $ p \in P $ 包含请求和工人，工人和请求依次出现。 PCOM 将为每个平台找到一个受益 $ Re\nu $ 最大的匹配结果 $ M $，并且满足以下约束： 时间约束：一个请求只能由发出之前就存在的工人来完成 1对1约束：一个请求同时只能由一个工人进行服务，反之亦然 不变约束：一旦某个工人被分配到某个请求，则该分配不可被更改或取消 范围约束：一个工人只能服务位置在服务半径内的请求 隐私约束：实时数据隐私（请求精确位置不应泄露给平台）和历史数据隐私（用户请求的出现、结束位置和时间不应泄露给合作平台） 评价准则 差分隐私（Differential Privacy） 地理不可分（Geo-indistinguishability） 假设 $ \mathcal{X} $ 是一个精确位置的集合，给定一个随机算法 $ A $，$ Range(A) $ 是可能报告的输出的集合，当对所有的 $ x, x^\prime \in \mathcal{X} $，$ z \in Range(A) $，$ d(x, x^\prime) \leq r $，有 $$ \operatorname{Pr}[A(x)=z] \leq e^{\varepsilon d\left(…

VLDB22 Federated Matrix Factorization with Privacy Guarantee
type: item
date: 2023-01-03T23:43:00+08:00
description: 摘要 本文主要研究了不同联邦学习环境下的矩阵分解（MF）问题，提出了一个通用的联邦矩阵分解（FMF）算法框架，系统地表征了垂直联邦学习（VFL）、水平联邦学习（HFL）和本地联邦学习（LFL）三种不同设置的数据采集、训练和发布阶段的隐私泄露风险，并引入隐私概念和一种新的被称为嵌入裁剪的私有学习技术以提供端到端的隐私保护。 介绍 本章主要介绍了一些联邦学习的概念和三种不同设置的联邦学习（VHL、HFL、LFL）所需要的不同的隐私边界设置。 本文的贡献如下： 提出了一个应用于三种设置的抽象的计算范式 针对不同的隐私泄露风险为不同的设置设计了不同的FL算法 提出使用嵌入裁剪（Embeddings Clipping）代替梯度裁剪（Gradient Clipping）来进行更新 提出了用于矩阵分解的 SGDMF 算法（包括 VFL-SGDMF、HFL-SGDMF、LFL-SGDMF） 背景 本章主要介绍了一些背景知识，如矩阵分解、差分隐私等 矩阵分解 矩阵分解问题可以形式化为如下最小化损失函数： $$ \mathcal{L}(X,U,V): \frac{1}{|\Omega|} \sum_{(i,j) \in \Omega} \mathcal{L}_{i,j}(X,U,V)=\frac{1}{|\Omega|} \sum_{(i,j) \in \Omega}(X_{ij}-\langle u_i,\nu_j \rangle)^2 $$ 差分隐私 Sequential composition: moments accountant $ M(X, aux) $ 表示 $ X $ 的输出，$ aux $ 为辅助输入，可包含前面步骤的所有中间结果 在 $ \lambda $ 处的矩生成函数（$ M $ 中的隐私损失）的对数定义如下： $$ \alpha_M(\lambda;X,X',aux) = logE_{o~M(X,aux)}[exp(\lambda log \frac{Pr[M(X,aux)=o]}{Pr[M(X',aux)=o]})] $$ 其中上界为 $ \alpha_M(\lambda) = max_{X,X',aux}\alpha_M(\lambda;X,X',aux) $，$ M_t $ 为适应性机制，使用 $ M_1 ~ M_{t-1} $ 和数据集 $ X $ 作为输入 Moments Accountant 将总体隐私损失限制在 $ M_1 $ 到 $ M_T $ 之间（通过 $ log $ 矩母函数） Moments Accountant 设机制 $ M $ 为一系列适应性机制 $ M_1,\dots,M_T $，则有 (1) 对任何 $ \lambda $，有 $ \alpha_M(\lambda) \leq \sum^{T}_{t=1}\alpha_{M_t}(\lambda) $ (2) 对任何 $ \epsilon > 0 $，机制 $ M $ 为 $ (\epsilon, \delta) $ - 差分隐私，$ \delta = min_{\lambda}exp(\alpha_M(\lambda)-\lambda_{\epsilon}) $ Parallel Composition 若 $ M_1, \dots, M_T $ 为 $ (\epsilon^{(1)}, \delta^{(1)}), \dots, (\epsilon^{(s)}, \delta^{(s)}) $ - 差分隐私，且他们都在不相交的数据集 $ X_1, \dots, X_s $ 上计算，则整体隐私损失为 $ (max_k\{\epsilon^{(k)}\}, max_k\{\delta^{(k)}\}) $ Per-rating Privacy 当有一索引 $ (i,j) $ 使得 $ X_{i,j} = \perp $ 且 $ X'_{i,j} \neq \perp $（或相反），且对任意 $ (i',j') \neq (i,j) $，有 $ X_{i',j'} = X_{i,j} $，则 $ X,X' $ 为相邻数据集 Per-rating Privacy 保护每个单独的由每个用户给出的评分 Bounding Sensitivity Sensitivity 指的是当数据有一条发生变化（增加/删除）时所产生的影响 Gradient Clipping 梯度裁剪可以用于 Bounding Sensitivity，但是在实际应用中有限制每个评分的效果和需要额外空间存储每个评分梯度的问题 Trimming 限制参与方 $ k $ 的最大评分数为 $ \theta^{(k)} $，并将剩余评分转换为 $ \perp $ 联邦矩阵分解 本章介绍了在三…

VLDB 22 Hu-Fu: Efficient and Secure Spatial Queries over Data Federation
type: item
date: 2022-11-21T15:31:53+08:00
description: 摘要 本篇文章提出了 Hu Fu（虎符） 系统，第一个基于数据联邦的安全空间查询处理系统，解决了现有解决方案空间查询效率低的问题，其思想是将空间查询的安全处理分解为尽可能多的明文操作和尽可能少的安全操作，并且支持原生SQL查询输入以及后端的异构空间数据库。 介绍 虎符系统消除了对诚实代理（Honest Broker（见SMCQL））的需求，并支持更多的数据仓库（测试了10个）。虎符的关键思想是在保证安全性的前提下将联邦空间查询分解为尽可能多的明文操作和尽可能少的安全操作，其中不涉及安全距离相关操作，且安全操作的实现速度比一般用途的 SMC 库更快。 虎符由三个组件组成：一个有着新颖组合方案的查询重写器，一组用于异构数据库的驱动程序以及一个支持 SQL 的易于使用的查询界面。查询重写器识别一组明文和安全运算符，以覆盖感兴趣的查询，并采用新颖的组合计划，在确保安全的同时尽量减少安全运算符的使用。驱动程序为安全运营商提供了专用的SMC协议和明文操作，作为不同数据仓库选择的异构空间数据库之上的接口。查询界面支持本地SQL中的空间查询，以便于使用。 本文的主要贡献如下： 第一个通过数据联邦执行高效、安全的空间查询的系统 新的关于联合空间查询的分解方案 Hu Fu（虎符），一个高效易用的支持 SQL 和异构空间数据库的系统 问题陈述 联邦范围查询/计数：返回所有在查询范围内的在联邦里的数据（个数） 联邦 KNN 查询：给定一个数据联邦 $ F = \{F_1, \dots, F_n\} $，一个查询点 $ p $ 和一个整数 $ k $，查询返回一个含有 $ k $ 个空间对象的集合 $ kNN(F, p, k) $（$ \forall o \in kNN(F, p, k), \forall o' \in F - kNN(F, p, k), d(p, o) \leq d(p, o') $） 联邦距离连接：给定一个空间对象的输入数据集 $ R $，一个数据联邦 $ F $ 和一个半径 $ r $，返回在 $ F $ 中的对 $ R $ 中所有对象距离小于半径的二元组（$ R \bowtie_r F = \{(o, o')|o \in R, o' \in F, d(o, o') \leq r \} $） 联邦 kNN 连接：给定一个空间对象的输入数据集 $ R $，一个数据联邦 $ F $ 和 $ k $，返回所有在 $ R $ 中的与 $ o' \in kNN(F, o, k) $ 成对的 $ o $（对象），整个过程不会泄露除返回集合以外的信息 当前研究的痛点主要在于过度的安全距离操作和对通用库的依赖，而虎符对大规模的安全距离操作涉及到的安全操作明显更少，每个安全操作也通过专用算法高效实现 系统概览 虎符通过两个模块解决了空间查询速度低下的问题：一个查询重写器和一个驱动程序 查询重写器江联邦空间查询分解为明文和安全操作符，驱动程序负责将这些操作符是纤维纯文本和安全原语，并使用专用算法实现和优化 虎符还包含一个透明的查询接口，他支持使用原生 SQL 编写的联邦空间查询 上图是虎符的工作流程，可以看到在每个数据孤岛上都运行着一个虎符 Drivers 实例，用于与其底层数据库进行交互。在用户机器上部署了查询接口和查询重写器，当查询时先通过查询接口进行解析，再通过查询重写器将其转换为一系列优化后的明文和安全运算符。随后这些运算符被发送到各个数据孤岛运行的 Drivers 并执行，随后各孤岛将局部结果返回给客户机的虎符接口，将结果汇总后再返回给用户。 查询重写器 运算符主要分为两大类：明文运算符和安全运算符 明文运算符 明文运算符可以涉及空间查询中强制执行的与距离相关的操作，在每个数据孤岛中本地执行，但应该是各种空间数据库广泛支持的常用操作 明文运算符分为明文范围查询和明文范围计数两种 明文范围查询：对于一个数据孤岛 $ F_i $，给定一个查询范围 $ \mathcal{R} $，明文范围查询 $ PRQ_{F_i}(\mathcal{R}) $ 返回 $ F_i $ 中在 $ \mathcal{R} $ 内的明文空间对象数据 明文范围计数：与明文范围查询相同，只不过返回的是空间对象的个数 安全运算符 安全运算符应避免有关距离的相关操作，用于孤岛间的数据操作，最好是高效实现的运算符 安全运算符分为安全求和、安全比较和安全集合合并三种 安全求和：对于一个联邦 $ F $，每个孤岛 $ F_i $ 持有一个数字 $ \beta_i $，安全求和在不向其他参与方泄漏 $ \beta_i $ 的同时计算并返回 $ \sum_{i=1}^{n}\beta_i $ ($ SSM_F(\beta_1, \dots, \beta_n) = \sum_{i=1}^…

VLDB17 SMCQL: Secure Querying for Federated Databases
type: item
date: 2022-09-13T15:53:00+08:00
description: 摘要 在数据量不断膨胀的今天，但是因为隐私问题，在科学研究等方面的数据共享工作仍然进展缓慢。 本文提出了一种名为 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——一个拥有类…