使用阈值完全同型加密的多客户私人决策树分类

使用阈值完全同型加密的多客户私人决策树分类

背景 决策树是以其简单性和有效性而闻名的广泛使用的机器学习分类器。 最近的作品主要关注如何在两党设置中私下评估决策树，在该设置中，客户端的敏感数据或服务器的决策树模型与另一方保持秘密。 但是，越来越多地需要在相互信任的客户之间进行机器学习任务的协作。 在本文中，我们考虑了一个多用户的私人决策树分类协议，其中一台服务器持有决策树，并提供秘密数据。 在协议末尾，客户或服务器可以在保护每个单独输入的隐私时学习分类结果。 更重要的是，我们还将最大程度地减少与每个客户的互动。 为了达到目标，我们利用完全同态加密的阈值。 我们的协议被证明是针对“诚实但懒惰”的对手的安全性。 此外，我们尝试改善计算开销和密文的大小，从而使我们的构建效率更高。

机器学习分类算法可以在给出新数据作为查询时可以做出鉴定，该查询广泛适用，用于推荐系统，垃圾邮件过滤和疾病诊断等。 客户可能不想透露的信息。 敏感数据的泄漏，例如远程诊断中的健康记录，将是生死或死亡的问题。 另一方面，分类模型可能是服务器不愿共享的宝贵资产，因为专门的研究工作花费了大量资源。 此外，公开模型可能会泄露有关敏感培训数据的信息，甚至违反了法律法规。

理想情况下，隐私保护机器学习分类可以保护客户和模型所有者的隐私。 在本文中，我们关注决策树分类器，它以其简单、有效和低训练成本而闻名。 评估过程从作为树的第一个决策节点的根节点开始。 它将模型中特定于节点的阈值与客户端查询中的输入变量之一进行比较。 比较的布尔结果决定遍历哪个子节点。 该过程遍历每个级别并最终导致叶节点，将分类标签表示为树分类结果。 最近，已经提出了许多用于两方设置中决策树评估的有效隐私保护解决方案。 例如，Tai 等人。 提出了一种纯粹基于加法同态加密的私有决策树评估协议，没有引入用于隐藏树结构的虚拟节点，因此它适用于实践中丰富的稀疏树。 然而，在许多相关场景中，多个互不信任的客户端之间的协作变得司空见惯，因为它提供了更精确的分类。 例如，拥有一名患者不同健康记录的多家医院合作提供更好的疾病诊断，而这只有在每个个体输入的隐私得到保证的情况下才能实现。

多客户端私有决策树分类。 为了捕获上述示例性协作场景，我们提供了多客户端私有决策树分类协议，其中来自多个客户端的敏感输入变量可能会发送到服务器以进行协作分类。 具体来说，我们希望有一个3轮协议，多个客户端用第一轮消息初始化协议，然后服务器在本地进行节点评估和路径评估并发出第二轮消息，然后多个客户端和服务器 联合恢复分类标签作为评估结果。 安全性要求是服务端或多个客户端可以获知最终的分类结果，仅此而已。 本质上，服务器可以从收到的分类标签中导出客户端输入查询的相应树路径，因为它拥有树模型。 更重要的是，我们希望最小化客户端的成本，因为它们可能是弱物联网设备：（1）每个客户端的计算和通信成本都与树的大小无关； (2) 如果客户端对接收最终结果不感兴趣，或者可能失去连接从而无法继续协议，则允许客户端在第一轮之后下线，即所谓的“诚实但懒惰”的各方. 我们的建设概览。 受 3 轮多客户端私有决策树分类评估协议的启发，同时保持客户端的最小成本，我们使用低深度阈值完全同态加密（TFHE）。

