两方安全比较的方法、装置和系统

摘要

本说明书实施例提供一种两方安全比较的方法、装置和系统，用于确定第一数据是否小于第二数据的比较结果，第一数据和第二数据均以分片形式，分布在第一方和第二方，方法包括：第一方本地计算第一数据的第一方分片与第二数据的第一方分片的第一差值，并根据第一差值确定第一输入数据；第二方本地计算第一数据的第二方分片与第二数据的第二方分片的第二差值，并根据第二差值确定第二输入数据；第一方将第一输入数据输入多方安全算子，第二方将第二输入数据输入所述多方安全算子，用于对第一输入数据和第二输入数据进行求和，得到求和结果，并根据求和结果的最高位，确定所述比较结果。能够有效减小通信代价。

说明书

技术领域

本说明书一个或多个实施例涉及计算机领域，尤其涉及两方安全比较的方法、装置和系统。

背景技术

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

两方安全比较是安全多方计算的基本计算单元，用于对两方各自的数，或者两方分片的数，做安全比较，数不会泄露给非拥有方，可用于构造If-Else逻辑，MAX/MIN等功能，安全多方计算中的通用计算和隐私保护机器学习等。

发明内容

本说明书一个或多个实施例描述了一种两方安全比较的方法、装置和系统，能够有效减小通信代价。

第一方面，提供了一种两方安全比较的方法，用于确定第一数据是否小于第二数据的比较结果，所述第一数据和第二数据均以分片形式，分布在第一方和第二方，所述方法由第一方执行，包括：

本地计算所述第一数据的本方分片与第二数据的本方分片的第一差值，并根据所述第一差值确定第一输入数据；

将所述第一输入数据输入多方安全算子，所述多方安全算子还接收第二输入数据，用于对所述第一输入数据和第二输入数据进行求和，得到求和结果，并根据所述求和结果的最高位，确定所述比较结果；所述第二输入数据基于第二差值确定，所述第二差值为第二方基于第一数据的第二方分片与第二数据的第二方分片相减得到的值。

在一种可能的实施方式中，所述根据所述第一差值确定第一输入数据，包括：

将所述第一差值作为所述第一输入数据；或者，

将所述第一差值乘以第一常数后，得到所述第一输入数据。

在一种可能的实施方式中，所述多方安全算子为布尔电路，所述布尔电路采用混淆电路或GMW的执行方式。

进一步地，所述第一输入数据和所述第二输入数据均为L位二进制数；所述布尔电路用于执行如下计算过程：

针对所述第一输入数据和所述第二输入数据的当前位，计算所述求和结果的所述当前位。

在一种可能的实施方式中，所述根据所述求和结果的最高位，确定所述比较结果，包括：

当所述求和结果的最高位为1时，确定所述比较结果对应于第一数据小于第二数据；

当所述求和结果的最高位为0时，确定所述比较结果对应于第一数据大于或等于第二数据。

在一种可能的实施方式中，所述第一数据的第一方分片与所述第一数据的第二方分片之和为所述第一数据；所述第二数据的第一方分片与所述第二数据的第二方分片之和为所述第二数据。

在一种可能的实施方式中，所述比较结果为一位二进制数；

所述方法还包括：

生成第一随机比特，将所述第一随机比特作为所述比较结果的本方分片；

将所述第一随机比特输入所述多方安全算子，用于确定所述比较结果的第二方分片，将其输出给所述第二方。

进一步地，所述多方安全算子通过对所述比较结果和所述第一随机比特进行异或操作，得到所述比较结果的第二方分片。

第二方面，提供了一种两方安全比较的方法，用于确定第一数据是否小于第二数据的比较结果，所述第一数据和第二数据均以分片形式，分布在第一方和第二方，所述方法包括：

所述第一方本地计算所述第一数据的第一方分片与第二数据的第一方分片的第一差值，并根据所述第一差值确定第一输入数据；

所述第二方本地计算所述第一数据的第二方分片与第二数据的第二方分片的第二差值，并根据所述第二差值确定第二输入数据；

所述第一方将所述第一输入数据输入多方安全算子，所述第二方将所述第二输入数据输入所述多方安全算子，用于对所述第一输入数据和第二输入数据进行求和，得到求和结果，并根据所述求和结果的最高位，确定所述比较结果。

