type
status
date
slug
summary
tags
category
icon
password
Mastic: Private Weighted Heavy-Hitters and Attribute-Based Metrics阅读记录
基本信息
Mastic: Private Weighted Heavy-Hitters and Attribute-Based Metrics
作者：Dimitris Mouris
期刊 & 会议：IACR ePrint
时间：2024
JCR/CCF：N/A
相关链接：
研究对象
应用场景
- 隐私频繁项（Private Heavy-Hitters）问题：多个客户端都拥有一个秘密的比特串，服务器在不获取任何与客户端秘密比特串有关信息的前提下，区别出出现频率最高的那条字符串。例如，用户（即客户端）访问不同的网页，服务器需要在不知道用户访问的是那个网页的前提下，统计出用户访问频率最高的那个网页。
- 隐私频繁项问题与隐私信息检索问题相似，隐私检索问题是客户端向服务器发送一个数据查询请求，服务器在不知道客户端到底访问的是数据库里面的那条数据的前提下，返回检索结果给客户端。
- - PHH问题：与PHH问题相似，只不过服务器需要返回前 个访问频率最高的结果。
研究动机
潜在问题
- 在一个多客户端和服务器场景下，如何在不泄露客户端个人隐私输入的情况下，服务器基于给定的客户端输入计算一个函数值，实现这一目标是相对比较困难的。
研究目标&贡献
主要贡献
- 基于可验证的增量式分布式点函数以及针对秘密共享数据的零知识证明提出了一个针对weighted heavy hitters 和 attributed-based metrics 的具体协议，以解决
研究基础
分布式点函数 (Incremental Distributed Point Function, IDPF)
上式为一个分布式点函数的表达式。
增量式分布式点函数要求在 的基础之上满足增量属性，如下图所示。
上图展示了一个二进制的二叉树，又成为索引树，其中每个节点存储的是输出值，被成为权重 (weights)。遍历一条二叉树路径，例如图中绿色节点那条路径。 ，其中 对应着图中 。
可验证分布式点函数要求能够抵御恶意客户端发起的攻击。（由于在很多场景中，客户端并不可能完全可信，并且函数秘密共享要求共享不能够泄露任何与函数有关的任何信息，因此其生成的函数共享不一定可以用于评估目标函数，进而导致评估错误。）
可验证的增量式分布式点函数形式化定义
- . 给定 作为输入，输出两个密钥 以及 一个公开共享 .
- . 给定一个密钥 ，公开共享 ，状态 以及 （对于索引树路径 ，从根节点到节点 ，其中 是 的叶子节点）作为输入，输出新的状态和证明（对于索引树路径 ，从根节点到当前节点）以及一个权重值 的共享 。根节点 的状态和证明定义为
- . 给定一个密钥 以及公开共享 作为输入，输出一个聚合者的共享
一个VIDPF需要满足以下属性：
- 正确性：对于任意给定的输入 ，以及权重值 ，任意 ，以及任意 ，令 以及 ，对于任意的 以及 ，均有 以及 （当且仅当 ）; 成立。
- 隐私性：任意的聚合者不能够从公开信息中获得任何与该共享函数有关的信息，不可区分的游戏定义如下。
- 敌手 选取 以及一个恶意聚合者索引
- 挑战者均匀随机从 中随机选择一对
- 挑战者运行 并将公开共享以及恶意聚合者索引所对应的密钥 返回给敌手
- 敌手 猜测并输出 ，当且仅当 时，敌手赢得该游戏
- 隐私性是针对恶意聚合者，即客户端为半诚实，聚合者不可以知道具体函数有关信息。
- 可验证性：任何恶意客户端均不能重构一个 使得层索引树出现两条路径满足VIDPF的正确性要求。对应于IDPF图中出现了两条从根节点到第层叶子节点的路径，并且路径中每个节点中权重，即节点值都为
- 敌手运行 获得 以及 并发送给挑战者
- 挑战者对于 ，计算如下两个
- 敌手输出 ，当且仅当输出为时敌手获胜。
共享的零知识证明形式化定义
- . 给定秘密共享值 的两个秘密共享 作为输入，输出一个部分证明以及一个随机值（对于每个聚合者），该算法由客户端执行，且每个客户端都需要执行。
- . 给定一个由聚合者们共享的验证密钥 ，某聚合者的 ，一个秘密共享 以及对应的部分证明 ，输出该聚合者的状态 以及一个 部分验证值 ，该算法每个聚合者都运行。
- . 给定一个聚合者的所有验证值 以及该聚合者的状态 作为输入，若 输出 ，否则输出 。该算法同样要求每个聚合者都运行。
一个共享的零知识证明需要满足以下属性：
- 完备性：当所有的客户端和聚合者都是诚实的，聚合者会一直接收该证明，即 会始终输出
- Sound：当聚合者都是诚实的，来自恶意客户端的共享值将会被聚合者以不可忽略的概率检测到
- 敌手基于秘密共享值 运行 获得
- 随机选取一个验证密钥
- 对于任意 聚合者运行
- 存在 b 使得 （恶意客户端共享了一个不在 中的 ，并且其仍然通过了聚合者的验证，则表示该恶意客户端成功攻破了该零知识证明系统。）
- 如果上述布尔表达式输出 true 则敌手获胜。
- 零知识性：当客户端是诚实的，并且至少一个聚合者是诚实的，整个零知识证明系统不会泄露有关秘密共享值 的任意信息，除了可验证性结果。
在模拟游戏中的 阶段是不知道秘密值 的共享值，直接获得部分证明的。模拟游戏与真实游戏不可区分表明敌手是不知道秘密共享值的任何信息，因为一旦敌手能够获得秘密共享值 的具体信息，那么敌手就能够很容易去区分两个游戏。
研究内容
系统模型
- 客户端：每个客户端都拥有一个秘密输入值对
- 服务器（聚合者）：整个系统中存在两个聚合者，第一个聚合者被称为 ,，第二个被称为 。 它们的主要功能是给定所有客户端的秘密输入，计算一个聚合结果。除了 需要选择一个共享的验证密钥去验证权重 之外，两个聚合者的计算操作大致相同。
- 主要流程：客户端向每个聚合者发送一个编码后的秘密共享，随后聚合者之间相互交互验证每个秘密共享是否合法，最后去计算weighted heavy hitters。整个协议流程中，客户端仅参加发送消息那个步骤，后续便不再参与。
安全模型
敌手能力
敌手是完全恶意的，它可以在协议的任意阶段发起攻击
敌手攻击的客户端和聚合者集合是固定的
敌手在攻击前选定需要攻击的实体集合，并且在后续阶段保持不变
敌手可以去监听任何通信信道，除了诚实客户端和诚实聚合者的信道（文中默认这个通信信道为安全信道，敌手无法监听）
安全目标
隐私性：在存在恶意客户端以及最多一个恶意聚合者的情况下，攻击者仅能够获得聚合者计算后的 weighted heavy hitters，而不会获得任何与客户端秘密输入值对有关的信息。当两个聚合者都是恶意的，隐私性的目标将无法保障。
鲁棒性：对于恶意客户端提交的秘密输入值对，聚合者可以能够检测出来，不会对最后计算结果造成影响
Mastic协议
客户端计算：
聚合者计算：
聚合者所拥有的输入信息
聚合者检查所有客户端发送的编码后的秘密值对 是否合法，包括：格式检查与共享零知识证明验证
这个部分主要目标是两个聚合者之间相互交互，以验证客户端的 是否合法，即检测客户端是否为恶意的。
聚合者验证后计算 weighted heavy hitters
验证 层索引树的 输出 是否等于 层的左右叶子节点的两颗索引树的 输出之和，即
聚合者返回结果
研究结果
总结与展望
参考文献
- Mouris D, Patton C, Davis H, et al. Mastic: Private Weighted Heavy-Hitters and Attribute-Based Metrics[J]. Cryptology ePrint Archive, 2024.
有关这篇论文的任何问题，欢迎您在底部评论区留言，一起交流~