基本信息

📢

Title for papers

作者：Emma Dauterman

期刊 & 会议：IEEE S&P

时间：2022

JCR/CCF：CCF-A

相关链接：

PPT：

原文：https://eprint.iacr.org/2021/1661.pdf

视频：

代码：https://github.com/ucbrise/waldo

研究对象

研究动机

⚠️

潜在问题

1. 时间序列数据通常会涉及到个人敏感信息，例如，医院所记录的不同时间段的病人心率等信息。如果直接将这些数据外包存储至云服务器数据库，会直接面临着隐私泄露的问题。

2. 虽然现有的方法，如Timecrypt 和 Zeph，通过加密时间序列数据来解决隐私泄露问题。但是他们面临着两个挑战：首先，他们所支持的数据检索的功能比较单一，仅支持时间序列数据的简单叠加聚合操作。例如，计算一周以内某病人的心率均值。然而在现实场景中，例如，医生想通过运行下面这个sql查询语句来评估充血性心力衰竭风险，Timecrypt 和 Zeph 仅具备的单一数据检索功能便不再适用了。其次，Zeph 和 Timecrypt 在数据检索过程中会泄露查询请求给服务器，例如，如果医生正在查询患者的心率，则该次查询请求会揭漏患者心脏病发作时间、患者服用何种药物以及患者服用药物的时间等，显然，这不仅会造成患者隐私泄露，甚至会危及患者的生命健康安全。

1. 虽然oblivious RAM 以及 MPC 等技术可以解决上述问题，但是这两种技术有着各自的弊端。ORAM技术适用于可信代理场景，即服务器是完全可信的。这种假设太强，对于现实场景而言比较难以接受。MPC技术适用于分布式场景，即服务器部署在不同的云中。然而，这会导致服务器之间需要相互交互，显著增加计算和通信开销。此外，无论是ORAM技术还是MPC技术，它们的通信和计算开销都非常大，例如，ORAM 和 MPC 都需要客户端和服务器之间进行多轮交互。

研究目标&贡献

研究基础

研究内容

💫

核心技术

• Waldo系统模型

• Waldo的两个核心结构
• WaldoTable：
• 能够存储一个时间戳所对应的数据的多个特征，支持多谓词问询检索
• 能够支持复杂的多谓词过滤，即对应sql语句中where存在多个条件
• WaldoTree：
• 能够存储一个时间戳所对应的数据的单个特征，仅支持时间范围内的问询检索
• 支持众多聚合检索类型
• 支持具有预定义筛选器的sql查询，并且比WaldoTable更快，使用更少的存储空间，但是无法支持未预定义的筛选器，WaldoTable支持这一功能，因此它存储了多个特征。

• 威胁模型与安全保障
• Waldo 中恶意攻击者可以以任意方式影响服务器行为，并且如果一个服务器是恶意的，客户端不会接受它返回的结果或者认为发生错误。
• Waldo 是一个三方 honest-majority security，并且当有一个以上的服务器是恶意的，Waldo无法保障安全要求。
• 如果最多有一个服务器是恶意的，Waldo 可以保证恶意攻击者不会了解数据库中记录内容、查询过滤器输出的值以及任意搜索访问模式，仅了解公共信息。该公共信息包括：1）WaldoTable 和 WaldoTree 中的 schema；2）sql 问询的构造；3）sql 问询是什么时间执行的以及是那个客户端执行的。
• Waldo 支持客户端去验证问询结果的完整性
• 当任意一个服务器不提供服务时，Waldo 不再提供可用性。

• 技术难题 1️⃣
• 基于分布式点函数、分布式比较函数的函数秘密共享（Function Secret Sharing, FSS）可以为分布式场景下时间序列数据库实现相等以及范围谓词检索，但是由于 FSS 中要求所有评估者在使用 Eval 算法时的输入是公开且相同的，这使得 FSS 不能直接应用于 Waldo。 因为Waldo中服务器不应该知道数据库内容，并且服务器之间也不知道它们是否使用了相同的数据库内容，即FSS所要求的公开相同的输入在Waldo数据库中无法满足，不能直接使用

• 解决方法 （对于难题 1️⃣）
• 构造一个one-hot index：对于每一个特征，构造一个 的表格，其中行表示为 当前能够查询的数据库记录总数量，列表示这个特征所对应的数值可能的范围。例如，对于下图中的心率，其可能范围会从 或者更高。表中每一位 的值仅在第 个数据库记录中该特征值 等于列中某一值时对应的值为1，否则为0。例如，下图中，在第一条数据库记录中，心率特征值为80，因此在该表格中， 位置的值被设置为 1，其余位置均为0。服务器针对特征值 计算 FSS 密钥 并计算下式。以分布式点函数为例，其中 只有在 时才为 1， 对应着one-hot index 表中的值。