其基本思想是：（1）每个客户端都对自己的秘密输入变量进行分量加密，然后服务器通过同态运算将加密后的客户端输入变量与自己的每个决策节点的加密阈值进行比较。 然后服务器将所有节点比较的加密结果位存储在其子节点中。 对于决策节点d ∈ D，让加密的比较位由Enc(b) ← Enc(xd.index ≥ d.threshold)给出，然后将Enc(b)存入右子节点，将Enc(1−b)存入 在左子节点。 为了在树中找到对应分类标签的正确遍历路径，需要考虑所有路径。 通过组合该路径上所有决策节点的比较位，可以安全地评估所有路径。 特别地，服务器可以同态乘以每条路径的比较位，只有正确的路径的加密值 l.cmp 等于 1，否则等于 0。相应的叶节点 l ∈ L 持有正确的分类标签 $l_{label}$。(2) 服务器通过加同态广播正确分类标签的加密Enc(l.cmp)·Enc(llabel). (3) 只要有阈值数量的客户端和服务器可用于发布部分解密（比如 n 中的 t），即使几个弱客户端已经离线，正确的分类标签也会显示出来。 此外，TFHE 方案的紧凑性确保了深度成比例的通信复杂度，与树的大小无关。

当然，上述基于TFHE的基本解决方案成功地降低了多个客户端的开销。 然而，服务器的计算开销太高而无法限制其在实践中的使用。 Tuneo 等人表明即使在两方设置中，也需要几秒钟的单次执行才能输出具有 50-500 个决策节点的树的分类结果。 众所周知，同态乘法比同态加法引起更大的噪声增长。 即，降低路径评估的乘法深度可以显着节省计算成本，也可以节省密文大小。 因此，我们转向 Tai 等人的路径评估方法，它只调用同态加法 。 具体来说，他们的方法将 Enc(1−b) 存储在右子节点，而 Enc(b) 存储在左子节点。 通过同态地添加该路径上所有节点的加密比较位来评估路径。 这个总和称为路径成本。 现在，只有当路径成本等于 0 时，相应的叶节点才拥有正确的分类标签。

与上述基本解决方案相反，为了正确输出最终的分类标签，我们让阈值参与方共同解密所有路径成本。 然后他们可以找到成本等于0的确切路径，并且可以通过将标签同态地添加到路径成本来发送相应叶节点的分类标签。 为了避免更多关于未选择路径和分类标签的信息被泄漏，将路径成本乘以随机非零元素 r0,r1。

值得注意的是，在我们的 n-1 个客户端和一个服务器场景中，由于我们假设某些客户端和服务器之间可能发生串通，因此必须独立和私密地选择两个随机非零值 r0，r1。 否则，r0 = 0 或 r1 = 0 将违反协议的正确性或服务器树模型的隐私。 最重要的是，r0 的泄露将直接泄露非选择路径成本，侵犯了客户端和服务器双方的隐私。 如果 r0 和 r1 不是独立选择的，则可能会显示未选择的分类标签。 因此，在我们的多客户端私有决策树分类协议中，我们要求 n 个客户端和服务器在第一轮通过广播其加密提供自己的贡献 rij，其中 i = 0, 1，使得 ri = ri1 + · · · + rn+1，假设这些方是半诚实的或依靠非交互式零知识证明来对抗恶意对手。 此外，我们仍然要求服务器对Tai文中引入的叶节点进行随机洗牌，以防止客户端了解输出叶节点在树中的位置。

对于阈值 FHE 解密，通过将 Shamir t-out-of-n 秘密共享应用于秘密密钥 sk，正如 Asharov 等人所指出的。需要每个解密器 i 为部分解密添加额外的模糊噪声，以防止有关她的秘密密钥共享 ski 的信息泄露。 令人惊讶的是，所有其它文献中使用了一种相对效率较低的方法，即每一方在广播之前向部分解密添加独立的噪声。 但是，此方法不适用于我们的案例。 在我们的重建过程中，当部分解密乘以拉格朗日系数时，这些噪声值被放大了 O((n!)2)。 为了解决这个问题，我们采用DovGordon的技术：让每个解密者I 将一些小噪声ei 秘密共享到(e1i , · · · , eni ) 中并将共享发送给其他各方。 然后每个解密器 I 在本地将 $\Sigma e_i$ 添加到其部分 jj 解密中。 由于 Shamir 秘密共享方案是线性的，这相当于将 e1 + · · · + en 添加到原始重构输出值，显着降低了噪声增长，从而提高了我们 TFHE 构造的整体性能。