在一种可能的实施方式中，所述第一方根据所述第一差值确定第一输入数据，包括：

所述第一方将所述第一差值作为所述第一输入数据；

所述第二方根据所述第二差值确定第二输入数据，包括：

所述第二方将所述第二差值作为所述第二输入数据。

第三方面，提供了一种两方安全比较的装置，用于确定第一数据是否小于第二数据的比较结果，所述第一数据和第二数据均以分片形式，分布在第一方和第二方，所述装置设置于第一方，包括：

本地计算单元，用于本地计算所述第一数据的本方分片与第二数据的本方分片的第一差值，并根据所述第一差值确定第一输入数据；

联合计算单元，用于将所述本地计算单元得到的第一输入数据输入多方安全算子，所述多方安全算子还接收第二输入数据，用于对所述第一输入数据和第二输入数据进行求和，得到求和结果，并根据所述求和结果的最高位，确定所述比较结果；所述第二输入数据基于第二差值确定，所述第二差值为第二方基于第一数据的第二方分片与第二数据的第二方分片相减得到的值。

第四方面，提供了一种两方安全比较的系统，用于确定第一数据是否小于第二数据的比较结果，所述第一数据和第二数据均以分片形式，分布在第一方和第二方，所述系统包括：

所述第一方，用于本地计算所述第一数据的第一方分片与第二数据的第一方分片的第一差值，并根据所述第一差值确定第一输入数据；

所述第二方，用于本地计算所述第一数据的第二方分片与第二数据的第二方分片的第二差值，并根据所述第二差值确定第二输入数据；

所述第一方，还用于将所述第一输入数据输入多方安全算子，所述第二方，还用于将所述第二输入数据输入所述多方安全算子，用于对所述第一输入数据和第二输入数据进行求和，得到求和结果，并根据所述求和结果的最高位，确定所述比较结果。

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

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

通过本说明书实施例提供的方法、装置和系统，用于确定第一数据是否小于第二数据的比较结果，所述第一数据和第二数据均以分片形式，分布在第一方和第二方，首先第一方本地计算所述第一数据的第一方分片与第二数据的第一方分片的第一差值，并根据所述第一差值确定第一输入数据；第二方本地计算所述第一数据的第二方分片与第二数据的第二方分片的第二差值，并根据所述第二差值确定第二输入数据；然后第一方将所述第一输入数据输入多方安全算子，第二方将所述第二输入数据输入所述多方安全算子，用于对所述第一输入数据和第二输入数据进行求和，得到求和结果，并根据所述求和结果的最高位，确定所述比较结果。由上可见，本说明书实施例，为了实现对第一数据和第二数据进行比较，先通过第一方和第二方各自进行本地计算，分别得到第一输入数据和第二输入数据，再利用多方安全算子对所述第一输入数据和第二输入数据进行求和，得到求和结果，并根据所述求和结果的最高位，确定所述比较结果，这种方式不需要对第一数据的分片和第二数据的分片做合并，多方安全算子减少了一次加法运算，并且只需要基于所述求和结果的最高位，确定所述比较结果，相对于两个数据的比较更为简单，因此相对于通常的处理方式，能够有效减小通信代价。

附图说明

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

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

图2示出根据一个实施例的两方安全比较的方法交互示意图；

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

图4示出根据一个实施例的两方安全比较的装置的示意性框图；

图5示出根据一个实施例的两方安全比较的系统的示意性框图。

具体实施方式

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

图1为本说明书披露的一个实施例的实施场景示意图。该实施场景涉及两方安全比较，用于确定第一数据是否小于第二数据的比较结果，所述第一数据和第二数据均以分片形式，分布在第一方和第二方。各方可以实现为任何具有计算处理能力的设备、平台、服务器或设备集群。参照图1，第一数据a可以表示为L位二进制数，第一方具有a的一个分片a0，第二方具有a的另一个分片a1，a＝a0+a1；第二数据b也可以表示为L位二进制数，第一方具有b的一个分片b0，第二方具有b的另一个分片b1，b＝b0+b1。可以理解的是，第一数据、第二数据均属于隐私数据，第一方和第二方仅具有上述隐私数据的分片，而不能获知隐私数据。两方安全比较，即在保护上述隐私数据不会泄露的前提下，确定第一数据是否小于第二数据的比较结果，比较结果可以以分片的形式存在于第一方和第二方。

