关于两方安全计算的决策树分类这件事

关于两方安全计算的决策树分类这件事

安全多方计算（或 MPC）允许两方或多方计算私有输入上的任何数学函数，而不会透露函数输出以外的任何内容。 通常，MPC 在预处理模型中实例化，在离线输入独立阶段从受信任的经销商或通过离线交互生成特制的随机数，然后在在线阶段使用此随机数来计算函数，一旦 输入是已知的。 这种两阶段方法产生了可观的性能优势。 这种相关随机性的一些示例包括 Beaver 乘法三元组和乱码电路预处理 。 当用于评估仅基于二进制或仅基于算术交互的电路时，MPC 协议提供非常快速的在线执行。 但是，生物识别或机器学习等应用程序需要线性运算（在大环上进行加法和乘法）和整数比较或截断等非线性运算的组合。 仅使用一种 MPC 电路类型盲目地实现这两种类型的操作的成本可能高得令人望而却步。 为了解决这个问题，许多工作已经解决了混合模式 MPC，以提供算术域和二进制域之间的有效转换，支持线性和非线性运算。 然而，这些转换通常会在在线阶段带来巨大的通信开销。 根据 TinyTable 协议以简洁的方式秘密共享真值表，Boyle 等人提出了一种基于功能秘密共享 (FSS)的非常有前途的方法。 为非线性函数评估提供与纯算术电路中的纯算术计算相同的在线通信和轮复杂度，FSS 依赖于快速对称加密原语来产生快速在线评估。

秘密共享是一种密码学原语，它允许在 𝑛 方之间共享秘密 𝑥，这样其中的任何 𝑡 都可以重建秘密。 秘密共享方案由 𝑘 各方数和阈值 𝑡 定义，即重建秘密所需的最小各方数。 在两方计算 (2PC) 领域，参与方数为 𝑛 = 2，阈值为 𝑡 = 2。这项工作着重于环中的 2PC 算术秘密共享（为方便起见简称为 SS），其中一个秘密值 𝑥 被分成两个随机份额𝑥0 和𝑥1 使得𝑥 =𝑥0+𝑥1 模数𝑁，其中𝑁 是环的大小。份额被分配给两个计算方，使得一方𝑃 𝑗 收到份额𝑥 𝑗。 通过这种共享方案，双方可以对两个秘密共享值进行本地加/减。 此外，各方可以求助于 Beaver 的乘法三元组以一轮通信为代价执行乘法：

在计算结束时，可以通过将两个份额发送给选定方𝑃𝑟𝑒𝑠，将两个份额加在一起并重建结果来重建得到的秘密共享值。 我们使用 𝑁 =2𝑛 来获取 𝑛∈{8,16,32,64} 的值，以便在处理 𝑛 位模块化算术时受益于现代计算机中存在的本机整数类型的相当大的加速。 对于这项工作特别感兴趣的是，使用 SS 计算标量积 𝒙𝑇𝒚 = scular 𝑙 𝒙(𝑖) ·𝒚(𝑖) 需要为每个多 𝑖=1 次重复发送 2 个项，总共发送 2𝑙 值。