CN113098687B - 生成安全计算协议的数据元组的方法及装置 - Google Patents

Abstract

本说明书实施例提供一种生成安全计算协议的数据元组的方法和装置，方法包括：第一方生成第一随机数；第二方生成稀疏的第一噪声向量，其中的t个非零噪声点形成t维的第二噪声向量。然后，双方通过秘密分享，分别得到第一随机数与第二噪声向量的乘积向量的两个分片。接着，第一方构建t棵完整树，第二方对应构建t棵刺穿树；其中第j棵刺穿树中的一个刺穿叶节点的计算值与完整树中对应节点的计算值之和，等于乘积向量的第j个元素；非刺穿叶节点的计算值与完整树中对应节点的计算值之和为零。于是第一方和第二方，可以分别基于t棵完整树/刺穿树的一侧叶节点，形成分片向量；并分别基于其分片向量，形成安全计算协议的数据元组。

Description

生成安全计算协议的数据元组的方法及装置

技术领域

本说明书一个或多个实施例涉及数据隐私安全领域，尤其涉及生成安全计算协议的数据元组的方法和装置。

背景技术

随着计算机技术的发展，机器学习已经应用到各种各样的技术领域，用于分析、处理各种业务数据。机器学习所需要的数据往往会涉及到多个领域，例如在基于机器学习的商户分类分析场景中，电子支付平台拥有商户的交易流水数据，电子商务平台存储有商户的销售数据，银行机构拥有商户的借贷数据。数据往往以孤岛的形式存在。由于行业竞争、数据安全、用户隐私等问题，数据整合面临着很大阻力，将分散在各个平台的数据整合在一起进行机器学习模型的训练难以实现。因此，提出多方联合训练和使用机器学习模型进行业务处理的方式。

在多方联合训练和使用机器学习模型的场景下，数据隐私的保护和安全性成为值得关注的问题。例如，在一个多方计算的场景下，A方持有待处理的用户样本特征数据形成的特征矩阵，B方持有数据处理模型的模型参数形成的参数矩阵。为了各方隐私数据安全，A方和B方需要在不暴露各自矩阵数据的情况下，实现安全的矩阵相乘。在其他多方计算场景下，还存在其他的安全运算需求。

为了在多方计算过程中保护各方数据隐私，提出了多种安全计算协议，适用于不同的安全计算场景。多数安全计算协议都需要预先生成数据元组，以便在计算过程中使用。

因此，希望提供改进的方案，更加高效更加安全地生成安全计算协议的数据元组，从而提高多方计算的效率和安全性。

发明内容

本说明书一个或多个实施例描述了一种双方联合生成安全计算协议的数据元组的方法和装置，可以更加高效更加安全地生成用于安全计算协议的数据元组。

根据第一方面，提供了一种生成安全计算协议的数据元组的方法，包括：

第一方生成第一随机数；

第二方随机生成稀疏的第一噪声向量，该第一噪声向量中包含的t个非零噪声点形成t维的第二噪声向量；

第一方和第二方通过秘密分享，分别得到第一中间向量的第一分片和第二分片，所述第一中间向量对应于第一随机数与第二噪声向量的乘积；

第一方构建t棵完整树，第二方和第一方进行安全交互，从而对应构建t棵刺穿树；其中任意第j棵刺穿树包括位于第一侧的第一刺穿叶节点，该第一刺穿叶节点的计算值与第j棵完整树中对应节点的计算值之和，等于第一中间向量的第j个元素；该第j棵刺穿树中各个非刺穿叶节点的计算值，与第j棵完整树中对应节点的计算值之和为零；

第一方和第二方，分别基于所述t棵完整树和所述t棵刺穿树的第一侧叶节点的计算值，形成第一分片向量和第二分片向量；

第一方和第二方，分别基于所述第一分片向量和第二分片向量，形成安全计算协议的数据元组。

根据一种可能的实施方式，上述方法还包括：

第一方还生成第二随机数；

第一方和第二方通过所述秘密分享，还分别得到第二中间向量的第一分片和第二分片，其中该第二中间向量对应于所述第二随机数与第二噪声向量的乘积；

其中，所述第j棵刺穿树还包括位于第二侧的第二刺穿叶节点，该第二刺穿叶节点的计算值与第j棵完整树中对应节点的计算值之和，等于第二中间向量的第j个元素。

基于上述实施方式，在一个实施例中，所述方法还包括：

第二方选择挑战数组，并将其发送给第一方；第一方根据所述挑战数组，所述第一随机数和第二随机数，以及所述t棵完整树的全部叶节点的计算值，计算响应值，并将其发送给第二方；第二方根据所述第二噪声向量，以及所述t棵刺穿树的全部叶节点的计算值，验证所述响应值是否符合预期；所述形成安全计算协议的数据元组，包括：在第二方验证所述响应值正确的情况下，第一方和第二方分别形成所述数据元组。

进一步的，在一个示例中，所述挑战数组包括第一挑战数和第一数组；所述计算响应值包括：第一方根据所述第一挑战数，对所述第一随机数和第二随机数执行第一运算，得到第一响应值；并根据所述第一数组，对所述t棵完整树的全部叶节点的计算值进行第二运算，得到第二响应值；所述验证所述响应值是否正确，包括：根据所述第二噪声向量，对所述第一响应值进行进一步运算，得到第一验证值；在所述第二响应值基础上，叠加对所述t棵刺穿树的全部叶节点的计算值进行所述第二运算的结果，得到第二验证值；判断该第一验证值和第二验证值是否相等。

根据一种实施方式，所述安全计算协议为伪随机VOLE协议；所述形成安全计算协议的数据元组，包括：第一方基于所述第一分片向量和预设的压缩矩阵，确定第一伪随机向量；第二方基于所述第一噪声向量和所述压缩矩阵，确定第二伪随机向量；并基于所述第二分片向量和所述压缩矩阵，确定第三伪随机向量；其中，第二伪随机向量与所述第一随机数的乘积，叠加上第三伪随机向量的结果，等于所述第一伪随机向量。

根据第二方面，提供了一种生成安全计算协议的数据元组的方法，通过第一方执行，包括：

生成第一随机数；

与第二方执行秘密分享，得到第一中间向量的第一分片，对应的第二分片由第二方持有，其中所述第一中间向量对应于第一随机数与第二噪声向量的乘积，该第二噪声向量由第二方随机生成的稀疏的第一噪声向量中包含的t个非零噪声点形成；

构建t棵完整树；

与第二方进行安全交互，辅助其构建t棵刺穿树；其中任意第j棵刺穿树包括位于第一侧的第一刺穿叶节点，该第一刺穿叶节点的计算值与第j棵完整树中对应节点的计算值之和，等于第一中间向量的第j个元素；该第j棵刺穿树中各个非刺穿叶节点的计算值，与第j棵完整树中对应节点的计算值之和为零；

基于所述t棵完整树第一侧叶节点的计算值，形成第一分片向量；

基于所述第一分片向量，形成安全计算协议的数据元组的一部分，该数据元组的另一部分基于第二方持有的第二分片向量形成，所述第二分片向量基于所述t棵刺穿树第一侧叶节点的计算值形成。

在一个实施例中，构建t棵完整树，包括：

根据约定方式，将第一噪声向量的维度划分为t个区间，使得每个区间包含一个非零噪声点；生成第j个树形结构，该树形结构在倒数第二层包括N个节点，其中N为第j个区间的元素数目；从根节点开始到所述倒数第二层，利用第一伪随机生成算法，根据父节点的计算值确定两个子节点的计算值；利用第二伪随机生成算法，根据倒数第二层各个节点的计算值，确定最后一层N对叶节点的计算值，从而得到第j棵完整树。

在一个可能的实施例中，与第二方进行安全交互，辅助其构建t棵刺穿树，具体包括：

对于第j棵完整树，通过与第二方执行不经意传输OT协议，使得第二方恢复出对应树形结构的各个层中除刺穿节点之外的节点的计算值；基于所述第一分片和所述第j棵完整树的叶节点的计算值，确定混淆值，将其发送给第二方，以使得第二方基于所述混淆值，所述第二分片，以及所述树形结构中恢复出的计算值，确定该树形结构中各个叶节点的最终计算值，从而得到第j棵刺穿树。

进一步的，在一个例子中，通过与第二方执行不经意传输OT协议，使得第二方恢复出对应树形结构的各个层中除刺穿节点之外的节点的计算值，包括：

对于第j棵完整树的各个中间层，计算第一取值和第二取值，其中第一取值为该中间层所有左侧节点的计算值的异或值，第二取值为该中间层所有右侧节点的计算值的异或值；与第二方执行OT协议，使得第二方根据该中间层中的刺穿节点的位置选择第一取值和第二取值之一，并根据选择的取值恢复出该中间层中除刺穿节点之外的节点计算值。

根据第三方面，提供了一种生成安全计算协议的数据元组的方法，通过第二方执行，包括：

随机生成稀疏的第一噪声向量，该第一噪声向量中包含的t个非零噪声点形成t维的第二噪声向量；

与第一方执行秘密分享，得到第一中间向量的第二分片，对应的第一分片由第一方持有，其中所述第一中间向量对应于第一方生成的第一随机数与所述第二噪声向量的乘积；

与第一方进行安全交互，从而基于第一方构建的t棵完整树，对应构建t棵刺穿树；其中任意第j棵刺穿树包括位于第一侧的第一刺穿叶节点，该第一刺穿叶节点的计算值与第j棵完整树中对应节点的计算值之和，等于第一中间向量的第j个元素；该第j棵刺穿树中各个非刺穿叶节点的计算值，与第j棵完整树中对应节点的计算值之和为零；

基于所述t棵刺穿树第一侧叶节点的计算值，形成第二分片向量；

基于所述第二分片向量，形成安全计算协议的数据元组的一部分，该数据元组的另一部分基于第一方持有的第一分片向量形成，所述第一分片向量基于所述t棵完整树第一侧叶节点的计算值形成。

根据一种实施方式，对应构建t棵刺穿树，具体包括：

生成第j个树形结构，并根据第j个非零噪声点在第一噪声向量中的全局位置，确定该树形结构的各个层中的刺穿节点；通过与第一方执行不经意传输OT协议，针对各个层中除刺穿节点之外的节点，恢复出与第j棵完整树对应节点相同的计算值；从第一方接收混淆值，该混淆值基于第一方持有的所述第一分片和所述第j棵完整树的叶节点的计算值确定；基于所述混淆值，所述第二分片，以及所述树形结构中恢复出的计算值，确定该树形结构中各个叶节点的最终计算值，从而得到第j棵刺穿树。

