两方安全选择确定选择结果分片的方法、装置和系统

摘要

本说明书实施例提供一种两方安全选择确定选择结果分片的方法、装置和系统，所述两方安全选择用于根据选择值，在第一方拥有的N个数据中进行选择，所述选择值以分片形式，分布在第一方和第二方，采用多方安全计算实现，如混淆电路。方法包括：第一方生成第一随机数，并将其作为选择结果的第一分片；第一方本地计算所述N个数据分别与所述第一随机数的第一差值，并将N个第一差值确定为N个第一输入数据；所述第一方与所述第二方联合执行安全选择算子，所述安全选择算子基于所述选择值在所述N个第一输入数据中选择目标输入数据，将其作为所述选择结果的第二分片输出给第二方。能够有效减小通信代价。

说明书

技术领域

本说明书一个或多个实施例涉及计算机领域，尤其涉及两方安全选择确定选择结果分片的方法、装置和系统。

背景技术

安全多方计算又称为多方安全计算，即多方共同计算出一个函数的结果，而不泄露这个函数各方的输入数据，计算的结果公开给其中的一方或多方。其中，各方的输入数据常常为隐私数据。

两方安全选择是安全多方计算的基本计算单元，可用于构造If-Else逻辑，MAX/MIN等功能，安全多方计算中的通用计算和隐私保护机器学习等。

发明内容

本说明书一个或多个实施例描述了一种两方安全选择确定选择结果分片的方法、装置和系统，能够有效减小通信代价。

第一方面，提供了一种两方安全选择确定选择结果分片的方法，所述两方安全选择用于根据选择值，在第一方拥有的N个数据中进行选择，所述选择值以分片形式，分布在第一方和第二方，该方法由第一方执行，包括：

生成第一随机数，并将其作为选择结果的第一分片；

本地计算所述N个数据分别与所述第一随机数的第一差值，并将N个第一差值确定为N个第一输入数据；

与所述第二方联合执行安全选择算子，所述安全选择算子基于所述选择值在所述N个第一输入数据中选择目标输入数据，将其作为所述选择结果的第二分片输出给第二方。

在一种可能的实施方式中，所述安全选择算子为布尔电路；所述与所述第二方联合执行安全选择算子，包括：

将所述N个第一输入数据、所述选择值的第一方分片输入布尔电路，所述布尔电路还接收第二方输入的所述选择值的第二方分片，并根据所述选择值，在所述N个第一输入数据中选择目标输入数据。

进一步地，所述布尔电路用于执行如下计算过程：

对所述选择值的第一方分片和所述选择值的第二方分片进行加法运算，得到所述选择值；

根据所述选择值，在所述N个第一输入数据中选择目标输入数据。

进一步地，所述选择值为L位二进制数，所述加法运算通过L个加法子单元分别确定所述选择值的各个位，每个加法子单元具有不多于一个与门。

在一种可能的实施方式中，所述N个数据具有第一排序；所述N个第一输入数据具有对应于所述N个数据的第一排序；

所述与所述第二方联合执行安全选择算子，包括：

根据所述选择值，确定与所述选择值对应的所述第一排序中的位置编号；

在所述N个第一输入数据中，选择出具有所述位置编号的第一输入数据。

在一种可能的实施方式中，所述选择值的第一方分片与所述选择值的第二方分片之和为所述选择值，所述选择值的可选取值数目大于或等于N。

进一步地，所述布尔电路采用混淆电路或GMW的执行方式。

第二方面，提供了一种两方安全选择确定选择结果分片的方法，所述两方安全选择用于根据选择值，在第一方拥有的N个数据中进行选择，所述选择值以分片形式，分布在第一方和第二方，方法包括：

所述第一方生成第一随机数，并将其作为选择结果的第一分片；

所述第一方本地计算所述N个数据分别与所述第一随机数的第一差值，并将N个第一差值确定为N个第一输入数据；

所述第一方与所述第二方联合执行安全选择算子，所述安全选择算子基于所述选择值在所述N个第一输入数据中选择目标输入数据，将其作为所述选择结果的第二分片输出给第二方。

第三方面，提供了一种两方安全选择确定选择结果分片的装置，所述两方安全选择用于根据选择值，在第一方拥有的N个数据中进行选择，所述选择值以分片形式，分布在第一方和第二方，该装置设置于第一方，包括：

生成单元，用于生成第一随机数，并将其作为选择结果的第一分片；