其中，两方安全比较，即实现如下计算：两方有两个数据的加法分片，数据a＝a0+a1，数据b＝b0+b1，第一方拥有a0和b0，第二方拥有a1和b1，确定a＜b的比较结果。输出：第一方获得比较结果的第一分片r0，第二方获得比较结果的第二分片r1，r＝r0^r1，可以理解的是，比较结果为1比特，r0和r1为异或分片。

异或分片(XORShare)，一个比特串用异或拆分为的两个比特分片。两个异或分片做异或可以获得原比特串，两方各持有一个异或分片。

第一数据和第二数据的分片形式具体称为加法分片(ADDShare)，一个数在模2

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

通常的两方安全比较的电路实现方案包括：在电路完成对两个数据的加法分片做合并，即得到a＝a0+a1,b＝b0+b1；再对数据a和数据b做比较得到比较结果r。

本说明书实施例提供的方案，先由两方对各自拥有的两个数据的加法分片分别做减法，将加法分片的差值输入电路，在电路中做加法算出两个数据的差值，再与零做比较。该方案的电路省去了一个加法，并且小于零的比较只需要看符号位是否为1，减少了与门个数以及与门深度，能够有效减小通信代价。其中，通信代价包括通信量和通信轮数。

图2示出根据一个实施例的两方安全比较的方法交互示意图，该方法可以基于图1所示的实施场景，用于确定第一数据是否小于第二数据的比较结果，所述第一数据和第二数据均以分片形式，分布在第一方和第二方。如图2所示，该实施例中两方安全比较的方法包括以下步骤：步骤21，第一方本地计算所述第一数据的第一方分片与第二数据的第一方分片的第一差值，并根据所述第一差值确定第一输入数据；步骤22，第二方本地计算所述第一数据的第二方分片与第二数据的第二方分片的第二差值，并根据所述第二差值确定第二输入数据；步骤23，第一方将所述第一输入数据输入多方安全算子，第二方将所述第二输入数据输入所述多方安全算子，用于对所述第一输入数据和第二输入数据进行求和，得到求和结果，并根据所述求和结果的最高位，确定所述比较结果。下面描述以上各个步骤的具体执行方式。

首先在步骤21，第一方本地计算所述第一数据的第一方分片与第二数据的第一方分片的第一差值，并根据所述第一差值确定第一输入数据。可以理解的是，第一输入数据通过第一方本地计算得到，上述本地计算至少包括计算第一差值。

在一个示例中，所述第一数据的第一方分片与所述第一数据的第二方分片之和为所述第一数据；所述第二数据的第一方分片与所述第二数据的第二方分片之和为所述第二数据。

在一个示例中，所述根据所述第一差值确定第一输入数据，包括：

将所述第一差值作为所述第一输入数据；或者，

将所述第一差值乘以第一常数后，得到所述第一输入数据。

举例来说，第一数据的第一方分片为a0，第二数据的第一方分片为b0，上述第一差值为a0-b0，可以直接将所述第一差值作为所述第一输入数据，也就是说，第一输入数据v0＝a0-b0；也可以将所述第一差值乘以第一常数后，得到所述第一输入数据，上述第一常数为第一方与第二方共享的约定数据，例如，第一常数为2时，v0＝2(a0-b0)。

然后在步骤22，第二方本地计算所述第一数据的第二方分片与第二数据的第二方分片的第二差值，并根据所述第二差值确定第二输入数据。可以理解的是，第二输入数据通过第二方本地计算得到，上述本地计算至少包括计算第二差值。

在一个示例中，所述第二方根据所述第二差值确定第二输入数据，包括：

所述第二方将所述第二差值作为所述第二输入数据；或者，

将所述第二差值乘以第一常数后，得到所述第二输入数据。