进一步的，在上述实施方式的一个可能实施例中，生成第j个树形结构，并确定该树形结构的各个层中的刺穿节点，具体包括：

根据约定方式，将第一噪声向量的维度划分为t个区间，使得每个区间包含一个非零噪声点；确定第j个树形结构，该树形结构在倒数第二层包括N个节点，其中N为第j个区间的元素数目；根据所述全局位置，以及所述t个区间的划分，确定所述第j个非零噪声点在所述第j个区间的相对位置；根据所述相对位置确定刺穿路径，该刺穿路径沿父子节点关系连接各个中间层的刺穿节点，其中倒数第二层的N个节点中位于所述相对位置的目标节点作为该倒数第二层的刺穿节点，该目标节点的一对子节点作为叶节点层的一对刺穿叶节点。

在上述实施方式的一个可能实施例中，恢复出与第j棵完整树对应节点相同的计算值，具体包括：

对于各个中间层中除刺穿节点和与该刺穿节点共享同一父节点的配对节点之外的其余节点，利用第一伪随机生成算法，根据父节点的计算值确定所述其余节点的计算值；与第一方执行OT协议，根据所述配对节点位于第一侧或第二侧的指示值，从第一方提供的第一取值和第二取值中选择其中之一作为目标取值，其中第一取值为第j棵完整树中该中间层所有第一侧节点的计算值的异或值，第二取值为第j棵完整树中该中间层所有第二侧节点的计算值的异或值；根据所述目标取值，和与所述配对节点位于同一侧的节点的计算值，恢复得到所述配对节点的计算值；利用第二伪随机生成算法，根据倒数第二层中除刺穿节点之外的各个节点的计算值，恢复出最后一层除一对刺穿叶节点之外的其余叶节点的计算值。

在上述实施方式的一个可能实施例中，接收的混淆值包括第一混淆值，该第一混淆值基于所述第一分片和所述第j棵完整树的第一侧叶节点的计算值确定；所述确定该树形结构中各个叶节点的最终计算值，具体包括：

基于所述第一混淆值，所述第二分片，以及除第一刺穿叶节点之外的第一侧叶节点的恢复计算值，得到第一目标值，使得该第一目标值与所述第一刺穿叶节点在第j棵完整树中的对应节点的计算值之和，等于所述第一中间向量的第j个元素；将所述第一目标值确定为所述第一刺穿叶节点的最终计算值；将除所述一对刺穿叶节点之外的其余叶节点的最终计算值确定为其恢复计算值的相反数。

通过执行所述秘密分享，得到第二中间向量的第二分片，对应的第一分片由第一方持有；其中该第二中间向量对应于第一方生成的第二随机数与所述第二噪声向量的乘积；

其中，所述第j棵刺穿树中，该对刺穿叶节点中位于第二侧的第二刺穿叶节点的计算值与第j棵完整树中对应节点的计算值之和，等于第二中间向量的第j个元素。

根据一种实施方式，所述方法还包括：

选择挑战数组，并将其发送给第一方；从第一方接收响应值，该响应值是由第一方根据所述挑战数组，所述第一随机数和第二随机数，以及所述t棵完整树的全部叶节点的计算值而确定；根据所述第二噪声向量，以及所述t棵刺穿树的全部叶节点的计算值，验证所述响应值是否符合预期；形成安全计算协议的数据元组的一部分，包括：在对所述响应值验证通过之后，形成所述数据元组的一部分。

进一步的，在一个实施例中，选择挑战数组包括，随机选择第一挑战数和第一数组；所述响应值包括第一响应值和第二响应值，所述第一响应值根据所述第一挑战数，对所述第一随机数和第二随机数执行第一运算而得到，所述第二响应值根据所述第一数组，对所述t棵完整树的全部叶节点的计算值进行第二运算而得到；验证所述响应值是否符合预期，具体包括：根据所述第二噪声向量，对所述第一响应值进行进一步运算，得到第一验证值；在所述第二响应值基础上，叠加对所述t棵刺穿树的全部叶节点的计算值进行所述第二运算的结果，得到第二验证值；判断该第一验证值和第二验证值是否相等。

根据第四方面，提供了一种生成安全计算协议的数据元组的装置，部署在第一方中，包括：

随机数生成单元，配置为生成第一随机数；

秘密分享单元，配置为与第二方执行秘密分享，得到第一中间向量的第一分片，对应的第二分片由第二方持有，其中所述第一中间向量对应于第一随机数与第二噪声向量的乘积，该第二噪声向量由第二方随机生成的稀疏的第一噪声向量中包含的t个非零噪声点形成；

完整树构建单元，配置为构建t棵完整树；

刺穿树辅助单元，配置为与第二方进行安全交互，辅助其构建t棵刺穿树；其中任意第j棵刺穿树包括位于第一侧的第一刺穿叶节点，该第一刺穿叶节点的计算值与第j棵完整树中对应节点的计算值之和，等于第一中间向量的第j个元素；该第j棵刺穿树中各个非刺穿叶节点的计算值，与第j棵完整树中对应节点的计算值之和为零；

分片形成单元，配置为基于所述t棵完整树第一侧叶节点的计算值，形成第一分片向量；

元组形成单元，配置为基于所述第一分片向量，形成安全计算协议的数据元组的一部分，该数据元组的另一部分基于第二方持有的第二分片向量形成，所述第二分片向量基于所述t棵刺穿树第一侧叶节点的计算值形成。

根据第五方面，提供了一种生成安全计算协议的数据元组的方法，部署在第二方中，包括：

噪声向量生成单元，配置为随机生成稀疏的第一噪声向量，该第一噪声向量中包含的t个非零噪声点形成t维的第二噪声向量；

秘密分享单元，配置为与第一方执行秘密分享，得到第一中间向量的第二分片，对应的第一分片由第一方持有，其中所述第一中间向量对应于第一方生成的第一随机数与所述第二噪声向量的乘积；

刺穿树构建单元，配置为与第一方进行安全交互，从而基于第一方构建的t棵完整树，对应构建t棵刺穿树；其中任意第j棵刺穿树包括位于第一侧的第一刺穿叶节点，该第一刺穿叶节点的计算值与第j棵完整树中对应节点的计算值之和，等于第一中间向量的第j个元素；该第j棵刺穿树中各个非刺穿叶节点的计算值，与第j棵完整树中对应节点的计算值之和为零；

分片形成单元，配置为基于所述t棵刺穿树第一侧叶节点的计算值，形成第二分片向量；

元组形成单元，配置为基于所述第二分片向量，形成安全计算协议的数据元组的一部分，该数据元组的另一部分基于第一方持有的第一分片向量形成，所述第一分片向量基于所述t棵完整树第一侧叶节点的计算值形成。

根据第六方面，提供了一种计算设备，包括存储器和处理器，其特征在于，所述存储器中存储有可执行代码，所述处理器执行所述可执行代码时，实现第二方面或第三方面的方法。

根据本说明书实施例提供的方法和装置，在第一方拥有随机数，第二方拥有高维稀疏的噪声向量的情况下，双方通过安全交互，分别构建完整树和对应的刺穿树，基于完整树/刺穿树的一侧叶节点的计算值，形成对高维噪声向量和随机数乘积向量的分片向量，从而生成安全计算协议的数据元组。以上过程中，通过避免直接对高维噪声向量进行向量秘密分享而显著降低了向量秘密分享带来的通信成本，提高了运算效率。并且，还可以基于双方生成的树结构的另一侧节点进行数据合法性校验，排除了一方进行数据欺诈的可能性，更好地保证了隐私数据的安全。

附图说明

为了更清楚地说明本发明实施例的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其它的附图。

图1示意性示出两方进行安全矩阵乘法的过程；

图2示出在一个实施例中生成数据元组的示意图；

图3示出根据一个实施例两方生成安全计算协议的数据元组的方法流程图；

图4示出在一个实施例中第一方构建t棵完整树的步骤流程；

图5示出在一个实施例中第一方构建t棵完整树的步骤流程；

图6示出在一个实施例中第二方确定的刺穿树的结构；

图7示出第二方在刺穿树中恢复出节点计算值的过程示意图；

图8示意性示出第j棵完整树和第j棵刺穿树中叶节点计算值的关系；

图9示出第二方对第一方的数据进行验证的步骤流程图；

图10示出根据一个实施例部署在第一方的数据元组生成装置示意图；

图11示出根据一个实施例部署在第二方的数据元组生成装置示意图。

具体实施方式

下面结合附图，对本说明书提供的方案进行描述。

如前所述，出于隐私保护中加强安全性的考虑，提出多种安全计算协议，用于在不同的场景中，实现多方安全建模和预测，实现联合风控和联合业务预测。例如，在一个示例，基于对偶LPN(learning parity with noise)困难假设构造伪随机VOLE(vectoroblivious linear-function evaluation，VOLE)协议，可以用于多种多方安全计算场景。

下面分别针对对偶LPN困难假设以及VOLE协议进行简要说明。

LPN困难假设：令C为概率性的码字生成算法，给定参数维度k,查询数量n,有限域F，输出矩阵G∈F^k×n。令噪声率为r，那么LPN(k,n,r)困难假设陈述：对任意的多项式时间的敌手，无法区分b＝s·G+e和一均匀随机向量b＇。其中，向量e服从伯努利分布Berr(F)，向量s从Fk中选择。

对偶LPN困难假设：LPN困难假设的对偶版本，陈述了对任意的多项式时间的敌手，都无法区分eH和一均匀随机向量。其中，H为G的奇偶校验矩阵。

不经意线性函数评估(oblivious linear function evaluation,OLE)：安全的两方计算协议，允许接收方(Alice)获得其持有秘密关于发送方(Bob)数据的一个线性组合。具体为，假设Bob拥有有限域元素u和v，Alice持有秘密元素x。通过该协议，最终Alice获得到值w，满足w＝ux+v。协议的安全性保证整个协议执行后，Alice没有获得任何关于u和v的信息，Bob没有获得任何关于x的信息。

VOLE：不经意线性函数评估的向量版本。具体为，假设发送方(Bob)拥有向量

和

接收方(Alice)持有元素x。通过该协议，最终Alice获得到向量

满足

协议的安全性保证整个协议执行后，Alice没有获得任何关于

和

的信息，Bob没有获得任何关于x的信息。