两方私人决策树评估。 现有的两方私有决策树评估协议根据底层技术可分为三类，包括同态加密、乱码电路和秘密共享。

博斯特等人将决策树视为一个高次多项式，将分类结果作为输出，然后使用全同态加密（FHE）对其进行评估。 吴等通过添加虚拟节点来形成一个完整的二叉树来隐藏树结构，从而摆脱了 FHE。 但在很多实际情况下，决策树很深但很稀疏，将这样一棵树填充成完整的树会导致通信和计算上的巨大浪费。 泰等人没有引入虚拟节点来完成树转换，并提出了一种更有效的协议，其新概念是“路径成本”，通过纯加法同态加密来执行路径评估。 2018 年，Joye 和 Salehi 中的安全比较数量减少到 d-1，其中 d 是树深度，每个比较在每个树级别进行 2 轮。 因此，总轮数与 d 呈线性关系。该协议仍然需要服务器添加虚拟节点以隐藏树结构。 最近，Tueno 等人通过对在客户端公钥下同态加密的密文树进行评估，引入了一种非交互式决策树评估协议。

Tueno 等人通过将树表示为数组并使用乱码电路 (GC) 实现不经意的数组索引 (OAI)，提出了一种亚线性决策树协议。 早些时候，Brinckell 等人和巴尼等人提出了基于 GC 的隐私保护决策树评估解决方案，其性能优于上述方法。

Cock等提出了一种基于秘密共享的信息理论上安全的决策树评估协议，并利用基于商品的密码学 来减少交互次数。 对于特别小的树，他们的协议比所有其他协议执行得更好。 但是他们的协议对于大树来说效率较低，因为它在树的大小上仍然是线性的。 2019 年，Damgard 等人使用了一种新的基于秘密共享的协议，它在环而不是字段上工作，以显着提高实现效率，尽管通信成本略高。

阈值完全同态加密。 TFHE 方案允许对加密数据进行评估以及密文的阈值解密，其中密钥持有者的阈值数量必须聚集在一起才能解密任何密文。 2012 年，Asharov 等人使用 n-out-of-n 阈值解密程序扩展了Brakerski等人的 FHE 结构，以实现低通信（独立于正在计算的函数）、低交互和云辅助计算（大量计算）的多方计算 可以有效地外包给云服务）。 他们的协议是在公共随机字符串 (CRS) 模型中进行 3 轮交互，在可以重用设置时进行 2 轮交互。 通过假设非交互式零知识论证 (NIZKs) 存在，构造在（环）错误学习（LWE）假设下是安全的，可以抵御完全恶意的攻击者。

多密钥，FHE可以动态地将在一个密钥下加密的密文扩展为来自各方的密钥串联。 Lo ´pez-Alt 等人首先提出了一种基于 NTRU 假设的多密钥 FHE 方案。 Clear 和 McGoldrich介绍了一种基于 LWE 的结构。 2016 年，Mukherjee 和 Wichs通过显着简化的构造，在没有混淆的标准假设下，在 CRS 模型中提出了前两轮通用多方计算（MPC）协议。 这些方案对于密钥是单跳的，在计算开始之前必须知道参与方的列表。 同年，Peikert-Shiehian和 Brakershi-Pelman都试图解决这个问题。 陈等构建了一个多跳方案，它可以加密一个环元素，而不是一个比特。 不幸的是，以前的所有方案都是不切实际的，无法实施。 最近，陈等人提出了实现多跳多密钥 FHE 方案的首次尝试。

