安全多方计算技术如何助力分布式数据安全聚合

提出背景：1982年，姚期智先生提出百万富翁问题，探讨在不暴露财富信息的情况下比较财富的场景。
形式化定义：n个参与者以安全方式共同计算函数f(X1, X2, ..., Xn)，每个参与者仅获知输出Yi，无法获取其他信息。
特点：输入隐私性、计算正确性、去中心化。
关注问题：多数据所有者在互不信任情况下协同计算时的计算安全和数据隐私。
发展进程：
- 初始阶段：[Yao82]百万富翁问题。
- 理论问题研究阶段：[BMR90]多方混淆电路，[Yao86, GMW87]混淆电路、加法秘密分享。
- MPC协议高效实现与应用阶段：[MNPS04]首个百万富翁问题的MPC实现。
- 可行性论证阶段：[BGW88, CCD88, RB89]诚实大多数MPC协议。

混淆电路技术：
- 计算模型：布尔电路（XOR、AND）。
- 技术核心：Alice加密电路并发送给Bob，双方通过不经意传输协议获取随机数，逐层计算输出。
线性秘密分享技术：
- 计算模型：布尔电路和算术电路（ADD、MULT）。
- 技术核心：每一方对输入比特进行分享，ADD门本地计算输出分享，MULT门通过不经意传输协议构建加性分享。
- 代表性协议：GMW协议、BGW协议、SPDZ协议。

定义：数据统计分析领域的分位数近似算法，确定性、基于树状结构，支持流式数据。
性能表现：
- 输出长度为m时，回答分位数询问的错误率为O(logσ/m)（σ为universe size）。
- 单个节点最大通信量为3k（k为compression parameter）。
优势：支持多次聚合。
原始数据计算过程：
- Digest property 1：count(v) ≤ n/k。
- Digest property 2：count(v+c) + count(v!) + count(v) > n/k。
- 示例：n=15，k=5，σ=8，算法执行过程分四步。
询问回答过程：
- 示例：L=<1,1>,<6,2>,<7,2>,<10,4>,<11,6>，重排序后<10,4>,<11,6>,<6,2>,<7,2>,<1,1>。
- 中位数询问（0.5n=7.5），因4+6>7.5，故11为回答。

目标及挑战：将Q-Digest算法执行逻辑转化为MPC框架下的安全高效电路。
主要技术：
- 技术一：针对Q-Digest二叉树线性访问结构，通过标记位引入迁移节点，以ib#判断操作为例，从ib!迁移信息标记为1，原始ib!节点标记为0，避免搜索次数不确定问题。
- 技术二：基于差分隐私为本地聚合结果产生噪声，解决原始数据分布不同导致输出长度差异问题。Q-digest结构本地聚合长度理论最大值为3k，借助差分隐私大幅降低噪声总量，首次给出Q-Digest本地单次聚合敏感度为常数2，与universe和数据集大小无关。
- 技术三：设计输入检查机制，提升对恶意敌手的抵抗能力。通过观察真实数据集Q-Digest结构满足叶子节点和门限节点counter值大于门限值，重构原始数据集。
方案安全性分析：在real-ideal框架下证明协议安全性。
整体性能表现：
- 真实数据集表现：
  - 数据集1：WIDE project每日网络通信流量数据（2020年12月1日，49,282,099条TCP/IP数据包）。
  - 数据集2：Kosarak dataset（41,270个网页的8,019,015次点击操作记录）。
- 整体方案优越性：相比原始数据直接排序支持后续分位数询问，方案随数据规模增加，整体电路规模无明显增加。