本地计算单元，用于本地计算所述N个数据分别与所述生成单元生成的第一随机数的第一差值，并将N个第一差值确定为N个第一输入数据；

联合处理单元，用于与所述第二方联合执行安全选择算子，所述安全选择算子基于所述选择值在所述本地计算单元得到的N个第一输入数据中选择目标输入数据，将其作为所述选择结果的第二分片输出给第二方。

第四方面，提供了一种两方安全选择确定选择结果分片的系统，所述两方安全选择用于根据选择值，在第一方拥有的N个数据中进行选择，所述选择值以分片形式，分布在第一方和第二方，系统包括：

所述第一方，用于生成第一随机数，并将其作为选择结果的第一分片；本地计算所述N个数据分别与所述第一随机数的第一差值，并将N个第一差值确定为N个第一输入数据；

所述第一方与所述第二方，用于联合执行安全选择算子，所述安全选择算子基于所述选择值在所述N个第一输入数据中选择目标输入选择，将其作为所述选择结果的第二分片输出给第二方。

第五方面，提供了一种计算机可读存储介质，其上存储有计算机程序，当所述计算机程序在计算机中执行时，令计算机执行第一方面或第二方面的方法。

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

通过本说明书实施例提供的方法、装置和系统，两方安全选择用于根据选择值，在第一方拥有的N个数据中进行选择，所述选择值以分片形式，分布在第一方和第二方，首先第一方生成第一随机数，并将其作为选择结果的第一分片；然后第一方本地计算所述N个数据分别与所述第一随机数的第一差值，并将N个第一差值确定为N个第一输入数据；最后第一方与第二方联合执行安全选择算子，所述安全选择算子基于所述选择值在所述N个第一输入数据中选择目标输入数据，将其作为所述选择结果的第二分片输出给第二方。由上可见，本说明书实施例，为了实现选择结果以分片的形式输出，先通过第一方生成选择结果的一个分片，并进行本地计算，得到N个第一输入数据，再从N个第一输入数据中进行选择，这种方式不需要通过减法对选择结果做拆分，只需要针对N个第一输入数据做选择，选择出的目标输入数据作为选择结果的另一个分片，相对于通常的处理方式，能够有效减小通信代价。

附图说明

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

图1为本说明书披露的一个实施例的实施场景示意图；

图2示出根据一个实施例的两方安全选择确定选择结果分片的方法交互示意图；

图3示出根据一个实施例的布尔电路结构示意图；

图4示出根据一个实施例的两方安全选择确定选择结果分片的装置的示意性框图；

图5示出根据一个实施例的两方安全选择确定选择结果分片的系统的示意性框图。

具体实施方式

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