举例来说，第一数据的第二方分片为a1，第二数据的第二方分片为b1，上述第二差值为a1-b1，可以直接将所述第二差值作为所述第二输入数据，也就是说，第二输入数据v1＝a1-b1；也可以将将所述第二差值乘以第一常数后，得到所述第二输入数据，上述第一常数为第一方与第二方共享的约定数据，例如，第一常数为2时，v1＝2(a1-b1)。

本说明书实施例中，第一输入数据和第二输入数据的确定方式有多种可能的组合，例如，第一输入数据v0＝a0-b0，第二输入数据v1＝a1-b1；第一输入数据v0＝2(a0-b0)，第二输入数据v1＝2(a1-b1)；第一输入数据v0＝0.5(a0-b0)，第二输入数据v1＝0.5(a1-b1)等等，可能的情况有很多，在此不再一一赘述。

最后在步骤23，第一方将所述第一输入数据输入多方安全算子，第二方将所述第二输入数据输入所述多方安全算子，用于对所述第一输入数据和第二输入数据进行求和，得到求和结果，并根据所述求和结果的最高位，确定所述比较结果。可以理解的是，根据第一输入数据和第二输入数据的具体确定方式，上述求和结果可能为第一数据和第二数据的差值，或者，该差值的第一常数倍。

本说明书实施例，多方安全算子可以基于多方安全计算的任一种执行方式实现，可以但不限于包括秘密分享、同态加密、混淆电路等。

在一个示例中，所述多方安全算子为布尔电路，所述布尔电路采用混淆电路或GMW的执行方式。

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

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

进一步地，所述第一输入数据和所述第二输入数据均为L位二进制数；所述布尔电路用于执行如下计算过程：

针对所述第一输入数据和所述第二输入数据的当前位，计算所述求和结果的所述当前位。

可以理解的是，该实施例中第一输入数据和第二输入数据均为L位二进制数，那么求和结果也为L位二进制数，可以分别计算出求和结果的各个位，其中，在计算求和结果的当前位时，至少根据所述第一输入数据和所述第二输入数据的当前位，对于当前位非首位时，还要考虑上一位的进位。

在一个示例中，所述根据所述求和结果的最高位，确定所述比较结果，包括：

当所述求和结果的最高位为1时，确定所述比较结果对应于第一数据小于第二数据；

当所述求和结果的最高位为0时，确定所述比较结果对应于第一数据大于或等于第二数据。

该示例中，可以直接将所述求和结果的最高位作为所述比较结果，当所述求和结果的最高位为1时，确定所述比较结果为1，用于表示第一数据小于第二数据；当所述求和结果的最高位为0时，确定所述比较结果为0，用于表示第一数据大于或等于第二数据。

在一个示例中，所述比较结果为一位二进制数；

所述方法还包括：

第一方生成第一随机比特，将所述第一随机比特作为所述比较结果的本方分片；

第一方将所述第一随机比特输入所述多方安全算子，用于确定所述比较结果的第二方分片，将其输出给所述第二方。

进一步地，所述多方安全算子通过对所述比较结果和所述第一随机比特进行异或操作，得到所述比较结果的第二方分片。

可以理解的是，当所述多方安全算子为布尔电路时，上述异或操作可以通过异或门实现。

本说明书实施例的布尔电路与通常的用于两方安全比较的布尔电路，在输入和电路结构上均有明显的差别。上述布尔电路的输入包括第一方的第一输入数据、第二方的第二输入数据，而不包括第一方和第二方各自具有的第一数据的分片和第二数据的分片；上述布尔电路的电路结构仅需要对第一输入数据和第二输入数据进行一次加法运算，而不需要对第一数据和第二数据的加法分片分别做合并，减少了一次加法运算，并且根据求和结果的最高位确定比较结果，相对于两个多位二进制数的比较要简单得多，电路明显变小，包括与门数和与门深度都变小。

图3示出根据一个实施例的布尔电路结构示意图。参照图3，布尔电路包括求和模块、结果确定模块和拆分模块，其输入包括第一方具有的第一输入数据v0、第一随机比特r0，第二方具有的第二输入数据v1。求和模块用于对第一输入数据和第二输入数据进行加法运算，得到求和结果v；结果确定模块用于提取求和结果v的最高位，作为比较结果r；拆分模块用于对第一随机比特r0和比较结果r进行异或操作，得到r1，r1作为该布尔电路的输出，将其输出给第二方。