伪随机VOLE(向量不经意线性函数求值)：通过该协议，发送方Bob拥有随机的向量

和

接收方Alice获得随机的标量元素x和向量

满足关系

协议的安全性保证整个协议执行后，Alice方没有获得任何关于

和

的信息，Bob方没有获得任何关于x和

的信息。

伪随机VOLE协议可用于多种安全计算场景。例如，在一个示例中，可以使用伪随机VOLE协议实现两方安全乘法，例如，一方隐私数值与另一方的隐私向量的安全相乘。

在另一示例中，两方为了进行安全矩阵乘法，需要使用乘法三元组。图1示意性示出两方进行安全矩阵乘法的过程，其中矩阵X和矩阵Y分别由两方的隐私数据构成。可以看到，在第1步中，双方需要获得乘法三元组，一方获得(U1、V1、W1)，另一方获得(U2、V2、W2)，满足(U1+U2)*(V1+V2)＝(W1+W2)。常规技术中往往采用第三方来分发该乘法三元组。为了避免该第三方与其他方合谋导致的安全风险，近来也提出可以使用上述伪随机VOLE协议，由两方安全地构造乘法三元组，实现安全矩阵乘法。

为了执行安全计算协议，需要预先生成协议中使用的数据元组。例如，对于伪随机VOLE协议来说，就需要一方获得向量

和

另一方获得标量元素x和向量

作为数据元组。

为此，本说明书中提供一些方案实施例，可以高效、安全地生成安全计算协议的数据元组。图2示出在一个实施例中生成数据元组的示意图。如图2所示，第一方P1生成随机数x，第二方P2生成随机噪声向量

该向量为一个规则的稀疏向量，假定其中包含t个非零噪声点。然后，第一方和第二方进行安全交互，从而，第一方P1生成t棵完整树，第二方P2相对应地生成t棵刺穿树，每棵刺穿树包含有刺穿叶节点。通过两方的安全交互，保证两方的第j棵树具有如下关系：对于某刺穿位置，两方叶节点计算值之和等于x和第j个噪声点的乘积；对于非刺穿位置，两方叶节点计算值之和为0。

基于以上构造的树形结构，两方就可以分别形成分片向量。具体的，第一方基于t棵完整树的叶节点形成分片向量

第二方基于t棵刺穿树的叶节点形成分片向量

可以验证，

于是接着，第一方P1和第二方P2，可以各自基于其分片向量，形成安全计算协议的数据元组。例如，第一方获得前述x和向量

作为第一部分数据元组，第二方B获得

和

作为第二部分数据元组。

在生成数据元组基础上，第一方P1和第二方P2就可以利用安全计算协议，进行后续的多方安全计算，例如，进行两方标量和向量的安全乘法运算，或者，利用伪随机VOLE协议生成乘法三元组，进而进行安全矩阵乘法运算。

下面描述两方生成数据元组的详细过程。

图3示出根据一个实施例两方生成安全计算协议的数据元组的方法流程图。该流程涉及第一方P1和第二方P2。需要理解的是，第一方P1和第二方P2可以是需要进行安全计算的任何实体，例如，第一方P1为拥有用户隐私数据的银行或支付平台，第二方P2为拥有训练好的模型数据的模型拥有方；或者，第一方P1和第二方P2各自拥有部分隐私数据和部分模型数据。并且，应理解，第一方和第二方，均可以通过任何具有计算、处理能力的设备、装置、平台、设备集群来实现。

为了生成安全计算协议使用的数据元组，如图3所示，首先在步骤31，第一方P1生成第一随机数x。可选的，在一个实施例中，为了后续验证需要，第一方P1还生成第二随机数ρ。该验证是为了满足协议恶意安全，即能够抵抗恶意的敌手。验证的过程和作用将在后续详细描述。

另一侧，在步骤32，第二方生成稀疏的第一噪声向量

具体的，第二方可以按照LPN假定的噪声分布进行随机采样，得到该稀疏的噪声向量。如本领域技术人员所公知的，所谓稀疏向量是指，向量中0元素占比极大(例如大于业界认可的一定阈值，比如90％)，非零元素占比很小。作为稀疏向量，可以假定该第一噪声向量

中包含t个非零噪声点，其中t的大小远远小于向量

的维度M。稀疏参数t的选择需满足对偶LPN困难假设的安全性。可以令该t个噪声点形成t维的第二噪声向量

则第二噪声向量中不包含零元素，其维度t远远小于第一噪声向量的维度M。

例如，假定第一噪声向量

为100维向量，其中包含8个非零噪声点(t＝8)，则这8个非零噪声点可以形成第二噪声向量

需要说明的是，步骤31和32可以以任何合理的相对顺序执行，或者并行执行。

然后，在步骤33，第一方和第二方通过秘密分享，分别得到第一随机数x和第二噪声向量

的乘积向量

的分片。下文将该乘积向量称为第一中间向量。这里的秘密分享具体可以是标量-向量加性秘密分享。则通过该秘密分享，第一方得到第一中间向量的第一分片

第二方得到第二分片

满足两个分片之和等于该第一中间向量：

存在多种已有的多方安全计算MPC方式，可以实现上述秘密分享。例如，在一个实施例中，可以通过不经意传输OT协议，实现上述过程。更具体的，在一个例子中，在需要实现恶意安全性的情况下，此处的OT协议可以使用恶意安全的OT协议。

具体的，第二方P2可以将第二噪声向量

中任意第j维的元素y_j表示为k位的二进制形式：Y_j＝(b_k-1...b_ib₀)₂。而第一方P1可以选择随机数组{q_j，m}，0≤m＜k。基于此，第一方P1和第二方P2可以通过构造k组OT实现xy_j的秘密分享。每组OT的输入为，P1输入(q_j,m，q_j,m+x2^m),P2输入b_m。每组OT执行后，P2获得OT结果q_j,m+x2^mb_m。

则在双方调用k组OT后，第一方P1计算β_j，1＝-Σ_mq_j，m；第二方P2计算β_j，2＝-∑_m(q_j,m+x2^mb_m)。可以验证，β_j，1+β_j，2＝xy_j。对于第二噪声向量

中每一维均执行上述过程，通过执行t次，第一方可以得到

第二方得到

可选的，为了后续验证的需要，在第一方还生成第二随机数ρ的情况下，在上述步骤中，第一方和第二方还通过秘密分享，分别得到第二随机数ρ和第二噪声向量

的乘积向量

的分片。下文将该乘积向量称为第二中间向量。则通过向量秘密分享，第一方得到第二中间向量的第一分片

第二方得到第二分片

满足两个分片之和等于该第二中间向量：

双方执行向量秘密分享的过程，可以与以上基于OT协议的相同，不复赘述。并且，在需要实现恶意安全的实施例中，第一方和第二方通过k组OT，同时实现对xy_j和ρy_j秘密分享。

在以上获得

和

的秘密分享向量分片的基础上，接下来，第一方和第二方联合进行计算树的构建。

具体的，在步骤34，第一方P1构建t棵完整树；在步骤35，第二方P2和第一方P1安全交互，对应构建t棵刺穿树，使得双方的第j棵树满足，某个刺穿位置上两棵树叶节点计算值之和为xy_j，非刺穿位置上两棵树叶节点计算值之和为0。每棵刺穿树的构建，相当于调用了一次点函数秘密分享SPFSS。

下面详细描述双方构建t棵完整树/刺穿树的过程。

图4示出在一个实施例中第一方构建t棵完整树的步骤流程，即上述步骤34的子步骤。如图4所示，首先在步骤341，双方根据约定方式，将第一噪声向量

的维度M划分为t个区间，使得每个区间包含一个非零噪声点。优选的，上述t个区间长度相等。

如前所述，第一噪声向量按照LPN假设基于规则的噪声分布而生成，因此，可以假定，非零噪声点的分布是规则的。因此，可以将第一噪声向量的维度M等距离划分为t个区间，每个区间仅包含一个噪声点。如果维度M不能被t整除，则可以令前t-(M％t)个区间长度为

后M％t个区间长度为

其中

表示向下取整,M％t表示M除以t的余数。在另一例子中，可以要求M需要是t的倍数，或者在M不能被t整除时，截断第一噪声向量的后M％t个零元素或者补足一定数量的零元素，使得截断或补足后的维度M’可以被t整除。

延续前面的例子。假定第一噪声向量

为100维向量，其中包含8个非零噪声点，则M＝100，t＝8。在一个例子中，可以将100维向量划分为8个区间，其中前4个区间的区间长度为12，后4个区间的区间长度为13。

然后，在步骤342，第一方生成第j个树形结构，使得该树形结构在倒数第二层包括N个节点，其中N为第j个区间的元素数目，即前述区间长度。相应的，该树形结构在最后一层，包括2N个叶节点，或者说N对叶节点。

为了形成上述树形结构，可以根据区间长度N确定该树形结构的层数。具体的，可以求得

表示向上取整，将第l层作为上述倒数第二层。在2^l大于N的情况下，在一个例子中，可以将第l层中多于N的节点作为空节点，或者裁剪掉这些节点。

例如，延续上例，假定j＝3，区间长度N＝12，那么，l＝4，可以将第4层作为倒数第二层，并且将该层原本应具有的16个节点中的后面4个作为空节点，保留前面12个作为有效节点。相应的，该树形结构的最后一层为第5层(l+1)，该最后一层具有12对叶节点。

接着，可以分别为上述树形结构的各个节点赋予计算值。下文中用

表示h层的第i个节点的计算值，每层中的节点索引从0开始编号。

首先对于根节点，可以将一定长度λ的随机采样的比特串作为随机种子，赋值给该根节点。即，第一方采样随机种子seed∈{0，1}^λ，赋值给根节点

在一个具体例子中，在要求128比特安全性的情况下，选择长度λ＝128比特。

在步骤343，从根节点开始到倒数第二层，利用第一伪随机生成算法，根据父节点的计算值确定两个子节点的计算值。

具体的，对层数h∈{1，...，l},第一方将h-1层的任意第i个节点

作为父节点，对其施加第一伪随机生成算法G，得到其在h层的两个子节点的计算值

即，

在一个具体例子中，父节点

的计算值为λ位的比特串。当将λ位的比特串输入到上述第一伪随机生成算法，该算法输出2λ位的伪随机比特串。可以将该2λ位的比特串拆分为两个λ位的比特串，分别作为左右子节点的计算值

从而每个节点的计算值仍为λ位的比特串。

以上运算从根节点开始，直到计算出倒数第二层N个节点的计算值。