• 上述方法存在问题
• 1️⃣ 需要知道怎样通过比较大的特征大小 去编码不同的记录值？
• bucketing intervals in



• 哈希函数和布隆过滤器：哈希函数可以将一些标识符，如地址、ID等，又或者一些大整数值压缩到
• 谓词连接，例如，时间可以表示为时间戳，也可以表示为年、月、日、小时、分钟的组合
• 2️⃣ 当 时，可以正确计算出查询结果，但是如果 是密文，可能无法得到正确的结果。
• replicated secret sharing：在复制秘密共享中，每个参与者持有秘密的一份或多份副本，而不是持有秘密的一个片段。这种方法的优点是，即使在参与者中有一部分不可信或不可用，也能保证秘密的安全性和可恢复性。
• 数据库会被划分为三个秘密共享 ， ，
• 客户端生成三对 FSS 密钥 ， ，
• 每个服务器拥有一对数据库 的秘密共享， ： ； ： ； ：
• 客户端分别向服务器 ， 以及 发送 ， ，
• 服务器 计算 和
• 服务器 计算 和
• 服务器 计算 和
• 客户端接收到所有服务器返回值后，计算

• 解决方法-进阶-支持多谓词检索 & semi-honest security
• 上述方法 仅支持统计满足谓词匹配的数据库记录条数，例如，满足心率大于 的数据库记录有 30 条。
• 例如，如何查询某患者在某段时间内心率变化的总和，即
• 显然，只要将 输出的向量叠加求和，即可得到与 相同的结果 (count)。
• 显然，计算求和（sum）的方法是，需要数据库中对应特征的特征值向量 。然后计算该向量与 $FilterPred$ 输出向量的内积 即可。注意此时的这个特征值向量同样也是秘密共享的
• 组合谓词：
• ：直接将这两个 和 向量按位相乘即可，因为 和 向量每一位元素都是 或者
• ：
• ：等价于
• 实现上述组合谓词，需要解决秘密共享值的乘法运算
• 通用的MPC技术，给定共享 ，计算 。显然可以得到
• 在上述通用方法的基础之上获得一个RSS
• 首先秘密共享一个零值：通过伪随机生成器的方法。首先，在初始化阶段，服务器 随机选择一个伪随机函数密钥 并将 其发送给
• 服务器 获得的零值的秘密共享值为
• 服务器 计算 发送给服务器 ，如下图所示。
• 多种聚合检索类型
• 均值：根据设置的过滤器 计算 sum 和 count，客户端本地做除法即可
• 方差：存储数据不再是 而是 ，同样计算一个均值 和一个均值的平方 ，相减即可
• 标准差：方差开根号

• 解决方法-再进阶-支持多谓词检索 & malicious security
• 上面的假设都是一个半诚实敌手，即所有服务器都会诚实执行协议，然而对于恶意敌手而言，需要保障其在执行协议后结果的正确性
• Boyle等人的基于信息论的MAC：验证一个值 ，客户端选择一个秘密值 ，计算MAC 。因此只要 即可验证通过。

• 范围检索（最小值，最大值，前k项），例如，医生想要去查询某患者在一周中最高心率以及时间（并没有看明白，后续再补充）
• WaldoTree：每个叶子节点都有一个记录值，每个节点都包含一个记录其左右子节点记录值的聚合结果。同时，每个叶子节点都有一个公开的时间戳，并且所有的叶子节点都按照时间戳排序，因此每个节点之间都有一个公开的时间间隔。
• To be Continued……

💫

WaldoTable 核心算法：主要就是将上面的核心技术组合在一起，就得到了这两个完整的算法流程，看懂前面的，后面就能理解。

• 客户端执行算法

• 服务器执行算法

研究结果

🔬

实验结果

• WaldoTable Latency

• 不同种类以及数量谓词、不同数量数据库记录下，WaldoTable的问询延迟

• 不同种类问询下，WaldoTable、WaldoTree 与现存方案的对比

总结与展望

参考文献

• https://github.com/osu-crypto/libPSI

• https://zhuanlan.zhihu.com/p/600847687

• Dauterman E, Rathee M, Popa R A, et al. Waldo: A private time-series database from function secret sharing[C]//2022 IEEE Symposium on Security and Privacy (SP). IEEE, 2022: 2450-2468.