type
status
date
slug
summary
tags
category
icon
password
PLASMA: Private, Lightweight Aggregated Statistics against Malicious Adversaries阅读记录
基本信息
PLASMA: Private, Lightweight Aggregated Statistics against Malicious Adversaries
作者：Dimitris Mouris
期刊 & 会议：Proceedings on Privacy Enhancing Technologies
时间：University of Delaware
JCR/CCF：CCF-C
相关链接
研究对象
密码技术 & 应用场景
- 隐私频繁项（Private Heavy-Hitters）问题：多个客户端都拥有一个秘密的比特串，服务器在不获取任何与客户端秘密比特串有关信息的前提下，区别出出现频率最高的那条字符串。例如，用户（即客户端）访问不同的网页，服务器需要在不知道用户访问的是那个网页的前提下，统计出用户访问频率最高的那个网页。
- 隐私频繁项问题与隐私信息检索问题相似，隐私检索问题是客户端向服务器发送一个数据查询请求，服务器在不知道客户端到底访问的是数据库里面的那条数据的前提下，返回检索结果给客户端。
- - PHH问题：与PHH问题相似，只不过服务器需要返回前 个访问频率最高的结果。
研究动机
潜在问题
- 基于差分隐私方法去解决隐私频繁项问题，虽然计算效率比较高，但是差分隐私并不能提供很强的隐私保护级别，它的隐私保护是与其隐私预算有关的，隐私预算越高，安全保护越强
- 基于安全多方计算的隐私频繁项方法中，服务器之间交互的通信开销比较大，并且与客户端数量成正比。
- 现有的方法虽然解决了隐私频繁项问题，但是服务器之间的通信开销非常大，并且与客户端数量成正比。
- Poplar和一些基于差分隐私的方法无法抵御来自恶意服务器的攻击，它们仅能抵御来自恶意客户端的攻击。
- 现有方法也不能够在恶意服务器和恶意客户端合谋的情况下为隐私频繁项提供隐私保护并保证计算结果的正确性。
研究目标&贡献
研究目标：能否获得一个具有低服务器交互通信开销的隐私频繁项协议，并且能够在恶意客户端以及一个恶意服务器的前提下保障协议安全（隐私、正确性）
主要贡献
- 可验证的增量分布式点函数（Verifiable Incremental Distributed Point Function, VIDPF）：一个新的密码学原语，实现客户端秘密输入的验证并保证客户端秘密输入的隐私不会被泄露。
- 批量一致性检查（Batched Consistency Check）：有效降低服务器之间交互的通信开销，从 降低至 ，其中 表示客户端总数量， 表示的是恶意客户端数量。
- PLASMA协议：一个用于三方服务器设置中的保障隐私频繁项安全的协议，可以保证针对恶意服务器和恶意客户端的安全性（隐私、正确性），同时实现低服务器通信开销。
- 应用：将PLASMA协议应用于两个隐私频繁项场景：检测频繁访问的URL；识别流行的地理位置坐标（可以避免交通堵塞、餐厅推荐等）
研究基础
分布式点函数 (Distributed Point Function, DPF)
上式为一个分布式点函数的表达式。分布式点函数是仅有一个非零点
增量式分布式点函数要求在 的基础之上满足增量属性，此时那个非零点变为一条二叉树路径且该路径中节点的值均不为0，如下图所示，绿色路径中节点的值均不为0。
上图展示了一个二进制的二叉树，又成为索引树，其中每个节点存储的是输出值，被成为权重 (weights)。遍历一条二叉树路径，例如图中绿色节点那条路径。 ，其中 对应着图中 。
可验证分布式点函数要求能够抵御恶意客户端发起的攻击。（由于在很多场景中，客户端并不可能完全可信，并且函数秘密共享要求共享不能够泄露任何与函数有关的任何信息，因此其生成的函数共享不一定可以用于评估目标函数，进而导致评估错误。）
可验证的增量式分布式点函数形式化定义
- . 给定 作为输入，输出两个密钥 以及 一个公开共享 .
- . 给定一个密钥 ，公开共享 ，状态 以及 （对于索引树路径 ，从根节点到节点 ，其中 是 的叶子节点）作为输入，输出新的状态和证明（对于索引树路径 ，从根节点到当前节点）以及一个权重值 的共享 。根节点 的状态和证明定义为
- . 给定一个密钥 以及公开共享 作为输入，输出一个聚合者的共享
一个VIDPF需要满足以下属性：
- 正确性：对于任意给定的输入 ，以及权重值 ，任意 ，以及任意 ，令 以及 ，对于任意的 以及 ，均有 以及 （当且仅当 ）; 成立。
- 隐私性：任意的聚合者不能够从公开信息中获得任何与该共享函数有关的信息，不可区分的游戏定义如下。
- 敌手 选取 以及一个恶意聚合者索引
- 挑战者均匀随机从 中随机选择一对
- 挑战者运行 并将公开共享以及恶意聚合者索引所对应的密钥 返回给敌手
- 敌手 猜测并输出 ，当且仅当 时，敌手赢得该游戏
- 隐私性是针对恶意聚合者，即客户端为半诚实，聚合者不可以知道具体函数有关信息。
- 可验证性：任何恶意客户端均不能重构一个 使得层索引树出现两条路径满足VIDPF的正确性要求。对应于IDPF图中出现了两条从根节点到第层叶子节点的路径，并且路径中每个节点中权重，即节点值都为
- 敌手运行 获得 以及 并发送给挑战者
- 挑战者对于 ，计算如下两个
- 敌手输出 ，当且仅当输出为时敌手获胜。
Histogram Protocol of Poplar
私有直方图问题
每个客户端拥有一个隐私输入—一个n比特字符串 ，服务器 和 拥有一个集合 ，其中每个元素都是一个 n比特字符串。
客户端秘密共享其隐私输入 ，获得两个密钥 并返回给服务器 密钥
每个服务器 对所有的 使用密钥 计算评估结果 ，输出
服务器与多个客户端完成上述计算后，获得
服务器之间相互交换 ，计算 并返回给客户端
为抵御恶意客户端通过伪造隐私输入或恶意的评估密钥对协议输出结果造成影响，Poplar利用一个·恶意摘要协议，但是这个协议中，服务器之间的通信开销是与客户端数量成线性关系，即
研究内容
系统模型&安全模型
- 本文的主要实体包括三个不共谋的服务器以及 个客户端，客户端提供其隐私输入给服务器完成计算，服务器不能知道客户端隐私输入的具体内容。
- 恶意敌手 可以控制一个服务器以及 个客户端。
- 恶意客户端可以通过伪造一些恶意的隐私输入，以使得最终服务器计算结果不正确，进而影响协议的正确性。
- 恶意服务器可以随时违背协议流程，并试图去获取客户端的隐私输入内容，同时，恶意服务器还可能会伪造最后的计算结果以影响协议正确性。
与Poplar相比的优势
在一个恶意服务器与恶意客户端合谋的情况下，所提协议可以提供鲁棒性
对于恶意客户端的攻击行为，所提协议可以通过一个轻量级的一致性检测来发现并抵御
在所提协议中，服务器与服务器之间的通信开销与客户端数量成log级，即
核心技术解析
- 三服务器模型
- 服务器通信开销优化：为降低服务器间的通信开销和带宽，任意两个服务器之间不再维护两个会话，而是在服务器 和 服务器 之间维持三个原本的所有三个会话，而服务器 仅作为证明服务器。因此客户端需要向服务器 分别发送 key(2,1)，key(2,0)
- 服务器 因为拥有 key(2,1) 可以复制原本 会话的计算结果；同理，服务器 同样也可以复制会话 的计算结果
- 服务器 作为证明服务器，会计算服务器 发送的相同消息的哈希给服务器 ，以防止服务器 的恶意行为。服务器 同理
- 会话阶段客户端输入验证（确保三服务器会话过程中，客户端输入的可靠性）
- 服务器 拥有DPF密钥 key(0,1)，key(0,2)，key(2,1)，评估计算结果为 Y(0,1)，Y(0,2)，Y(2,1)
- 服务器 拥有DPF密钥 key(1,0)，key(1,2)，key(2,0)，评估计算结果为 Y(1,0)，Y(1,2)，Y(2,0)
- 根据DPF函数的性质，每对DPF评估结果 [Y(0,1),Y(1,0)] 会获得一个向量，其仅在DPF函数的指定位置非0
- 服务器 计算哈希值 给服务器
- 服务器 计算哈希值 并验证
- 计算 -频繁项算法（通过寻找 索引统计）
- 借用定义1中的预言机，寻找出现次数超过阈值 的前缀字符串，并构建集合
- 定义1中的预言机实现原理
- 定义1中的预言机实现是基于可验证的增量分布式点函数（VIDPF定义见研究基础）
- 完整的客户端输入验证思路
- check 1：服务器 和服务器 首先验证三个会话中VIDF密钥生成算法输出的证明是相同的，这可以确保二进制二叉树中至多存在一条节点值非零路径
- check 2：对于根节点层，服务器在空字符串 上评估VIDF密钥，并验证是否为1（根节点的值必为1，见研究基础中增量DPF的图）
- check 3：对于任意 k 子节点层，如研究基础中的IDPF示意图所示，当父节点值为1时，其左右子节点至多有一个节点为1。因此，前p长的索引树的评估输出一定是等于p+1长输出的和，即 。因此只需要验证 即可。
- check4：验证服务器之间通信过程中客户端输入的可靠性，见本小节 3 所述。
PLASMA协议
- 协议输入、输出以及部分符号定义
- 客户端计算
- 每个客户端计算三对 VIDPF 密钥（给定其隐私输入 ，）
- 执行服务器通信开销优化部分 Fig.2 中内容
- 服务器计算-1
- 初始化，用于记录每个前缀 以及 出现的频率
- 服务器使用 VIDPF 密钥对前缀索引树 进行 VIDPF 评估，获得对应的输出结果
- 对于 层前缀索引树 和 ，服务器进行VIDPF评估，获得对应的新输出结果
- 当 时，此时为索引树的根节点，需要验证根节点的VIDPF评估结果是否为 1，因为根节点是隐私输入的开始，其节点值肯定为1，若不为1，则表明存在恶意客户端。
- 当 ，服务器验证 前缀树的VIDPF输出是否等于 层前缀树 和 的VIDPF输出之和。（PS：根节点是一种特殊情况，仅考虑根节点层即可）
- 服务器计算-2
- 服务器 与服务器 分执行客户端输入验证步骤四，即 check 4，见上一小节 6
- 客户端状态累积：H（k轮迭代中所有的前缀索引树 、check 3 得到的哈希值以及下一层 前缀树的证明）
- 批量验证：可以将通信复杂度从 降低为
- ：输入两个字符串列表，能够判断字符串是否相等，并且返回不相等的字符串索引集合。这种方法能够实现的原因是在于客户端状态累积过程中，对所有的信息做了哈希，实际上每个状态，例如，其实是一个哈希值（maybe 256比特的字符串-sha-1）。对于Batch-Verification中所述的两个向量批量认证的实现是基于Merkle树，这还是因为状态里面的内容是哈希值。
- 算法输入与输出
- 计算Merkel树根节点
- 根节点验证是否相同
- 若根节点验证未通过，则表明存在恶意的客户端，需要去递归地寻找。如果客户端是诚实的，那么VIDPF中必然会是一条非零路径，即路径节点值不为空，并且左右节点值必不相同。若左右节点相同且都为0，则表示这条路径不是全非0路径，若左右节点相同且都为1，则表示可能存在两条非零路径，即分布式点函数会有两个非零点值。同时，基于与的具体内容，即是必然成立，可以得到下图中的那个判断。
- 服务器 是验证服务器，需要确保服务器 以及服务器 诚实运行协议，因此基于前面的协议，对进行验证（见核心技术部分的2）算法图里面的下标好像有点问题。。。
- 聚合
- 剪枝
- 输出
研究结果
实验结果
- 客户端通信与计算开销
- 服务器通信与计算开销
- 服务器与服务器之间的通信开销
总结与展望
- 这篇论文主要针对于隐私频繁项问题，解决现有研究Poplar存在的服务器之间通信开销大且与客户端成正比、不支持恶意服务器等问题。
- 对后续研究有启发意义的点在于所提出的一个可验证增量分布式点函数，即VIDPF
参考文献
- Mouris D, Sarkar P, Tsoutsos N G. PLASMA: Private, Lightweight Aggregated Statistics against Malicious Adversaries[J]. Cryptology ePrint Archive, 2023.
- AES-NI指令集：https://zh.wikipedia.org/zh-cn/AES指令集
- tarpc：适用于Rust的并行工具 https://blog.csdn.net/gitblog_00073/article/details/136931695
协议的安全性证明比较多，后续再慢慢更新…………
有关这篇论文的任何问题，欢迎您在底部评论区留言，一起交流~
<ins/>