之后，在步骤344，利用第二伪随机生成算法G’，根据倒数第二层各个节点的计算值，确定最后一层N对叶节点的计算值。也就是说，对h＝l+1，第一方计算

该第二伪随机生成算法G’与第一伪随机生成算法G的不同在于，其将λ位比特串的输入，映射为有限域中的输出值。

如此，第j个树形结构的节点均得到赋值，第一方生成了第j棵完整树。利用同样的方式，第一方可以生成所需的t棵完整树。

下面描述第二方通过与第一方交互，在其辅助之下，构建t棵刺穿树的过程。图5示出在一个实施例中第二方构建t棵刺穿树的步骤流程，即上述步骤35的子步骤。

首先，在步骤351，第二方生成第j个树形结构，并根据第j个非零噪声点在第一噪声向量中的全局位置，确定该树形结构的各个层中的刺穿节点。

具体的，第二方也根据约定方式，将第一噪声向量的维度M划分为t个区间，使得每个区间包含一个非零噪声点；并确定第j个树形结构，使得该树形结构在倒数第二层包括N个节点，其中N为第j个区间的元素数目或区间长度。该过程与前述步骤341-342相似，不复赘述。如此，第二方确定的第j棵树的树结构与第一方的相同。

进一步的，第二方需要根据第j个噪声点的位置，在第j个树形结构中确定出刺穿节点。具体地，第二方可以根据第j个噪声点在第一噪声向量中的全局位置，以及上述t个区间的划分，确定该第j个非零噪声点在第j个区间的相对位置。假定该第j个噪声点在第一噪声向量的M个元素中的位置索引为z，将其映射到第j个区间中，可以得到其在第j个区间的相对位置的索引为α_j＝z-(j-1)N′，其中N′为前j-1个区间的区间长度。

然后，根据该相对位置确定刺穿路径，该刺穿路径沿父子节点关系连接各个中间层的刺穿节点，其中倒数第二层的N个节点中位于该相对位置的目标节点即为该倒数第二层的刺穿节点，该目标节点的一对子节点即为叶节点层的一对刺穿叶节点。

在一个实施例中，可以首先在倒数第二层的N个节点中，确定出上述相对位置处的节点作为目标节点，将从该目标节点回溯到根节点的路径中所途径的各个中间层节点，作为对应中间层的刺穿节点。

在另一实施例中，可以将上述相对位置的索引α_j表示为二进制串α_j＝(a₁a₂...a_l)₂，该二进制串中依次排列的0或1，分别对应从根节点开始依次向左侧子节点或右侧子节点行进的刺穿路径。

延续之前的例子并结合图示进行描述。图6示出在一个实施例中第二方确定的刺穿树的结构。在图6的示例中，延续上例，假定j＝3，区间长度N＝12，那么生成的刺穿树在倒数第二层(h＝4)具有12个节点。假定这第3个噪声点在原始的100维第一噪声向量中的位置索引为z＝30，那么由于前2个区间的区间长度N都是12，可以得到，该噪声点对应于第3个区间中第6个元素。由于在树结构中位置编号从0开始，可以得到该噪声点在第j个区间的相对位置的索引α_j＝5，表示为二进制为(0101)。

于是，在倒数第二层的12个节点中，位于上述相对位置的节点，即第6个节点(编号为5)为该层的刺穿节点，刺穿节点用灰色表示。该第6个节点的两个子节点，是最后一层(h＝5)中的一对刺穿叶节点。从第1层开始到该倒数第二层的刺穿节点的路径即为刺穿路径，该路径所经过的中间层的节点均为刺穿节点。当用0表示左侧子节点，用1表示右侧子节点时，上述刺穿路径中各个刺穿节点所位于的左侧或右侧的指示序列，即对应于相对位置的索引α_j＝5的二进制表示(0101)。

至此，第二方确定出了第j棵刺穿树的树结构和其中的刺穿节点位置。

然后，在步骤352，第二方与第一方执行不经意传输OT协议，针对各个层中除刺穿节点之外的节点，恢复出与第j棵完整树对应节点相同的计算值。

为此，第一方在如图4所示生成第j棵完整树后，还需要针对各个中间层，生成针对左侧节点的第一取值和针对右侧节点的第二取值，其中，第一取值为该中间层所有左侧节点的计算值的异或值，第二取值为该中间层所有第二侧节点的计算值的异或值。

具体的，对于中间层h∈{1，...，l}，第一方P1分别计算第j棵完整树的每一层h左侧节点的异或值作为第一取值

右侧节点的异或值作为第二取值

其中

对于第二方而言，在中间层h，对于除刺穿节点和与该刺穿节点共享同一父节点的配对节点之外的其余节点，利用第一伪随机生成算法，根据上一层父节点的计算值确定所述其余节点的计算值；并且，与第一方执行OT协议，根据配对节点位于左侧或右侧的指示值

从第一方提供的第一取值

和第二取值

中选择其中之一作为目标取值

从而根据该目标取值，和与配对节点位于同一侧的节点的计算值，恢复得到配对节点的计算值。于是，恢复出该中间层中除刺穿节点之外的所有节点的计算值。

下面结合图7进行描述，其中图7示出第二方在刺穿树中恢复出节点计算值的过程示意图。该图7延续图6的示例，其中用灰色节点示出刺穿节点。此外，在图7中，还用画有斜线的节点示出与刺穿节点共享同一父节点的配对节点。

首先，在h＝1层，该层中左侧节点为刺穿节点，右侧节点为配对节点，该层不存在其余节点。则直接与第一方执行OT协议。由于配对节点位于右侧，

则从第一方提供的两个取值中选择第二取值

然而，在第1层，

由此，第二方恢复出第1层中配对节点的计算值

接着，在h＝2层，该层中编号为0的是配对节点，编号为1的是刺穿节点，编号为2,3的为其余节点。对于其余节点，可以利用第一伪随机生成算法，根据其上一层恢复出的父节点的计算值

恢复出其各自的计算值，即

对于配对节点，第二方与第一方执行OT协议，由于该层中配对节点位于左侧

则第二方从第一方提供的两个取值中选择该层的第一取值

作为目标取值。需要理解，该第一取值为对应完整树中h＝2层中所有左侧节点的异或值，而第二方已恢复出该层中其他左侧节点的计算值，于是可以根据该目标取值

和已恢复出的本层其他左侧节点的计算值，恢复得到该配对节点的计算值

于是，恢复出h＝2层中除刺穿节点之外的节点计算值。

对于后续的中间层h＝3,4，均可以执行上述过程。

在上述过程中，对于中间层的一个节点，如果该节点既不是刺穿节点也不是与刺穿节点对应的配对节点，也就是图7中的白色节点，那么其父节点必然不是上一层的刺穿节点，于是，可以根据其父节点，和约定的第一伪随机算法，确定出该节点的计算值。如果该节点是配对节点，也就是图7中斜线所示的节点，那么可以通过与第一方执行OT，获取该配对节点所在侧的节点的异或值，再根据该异或值和已恢复出的其他同侧节点的计算值，确定出配对节点的计算值。

上述过程针对各个中间层进行，直至倒数第二层节点(第l层)。对于最后一层节点(l+1层)，也就是叶节点层，第二方利用与第一方约定的相同的第二伪随机生成算法G′，根据倒数第二层中除刺穿节点之外的各个节点的计算值，确定出最后一层除刺穿叶节点之外的其余叶节点的恢复计算值。也就是，对于第l层中除刺穿位置之外的节点

其中i∈[2^l]\{α_j}(\表示排除)，计算

从而得到非刺穿叶节点的恢复值。

至此，在图5的步骤352，针对第j棵刺穿树的各个层中除刺穿节点之外的其他节点，第二方均恢复得到与第j棵完整树对应节点相同的计算值。

然而如前所述，为了生成数据元组，对第j棵刺穿树的叶节点具有特殊要求，要求其中的一个刺穿叶节点的计算值与第j棵完整树中对应节点的计算值之和，等于第一中间向量

的第j个元素xy_j；非刺穿叶节点的两方计算值之和为0。为此，需要对叶节点层进行进一步处理。

回到图5的流程图，接着，在步骤353，第一方基于其持有的第一中间向量

的第一分片

和第j棵完整树的叶节点的计算值，确定混淆值，将其发送给第二方。从而，在步骤354，第二方可以基于接收的混淆值，其持有的第一中间向量

的第二分片

以及第j棵树形结构中恢复出的计算值，确定该树形结构中各个叶节点的最终计算值。下面具体描述这两个步骤。

如前所述，每棵刺穿树中具有一对刺穿叶节点。第一方和第二方可以约定该一对刺穿叶节点中固定的一侧叶节点，用于组合得到第一中间向量的元素。下文中，将该侧称为第一侧，其可以是左侧，或者右侧。将位于该第一侧的刺穿叶节点，称为第一刺穿叶节点。

如此，在步骤353，第一方可以基于第一中间向量的第一分片，和第j棵完整树的所有的第一侧叶节点的计算值，确定出第一混淆值。具体的，该第一混淆值可以是，第j棵完整树中所有第一侧叶节点的计算值之和，减去第一中间向量的第一分片的第j元素。

例如，假定第一侧为右侧，第一方可以确定出如下的第一混淆值：

其中，

为第j棵完整树中的右侧叶节点，β_j，1为第一分片

中的第j元素。

相应的，在步骤354，第二方基于上述第一混淆值，其拥有的第二分片，以及除第一刺穿叶节点之外的第一侧叶节点的恢复计算值，得到第一目标值

使得该第一目标值与第一刺穿叶节点在完整树中对应节点的计算值之和，等于第一中间向量的第j个元素。

在第一混淆值如公式(1)所示的情况下，第二方可以根据如下公式(2)计算第一目标值：

公式(2)中的最后一项，是将刺穿树中除第一刺穿叶节点之外的其他右侧叶节点的恢复计算值求和。可以将第一刺穿节点在第j棵完整树中的对应节点的计算值称为第一计算值，记为pn_j。那么，公式(1)中第一项和公式(2)中最后一项之差，即为上述第一计算值，从而可以得到：

即，第一目标值与第一刺穿叶节点在完整树中对应计算值(第一计算值)之和，等于第一中间向量的第j个元素。

于是，第二方将上述第一目标值

确定为第一刺穿叶节点的最终计算值；将除一对刺穿叶节点之外的其余叶节点的最终计算值确定为其恢复计算值的相反数。

