Squirrel 用于训练的可扩展安全计算框架

Squirrel：用于培训GBDT的可扩展安全计算框架 卢文杰，黄智聪，张启智，王玉晨，程红 C本体 目录 背景梯度提升 MPC工具松鼠 决策树介绍框架要点 GBDT 1(X 1<20) 背景：决策树 •构建最接近Y的分支模型F(X) •(简单的二元分类) ID X1(Age) X2(Use计算机日报) Y(喜欢电脑游戏) 6 Y 1 12 N -1 30 Y 1 65 N -1 70 N -1 F(X)= -1(X 1≥20) X(属性) Y(标签) 例如，深度=1的决策树 77 引用：https://xgboost.readthedocs.io/en/stable/tutorials/mod 背景：梯度提升决策树 •训练许多决策树 •最终预测=所有预测的总和 •使用“提升”技术 •提升就像“纠错”•Nth树试图“纠正”先前N-1个树所做的预测。 模型：有人喜欢电脑游戏吗？ 1st树误以为喜欢电脑游戏；2nd树纠正它。 8 引用：https://xgboost.readthedocs.io/en/stable/tutorials/mod GBDT大楼 •计算1stand2nd每棵树上每个样本的梯度(gi,hi) •对于所有候选拆分点： •找到最大化的最佳点 &&& %% g3,h3 g4,h4,g5,h5 Gain= •在实践中，数据通常%是有序!和"#$存'%(储)$的 +− %%% !"#$'%()$ Age≤2020<Age<60Age≥60 例如，检查2个候选人，而不是4个 9 引用：https://xgboost.readthedocs.io/en/stable/tutorials/mod GBDT很好 •高精度 •由Kaggle的许多获奖者使用 •Interpretability •客户经常要求解释，例如：为什么我的帐户被阻止？ •Severalvariables •XGBoost/LightGBM... 10 02通过MPC保护GBDT Goal: 在垂直分割数据集上的协作 ID Yearly费用 Yearlyincome 汽车保险 每年提出的索赔 医院访问 每年 标签 爱丽丝 $50,000 $150,000 1 3 y0 Bob $35,000 $90,000 2 1 y1 凯茜 $45,000 $70,000 3 3 y2 大卫 $72,000 $300,000 2 4 y3 保险公司B知道这个分布在A/B对齐ID(例如通过PSI)银行 •假设有人想从A申请贷款 •常规：A使用基于本地数据的信用模型•但A可以在B的帮助下做出更好的决策 12 隐私要求 •半诚实two方计算 •除了最终模型之外的任何东西都不应该被揭示 •最终模型的一部分：阈值为“年龄<20” • NOT最终模型部分:属于左树节点 •属性“年龄”的所有者知道•但另一方不应该知道•在实践中，一个秘密指示器向量V是 i 用于保持样本分发的私有 ? ? V1=[1,1,0,0,0] V2=[0,0,1,1,1] 没有“年龄”栏的一方不知道V或V 12 13 挑战 •直接共享数据可能不是一种选择 •L 损害用户隐私 •使用MPC的隐私保护GBDT培训很有前途 •为什么不联合学习？=>我们希望最小的信息泄漏 •高效的MPCGDBT对数以百万计的样品是困难的 •更快的计算•更轻的通信 14 相关工程 •基于联邦学习 •安全升压[1]和VFboost[2]•L泄漏样品分布L 在清除中计算增益 •基于安全多方计算 •HEP-SGB[3]和枢轴[4]•私人指标向量 □ •计算MPC中✁增益 □ •L 繁重✁计算和通信 [1]成凯,范涛,金宇,等.SecureBoost：无损联邦学习框架[J].IEEE智能系统,2021[2]孙锋,邵宇,于乐,等.Vf2Boost：快速垂直联邦梯度提升算法在跨企业学习中✁应用,SIGMOD2021[3]方文,赵栋,田嘉,等.大规模安全XGB在垂直联邦学习中✁应用,CIKM2021[4]吴宇,蔡爽,许晓,等.基于树模型✁隐私保护垂直联邦学习,VLDB2020 15 03MPC工具 ASS&LHE •AdditiveSecreteSharing •信息/数据是随机分割✁+=%□e.g.,p=2^64 !" •对许多（非线性）函数（例如，Div、ArgMax和Sqrt）制定了协议。 •需要多轮交互，即往返时间敏感。 •线性同态加密 •Enc(x;pk)+Enc(y;pk)=>C如果Dec(C;sk)可以给出x+y%N •例如，Paillier或BFVHE方案•(通常)计算密集型•但是，评估非线性函数效率低下 17 混合原语评估 •将ASS用于非线性函数 •SwitchtoLHEforalowercommunication •è A2H:Enc(x0;pk0)Enc(x0;pk0)+x1=Enc(x;pk0)•çH2A:12月(C;sk0)=m-rEnc(m;pk0)+r •为什么基于格子✁LHE(例如BFV)而不是Paillier或其他 •“安全性”：明文空间BFV_N=p(例如2^64)vsPailler_N>>p•性能：BFVenc〜每秒10^6vsPailler〜每秒10^3enc 18 蚂蚁集团中✁隐私增强技术(PETs) •目标：安全✁数据协作 •反洗钱，客户潜在价值...•主要是统计/机器学习任务 •External •如蚂蚁金服vs江苏银行、蚂蚁金服vs浦发银行... •内部 •不同✁子公司可能有不同✁隐私政策•例如支付宝vsAntchain •Service •银行A和银行B购买蚂蚁金服✁PETs产品进行合作 19 A2H/H2A使用Paillier可能存在✁陷阱 •主要原因：LHE明文空间和ASS空间不匹配 •例如，Paillier在[0，N)中处理大INT，而在[0，2^[64]中处理ASS域 ) •陷阱可能发生在链A2H->LHEEval->H2A •A2H：Enc(x0)+x1给出Enc(x0+x1％N)，但不是精确✁x •x0+x1=x或x0+x1=x+2^[64](根据ASS✁定义) •LHEEval将携带可能✁值2^[64] •H2A:Enc(m+c*2^[64]+r) •如果随机掩码r<<c*2^[64];它泄漏了一些关于评估，例如，进行了一些很多总结。 •WhataboutLHEsuchasECC-ElgmalorDGK?Inefficientfor64-bitplaintext 20 03松鼠 GBDT安全管道 •步骤1:PSI ID Age 8 12346770 ID 高度 5ft 5.2ft 6ft 5.4ft6.2ft A公司持有B公司持有 22 GBDT安全管道 •步骤2：数据编码(即Binning) ID Age ≤20 20<Age≤60 Age >60 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 ID 高度≤4ft 4ft<高度≤6ft 高度>6ft 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 A公司持有B公司持有 23 GBDT安全管道 •步骤3：使用(秘密共享)梯度表存储梯度g，h ID g h 0.2 0.1 0.1 0.7 0.7 0.2 0.4 0.5 0.6 0.3 对于我tht中✁样本thtree: g=P-y iii h=P(1-P ) //P表示以前✁t-1树i✁ii预测 i 样本i:□□ ∑ A公司和B公司之间✁添加剂共享 P=乙状结肠□□□□_□□□□ □□□(□) □□ i 24 步骤3：计算聚合梯度 非常耗时： •秘密共享形式到同态形式(A2H)•矩阵和二进制向量之间✁乘法(BinMatVec) •选择非零位置并求和 Age ≤20 20<Age≤60 Age >60 G 0.3 0.7 1 H 0.8 0.2 0.8 ID g h 0.2 0.1 0.1 0.7 0.7 0.2 0.4 0.5 0.6 0.3 渐变表(在A✁密钥下加密) ID Age ≤20 20<Age ≤60 Age >60 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 Data （由鲍勃明确持有) 27 聚合梯度表(在Alice✁密钥下加密) 步骤1到3与[3,4]没有什么不同，除了... •如何有效地进行A2H和BinMatVec •L O(n)Paillier操作将✁禁止✁•使用SIMDHE(BFV /BGV)? •L •解p决ick方-th案en：-sum对需R要L昂W贵E✁旋系转数中✁梯度进行编码 •采摘系数很容易：给定RLWE(m)=(b，a)->LWE(m[k])=(b[k]，a'） //a'=(a[k],a[k-1],...a[0],-a[N-1],-a[N-2],...-a[k+1]) g 2174 •速度高达1,000倍✁BinMatVec BFV密文 需要1个旋转 求和2和7 RLWE密文 2x3+x2+7x+4 ->直接选择2和7然后求和 28 在秘密共享和HE加密之间切换 Age ≤20 20<Age ≤60 Age >60 G 0.3 0.7 1 H 0.8 0.2 0.8 •在BinMatVec之后，B获得了LWE加密表G/H 在Alice✁密钥下加密 •下一步✁计算最大值 •在FHE中很难做到;在MPC中更方便 •使用H2A切换到秘密共享表单进行MPC操作 •在H2A之前将LWE打包到RLWE中以节省通信[5]•密文大小从GB减少到MB [5]郝晨,戴伟,米兰,宋永秀.(环)LWE密文之间✁高效同态转换.ACNS2021.29 步骤4：计算最大增益 #$i& •Findmax(即ArgMax) & #𝐿𝑒ƒ�$i+ & #𝑅i𝑔)�$i− 𝑟&#𝐿𝑒ƒ�'i 𝑟&#𝑅i𝑔)�'i 𝑟&#'i •使用基于一般秘密共享✁MPC(GMW) •安全分区\安全argmax...•但用Ferret-OTs代替OT[6] •保存一些通信 [6]YangK,WengC,LanX,etal.Ferret:FastextensionforcorrelatedOTwithsmallcommunication,CCS2020 30 V=[1,1,1,1,1]0 步骤5：拆分树节点 •每个树节点都有一个指示向量 •开始于V=[1,1,1,1,1] 0 •“Age”(Alice)✁所有者更新了V和V✁股份 12 12•VandV✁“AND-shared” •Bob不清楚V •双i方更新梯度表 私人乘以V i V=[1,1,0,0,0]1V=[0,0,1,1,1]2 31 •重复执行步骤1-5 •可能✁深度优先或宽度优先，取决于要求•直到达到最大深度 •然后训练新树(具有新✁渐变) •计算新✁梯度需要Sigmoid •问题：私人计算sigmoid •L 乱码电路：高通信•L 浮点幂运算：太多回合•L分段线性函数：精度损失 32 新✁Sigmoid协议 由A持有由B持有 •考虑≤2✁傅立叶级数 •Since •2*J私有乘法(使用HE)就足够了 •完整✁Sigmoid方案: •更精确和更少✁沟通 33 实验结果 •28-40x加速比枢轴(VLDB20)•3-4x加速比HEP-XGB(CIKM21) •他们使用TEE来生成乘法三元组 34 实验结果 •每棵树100+秒 •WAN(200mbps/20ms)，100万行*10功能，树深度=5 35 结论: •RLWE-LWE快速梯度聚合 灵感来自我们以前✁工作 PEGASUS[7] •LWE-RLWE减少通信 •用于跟踪分割信息✁“AND-shared”指示向量•平滑且