通过本说明书实施例提供的方法，用于确定第一数据是否小于第二数据的比较结果，所述第一数据和第二数据均以分片形式，分布在第一方和第二方，首先第一方本地计算所述第一数据的第一方分片与第二数据的第一方分片的第一差值，并根据所述第一差值确定第一输入数据；第二方本地计算所述第一数据的第二方分片与第二数据的第二方分片的第二差值，并根据所述第二差值确定第二输入数据；然后第一方将所述第一输入数据输入多方安全算子，第二方将所述第二输入数据输入所述多方安全算子，用于对所述第一输入数据和第二输入数据进行求和，得到求和结果，并根据所述求和结果的最高位，确定所述比较结果。由上可见，本说明书实施例，为了实现对第一数据和第二数据进行比较，先通过第一方和第二方各自进行本地计算，分别得到第一输入数据和第二输入数据，再利用多方安全算子对所述第一输入数据和第二输入数据进行求和，得到求和结果，并根据所述求和结果的最高位，确定所述比较结果，这种方式不需要对第一数据的分片和第二数据的分片做合并，多方安全算子减少了一次加法运算，并且只需要基于所述求和结果的最高位，确定所述比较结果，相对于两个数据的比较更为简单，因此相对于通常的处理方式，能够有效减小通信代价。

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

本地计算单元41，用于本地计算所述第一数据的本方分片与第二数据的本方分片的第一差值，并根据所述第一差值确定第一输入数据；

联合计算单元42，用于将所述本地计算单元41得到的第一输入数据输入多方安全算子，所述多方安全算子还接收第二输入数据，用于对所述第一输入数据和第二输入数据进行求和，得到求和结果，并根据所述求和结果的最高位，确定所述比较结果；所述第二输入数据基于第二差值确定，所述第二差值为第二方基于第一数据的第二方分片与第二数据的第二方分片相减得到的值。

可选地，作为一个实施例，所述本地计算单元41，具体用于：

将所述第一差值作为所述第一输入数据；或者，

将所述第一差值乘以第一常数后，得到所述第一输入数据。

可选地，作为一个实施例，所述多方安全算子为布尔电路，所述布尔电路采用混淆电路或GMW的执行方式。

进一步地，所述第一输入数据和所述第二输入数据均为L位二进制数；所述布尔电路用于执行如下计算过程：

针对所述第一输入数据和所述第二输入数据的当前位，计算所述求和结果的所述当前位。

可选地，作为一个实施例，所述多方安全算子，具体用于：

当所述求和结果的最高位为1时，确定所述比较结果对应于第一数据小于第二数据；

当所述求和结果的最高位为0时，确定所述比较结果对应于第一数据大于或等于第二数据。

可选地，作为一个实施例，所述第一数据的第一方分片与所述第一数据的第二方分片之和为所述第一数据；所述第二数据的第一方分片与所述第二数据的第二方分片之和为所述第二数据。

可选地，作为一个实施例，所述比较结果为一位二进制数；

所述装置还包括：

生成单元，用于生成第一随机比特，将所述第一随机比特作为所述比较结果的本方分片；

所述联合计算单元42，还用于将所述第一随机比特输入所述多方安全算子，用于确定所述比较结果的第二方分片，将其输出给所述第二方。

进一步地，所述多方安全算子通过对所述比较结果和所述第一随机比特进行异或操作，得到所述比较结果的第二方分片。

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

第一方51，用于本地计算所述第一数据的第一方分片与第二数据的第一方分片的第一差值，并根据所述第一差值确定第一输入数据；

第二方52，用于本地计算所述第一数据的第二方分片与第二数据的第二方分片的第二差值，并根据所述第二差值确定第二输入数据；

所述第一方51，还用于将所述第一输入数据输入多方安全算子，所述第二方52，还用于将所述第二输入数据输入所述多方安全算子，用于对所述第一输入数据和第二输入数据进行求和，得到求和结果，并根据所述求和结果的最高位，确定所述比较结果。

可选地，作为一个实施例，所述第一方51，具体用于将所述第一差值作为所述第一输入数据；

所述第二方52，具体用于将所述第二差值作为所述第二输入数据。

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

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

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

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