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

演讲人：兰晓四川大学助理研究员 目录Contents MPC基本概念 01 MPC基本概念 概念如何被提出 •1982年，图灵奖获得者姚期智先生提出了百万富翁问题 •两个争强好胜的富翁Alice和Bob在街头相遇，想在不暴露各自财富的前提下比较出谁更富有？ 概念如何被提出 •形式化定义 •有n个参与者P1，P2，…，Pn，要以一种安全的方式共同计算一个函数，这里的安全是指输出结果的正确性和输入信息、输出信息的保密性。具体地讲，每个参与者P1，有一个自己的保密输入信息X1，n个参与者要共同计算一个函数f(X1,X2, … ,Xn)=(Y1,Y2, … ,Yn)，计算结束时，每个参与者Pi只能了解Yi，不能了解其他方的任何信息。 •特点 •输入隐私性，计算正确性，去中心化 概念如何被提出 •类似的场景 概念如何被提出 •关注的问题 安全多方计算关注多个数据所有者在互不信任的情况下进行协同计算时计算的安全和数据的隐私 概念如何被提出 •发展进程 初始阶段：•[Yao82]百万富翁问题 理论问题研究阶段：•[BMR90]多方混淆电路 •[Yao86, GMW87]混淆电路、加法秘密分享 MPC协议高效实现与应用阶段：•[MNPS04]首个百万富翁问题的MPC实现 可行性论证阶段：•[BGW88，CCD88，RB89]诚实大多数MPC协议 02 MPC主要技术 混淆电路技术 •计算模型 •布尔电路：由逻辑门（XOR、AND）组成的电路 •技术核心 •Alice为每个门选择2个随机数，分别对应0和1 •Alice将电路以门为单位，把真值表转换为加密状态，并将加密电路及自己输入对应的随机数发送给Bob •Alice和Bob执行不经意传输协议，帮助Bob获得与其输入对应的随机数 •Bob根据收到的加密电路、与Alice输入对应的随机数，以及通过不经意传输协议得到的与Bob输入对应的随机数，逐层计算电路，获得输出 混淆电路技术 线性秘密分享技术 •计算模型 •布尔电路：由逻辑门（XOR、AND）组成的电路•算术电路：由算术门（ADD、MULT）组成的电路 •技术核心 •参与计算的每一方对于自己输入的每个比特进行分享，保证电路每一个输入均以秘密分享的形式进行计算•ADD门可以通过所有参与方本地计算每个门的分享得到对输出的分享•MULT门额外通过运行不经意传输协议，构建对输出的加性分享 •代表性协议 •GMW协议（加法秘密分享）•BGW协议（Shamir秘密分享）•SPDZ协议 03 Q-Digest算法 Q-Digest算法 •数据统计分析领域的著名算法 •分位数近似算法 •确定性算法•基于树状结构•支持处理流式数据•可用于大规模传感器网络 •性能表现 •算法输出长度为𝑚的情况下回答分位数询问的错误率为Ο(log𝜎/𝑚)(𝜎代表universesize)•单个节点最大通信量为3𝑘(𝑘代表compressionparameter) •优势 •支持多次聚合 Q-Digest算法 •原始数据计算过程 •Digestproperty1：count(𝑣)≤𝑛/𝑘•Digestproperty2：count𝑣+𝑐𝑜𝑢𝑛𝑡𝑣!+𝑐𝑜𝑢𝑛𝑡𝑣">𝑛/𝑘•以数据集大小𝑛=15，压缩因子𝑘=5，数据集元素类别（universe）𝜎=8为例的算法执行过程如a-d所示 Q-Digest算法 •询问回答过程 •𝐿=<1,1>,<6,2>,<7,2>,<10,4>,<11,6>•将𝐿按区间右端点大小+区间总大小重排序为<10,4>,<11,6>,<6,2>,<7,2>,<1,1>•按新序例计算count值之和，大于等于所求位次则为回答•如中位数询问0.5𝑛=15∗0.5=7.5，因为4+6>7.5，故11为回答 04分布式安全聚合 目标及挑战 •如何将现有Q-Digest算法的执行逻辑转化成可在MPC框架下安全执行的电路（安全+高效） •主要挑战 主要技术一 •针对Q-Digest算法二叉树数据结构的线性访问结构•一个具体的例子 主要技术一 •针对Q-Digest算法二叉树数据结构的线性访问结构 •通过为每个节点设置一个标记位，引入迁移节点的概念，以𝑖𝑑#的判断操作为例：•从𝑖𝑑!迁移来的信息标记为1，而原始𝑖𝑑!节点的信息标记为0•整个判断过程只需要判断相邻数据•避免了由于数据不同导致的搜索次数不确定问题id$ 主要技术二 •基于差分隐私技术为本地的聚合结果产生噪声 •存在因原始数据分布不同输出长度差异的问题•以𝑛=50,𝑘=6为例，则𝑛/𝑘=50/6=8•因此长度信息需要隐藏 主要技术二 •基于差分隐私技术为本地的聚合结果产生噪声 •Q-digest结构的本地聚合长度理论最大值为3𝑘（LEMMA1 ofQ-Digestpaper） •直接隐藏噪声太大•借助差分隐私能够大幅度降低噪声总量•我们首次给出Q-Digest本地单次聚合长度的敏感度为常数2•与universe独立•与数据集大小独立 •基于我们证明的常数级敏感度，在TruncatedLaplace机制下可计算在不同隐私预算下的噪声值 主要技术三 •设计输入检查机制，提升对恶意敌手的抵抗能力 •恶意敌手通过输入特殊构造的不合法输入，有可能推测诚实参与者的输入 •我们发现，对于真实数据集计算的Q-Digest结构，一定满足以下条件 叶子节点counter值一定大于门限值 非叶子节点counter值一定大于门限值 •基于上述观察，我们设计了Q-Digest算法输入合法性检查机制•并能够重构出与Q-Digest结构吻合的原始数据集 方案安全性分析 •在real-ideal框架下证明了协议的安全性 •real-ideal框架：即证明对于真实世界的敌手，总是能够模拟出理想世界的敌手，使得所有参与者的view连同函数输出在两个世界中的分布是计算不可区分的 整体性能表现 整体性能表现 •在真实数据集上的表现 •数据集1:WIDEproject的每日网络通信流量数据2020年12月1日当天的总数据（包含完整TCP/IP数据包49,282, 099条） •数据集2:Kosarakdataset（包含对41,270个网页的8,019,015次点击操作记录） 整体性能表现 •整体方案的优越性 •与用原始数据直接排序以支持后续分位数询问的做法相比，我们的方案随着数据规模增加，整体电路规模无明显增加 更多细节。。 •Xiao Lan,HongjianJin, Hui Guo and Xiao Wang, Efficient and Secure QuantileAggregation of Private Data Streams, IEEE Transactions on Information Forensicsand Security, vol. 18, pp. 3058-3073, 2023,doi: 10.1109/TIFS.2023.3272775 这一领域还有许多工作有待深入，欢迎对这一领域感兴趣的同行多多交流合作！ —THANKS— 感谢您的观看