简洁起见，可以将第一方的第j棵完整树中，第i对(其中i＝[N])叶子节点的计算值表示为

那么对于第二方而言，对于非刺穿叶节点i≠α_j，最终计算值为

对于一对刺穿叶节点中位于第一侧的第一刺穿叶节点，其最终计算值为第一目标值

可选的，如前所述，出于验证需要，第一方和第二方还可以通过向量秘密分享，分别得到第二中间向量

的第一分片

和第二分片

在以上过程中，一对刺穿叶节点中的第一侧节点用来组合得到第一中间向量的元素，那么可以利用另一侧的节点，即第二侧的节点来组合得到第二中间向量的元素。下文将该一对刺穿节点中位于第二侧的节点称为第二刺穿叶节点。

针对第二刺穿叶节点，可以实施与第一刺穿叶节点相似的赋值过程。

延续公式(1)的例子。假定第一侧为右侧，则第二侧为左侧。第一方还可以确定出如下的第二混淆值：

其中，

为第j棵完整树中左侧叶节点，γ_j，1为第二中间向量的第一分片的第j元素。

对应的，第二方可以根据如下公式(5)计算第二目标值：

可以验证，该第二目标值与第二刺穿节点在完整树中对应计算值之和，等于第二中间向量的第j个元素ρy_j。

在这样的情况下，在第二方的第j棵刺穿树中，对于非刺穿叶节点i≠α_j，最终计算值为

对于一对刺穿叶节点，其最终计算值为

图8示意性示出第j棵完整树和第j棵刺穿树中叶节点计算值的关系。如图所示，双方的第j棵树结构相同，在倒数第二层包含n个节点，在最后一层具有n对叶节点。在图8中，用下角标S表示第一方，用R表示第二方。对于非刺穿叶节点，双方树中计算值之和为0。对于一对刺穿叶节点，第一侧(图8所示为右侧)刺穿叶节点位置上的双方节点计算值之和，为第一中间向量的第j元素xy_j；第二侧(图8所示为左侧)刺穿叶节点位置上的双方节点计算值之和，为第二中间向量的第j元素ρy_j。

如上，通过图4的步骤流程，第一方可以构建t棵完整树，通过图5的步骤流程，第二方可以在第一方的辅助下，构建t棵对应的刺穿树，如此，执行了图3中的步骤34和35。在此基础上，第一方和第二方就可以基于之前构建的完整树/刺穿树，进行生成数据元组的进一步操作。

回到图3，在接下来的步骤36，第一方和第二方，分别基于t棵完整树和t棵刺穿树的第一侧叶节点的计算值，形成第一分片向量和第二分片向量。

具体的，第一方基于t棵完整树的第一侧叶节点的计算值，形成第一分片向量

第二方基于t棵刺穿树的第一侧叶节点的计算值，形成第二分片向量

可以理解，第j棵完整树/刺穿树的一侧叶节点的数量，等同于倒数第二层的节点数量，即第j个区间的区间长度。因此，全部t棵树的第一侧叶节点的数量之和，即为第一噪声向量的维度M。并且，由于在第一刺穿叶节点位置上，两方树的叶节点计算值之和等于xy_j，即第一随机数x和第j噪声点的乘积，而在非刺穿位置上两方树的叶节点计算值之和为0，因此可以得到：

需要说明的是，在第一方持有第一随机数x，第二方持有第一噪声向量

的情况下，尽管也可以通过与步骤33类似的方式，通过向量秘密分享得到第一分片向量和第二分片向量，但是，需要注意的是，第一噪声向量一般为高维向量，且其中包含大量零元素。如果按照步骤33的方式，直接对其进行向量秘密分享，则需要针对待处理向量的每个维度进行k次OT传输，带来极大的通信传输成本和计算成本。

因此，在本说明书的实施例中，仅对第一噪声向量中非常少量的非零元素构成的低维向量(第二噪声向量

)，进行常规的向量秘密分享，使得OT传输的次数得到指数级下降。然后，通过非常有限次数的安全交互，实现t棵刺穿树的构建，从而双方在本地各自基于本方的t棵树，得到第一/第二向量分片。

接着，就可以基于上述第一/第二向量分片，形成安全计算协议的数据元组。

可选的，在形成数据元组之前，在步骤37，第二方对第一方的数据进行验证，以确保第一方的作恶行为可以被检测出来。这是因为，第二方是在第一方的辅助之下，借助于第一方提供的数据(包括各层的第一取值，第二取值，混淆值等等)而生成的刺穿树，进而形成了第二向量分片。如果第一方存在恶意欺诈行为，则有可能通过精心构造提供的数据，反推出第二方的隐私数据信息。为此，第二方需要对第一方的数据合法性进行验证。

如前所述，根据可选的实施例，在第一方和第二方协同构建的t棵树中，第一侧刺穿叶节点位置上的双方节点计算值之和，为第一中间向量的第j元素xy_j；而第二侧刺穿叶节点位置上的双方节点计算值之和，为第二中间向量的第j元素ρy_j。双方可以利用第一侧叶节点形成第一/第二分片向量，第二方可以利用余下的第二侧叶节点进行数据的验证。

具体的，图9示出第二方对第一方的数据进行验证的步骤流程图，即前述步骤37的子步骤。如图9所示，在步骤371，第二方选择挑战数组，并将其发送给第一方。在一个实施例中，上述挑战数组可以包括第一挑战数τ和第一数组S。

然后，在步骤372，第一方根据挑战数组，其生成的第一随机数x和第二随机数ρ，以及t棵完整树的全部叶节点的计算值，计算响应值，并将其发送给第二方。

具体的，在一个实施例中，第一方根据第一挑战数τ，对第一随机数x和第二随机数ρ执行第一运算，得到第一响应值X1；并根据第一数组S，对t棵完整树的全部叶节点的计算值进行第二运算，得到第二响应值V1。可以理解，该第二运算涉及第一数组与t棵完整树中全部叶节点(包含第一侧叶节点和第二侧叶节点)的组合运算。然后，第一方将计算得到的该第一响应值X1和第二响应值V1发送给第二方。

于是，在步骤373，第二方根据其拥有的第二噪声向量，以及t棵刺穿树的全部叶节点的计算值，验证上述响应值是否符合预期。

具体的，在一个实施例中，第二方在接收到第一方计算的第一响应值X1和第二响应值V1后，根据第二噪声向量

对第一响应值X1进行进一步运算，得到第一验证值X2；在第二响应值V1基础上，叠加对t棵刺穿树的全部叶节点(包含第一侧叶节点和第二侧叶节点)的计算值进行前述第二运算的结果，得到第二验证值V2；判断该第一验证值X2和第二验证值V2是否相等。若相等，则意味着，第二方数据合法，验证通过。

更具体的，在一个具体例子中，第二方选择的第一数组S包括两个子数组τ₁，τ₂，...，τ_t和δ₀，δ₁，...，δ_N-1，其中第一个子数组对应于t棵树，第二个子数组对应于各个树中有多少对叶节点。对此，第一方可以按照如下公式(7)计算第一响应值X1，按照公式(8)计算第二响应值V1：

X1＝ρ+τx (7)

可以看到，计算第二响应值的第二运算包括，对于节点对中的第一侧节点和第二侧节点的计算值施加不同系数(第一侧节点系数为第一挑战数τ，第二侧节点系数为1)进行求和，然后根据上述两个子数组，逐对节点逐棵树进行累加，得到第二响应值。

对此，第二方可以按照如下公式(9)计算第一验证值X2，并按照公式(10)计算第二验证值V2：

其中，公式(9)中的α_j指示刺穿位置。公式(10)中，第二验证值是对t棵刺穿树进行上述的第二运算，将运算结果叠加到第二响应值V1上。

基于公式(10)可以得到以下关系：

如果第一方按照约定方式构造完整树，并辅助构造刺穿树，则对于非刺穿节点i≠α_j，有

对于刺穿节点i＝α_j，则有：

在这样的情况下，公式(11)可以改写为：

因此，如果第一验证值X2与第二验证值V2相等，则可以确定，第一方和第二方是按照约定的合法方式生成的完整树/刺穿树，从而第二方可以确定第一方的数据合法，通过验证。

以上结合图6所示的树形结构的例子，描述了第一方和第二方生成分片向量，并可选地进行数据验证的过程。在可行的替代实施方式中，还可以在图6基础上修改树结构，从而进一步简化运算。

具体的，在一个替代实施例中，树形结构在第l-1层具有N/2个节点。然而，不同于如图6所示在第l层和l+1层，依次扩展成N个节点和2N个叶节点的结构，在替代实施例中，可以采用另一伪随机生成算法，根据一个父节点计算出4个子节点的值，如此，在第l层，直接扩展到2N个叶节点。在该实施例下，叶节点4个为一组排列。如此，第l-1层的刺穿节点将会具有一组4个叶节点，或者说2对叶节点。第一方和第二方可以约定，在一组的4个位置中，指定其中一对作为刺穿叶节点，并指定该对刺穿叶节点的一侧作为第一侧，用于组合得到xy_j；另外一侧作为前述第二侧，用于组合得到ρy_j。其他实施方式与前述实施例相同。通过该替代实施例，可以缩减树的深度，简化计算。

通过以上多种方式，第一方和第二方生成了第一/第二向量分片。如此，可以执行后续的数据元组生成步骤。即，在步骤38，第一方和第二方，分别基于所述第一分片向量和第二分片向量，形成安全计算协议的数据元组。

具体的，在安全计算协议为伪随机VOLE协议的情况下，第一方可以基于前述得到的第一分片向量

和预设的压缩矩阵H，确定第一伪随机向量

为了确保生成向量的“随机性”，这里的压缩矩阵H可以是基于对偶LPN困难假设提出的矩阵，实践中可以采用LPN困难理论中生成矩阵G的奇偶校验矩阵。

相应的，第二方基于第一噪声向量

和所述压缩矩阵H，确定第二伪随机向量

还基于前述第二分片向量

和所述压缩矩阵H，确定第三伪随机向量

可以验证，如此确定的第一，第二，第三伪随机向量满足：第二伪随机向量与所述第一随机数的乘积，叠加上第三伪随机向量的结果，等于第一伪随机向量，即：

如此，第一方和第二方生成了用于伪随机VOLE安全计算协议的数据元组。

在其他例子中，还可以利用以上产生的第一分片向量/第二分片向量，生成其他安全计算协议的数据元组，例如在一些已有的向量乘法计算协议中，也会需要双方准备随机而满足预定关系的分片向量。