2018 年，Boneh 等人设计了一个名为通用阈值器的新原语，它由相对重的阈值完全同态加密（TFHE）构建，支持 t-out-of-n 阈值访问结构。 2020 年，Badrinarayanan 等人引入了称为阈值多键 FHE (TMFHE) 的新概念，以处理可以重建输出的任意访问模式。 然而，由于处理噪声放大的方法，上述两种方案是不切实际的。 特别是，Boneh 等人首先证明了 {0,1}-LSSS 类足以表达 t-out-of-n 阈值访问结构。 然后他们使用了一种不同的线性秘密共享方案，其中重建系数始终是二进制的，而不是与拉格朗日系数相乘。 但是从阈值访问结构到 {0, 1}-LSSS 的转换确实非常昂贵且不切实际。

决策树考虑多个客户端提供他们各自的输入变量，一个服务器提供树模型。 直观上，对输入查询 x 进行决策树分类意味着遍历决策树； 在每个决策节点，将相应的输入条目与节点特定的阈值进行比较。 根据比较结果，选择右子节点或左子节点作为下一个节点。 遍历在某个叶节点处结束，它告诉输入查询根据树的唯一分类标签。

设客户端I的输入xi为Z上的ki维正整数向量，则总输入查询为x = (x1,··· ,xn−1) ∈ Zk，其中k = k1 +···+ kn−1。 令 T 为决策树，包括一组决策节点 D 和一组叶节点 L。然后决策树对输入 x = (x1, · · · , xn−1) 的评估由 llabel = T (x ) 与 T : Zk → {l1label,··· ,lmlabel}，其中 m 为叶节点数。 该函数从根节点开始，然后在每个决策节点进行比较。 令 j 为决策节点的索引，f 为将决策节点索引 j 映射到相应输入条目的索引 f(j) 的函数。 此外，设 tj 为决策节点 j 的阈值。 然后如果 xf(j) ≥ tj 对于节点 j 成立，则选择右孩子作为下一个决策节点，否则选择左孩子节点。 最后，函数输出最终叶节点的分类标签llabel。

两个依赖于低深度阈值完全同态加密（TFHE）的高效多客户端私有决策树分类协议。

节点评估。 对于节点评估，需要相应的加密输入条目和加密节点特定阈值的逐位比较方法。 遵循 Tuneo 等人的想法和 Cheon 等人提出的安全比较协议。然后 Tuneo 等人将所有节点比较的加密结果存储在其子节点中。 具体地，对于决策节点d∈D，让加密的比较位结果由Enc(b)←Enc(xd.index≥d.threshold)给出，其中x是来自多个客户端的整个输入整数向量。 最后，他们将 Enc(b) 存储在右子节点，将 Enc(1−b) 存储在左子节点。

为了能够输出客户端输入向量的正确分类标签，遍历唯一正确的路径，应该考虑所有路径。 可以通过组合该路径上所有决策节点的存储比较位来评估每条路径。在两方设置中，Tueno 等人使用的想法是，通过同态乘以每条路径的这些比较位结果，只有正确的路径才会有一个等于 1 的加密值，否则为 0。相应的叶节点拥有正确的分类标签。

多客户端私有决策树分类。 在本节中，我们介绍了我们的多客户端私有决策树分类协议，以捕获多个客户端提供秘密数据并且单个服务器拥有决策树模型的场景。 特别地，我们要求至多服务器和客户端能够获得分类结果的知识，而仅了解其他方的个人输入。 我们的协议对“诚实但懒惰”的各方是安全的，允许多个客户在参与第一轮后下线。 显然，通过使用 [5] 中建议的 TFHE 技术，而不是在单个客户端的公钥下评估密文树，我们可以推广 [25] 中的构造以获得多客户端私有决策树分类方案。 但是，我们需要解决两个效率问题。 首先，正如 Tuneo 等人所指出的。 [25] 本身，服务器的计算开销仍然非常高，限制了它在实践中的使用。 为了减少整体计算开销，我们利用同态乘法比同态加密带来更多噪声增长的事实。 也就是说，我们需要一个低乘法深度树评估电路，以节省计算成本和密文大小。 然后我们转向由 Tai 等人 [24] 提出的称为“路径成本”的新概念。 通过结合 [25] 的节点评估和 [24] 的路径评估，我们提出了以下 Evaluation* 算法，如图 5 中所定义。