图1为本说明书披露的一个实施例的实施场景示意图。该实施场景涉及两方安全选择，用于根据选择值，在第一方拥有的N个数据中进行选择，所述选择值以分片形式，分布在第一方和第二方。参照图1，第一方有N个数据{v

加法分片，一个数在模2

对以上两方安全选择，可以通过安全选择算子来实现，安全选择算子可以但不限于为布尔电路。布尔电路(boolean circuit)，是一组用连接线连接的逻辑门的集合，能对一组输入完成函数计算并输出结果。逻辑门包括与门(AND)、异或门(XOR)、非门(NOT)等实现布尔函数的门，一般一个函数可以编译成一组与门、异或门和非门完成计算。

通常的两方安全选择的电路实现方案包括：根据s，对N个数据{v

本说明书实施例提供的方案，对N个数据进行本地处理后再输入布尔电路，布尔电路只需要针对输入数据做选择，而不需要对结果做拆分，也就是说不需要减法电路，电路明显变小，包括与门数和与门深度都变小，能够有效减小通信代价。其中，通信代价包括通信量和通信轮数。

图2示出根据一个实施例的两方安全选择确定选择结果分片的方法交互示意图，该方法可以基于图1所示的实施场景，所述两方安全选择用于根据选择值，在第一方拥有的N个数据中进行选择，所述选择值以分片形式，分布在第一方和第二方。如图2所示，该实施例中两方安全选择确定选择结果分片的方法包括以下步骤：步骤21，第一方生成第一随机数，并将其作为选择结果的第一分片；步骤22，第一方本地计算所述N个数据分别与所述第一随机数的第一差值，并将N个第一差值确定为N个第一输入数据；步骤23，第一方与第二方联合执行安全选择算子，所述安全选择算子基于所述选择值在所述N个第一输入数据中选择目标输入数据，将其作为所述选择结果的第二分片输出给第二方。下面描述以上各个步骤的具体执行方式。

首先在步骤21，第一方生成第一随机数，并将其作为选择结果的第一分片。可以理解的是，可以采用通常的任一种随机数生成方式生成第一随机数。

本说明书实施例，选择结果以分片的形式存在于第一方和第二方，单个分片并不具有任何意义，因此可以随意选取选择结果的第一分片。

然后在步骤22，第一方本地计算所述N个数据分别与所述第一随机数的第一差值，并将N个第一差值确定为N个第一输入数据。可以理解的是，第一输入数据通过第一方本地计算得到，上述N个数据与N个第一输入数据一一对应。

举例来说，第一随机数为v

最后在步骤23，第一方与第二方联合执行安全选择算子，所述安全选择算子基于所述选择值在所述N个第一输入数据中选择目标输入数据，将其作为所述选择结果的第二分片输出给第二方。可以理解的是，目标输入数据为N个第一输入数据中的一个第一输入数据，安全选择算子不需要对目标输入数据进行拆分。

在一个示例中，所述安全选择算子为布尔电路；所述与所述第二方联合执行安全选择算子，包括：

将所述N个第一输入数据、所述选择值的第一方分片输入布尔电路，所述布尔电路还接收第二方输入的所述选择值的第二方分片，并根据所述选择值，在所述N个第一输入数据中选择目标输入数据。

本说明书实施例的上述布尔电路与通常的用于两方安全选择的布尔电路，在输入和电路结构上均有明显的差别。上述布尔电路的输入包括第一方的N个第一输入数据，而不包括第一方初始具有的N个数据；上述布尔电路的电路结构不需要对选择结果做拆分，只需要对N个第一输入数据做选择，电路明显变小，包括与门数和与门深度都变小。

图3示出根据一个实施例的布尔电路结构示意图。参照图3，布尔电路包括选择模块，其输入包括第一方具有的N个第一输入数据{v

进一步地，所述布尔电路用于执行如下计算过程：

对所述选择值的第一方分片和所述选择值的第二方分片进行加法运算，得到所述选择值；

根据所述选择值，在所述N个第一输入数据中选择目标输入数据。

举例来说，第一方具有N个第一输入数据{v

s＝s0+s1；

输出{v

进一步地，所述选择值为L位二进制数，所述加法运算通过L个加法子单元分别确定所述选择值的各个位，每个加法子单元具有不多于一个与门。

可以理解的是，通过尽量减少加法运算所需要的与门数量可以进一步减少布尔电路的通信代价。

在一个示例中，所述N个数据具有第一排序；所述N个第一输入数据具有对应于所述N个数据的第一排序；

所述与所述第二方联合执行安全选择算子，包括：

根据所述选择值，确定与所述选择值对应的所述第一排序中的位置编号；

在所述N个第一输入数据中，选择出具有所述位置编号的第一输入数据。

该示例中，由于第一输入数据是通过对第一方初始具有的数据进行本地计算得到的，因此N个第一输入数据可以具有对应于所述N个数据的第一排序，根据该排序可以实现根据选择值选择目标输入数据。例如，N的取值为4，N个第一输入数据{v

在一个示例中，所述选择值的第一方分片与所述选择值的第二方分片之和为所述选择值，所述选择值的可选取值数目大于或等于N。

该示例中，选择值的可选取值数目大于或等于N，从而通过选择值能够唯一确定从N个第一输入数据中选择的目标输入数据，例如，N的取值为4，N个第一输入数据{v

进一步地，所述布尔电路采用混淆电路或GMW的执行方式。

混淆电路(garbled circuit，GC)，是一种两方安全多方计算协议，对实现一个计算函数的布尔电路用密码函数生成混淆表，对两方输入计算出结果，并且在计算过程一方输入不会泄漏给另一方。目前混淆电路最优的实现方案，对异或门和非门不需要通信，只需要本地计算，与门需要调用密码计算并进行通信，并且在一般应用场景中通信量是吞吐量上限的瓶颈。混淆电路的通信量与布尔电路的与门数正相关。

GMW(Goldreich-Micali-Wigderson)，是一种两方安全多方计算协议，实现一个计算函数的布尔电路，其每根线上的比特都是两方的异或分片，即每方对该线各持有一个比特，两个比特异或即为线上真值，GMW对每个门计算，异或门直接本地计算，与门用不经意传输执行。GMW执行布尔电路，两方交互的轮数，即执行延迟由电路中的与门的深度决定。与门的深度指电路中数据相关的与门的最长路径。

通过本说明书实施例提供的方法，为了实现选择结果以分片的形式输出，先通过第一方生成选择结果的一个分片，并进行本地计算，得到N个第一输入数据，再从N个第一输入数据中进行选择，这种方式不需要通过减法对选择结果做拆分，只需要针对N个第一输入数据做选择，选择出的目标输入数据作为选择结果的另一个分片，相对于通常的处理方式，能够有效减小通信代价。

此外，当本说明书实施例提供的方法与布尔电路相结合时，为了实现选择结果以分片的形式输出，不是直接将第一方初始具有的N个数据输入布尔电路，而是先通过第一方进行本地计算，得到N个第一输入数据，将N个第一输入数据输入布尔电路，上述布尔电路不需要选择结果做拆分，只需要针对输入的N个第一输入数据做选择，相对于通常的电路结构，少了用于拆分选择结果的减法电路，电路明显变小，包括与门数和与门深度都变小，从而能够有效减小通信代价。

根据另一方面的实施例，还提供一种两方安全选择确定选择结果分片的装置，所述两方安全选择用于根据选择值，在第一方拥有的N个数据中进行选择，所述选择值以分片形式，分布在第一方和第二方，所述装置设置于第一方，用于执行本说明书实施例提供的方法中第一方执行的动作。图4示出根据一个实施例的两方安全选择确定选择结果分片的装置的示意性框图。如图4所示，该装置400包括：

生成单元41，用于生成第一随机数，并将其作为选择结果的第一分片；

本地计算单元42，用于本地计算所述N个数据分别与所述生成单元41生成的第一随机数的第一差值，并将N个第一差值确定为N个第一输入数据；

联合处理单元43，用于与所述第二方联合执行安全选择算子，所述安全选择算子基于所述选择值在所述本地计算单元42得到的N个第一输入数据中选择目标输入数据，将其作为所述选择结果的第二分片输出给第二方。

可选地，作为一个实施例，所述安全选择算子为布尔电路；所述联合处理单元43，具体用于将所述N个第一输入数据、所述选择值的第一方分片输入布尔电路，所述布尔电路还接收第二方输入的所述选择值的第二方分片，并根据所述选择值，在所述N个第一输入数据中选择目标输入数据。

进一步地，所述布尔电路用于执行如下计算过程：

对所述选择值的第一方分片和所述选择值的第二方分片进行加法运算，得到所述选择值；

根据所述选择值，在所述N个第一输入数据中选择目标输入数据。

进一步地，所述选择值为L位二进制数，所述加法运算通过L个加法子单元分别确定所述选择值的各个位，每个加法子单元具有不多于一个与门。

可选地，作为一个实施例，所述N个数据具有第一排序；所述N个第一输入数据具有对应于所述N个数据的第一排序；

所述联合处理单元43，具体用于：

根据所述选择值，确定与所述选择值对应的所述第一排序中的位置编号；

在所述N个第一输入数据中，选择出具有所述位置编号的第一输入数据。

可选地，作为一个实施例，所述选择值的第一方分片与所述选择值的第二方分片之和为所述选择值，所述选择值的可选取值数目大于或等于N。

进一步地，所述布尔电路采用混淆电路或GMW的执行方式。

根据另一方面的实施例，还提供一种两方安全选择确定选择结果分片的系统，所述两方安全选择用于根据选择值，在第一方拥有的N个数据中进行选择，所述选择值以分片形式，分布在第一方和第二方，所述系统包括第一方和第二方，用于执行本说明书实施例提供的方法中第一方和第二方执行的动作。图5示出根据一个实施例的两方安全选择确定选择结果分片的系统的示意性框图。如图5所示，该系统500包括：

第一方51，用于生成第一随机数，并将其作为选择结果的第一分片；本地计算所述N个数据分别与所述第一随机数的第一差值，并将N个第一差值确定为N个第一输入数据；

第一方51与第二方52，用于联合执行安全选择算子，所述安全选择算子基于所述选择值在所述N个第一输入数据中选择目标输入数据，将其作为所述选择结果的第二分片输出给第二方52。

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

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

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

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