在生成了安全计算协议的数据元组的基础上，就可以利用这样的数据元组执行安全计算协议，用来进行多方安全计算。例如，在生成上述伪随机VOLE的数据元组后，就可以利用这样的数据元组，通过伪随机VOLE协议，实现双方安全地生成乘法三元组，进而利用乘法三元组进行安全矩阵乘法运算。

各种基于数据元组的安全计算协议，广泛应用于联合机器学习的隐私保护场景，在此不再一一举例。

综合以上，在本说明书的实施例中，在第一方拥有随机数，第二方拥有高维稀疏的噪声向量的情况下，双方通过安全交互，分别构建完整树和对应的刺穿树，基于完整树/刺穿树的一侧叶节点的计算值，形成对高维噪声向量和随机数乘积向量的分片向量，从而生成安全计算协议的数据元组。以上过程中，通过避免直接对高维噪声向量进行向量秘密分享而显著降低了向量秘密分享带来的通信成本，提高了运算效率。并且，还可以基于双方生成的树结构的另一侧节点进行数据合法性校验，排除了一方进行数据欺诈的可能性，更好地保证了隐私数据的安全。

根据另一方面的实施例，还提供了一种生成安全计算协议的数据元组的装置，该装置部署在第一方中，该第一方可以实现为任何具有计算、处理能力的设备或平台。图10示出根据一个实施例部署在第一方的数据元组生成装置示意图。如图10所示，该装置100包括：

随机数生成单元101，配置为生成第一随机数；

秘密分享单元102，配置为与第二方执行秘密分享，得到第一中间向量的第一分片，对应的第二分片由第二方持有，其中所述第一中间向量对应于第一随机数与第二噪声向量的乘积，该第二噪声向量由第二方随机生成的稀疏的第一噪声向量中包含的t个非零噪声点形成；

完整树构建单元103，配置为构建t棵完整树；

刺穿树辅助单元104，配置为与第二方进行安全交互，辅助其构建t棵刺穿树；其中任意第j棵刺穿树包括位于第一侧的第一刺穿叶节点，该第一刺穿叶节点的计算值与第j棵完整树中对应节点的计算值之和，等于第一中间向量的第j个元素；该第j棵刺穿树中各个非刺穿叶节点的计算值，与第j棵完整树中对应节点的计算值之和为零；

分片形成单元105，配置为基于所述t棵完整树第一侧叶节点的计算值，形成第一分片向量；

元组形成单元107，配置为基于所述第一分片向量，形成安全计算协议的数据元组的一部分，该数据元组的另一部分基于第二方持有的第二分片向量形成，所述第二分片向量基于所述t棵刺穿树第一侧叶节点的计算值形成。

在一个实施例中，所述完整树构建单元103具体配置为：根据约定方式，将第一噪声向量的维度划分为t个区间，使得每个区间包含一个非零噪声点；生成第j个树形结构，该树形结构在倒数第二层包括N个节点，其中N为第j个区间的元素数目；从根节点开始到所述倒数第二层，利用第一伪随机生成算法，根据父节点的计算值确定两个子节点的计算值；利用第二伪随机生成算法，根据倒数第二层各个节点的计算值，确定最后一层N对叶节点的计算值，从而得到第j棵完整树。

在一种实施方式中，刺穿树辅助单元104具体包括(未示出)：OT模块，配置为对于第j棵完整树，通过与第二方执行不经意传输OT协议，使得第二方恢复出对应树形结构的各个层中除刺穿节点之外的节点的计算值；混淆模块，配置为基于所述第一分片和所述第j棵完整树的叶节点的计算值，确定混淆值，将其发送给第二方，以使得第二方基于所述混淆值，所述第二分片，以及所述树形结构中恢复出的计算值，确定该树形结构中各个叶节点的最终计算值，从而得到第j棵刺穿树。

进一步的，在一个实施例中，所述OT模块配置为：对于第j棵完整树的各个中间层，计算第一取值和第二取值，其中第一取值为该中间层所有左侧节点的计算值的异或值，第二取值为该中间层所有右侧节点的计算值的异或值；与第二方执行OT协议，使得第二方根据该中间层中的刺穿节点的位置选择第一取值和第二取值之一，并根据选择的取值恢复出该中间层中除刺穿节点之外的节点计算值。

在一个实施例中，随机数生成单元101还生成第二随机数；秘密分享单元102通过所述向量秘密分享，还得到第二中间向量的第一分片，对应的第二分片由第二方持有；其中该第二中间向量对应于所述第二随机数与第二噪声向量的乘积；其中，所述第j棵刺穿树还包括位于第二侧的第二刺穿叶节点，该第二刺穿叶节点的计算值与第j棵完整树中对应节点的计算值之和，等于第二中间向量的第j个元素。

根据一种实施方式，所述装置100还包括响应单元106，配置为：从第二方接收挑战数组；根据所述挑战数组，所述第一随机数和第二随机数，以及所述t棵完整树的全部叶节点的计算值，计算响应值，并将其发送给第二方，以使得第二方根据所述第二噪声向量，以及所述t棵刺穿树的全部叶节点的计算值，验证所述响应值是否符合预期。在这样的情况下，元组形成单元107配置为，在接收到表示第二方对所述响应值验证通过的指示之后，形成所述数据元组的一部分。

进一步的，在一个实施例中，所述挑战数组包括第一挑战数和第一数组；响应单元106具体配置为，根据所述第一挑战数，对所述第一随机数和第二随机数执行第一运算，得到第一响应值；并根据所述第一数组，对所述t棵完整树的全部叶节点的计算值进行第二运算，得到第二响应值。

根据一个实施例，所述安全计算协议为伪随机VOLE协议；元组形成单元107配置为：基于所述第一分片向量和预设的压缩矩阵，确定第一伪随机向量。

根据又一方面的实施例，还提供了一种生成安全计算协议的数据元组的装置，该装置部署在第二方中，该第二方可以实现为任何具有计算、处理能力的设备或平台。图11示出根据一个实施例部署在第二方的数据元组生成装置示意图。如图11所示，该装置110包括：

噪声向量生成单元111，配置为随机生成稀疏的第一噪声向量，该第一噪声向量中包含的t个非零噪声点形成t维的第二噪声向量；

秘密分享单元112，配置为与第一方执行秘密分享，得到第一中间向量的第二分片，对应的第一分片由第一方持有，其中所述第一中间向量对应于第一方生成的第一随机数与所述第二噪声向量的乘积；

刺穿树构建单元113，配置为与第一方进行安全交互，从而基于第一方构建的t棵完整树，对应构建t棵刺穿树；其中任意第j棵刺穿树包括位于第一侧的第一刺穿叶节点，该第一刺穿叶节点的计算值与第j棵完整树中对应节点的计算值之和，等于第一中间向量的第j个元素；该第j棵刺穿树中各个非刺穿叶节点的计算值，与第j棵完整树中对应节点的计算值之和为零；

分片形成单元114，配置为基于所述t棵刺穿树第一侧叶节点的计算值，形成第二分片向量；

元组形成单元116，配置为基于所述第二分片向量，形成安全计算协议的数据元组的一部分，该数据元组的另一部分基于第一方持有的第一分片向量形成，所述第一分片向量基于所述t棵完整树第一侧叶节点的计算值形成。

根据一种实施方式，刺穿树构建单元113具体包括：

树结构确定模块1131，配置为生成第j个树形结构，并根据第j个非零噪声点在第一噪声向量中的全局位置，确定该树形结构的各个层中的刺穿节点；

计算值恢复模块1132，配置为通过与第一方执行不经意传输OT协议，针对各个层中除刺穿节点之外的节点，恢复出与第j棵完整树对应节点相同的计算值；

混淆值接收模块1133，配置为从第一方接收混淆值，该混淆值基于第一方持有的所述第一分片和所述第j棵完整树的叶节点的计算值确定；

叶节点确定模块1134，配置为基于所述混淆值，所述第二分片，以及所述树形结构中恢复出的计算值，确定该树形结构中各个叶节点的最终计算值，从而得到第j棵刺穿树。

在一个实施例中，上述树结构确定模块1131具体配置为：根据约定方式，将第一噪声向量的维度划分为t个区间，使得每个区间包含一个非零噪声点；确定第j个树形结构，该树形结构在倒数第二层包括N个节点，其中N为第j个区间的元素数目；根据所述全局位置，以及所述t个区间的划分，确定所述第j个非零噪声点在所述第j个区间的相对位置；根据所述相对位置确定刺穿路径，该刺穿路径沿父子节点关系连接各个中间层的刺穿节点，其中倒数第二层的N个节点中位于所述相对位置的目标节点作为该倒数第二层的刺穿节点，该目标节点的一对子节点作为叶节点层的一对刺穿叶节点。

在一个实施例中，上述计算值恢复模块1132具体配置：

对于各个中间层中除刺穿节点和与该刺穿节点共享同一父节点的配对节点之外的其余节点，利用第一伪随机生成算法，根据父节点的计算值确定所述其余节点的计算值；

与第一方执行OT协议，根据所述配对节点位于第一侧或第二侧的指示值，从第一方提供的第一取值和第二取值中选择其中之一作为目标取值，其中第一取值为第j棵完整树中该中间层所有第一侧节点的计算值的异或值，第二取值为第j棵完整树中该中间层所有第二侧节点的计算值的异或值；

根据所述目标取值，和与所述配对节点位于同一侧的节点的计算值，恢复得到所述配对节点的计算值；

利用第二伪随机生成算法，根据倒数第二层中除刺穿节点之外的各个节点的计算值，恢复出最后一层非刺穿叶节点的计算值。

在一个实施例中，混淆值接收模块1133接收的混淆值包括第一混淆值，该第一混淆值基于所述第一分片和所述第j棵完整树的第一侧叶节点的计算值确定；如此，叶节点确定模块1134具体配置为：

基于所述第一混淆值，所述第二分片，以及除第一刺穿叶节点之外的第一侧叶节点的恢复计算值，得到第一目标值，使得该第一目标值与所述第一刺穿叶节点在第j棵完整树中的对应节点的计算值之和，等于所述第一中间向量的第j个元素；

将所述第一目标值确定为所述第一刺穿叶节点的最终计算值；将除所述一对刺穿叶节点之外的其余叶节点的最终计算值确定为其恢复计算值的相反数。