然后，为了保证最终分类结果的输出，我们让阈值的参与方通过 Evaluation* 共同解密所有返回的密文对。 在我们的 n-1 个客户端（n≥3）和单服务器应用程序场景中，某些客户端和服务器之间可能会发生串通，我们需要公平私密地生成这些随机值 {r0l,r1l}。 直观上，{r0l}的泄露会直接泄露其他路径开销，破坏客户端和服务端的隐私。 如果 {r0l,r1l} 被恶意选择，未选择的分类标签可能会被泄露，从而损害服务器树模型的隐私。 因此，我们让 n−1 个客户端和服务器提供他们的贡献 {ril,j}，其中 i ∈ {0, 1}，j ∈ [n]，在第一轮中对这些值 {r0l , r1l } 广播其相应的加密。

其次，对于支持 t-out-of-n 访问结构的阈值 FHE，[1,5] 中介绍的一般模糊噪声技术是不切实际的。 事实上，为了确保关于秘密密钥份额 sk1, · · · , skn 或私有输入 μ1, · · · , μl 的信息不会被部分解密 {pi}i∈S 泄露，它需要每个解密者添加独立的 在广播之前将部分解密弄脏。

然而，在我们的 t-out-of-n TFHE.FinDec 程序中，这些噪声值将乘以拉格朗日系数，放大 O((n!)2)。 为了解决这个问题，我们利用了[18]中的想法：让每一方 Pi secret 将一些小噪声 ei 分享到 (e1i , · · · , eni ) 并通过私有点对点将分享发送给另一方 通道（假设 PKI）。 然后每个解密器 Pi 在本地添加 }ei 到它的部分解密。

根据 Shamir 秘密共享方案的线性，这相当于将 e1 + · · · + en 添加到原始重构输出值。 通过使用上述方法，我们显着降低了评估密文的噪声，并进一步降低了我们 TFHE 构造的计算成本和密文大小。

总之，我们提高了底层一般 TFHE 结构的效率，支持 t-out-of-n 访问结构，以及树同态评估电路的乘法深度。 我们的多客户端私有决策树分类协议如图 6 所示。

然后以随机顺序发出上述评估密文对的集合，由 ctC 表示。

其中我们要求在每个部分解密 pj 中使用的额外模糊噪声是 ej1 + · · · + ejn，而不是独立选择的随机噪声。

对唯一等于0的costl输出对应的resultl，作为分类标签。

假设底层 TFHE 方案和我们的 Evaluation* 算法的评估正确性，则上述构造是一个多客户端私有决策树分类协议，输出正确的分类标签。

基于TFHE和Evaluation∗的正确性，costl等于0当且仅当l.cmp等于0，则对应的结果满足resultl = r1l × 0 + llabel = llabel。

安全性：假设底层 TFHE 方案的语义安全性和模拟安全性，使用我们的 Evaluation* 算法，那么上述构造是一个多客户端私有决策树分类协议，可以安全地对抗“诚实但懒惰”的对手。

通过底层 TFHE 方案的语义安全性和模拟安全性，敌手 A 可以从协议执行中获得的唯一信息是 {(costl,resultl)}l∈L，仅此而已其他诚实方密钥共享或 输入。 根据 Evaluation* 算法，每个 (costl, resultl) 等于 (r0l × l.cmp, r1l × l.cmp + llabel)，其中 r0l 和 r1l 是完全未知的，并且对每一方都是随机的。 那么每一方可以从集合{(r0l × l.cmp, r1l × l.cmp + llabel )}中得到的唯一信息是(0,llabel)，即第一个元素等于0的分量和 相应的第二个组件。 此外，由于加密密文对 {Enc(costl),Enc(resultl)}l∈L 由服务器按照图 6 中第 3 行的要求随机打乱，客户端无法获知输出叶的位置 服务器决策树中的节点。