根据一种实施方式，秘密分享单元112还配置为，通过执行所述向量秘密分享，得到第二中间向量的第二分片，对应的第一分片由第一方持有；其中该第二中间向量对应于第一方生成的第二随机数与所述第二噪声向量的乘积；如此使得，所述第j棵刺穿树还包括位于第二侧的第二刺穿叶节点，该第二刺穿叶节点的计算值与第j棵完整树中对应节点的计算值之和，等于第二中间向量的第j个元素。

在一种实施方式中，上述装置110还包括验证单元115，配置为：选择挑战数组，并将其发送给第一方；从第一方接收响应值，该响应值是由第一方根据所述挑战数组，所述第一随机数和第二随机数，以及所述t棵完整树的全部叶节点的计算值而确定；根据所述第二噪声向量，以及所述t棵刺穿树的全部叶节点的计算值，验证所述响应值是否符合预期；如此，元组形成单元116配置为，在对所述响应值验证通过之后，形成所述数据元组的一部分。

进一步的，在一个实施例中，验证单元115具体配置为，随机选择第一挑战数和第一数组作为挑战数组；从第一方接收第一响应值和第二响应值，所述第一响应值根据所述第一挑战数，对所述第一随机数和第二随机数执行第一运算而得到，所述第二响应值根据所述第一数组，对所述t棵完整树的全部叶节点的计算值进行第二运算而得到；根据所述第二噪声向量，对所述第一响应值进行进一步运算，得到第一验证值；在所述第二响应值基础上，叠加对所述t棵刺穿树的全部叶节点的计算值进行所述第二运算的结果，得到第二验证值；判断该第一验证值和第二验证值是否相等。

在一个实施例中，所述安全计算协议为伪随机VOLE协议；元组形成单元116具体配置为：基于所述第一噪声向量和预设的压缩矩阵，确定第二伪随机向量；基于所述第二分片向量和所述压缩矩阵，确定第三伪随机向量；该数据元组的另一部分包括基于所述第一分片向量确定的第一伪随机向量和第一随机数；其中，第二伪随机向量与所述第一随机数的乘积，叠加上第三伪随机向量的结果，等于所述第一伪随机向量。

通过以上的装置，可以为实现第一方和第二方协同，安全高效地生成安全计算协议的数据元组，更好地保护隐私数据安全性。

根据另一方面的实施例，还提供一种计算机可读存储介质，其上存储有计算机程序，当所述计算机程序在计算机中执行时，令计算机执行结合图3至图5所描述的方法。

根据再一方面的实施例，还提供一种计算设备，包括存储器和处理器，所述存储器中存储有可执行代码，所述处理器执行所述可执行代码时，实现结合图3至图5所述的方法。

本领域技术人员应该可以意识到，在上述一个或多个示例中，本发明所描述的功能可以用硬件、软件、固件或它们的任意组合来实现。当使用软件实现时，可以将这些功能存储在计算机可读介质中或者作为计算机可读介质上的一个或多个指令或代码进行传输。

以上所述的具体实施方式，对本发明的目的、技术方案和有益效果进行了进一步详细说明，所应理解的是，以上所述仅为本发明的具体实施方式而已，并不用于限定本发明的保护范围，凡在本发明的技术方案的基础之上，所做的任何修改、等同替换、改进等，均应包括在本发明的保护范围之内。

Claims (25)

1.一种生成安全计算协议的数据元组的方法，包括：

第一方生成第一随机数；

第二方随机生成稀疏的第一噪声向量，该第一噪声向量中包含的t个非零噪声点形成t维的第二噪声向量；

第一方和第二方通过秘密分享，分别得到第一中间向量的第一分片和第二分片，所述第一中间向量对应于第一随机数与第二噪声向量的乘积；

第一方构建t棵完整树，第二方和第一方进行安全交互，从而对应构建t棵刺穿树；其中任意第j棵刺穿树包括位于第一侧的第一刺穿叶节点，该第一刺穿叶节点的计算值与第j棵完整树中对应节点的计算值之和，等于第一中间向量的第j个元素；该第j棵刺穿树中各个非刺穿叶节点的计算值，与第j棵完整树中对应节点的计算值之和为零，第j棵完整树与第j棵刺穿树为结构相同的树形结构；

第一方和第二方，分别基于所述t棵完整树和所述t棵刺穿树的第一侧叶节点的计算值，形成第一分片向量和第二分片向量；

第一方和第二方，分别基于所述第一分片向量和第二分片向量，形成安全计算协议的数据元组。

2.根据权利要求1所述的方法，还包括：

第一方还生成第二随机数；

第一方和第二方通过所述秘密分享，还分别得到第二中间向量的第一分片和第二分片，其中该第二中间向量对应于所述第二随机数与第二噪声向量的乘积；

其中，所述第j棵刺穿树还包括位于第二侧的第二刺穿叶节点，该第二刺穿叶节点的计算值与第j棵完整树中对应节点的计算值之和，等于第二中间向量的第j个元素。

3.根据权利要求2所述的方法，还包括：

第二方选择挑战数组，并将其发送给第一方；

第一方根据所述挑战数组，所述第一随机数和第二随机数，以及所述t棵完整树的全部叶节点的计算值，计算响应值，并将其发送给第二方；

第二方根据所述第二噪声向量，以及所述t棵刺穿树的全部叶节点的计算值，验证所述响应值是否符合预期；

所述形成安全计算协议的数据元组，包括：

在第二方验证所述响应值符合预期的情况下，第一方和第二方分别形成所述数据元组。

4.根据权利要求3所述的方法，其中，所述挑战数组包括第一挑战数和第一数组；

所述计算响应值包括：第一方根据所述第一挑战数，对所述第一随机数和第二随机数执行第一运算，得到第一响应值；并根据所述第一数组，对所述t棵完整树的全部叶节点的计算值进行第二运算，得到第二响应值；

所述验证所述响应值是否正确，包括：根据所述第二噪声向量，对所述第一响应值进行进一步运算，得到第一验证值；在所述第二响应值基础上，叠加对所述t棵刺穿树的全部叶节点的计算值进行所述第二运算的结果，得到第二验证值；判断该第一验证值和第二验证值是否相等。

5.根据权利要求1所述的方法，其中，所述安全计算协议为伪随机VOLE协议；所述形成安全计算协议的数据元组，包括：

第一方基于所述第一分片向量和预设的压缩矩阵，确定第一伪随机向量；

第二方基于所述第一噪声向量和所述压缩矩阵，确定第二伪随机向量；并基于所述第二分片向量和所述压缩矩阵，确定第三伪随机向量；

其中，第二伪随机向量与所述第一随机数的乘积，叠加上第三伪随机向量的结果，等于所述第一伪随机向量。

6.一种生成安全计算协议的数据元组的方法，通过第一方执行，包括：

生成第一随机数；

与第二方执行秘密分享，得到第一中间向量的第一分片，对应的第二分片由第二方持有，其中所述第一中间向量对应于第一随机数与第二噪声向量的乘积，该第二噪声向量由第二方随机生成的稀疏的第一噪声向量中包含的t个非零噪声点形成；

构建t棵完整树；

与第二方进行安全交互，辅助其构建t棵刺穿树；使得任意第j棵刺穿树包括位于第一侧的第一刺穿叶节点，该第一刺穿叶节点的计算值与第j棵完整树中对应节点的计算值之和，等于第一中间向量的第j个元素；该第j棵刺穿树中各个非刺穿叶节点的计算值，与第j棵完整树中对应节点的计算值之和为零，第j棵完整树与第j棵刺穿树为结构相同的树形结构；

基于所述t棵完整树第一侧叶节点的计算值，形成第一分片向量；

基于所述第一分片向量，形成安全计算协议的数据元组的一部分，该数据元组的另一部分基于第二方持有的第二分片向量形成，所述第二分片向量基于所述t棵刺穿树第一侧叶节点的计算值形成。

7.根据权利要求6所述的方法，其中，构建t棵完整树，包括：

根据约定方式，将第一噪声向量的维度划分为t个区间，使得每个区间包含一个非零噪声点；

生成第j个树形结构，该树形结构在倒数第二层包括N个节点，其中N为第j个区间的元素数目；

从根节点开始到所述倒数第二层，利用第一伪随机生成算法，根据父节点的计算值确定两个子节点的计算值；

利用第二伪随机生成算法，根据倒数第二层各个节点的计算值，确定最后一层N对叶节点的计算值，从而得到第j棵完整树。

8.根据权利要求6所述的方法，其中，与第二方进行安全交互，辅助其构建t棵刺穿树，包括：

对于第j棵完整树，通过与第二方执行不经意传输OT协议，使得第二方恢复出对应树形结构的各个层中除刺穿节点之外的节点的计算值；

基于所述第一分片和所述第j棵完整树的叶节点的计算值，确定混淆值，将其发送给第二方，以使得第二方基于所述混淆值，所述第二分片，以及所述树形结构中恢复出的计算值，确定该树形结构中各个叶节点的最终计算值，从而得到第j棵刺穿树。

9.根据权利要求8所述的方法，其中，通过与第二方执行不经意传输OT协议，使得第二方恢复出对应树形结构的各个层中除刺穿节点之外的节点的计算值，包括：

对于第j棵完整树的各个中间层，计算第一取值和第二取值，其中第一取值为该中间层所有左侧节点的计算值的异或值，第二取值为该中间层所有右侧节点的计算值的异或值；

与第二方执行OT协议，使得第二方根据该中间层中的刺穿节点的位置选择第一取值和第二取值之一，并根据选择的取值恢复出该中间层中除刺穿节点之外的节点计算值。

10.根据权利要求6所述的方法，还包括：

生成第二随机数；

通过所述秘密分享，得到第二中间向量的第一分片，对应的第二分片由第二方持有；其中该第二中间向量对应于所述第二随机数与第二噪声向量的乘积；

其中，所述第j棵刺穿树还包括位于第二侧的第二刺穿叶节点，该第二刺穿叶节点的计算值与第j棵完整树中对应节点的计算值之和，等于第二中间向量的第j个元素。

11.根据权利要求10所述的方法，还包括：

从第二方接收挑战数组；

根据所述挑战数组，所述第一随机数和第二随机数，以及所述t棵完整树的全部叶节点的计算值，计算响应值，并将其发送给第二方，以使得第二方根据所述第二噪声向量，以及所述t棵刺穿树的全部叶节点的计算值，验证所述响应值是否符合预期；

形成安全计算协议的数据元组的一部分，包括：

在接收到表示第二方对所述响应值验证通过的指示之后，形成所述数据元组的一部分。

12.根据权利要求11所述的方法，所述挑战数组包括第一挑战数和第一数组；

所述计算响应值包括：根据所述第一挑战数，对所述第一随机数和第二随机数执行第一运算，得到第一响应值；并根据所述第一数组，对所述t棵完整树的全部叶节点的计算值进行第二运算，得到第二响应值。

13.根据权利要求6所述的方法，其中，所述安全计算协议为伪随机VOLE协议；形成安全计算协议的数据元组的一部分，包括：

基于所述第一分片向量和预设的压缩矩阵，确定第一伪随机向量，将所述第一伪随机向量和所述第一随机数作为所述数据元组的一部分；

该数据元组的另一部分包括基于所述第二分片向量确定的第二伪随机向量和第三伪随机向量；其中，第二伪随机向量与所述第一随机数的乘积，叠加上第三伪随机向量的结果，等于所述第一伪随机向量。

14.一种生成安全计算协议的数据元组的方法，通过第二方执行，包括：

随机生成稀疏的第一噪声向量，该第一噪声向量中包含的t个非零噪声点形成t维的第二噪声向量；

与第一方执行秘密分享，得到第一中间向量的第二分片，对应的第一分片由第一方持有，其中所述第一中间向量对应于第一方生成的第一随机数与所述第二噪声向量的乘积；

与第一方进行安全交互，从而基于第一方构建的t棵完整树，对应构建t棵刺穿树；其中任意第j棵刺穿树包括位于第一侧的第一刺穿叶节点，该第一刺穿叶节点的计算值与第j棵完整树中对应节点的计算值之和，等于第一中间向量的第j个元素；该第j棵刺穿树中各个非刺穿叶节点的计算值，与第j棵完整树中对应节点的计算值之和为零，第j棵完整树与第j棵刺穿树为结构相同的树形结构；

基于所述t棵刺穿树第一侧叶节点的计算值，形成第二分片向量；

基于所述第二分片向量，形成安全计算协议的数据元组的一部分，该数据元组的另一部分基于第一方持有的第一分片向量形成，所述第一分片向量基于所述t棵完整树第一侧叶节点的计算值形成。

15.根据权利要求14所述的方法，其中，对应构建t棵刺穿树，包括：

生成第j个树形结构，并根据第j个非零噪声点在第一噪声向量中的全局位置，确定该树形结构的各个层中的刺穿节点；

通过与第一方执行不经意传输OT协议，针对各个层中除刺穿节点之外的节点，恢复出与第j棵完整树对应节点相同的计算值；

从第一方接收混淆值，该混淆值基于第一方持有的所述第一分片和所述第j棵完整树的叶节点的计算值确定；

基于所述混淆值，所述第二分片，以及所述树形结构中恢复出的计算值，确定该树形结构中各个叶节点的最终计算值，从而得到第j棵刺穿树。

16.根据权利要求15所述的方法，其中，生成第j个树形结构，并根据第j个非零噪声点在第一噪声向量中的全局位置，确定该树形结构的各个层中的刺穿节点，具体包括：

根据约定方式，将第一噪声向量的维度划分为t个区间，使得每个区间包含一个非零噪声点；

确定第j个树形结构，该树形结构在倒数第二层包括N个节点，其中N为第j个区间的元素数目；

根据所述全局位置，以及所述t个区间的划分，确定所述第j个非零噪声点在所述第j个区间的相对位置；

根据所述相对位置确定刺穿路径，该刺穿路径沿父子节点关系连接各个中间层的刺穿节点，其中倒数第二层的N个节点中位于所述相对位置的目标节点作为该倒数第二层的刺穿节点，该目标节点的一对子节点作为叶节点层的一对刺穿叶节点。

17.根据权利要求15所述的方法，其中，通过与第一方执行不经意传输OT协议，针对各个层中除刺穿节点之外的节点，恢复出与第j棵完整树对应节点相同的计算值，具体包括：

对于各个中间层中除刺穿节点和与该刺穿节点共享同一父节点的配对节点之外的其余节点，利用第一伪随机生成算法，根据父节点的计算值确定所述其余节点的计算值；

与第一方执行OT协议，根据所述配对节点位于第一侧或第二侧的指示值，从第一方提供的第一取值和第二取值中选择其中之一作为目标取值，其中第一取值为第j棵完整树中该中间层所有第一侧节点的计算值的异或值，第二取值为第j棵完整树中该中间层所有第二侧节点的计算值的异或值；

根据所述目标取值，和与所述配对节点位于同一侧的节点的计算值，恢复得到所述配对节点的计算值；

利用第二伪随机生成算法，根据倒数第二层中除刺穿节点之外的各个节点的计算值，恢复出非刺穿叶节点的计算值。

18.根据权利要求15所述的方法，其中，所述混淆值包括第一混淆值，该第一混淆值基于所述第一分片和所述第j棵完整树的第一侧叶节点的计算值确定；所述确定该树形结构中各个叶节点的最终计算值，具体包括：

基于所述第一混淆值，所述第二分片，以及除第一刺穿叶节点之外的第一侧叶节点的恢复计算值，得到第一目标值，使得该第一目标值与所述第一刺穿叶节点在第j棵完整树中的对应节点的计算值之和，等于所述第一中间向量的第j个元素；

将所述第一目标值确定为所述第一刺穿叶节点的最终计算值；将非刺穿叶节点的最终计算值确定为其恢复计算值的相反数。

19.根据权利要求14所述的方法，还包括：

通过执行所述秘密分享，得到第二中间向量的第二分片，对应的第一分片由第一方持有；其中该第二中间向量对应于第一方生成的第二随机数与所述第二噪声向量的乘积；

其中，所述第j棵刺穿树还包括位于第二侧的第二刺穿叶节点，该第二刺穿叶节点的计算值与第j棵完整树中对应节点的计算值之和，等于第二中间向量的第j个元素。

20.根据权利要求19所述的方法，还包括：

选择挑战数组，并将其发送给第一方；

从第一方接收响应值，该响应值是由第一方根据所述挑战数组，所述第一随机数和第二随机数，以及所述t棵完整树的全部叶节点的计算值而确定；

根据所述第二噪声向量，以及所述t棵刺穿树的全部叶节点的计算值，验证所述响应值是否符合预期；

形成安全计算协议的数据元组的一部分，包括：

在对所述响应值验证通过之后，形成所述数据元组的一部分。

21.根据权利要求20所述的方法，其中：

选择挑战数组包括，随机选择第一挑战数和第一数组；

所述响应值包括第一响应值和第二响应值，所述第一响应值根据所述第一挑战数，对所述第一随机数和第二随机数执行第一运算而得到，所述第二响应值根据所述第一数组，对所述t棵完整树的全部叶节点的计算值进行第二运算而得到；

验证所述响应值是否符合预期，包括：根据所述第二噪声向量，对所述第一响应值进行进一步运算，得到第一验证值；在所述第二响应值基础上，叠加对所述t棵刺穿树的全部叶节点的计算值进行所述第二运算的结果，得到第二验证值；判断该第一验证值和第二验证值是否相等。

22.根据权利要求14所述的方法，其中，所述安全计算协议为伪随机VOLE协议；形成安全计算协议的数据元组的一部分，包括：

基于所述第一噪声向量和预设的压缩矩阵，确定第二伪随机向量；

基于所述第二分片向量和所述压缩矩阵，确定第三伪随机向量；

该数据元组的另一部分包括基于所述第一分片向量确定的第一伪随机向量和第一随机数；其中，第二伪随机向量与所述第一随机数的乘积，叠加上第三伪随机向量的结果，等于所述第一伪随机向量。

23.一种生成安全计算协议的数据元组的装置，部署在第一方中，包括：

随机数生成单元，配置为生成第一随机数；

秘密分享单元，配置为与第二方执行秘密分享，得到第一中间向量的第一分片，对应的第二分片由第二方持有，其中所述第一中间向量对应于第一随机数与第二噪声向量的乘积，该第二噪声向量由第二方随机生成的稀疏的第一噪声向量中包含的t个非零噪声点形成；

完整树构建单元，配置为构建t棵完整树；

刺穿树辅助单元，配置为与第二方进行安全交互，辅助其构建t棵刺穿树；其中任意第j棵刺穿树包括位于第一侧的第一刺穿叶节点，该第一刺穿叶节点的计算值与第j棵完整树中对应节点的计算值之和，等于第一中间向量的第j个元素；该第j棵刺穿树中各个非刺穿叶节点的计算值，与第j棵完整树中对应节点的计算值之和为零，第j棵完整树与第j棵刺穿树为结构相同的树形结构；

分片形成单元，配置为基于所述t棵完整树第一侧叶节点的计算值，形成第一分片向量；

元组形成单元，配置为基于所述第一分片向量，形成安全计算协议的数据元组的一部分，该数据元组的另一部分基于第二方持有的第二分片向量形成，所述第二分片向量基于所述t棵刺穿树第一侧叶节点的计算值形成。

24.一种生成安全计算协议的数据元组的方法，部署在第二方中，包括：

噪声向量生成单元，配置为随机生成稀疏的第一噪声向量，该第一噪声向量中包含的t个非零噪声点形成t维的第二噪声向量；

秘密分享单元，配置为与第一方执行向量秘密分享，得到第一中间向量的第二分片，对应的第一分片由第一方持有，其中所述第一中间向量对应于第一方生成的第一随机数与所述第二噪声向量的乘积；

刺穿树构建单元，配置为与第一方进行安全交互，从而基于第一方构建的t棵完整树，对应构建t棵刺穿树；其中任意第j棵刺穿树包括位于第一侧的第一刺穿叶节点，该第一刺穿叶节点的计算值与第j棵完整树中对应节点的计算值之和，等于第一中间向量的第j个元素；该第j棵刺穿树中各个非刺穿叶节点的计算值，与第j棵完整树中对应节点的计算值之和为零，第j棵完整树与第j棵刺穿树为结构相同的树形结构；

分片形成单元，配置为基于所述t棵刺穿树第一侧叶节点的计算值，形成第二分片向量；

元组形成单元，配置为基于所述第二分片向量，形成安全计算协议的数据元组的一部分，该数据元组的另一部分基于第一方持有的第一分片向量形成，所述第一分片向量基于所述t棵完整树第一侧叶节点的计算值形成。

25.一种计算设备，包括存储器和处理器，其特征在于，所述存储器中存储有可执行代码，所述处理器执行所述可执行代码时，实现权利要求6-22中任一项所述的方法。

Images