CN114282076B - 一种基于秘密分享的排序方法和系统 - Google Patents

Abstract

本说明书涉及数据安全领域，特别涉及一种基于秘密分享的排序方法和系统，用于获取能够将待排序数据列的元素进行顺序排列的目标排序向量，该方法由第一参与方执行且包括至少两轮迭代，最后一轮迭代得到的第二排序向量的第一分片为所述目标排序向量的第一分片；在其中一轮迭代后，第一参与方得到第二排序向量的第一分片，第二参与方获得第二排序向量的第二分片。

Description

一种基于秘密分享的排序方法和系统

技术领域

本说明书涉及数据安全领域，特别涉及一种基于秘密分享的排序方法和系统。

背景技术

数据在当今世界，起着越来越重要的作用，在很多应用场景下数据已成为一种资源需要对其进行保护。在实际业务场景中，由于需要保护数据隐私安全和数据隔离等原因，经常会遇到一些棘手的问题。例如，参与业务的多个合作者，希望共同完成建模、统计分析等任务，但是由于数据隐私和数据隔离等原因，无法将数据进行直接融合建模或统计分析。密码学中用于解决多方安全计算的工具可以用于实现这类该任务。

因此，本说明书提供了一种基于秘密分享的排序方法和系统，可作为一些多方安全计算的底层实现。

发明内容

本说明书实施例之一提供一种基于秘密分享的排序方法，用于获取能够将待排序数据列的元素进行顺序排列的目标排序向量，排序向量用于标识对等长序列进行排序的操作，其元素指示所述等长序列中的对位元素在结果序列中的位置；第一参与方拥有二进制形式的待排序数据列的第一分片，第二参与方拥有二进制形式的待排序数据列的第二分片；该方法由第一参与方执行且包括至少两轮迭代，最后一轮迭代得到的第二排序向量的第一分片为所述目标排序向量的第一分片；其中一轮迭代包括：在待排序数据列第一分片的每个元素中取同一位的子元素，得到第一位列的第一分片；基于第一位列的第一分片和第一排序向量的第一分片，与第二参与方基于第一位列的第二分片和第一排序向量的第二分片，通过秘密分享排序算法，得到第一排序位列的第一分片，第二参与方获得第一排序位列的第二分片；所述第一排序位列等于使用第一排序向量对所述第一位列进行排序的结果序列；当所述一轮迭代为第一轮迭代时，所述第一排序向量为元素顺序排列的初始排序向量，否则所述第一排序向量为前一轮迭代得到的第二排序向量；基于第一排序位列的第一分片得到拓展标志序列的第一分片；其中，所述拓展标志序列包括均与第一排序位列等长的第一子序列和第二子序列；所述第一子序列的元素反映所述第一排序位列中的对位元素是否为第一数值；所述第二子序列的元素反映所述第一排序位列中的对位元素是否为第二数值；基于所述拓展标志序列的第一分片确定中间排序向量的第一分片，所述中间排序向量能够将第一位列中的元素进行顺序排列；基于第一排序向量的第一分片和所述中间排序向量的第一分片，与第二参与方基于第一排序向量的第二分片和所述中间排序向量的第二分片，通过秘密分享合并算法，得到第二排序向量的第一分片，第二参与方获得第二排序向量的第二分片；基于第二排序向量对等长序列进行排序的结果序列等于基于所述第一排序向量和中间排序向量对所述等长序列进行迭代排序的结果序列。

本说明书实施例之一提供一种基于秘密分享的排序系统，用于获取能够将待排序数据列的元素进行顺序排列的目标排序向量，排序向量用于标识对等长序列进行排序的操作，其元素指示所述等长序列中的对位元素在结果序列中的位置；第一参与方拥有二进制形式的待排序数据列的第一分片，第二参与方拥有二进制形式的待排序数据列的第二分片；该系统部署于第一参与方且用于进行至少两轮迭代，最后一轮迭代得到的第二排序向量的第一分片为所述目标排序向量的第一分片；所述系统包括第一位列分片获取模块、第一排序位列分片获取模块、拓展标志序列分片获取模块、中间排序向量分片确定模块和第二排序向量分片获取模块；在其中一轮迭代中：所述第一位列分片获取模块，用于在待排序数据列第一分片的每个元素中取同一位的子元素，得到第一位列的第一分片；所述第一排序位列分片获取模块，用于基于第一位列的第一分片和第一排序向量的第一分片，与第二参与方基于第一位列的第二分片和第一排序向量的第二分片，通过秘密分享排序算法，得到第一排序位列的第一分片，第二参与方获得第一排序位列的第二分片；所述第一排序位列等于使用第一排序向量对所述第一位列进行排序的结果序列；当所述一轮迭代为第一轮迭代时，所述第一排序向量为元素顺序排列的初始排序向量，否则所述第一排序向量为前一轮迭代得到的第二排序向量；所述拓展标志序列分片获取模块，用于基于第一排序位列的第一分片得到拓展标志序列的第一分片；其中，所述拓展标志序列包括均与第一排序位列等长的第一子序列和第二子序列；所述第一子序列的元素反映所述第一排序位列中的对位元素是否为第一数值；所述第二子序列的元素反映所述第一排序位列中的对位元素是否为第二数值；所述中间排序向量分片确定模块，用于基于所述拓展标志序列的第一分片确定中间排序向量的第一分片，所述中间排序向量能够将第一位列中的元素进行顺序排列；所述第二排序向量分片获取模块，用于基于第一排序向量的第一分片和所述中间排序向量的第一分片，与第二参与方基于第一排序向量的第二分片和所述中间排序向量的第二分片，通过秘密分享合并算法，得到第二排序向量的第一分片，第二参与方获得第二排序向量的第二分片；基于第二排序向量对等长序列进行排序的结果序列等于基于所述第一排序向量和中间排序向量对所述等长序列进行迭代排序的结果序列。

本说明书实施例之一提供一种基于秘密分享的排序装置，包括处理器，所述处理器用于执行上述的基于秘密分享的排序方法。

附图说明

本说明书将以示例性实施例的方式进一步说明，这些示例性实施例将通过附图进行详细描述。这些实施例并非限制性的，在这些实施例中，相同的编号表示相同的结构，其中：

图1是根据本说明书一些实施例所示的基于秘密分享的排序方法的示意图；

图2是根据本说明书一些实施例所示的生成排序向量的示意图；

图3是根据本说明书一些实施例所示的基于秘密分享的排序方法的示例性交互流程图；

图4是根据本说明书一些实施例所示的秘密分享排序算法的示意图；

图5是根据本说明书一些实施例所示的秘密分享合并算法的示意图；

图6是根据本说明书一些实施例所示的基于秘密分享的排序系统的示例性系统框图。

具体实施方式

为了更清楚地说明本说明书实施例的技术方案，下面将对实施例描述中所需要使用的附图作简单的介绍。显而易见地，下面描述中的附图仅仅是本说明书的一些示例或实施例，对于本领域的普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图将本说明书应用于其它类似情景。除非从语言环境中显而易见或另做说明，图中相同标号代表相同结构或操作。

应当理解，本文使用的“系统”、“装置”、“单元”和/或“模块”是用于区分不同级别的不同组件、元件、部件、部分或装配的一种方法。然而，如果其他词语可实现相同的目的，则可通过其他表达来替换所述词语。

如本说明书和权利要求书中所示，除非上下文明确提示例外情形，“一”、“一个”、“一种”和/或“该”等词并非特指单数，也可包括复数。一般说来，术语“包括”与“包含”仅提示包括已明确标识的步骤和元素，而这些步骤和元素不构成一个排它性的罗列，方法或者设备也可能包含其它的步骤或元素。

本说明书中使用了流程图用来说明根据本说明书的实施例的系统所执行的操作。应当理解的是，前面或后面操作不一定按照顺序来精确地执行。相反，可以按照倒序或同时处理各个步骤。同时，也可以将其他操作添加到这些过程中，或从这些过程移除某一步或数步操作。

多方安全计算能让参与的各方在不暴露各自数据隐私的情况下，实现基于各方联合数据的任务目标等。

在多方安全计算的过程中，经常会遇到对数据进行顺序排序（比如，升序排序或降序排序）的情况。例如，以机器学习的样本特征排序为例，在进行机器学习的模型训练时，可能会存在对训练样本集中的特征数据和标签数据进行排序的需求。比如，将特征数据按照其数值大小从小到大进行排序。除了机器学习场景外，基于顺序排序还可以用于其他多种场景，如统计分析场景。需要说明的是，以上例子仅出于示例的目的，本说明书所披露的技术方案可以适用于元素间具有顺序关系的任意序列，本说明书对此不作限定。

在待排序序列以明文的形式存在时，其可以很容易的实现排序。然而，当数据基于秘密共享以数据分片的形式存在于两方或多方时，由于各方无法得知数据分片的所对应的原始数据，也就是不能得知原始数据之间的大小关系，对其进行排序也就变得极为困难。因此，本说明书中的一些实施例提供了一种基于秘密分享的排序方法和系统，可以在有效地保护数据隐私安全的情况下实现对隐私数据的顺序排序。本说明书一些实施例提供的基于秘密分享的排序方法可以通过图1所示的算子表示，该排序方法或算子的输入数据包括待排序序列X（也可称为待排序数据列）的分片，输出数据包括能够对待排序数据列进行顺序排序的目标排序向量p的分片。其中，<>表示密态形式，具体可以是基于秘密分享的数据分片，所述分片可以是加性分片，即原始数据（或隐私数据）的各分片之和等于该原始数据。在一些实施例中，将向量或序列的每一个元素拆分为分片形式，向量或序列各元素的一个分片组成的新的向量或序列可以作为原始向量或原始序列的分片。继续以图1为例，在一些场景中，参与多方安全计算的包括两方，如A方和B方，A方持有待排序数据列的第一分片

，B方持有待排序数据列的第二分片

，双方基于各自持有的分片通过图1所示的基于秘密分享的排序方法或排序算子，A方可以得到目标排序向量的第一分片

，B方可以得到目标排序向量的第二分片

。

在通过附图详细阐述本说明书实施例所披露的技术方案之前，先介绍排序向量的概念。

图2是根据本说明书一些实施例所示的生成排序向量的示意图。排序向量用于标识对等长序列进行排序的操作，其元素指示所述等长序列中的对位元素在结果序列中的位置。如图2所示，假设存在一个数据列K，其包括5个元素，index列标识了5个元素在数据列K中的位置，需要对数据列K进行字典升序排序（即按照字母顺序进行排序）。对数据列K进行排序后，得到数据列K’。同时参考new index列，K的第1个元素a的新下标（即在数据列K’的位置）为0，第2个元素b的新下标为2，以此类推，最终得到描述K——>K'这个排列操作的排序向量p为 [0, 2, 1, 4, 3]。排序向量的引入可以便捷的将排序操作进行量化，在一些实施例中，排序向量p可以作为一个排列函数作用在数据列K上，可以表示为

。

图3是根据本说明书一些实施例所示的基于秘密分享的排序方法的示例性交互流程图。

在一些实施例中，基于秘密分享的排序方法可以包括至少两轮迭代，其中一轮迭代的交互流程如图3所示，该方法可以由第一参与方和第二参与方协同完成，其中，最后一轮迭代得到的第二排序向量的分片为所述目标排序向量的分片。

如前文中所述，待排序数据列以分片的形式存储于第一参与方和第二参与方，其中，分片可以是加性分片（和分片），分片之和为原始数据。需要说明的是，“第一”、“第二”仅用于区分存储于不同参与方的分片。当本说明书提及序列的分片时，主要是指将序列的各元素分别进行拆分，序列的第一分片包含序列各元素的其中一个分片，序列的第二分片包括序列各元素的另一个分片。示例性的，假设待排序数据列

，在一些实施例中，第一参与方持有的待排序数据列的第一分片可以是

，第二参与方持有的待排序数据列的第二分片可以是

。需要说明的是，第一参与方和第二参与方在交互过程中，中间数据可以分片的形式存储于各方，但分片的形式可以是多样的，为了便于描述，后文中不再对分片一一进行说明。

在一些实施例中，参与方持有的待排序数据列分片是以二进制的形式存储于各方且基于二进制的形式进行传输或计算。继续采用前述示例，设待排序数列

，将其通过二进制形式可以表示为

，相应的，第一参与方持有的待排序数据列的第一分片可以是

，第二参与方持有的待排序数据列的第二分片可以是

需要说明的是，二进制形式的数据列中的元素根据实际需要，可以设置不同位数（bit），例如，在一些其他实施例中，待排序数列

还可以表示为位数为3的二进制形式的序列

。

在一些实施例中，交互流程中的步骤310A~350A中的一个或多个步骤可以由第一参与方执行，流程310B~350B中的一个或多个步骤可以由第二参与方执行，所述至少两轮迭代中的其中一轮迭代的交互流程包括：

步骤310A，第一参与方在待排序数据列第一分片的每个元素中取同一位的子元素，得到第一位列的第一分片。在一些实施例中，步骤310A可由第一位列分片获取模块610执行。

步骤310B，第二参与方在待排序数据列第二分片的每个元素中取同一位的子元素，得到第一位列的第二分片。

在一些实施例中，待排序数据列为二进制形式，通过在其每个元素中取同一位的子元素得到的第一位列，显然也是二进制形式。作为示例，第一参与方持有的待排序数据列的第一分片可以是

，取待排序数据列的第一分片的每个元素的最低位，则可以得到位列

，作为某一轮迭代中的第一位列的第一分片。所述至少两轮迭代中的每一轮迭代对应于待排序数据列中的一个位列，因此迭代轮数与待排序数据列中元素的位数相同。例如，当使用2位数表示待排序数据列中的元素时，迭代数量为2。

以第一参与方为例，在一些实施例中，当所述一轮迭代为第一轮迭代时，在待排序数据列第一分片的每个元素中取最低位的子元素，得到所述第一位列的第一分片；当所述一轮迭代为第二轮迭代时，在待排序数据列第一分片的每个元素中取次低位的子元素，得到所述第一位列的第一分片；以此类推，当所述一轮迭代为最后一轮迭代时，在待排序数据列第一分片的每个元素中取最高位的子元素，得到所述第一位列的第一分片。

如前述示例，第一参与方持有的待排序数据列的第一分片可以是

，则在第一轮迭代时，第一位列的第一分片为对应于最低位即“0”位列

的第一分片，即

，在第二轮（最后一轮）迭代时，第一位列的第一分片为对应于最高位即“1”位

的第一分片

。对应的，在第一轮迭代时，第一位列的第二分片为

，在第二轮（最后一轮）迭代时，第一位列的第二分片为

。

第二参与方在每轮迭代中获取第一位列的第二分片的方式与之类似，在此不再赘述。

步骤320A，第一参与方基于第一位列的第一分片和第一排序向量的第一分片，与第二参与方通过秘密分享排序算法，得到第一排序位列的第一分片。在一些实施例中，步骤320A可由第一排序位列分片获取模块620执行。

步骤320B，第二参与方基于第一位列的第二分片和第一排序向量的第二分片，与第一参与方通过秘密分享排序算法，获得第一排序位列的第二分片。

在一些实施例中，第一排序位列等于使用第一排序向量对所述第一位列进行排序的结果序列。在一些实施例中，当所述一轮迭代为第一轮迭代时，第一排序向量可以是预设的向量，例如，所述第一排序向量为元素顺序排列的初始排序向量。当当前轮迭代不为第一轮时，第一排序向量为前一轮迭代得到的第二排序向量，关于第二排序向量的更多描述可以参见后文步骤350的描述。

以第一轮迭代进行明文示例，第一排序向量为元素顺序排列的初始排序向量，在一些实施例中，初始排序向量可以为第一项为0，且公差为1的等差数列。例如，第一排序向量可以表示为

。

在一些实施例中，初始排序向量第一项还可以是除0以外其他数值，如1、2、5等，公差也可以是除1以外的其他数值，在本说明书中不做限制，能够保证每个元素有唯一标识即可，示例性的，在一些实施例中，第一排序向量

可以是(1,2,3,4)或(2,3,4,5)。

在一些实施例中，双方可以预先约定好初始排序向量，并分别获得初始排序向量的分片。示例性的，第一参与方可以按照上述方法生成初始排序向量

，再将其随机拆分成两个分片，并将其中一个分片发送给第二参与方。或者，通过第三方生成初始排序向量，并将其随机拆分成两个分片，然后这两个分片分发给第一参与方和第二参与方。

以明文作为示例，在第一轮迭代中，若第一排序向量

，第一位列

，则基于第一排序向量对第一位列进行排序，可以得到第一排序位列

。由于本说明书一些实施例中，第一排序向量和第一位列都是以分片形式分布于各参与方，因此，第一参与方和第二参与方需要基于自身持有的分片，通过秘密分享排序算法完成前述排序过程，得到第一排序位列的分片。

参考图4，在一些实施例中，所述秘密分享排序算法可以描述为使用各参与方（例如，第一参与方和第二参与方）持有的秘密分享的排列函数（或称为排列序列、排序向量），将一个长度为n的秘密分享序列进行秘密排列，得到仍然以秘密分享的形式存在的排列结果。例如，以π表示排列函数，其以秘密分享形式存储于各参与方（如π的第一分片存储于第一方，π的第二分片存储于第二方），X表示待排列序列，其以秘密分享形式存储于各参与方（如X的第一分片存储于第一方，X的第二分片存储于第二方）处，

表示排列结果，也以秘密分享形式由各参与方获得（如

的第一分片由第一参与方获得，

的第二分片由第二参与方获得），秘密排序过程中，各方持有的数据不会被其他方知晓。

所述秘密分享排序算法又可记为

函数或算子：

，其中<>表示密文形式，具体可以是分片形式。

函数可以理解为一个功能函数，其一组输入数据包括排列函数的第一分片

和待排列序列的第一分片

，来自第一参与方，其另一组输入数据包括排列函数的第二分片

和待排列序列的第二分片

，来自第二参与方；其输出数据为包括结果序列的第一分片

和第二分片

，结果序列的第一分片由第一参与方获得，结果序列的第二分片由第二参与方获得。

在一些实施例中，两方的处理设备可以分别执行

函数中的流程，目前已有

函数的多种实现方式，本说明书不对其内部实现算法进行限制，只将其作为黑盒算子进行调用。应当理解，凡是目前已经出现的以及未来会出现的，能够实现

函数功能的数据处理/运算单元、程序代码、机器学习模型等各种方式均可作为本说明书提到的基于秘密分享排列协议。

以第一参与方和第二参与方协同作为示例，其中，第一参与方持有待排序序列的第一分片和排序序列的第一分片，第二参与方持有待排序序列的第二分片和排序序列的第二分片，

函数的一种实现方式可以包括：

第一参与方基于待排序序列的第一分片，与所述第二参与方基于所述待排序序列的第二分片，通过第一秘密分享排列协议，获得待排序乱序序列的第一分片；所述第二参与方获得所述待排序乱序序列的第二分片；

第一参与方基于排序序列的第一分片，与所述第二参与方基于所述排序序列的第二分片，通过第一秘密分享排列协议，获得乱序排序序列的第一分片；所述第二参与方获得所述乱序排序序列的第二分片；且对排序序列的乱序方式与待排序序列的乱序方式相同；

第一参与方从所述第二参与方获得所述乱序排序序列的第二分片，得到所述乱序排列序列；

第一参与方基于所述乱序排序序列和所述待排序乱序序列的第一分片，与所述第二参与方基于所述待排序乱序序列的第二分片，通过第一秘密分享排列协议，获得结果序列的第一分片；第二参与方获得结果序列的第二分片；所述结果序列等于基于所述排序序列对所述待排序序列进行排序的结果。

示例性的，所述基于待排序序列的第一分片，与所述第二参与方基于所述待排序序列的第二分片，通过第一秘密分享排列协议，获得待排序乱序序列的第一分片；所述第二参与方获得所述待排序乱序序列的第二分片，进一步包括：

第一参与方生成第一随机排序序列；

第一参与方基于所述第一随机排序序列以及所述待排序序列的第一分片，与第二参与方基于所述待排序序列的第二分片，通过第一秘密分享排列协议，获得第一乱序中间序列的第一分片；第二参与方获得第一乱序中间序列的第二分片；

第一参与方基于所述第一乱序中间序列的第一分片，与第二参与方基于第一乱序中间序列的第二分片以及第二随机排序序列，通过第一秘密分享排列协议，获得所述待排序乱序序列的第一分片；第二参与方获得待排序乱序序列的第二分片，所述第二随机排序序列由第二参与方生成。

上述第一秘密分享排列协议可以是基于秘密分享进行的另一排列算法或算子，在一些实施例中可以描述为使用一方（例如，第一参与方或第二参与方）私有的排列函数（或称为排列序列、排序向量），将一个长度为

的秘密分享序列进行秘密排列，得到仍然以秘密分享的形式存在的排列结果。例如，以p表示一方私有的排列函数，k1表示待排列序列，其以秘密分享形式存储于各参与方（如k1的第一分片存储于第一参与方，k1的第二分片存储于第二参与方）处，k1'表示排列结果，也以秘密分享形式由各参与方获得（如k1'的第一分片由第一参与方获得，k1'的第二分片由第二参与方获得），秘密排序过程中，各方持有的数据不会被其他方知晓。秘密分享排列协议又可记为ObliviousPerm函数或算子：

，<>表示密文形式，具体可以是分片形式。ObliviousPerm函数可以理解为一个功能函数，其一组输入数据包括排列函数

和待排列序列的第一分片

，来自第一参与方，其另一组输入数据包括待排列序列的第二分片

，来自第二参与方；其输出数据为包括结果序列的第一分片

和第二分片

，结果序列的第一分片由第一参与方获得，结果序列的第二分片由第二参与方获得。

目前已有ObliviousPerm函数的多种实现方式，本说明书不对其内部实现算法进行限制，只将其作为黑盒算子进行调用。应当理解，凡是目前已经出现的以及未来会出现的，能够实现ObliviousPerm函数功能的数据处理/运算单元、程序代码、机器学习模型等各种方式均可作为本说明书提到的基于秘密分享排列协议。

以第一参与方和第二参与方协同作为示例，其中，第一参与方持有目标排序向量、待排序数据列的第一分片，第二参与方持有所述待排序数据列的第二分片，ObliviousPerm函数的一种实现方式可以包括：

第一参与方从可信第三方获取第一排序向量、第一数据列的第一分片和基于所述第一排序向量对所述第一数据列进行排序的第一结果序列的第一分片。第二参与方从可信第三方处获取第一数据列的第二分片和第一结果序列的第二分片。

第一参与方基于目标排序向量和所述第一排序向量确定第二排序向量，并将其发送给第二参与方；在一些实施例中，基于所述第一排序向量对所述目标排序向量进行排序，得到的结果序列可以作为所述第二排序向量。

第一参与方将待排序数据列的第一分片与第一数据列的第一分片作差，获得第二数据列的第一分片，同时从第二方获取第二数据列的第二分片；第二数据列的第二分片为第二参与方将待排序数据列的第二分片与第一数据列的第二分片作差得到。

第一参与方基于第二数据列的第一分片以及第二数据列的第二分片，获得第二数据列，并基于目标排序向量对第二数据列进行排序，得到第二结果数据列；基于第二排序向量对所述第一结果数据列的第一分片进行排序，得到第三结果数据列；最后，对第二结果数据列和第三结果数据列求和，获得目标数据列的第一分片。

第二参与方基于第二排序向量对第一结果序列的第二分片进行排序，获得目标数据列的第二分片。所述目标数据列等于基于所述目标排序向量对所述待排序数据列进行排序的结果序列。

以第一轮迭代为例，第一参与方和第二参与方可以基于各自持有的第一排序向量的分片

、第一位列的分片

协同执行秘密分享排序算法

，得到第一排序位列的分片

。

步骤330A，第一参与方基于第一排序位列的第一分片得到拓展标志序列的第一分片。在一些实施例中，步骤330A可由拓展标志序列分片获取模块630执行。

步骤330B，第二参与方基于第一排序位列的第二分片得到拓展标志序列的第二分片。

在一些实施例中，所述拓展标志序列包括均与第一排序位列等长的第一子序列和第二子序列；所述第一子序列的元素反映所述第一排序位列中的对位元素是否为第一数值；所述第二子序列的元素反映所述第一排序位列中的对位元素是否为第二数值。

在一些实施例中，所述第一数值为0，所述第二数值为1。第一排序位列中的某元素为0时，第一子序列的对位元素则为1，否则为0；第一排序位列中的某元素为1时，第二子序列的对位元素则为1，否则为0。以第一排序位列

作为明文示例，则可以得到第一子序列为（0,1,0,1），第二子序列为（1,0,1,0）。在一些实施例中，第一子序列和第二子序列可以是两个序列也可以首尾相接形成一个序列（0,1,0,1,1,0,1,0），即在一些实施例中，拓展标志序列

。可以验证，以此方式得到的拓展标志序列为前提，得到的中间排序向量能够将第一排序位列进行升序排序。

在本说明书的一些实施例中，由于第一参与方基于第一排序位列的第一分片得到拓展标志序列的第一分片，第二参与方基于第一排序位列的第二分片得到拓展标志序列的第二分片，其分别利用分片形式的序列得到另一序列的分片，为避免造成隐私数据的泄露，确保各方独立计算结果为分片形式，在一些实施例中，第一参与方可以对第一预设位列与第一排序位列的第一分片按位求差，得到所述拓展标志序列的第一子序列的第一分片；所述第一预设位列与第二参与方的第二预设位列按位求和的结果为全1序列；第一参与方将所述第一排序位列的第一分片作为所述拓展标志序列的第二子序列的第一分片。在一些实施例中，第一预设位列和第二预设位列可以是参与方预先约定好的、第三方随机生成的或是通过伪随机数种子生成的，示例性的，若第一预设位列为（1,1,1,0），易得第二预设位列为（0,0,0,1）。第一参与方可以对第一预设位列与第一排序位列的第一分片按位求差，得到所述拓展标志序列的第一子序列的第一分片，第二参与方可以对第二预设位列与第一排序位列的第二分片按位求差，得到所述拓展标志序列的第一子序列的第二分片，由于在升序排列情况下，第二子序列的元素反映所述第一排序位列中的对位元素是否为1，因此，对于第一参与方和第二参与方，第一排序位列的分片可以直接作为所述拓展标志序列的第二子序列的分片。

在一些替代性实施例中，所述第一数值可以为1，所述第二数值可以为0，第一参与方可以对第一预设位列与第一排序位列的第一分片按位求差，得到所述拓展标志序列的第二子序列的第一分片；第二参与方可以对第二预设位列与第一排序位列按位求差，得到所述拓展标志序列的第二子序列的第二分片。对于第一参与方和第二参与方，可以将所述第一排序位列的分片直接作为所述拓展标志序列的第一子序列的分片。可以验证，以此方式得到的拓展标志序列为前提，得到的中间排序向量能够将第一排序位列进行降序排序。

步骤340A，基于所述拓展标志序列的第一分片确定中间排序向量的第一分片。在一些实施例中，步骤340A可由中间排序向量分片确定模块640执行。

步骤340B，基于所述拓展标志序列的第二分片确定中间排序向量的第二分片。

其中，中间排序向量能够将第一位列中的元素进行顺序排列。在明文形式下，为了基于拓展标志序列得到中间排序向量，可以先对所述拓展标志序列

进行前缀求和，可以得到拓展求和序列

，之后再将所述拓展标志序列

与所述拓展求和序列

按位相乘，得到拓展排序序列

，最后将所述拓展排序序列

中的第一子序列和第二子序列按位求和，可以得到所述中间排序向量。

接下来，接前述进行明文示例，对拓展标志序列

进行前缀求和，可以得到拓展求和序列

。从前述示例，不难看出，拓展求和序列的第i位元素等于拓展标志序列中第i位元素以及其前面全部元素的和。以拓展求和序列的第3位元素为例，其等于拓展标志序列中第0~3位元素的和，因此拓展求和序列的第3位元素值为2。

再将拓展标志序列

与拓展求和序列

按位相乘，得到拓展排序序列

，最后将所述拓展排序序列

中的第一子序列

和第二子序列

按位求和，可以得到向量

，考虑到序列中首位元素的下标从0开始，因此，需要将向量

逐位减1，得到所述中间排序向量

。

在一些实施例中，第一参与方与第二参与方需要在密态形式下完成上述明文过程，得到密态形式的中间排序相片，此过程可以包括：

第一参与方可以首先对所述拓展标志序列的第一分片进行前缀求和得到拓展求和序列的第一分片。第二参与方可以首先对所述拓展标志序列的第二分片进行前缀求和得到拓展求和序列的第二分片。

此后，第一参与方需要基于所述拓展标志序列的第一分片和所述拓展求和序列的第一分片，与第二参与方基于所述拓展标志序列的第二分片和所述拓展求和序列的第二分片，通过秘密分享乘法协议，得到所述拓展排序序列的第一分片，第二参与方获得拓展排序序列的第二分片。

在一些实施例中，秘密分享乘法协议可以描述为一方持有私有数据a，另一方持有私有数据b，通过计算

，并将秘密分享形式的乘积结果存储于各参与方（如结果的第一分片

存储于第一方，结果的第二分片

存储于第二方），秘密分享乘法计算过程中，各方持有的数据不会被其他方知晓。

在一些实施例中，两方的处理设备可以分别执行秘密分享乘法协议。目前已有秘密分享乘法协议的多种实现方式，本说明书不对其内部实现算法进行限制，只将其作为黑盒算子进行调用。应当理解，凡是目前已经出现的以及未来会出现的，能够实现秘密分享乘法协议功能的数据处理/运算单元、程序代码、机器学习模型等各种方式均可作为本说明书提到的基于秘密分享乘法协议。

以获取拓展排序序列的第一个元素为例，第一参与方可以基于所述拓展标志序列的第一分片的第一个元素a1和所述拓展求和序列的第一分片的第一个元素b1，与第二参与方基于所述拓展标志序列的第二分片的第一个元素a2和所述拓展求和序列的第二分片的第一个元素b2，计算所述拓展排序序列的第一个元素

，其中，

、

可以分别在第一参与方和第二参与方本地完成。

、

则需要第一参与方与第二参与方分别执行秘密分享乘法协议分别得到这两项乘积的分片，最终，第一参与方可以得到所述拓展排序序列的第一分片的第一个元素

，第二参与方获得拓展排序序列的第二分片

。以此类推，第一参与方可以得到所述拓展排序序列的第一分片的剩余元素，第二参与方可以得到所述拓展排序序列的第二分片的剩余元素。

第一参与方再将所述拓展排序序列

的第一分片中的第一子序列和第二子序列按位求和，可以得到所述中间排序向量的第一分片。第二参与方将所述拓展排序序列

的第二分片中的第一子序列和第二子序列按位求和，可以得到所述中间排序向量的第二分片。如果定义初始排序向量为第一项为0，即序列中首位元素的下标从0开始，第一参与方还需要将按位求和的结果中的每个元素分别减第一预设值，得到所述中间排序向量的第一分片；相应的，第二参与方将其按位求和的结果中的每个元素分别减第二预设值，得到所述中间排序向量的第二分片，其中第一参与方的第一预设值与第二参与方的第二预设值的和为1。

需要说明的是，在一些实施例中，第一预设值和第二预设值的和根据初始排序向量的形式还可以是其他取值，采用前述另一示例第一排序向量

为(2,3,4,5)为例，为了使序列的首位元素的下标从2开始，取第一预设值和第二预设值的和为-1，即按位求和的结果中的每个元素分别+1，得到所述中间排序向量。

在一些实施例中，中间排序向量能够将第一排序位列中的元素进行顺序排列，即中间排序向量中的元素能够反映第一排序位列中元素值为0和1在排列后的位置。继续采用上述示例，结合图2，中间排序向量

可以将第一排序位列

中的元素按升序排列，得到序列

。

在一些实施例中，为了保护第一参与方和第二参与方的隐私数据，与第一预设位列和第二预设位列相似，第一预设值和第二预设值可以是参与方预先约定好的、第三方随机生成的或是通过伪随机数种子生成的。示例性的，在一些实施例中，第一参与方的第一预设值与第二参与方的第二预设值的和为1，则第一预设值可以是5，第二预设值可以是-4。

步骤350A，第一参与方基于第一排序向量的第一分片和所述中间排序向量的第一分片，与第二参与方通过秘密分享合并算法，得到第二排序向量的第一分片。在一些实施例中，步骤350A可由第二排序向量分片获取模块650执行。

步骤350B，第二参与方基于第一排序向量的第二分片和所述中间排序向量的第二分片，与第一参与方通过秘密分享合并算法，得到第二排序向量的第二分片。

在一些实施例中，基于第二排序向量对等长序列进行排序的结果序列等于基于所述第一排序向量和中间排序向量对所述等长序列进行迭代排序的结果序列。

合并算法可以描述为将多个排列向量，合并成一个新的排序向量，使得新的排序向量对一个长度为n的序列进行排列的结果等同于分别利用多个排列向量依次对该序列进行迭代排列的结果。例如，以p1表示第一排列向量，p2表示第二排列向量，通过合并算法可以得到一个合并后的排序向量p，使得对于对一个长度为n的序列k满足

。

以明文下的多轮迭代为例，对待排序数据列任一非0位列进行顺序排序，首先需要将前面一轮或多轮迭代排序操作施加在当前轮迭代的非0位列上，再对排序后的非0位列按照元素大小顺序排序，因此，需要在每轮迭代中获取能够标识已完成的多轮迭代排序操作的排序向量，即需要将第一排序向量与中间排序向量进行合并，得到能够标识已完成的多轮迭代排序操作的第二排序向量。

需要说明的是，在一些实施例中，排序向量的合并具有方向性，或者说是有顺序的。续前例，假定合并排序向量p1、p2得到排序向量p，那么满足：p(k)=p2(p1(k))。即，合并得到的排序向量（可称为合并排序向量）标识的是先使用排序向量p1对等长序列进行排序，再使用排序向量p2对前述排序的结果序列进行排序。在一些实施例中，两个排序向量p1、p2（顺序为先p1后p2，向量长度为N）的合并可以通过以下流程实现：对于排序向量p1的每个元素（记为p1_i），将p1_i确定为目标位置j（即j=p1_i），并将排序向量p2目标位置j上的元素p2_j确定为合并排序向量p的第i位元素。通过遍历i，可以得到合并排序向量p各位置上的元素。继续前述明文示例，第一排序向量

，中间排序向量

，第一排序向量先于中间排序向量使用，因此合并两者得到的第二排序向量

。

在本说明书一些实施例中，第一参与方持有第一排序向量的第一分片和中间排序向量的第一分片，第二参与方持有第一排序向量的第二分片和中间排序向量的第二分片，双方需要协同执行秘密分享合并算法，以实现将第一排序向量和中间排序向量的合并，各自得到第二排序向量的分片。

参考图5，在一些实施例中，秘密分享合并算法又可记为

函数或算子：

，其中<>表示密文形式，具体可以是分片形式。

函数可以理解为一个功能函数，其一组输入数据包括秘密分享的第一排列函数（或称为排序序列、排序向量）的第一分片

和秘密分享的第二排列函数的第一分片

，来自第一参与方，其另一组输入数据包括秘密分享的第一排列函数的第二分片

和秘密分享的第二排列函数的第二分片

，来自第二参与方；其输出数据为合并后的秘密分享排序向量的第一分片

和第二分片

，合并后的秘密分享排序向量的第一分片由第一参与方获得，合并后的秘密分享排序向量的第二分片由第二参与方获得。

在一些实施例中，两方的处理设备可以分别执行

函数中的流程，目前已有

函数的多种实现方式，本说明书不对其内部实现算法进行限制，只将其作为黑盒算子进行调用。应当理解，凡是目前已经出现的以及未来会出现的，能够实现

函数功能的数据处理/运算单元、程序代码、机器学习模型等各种方式均可作为本说明书提到的基于秘密分享排列协议。

以第一参与方和第二参与方协同作为示例，其中，第一参与方持有第一排序序列的第一分片以及第二排序序列的第一分片；第二参与方持有第一排序序列的第二分片以及第二排序序列的第二分片，

函数的一种实现方式可以包括：

第一参与方基于第一排序序列的第一分片，与第二参与方基于第一排序序列的第二分片，通过第一秘密分享排列协议，获取第一排序乱序序列的第一分片；第二参与方获得第一排序乱序序列的第二分片；

第一参与方将第一排序乱序序列的第一分片发送给第二参与方，并从第二参与方接收第一排序乱序序列的第二分片，进而获取第一排序乱序序列；同时第二参与方也能获得第一排序乱序序列；

第一参与方基于所述第一排序乱序序列和第二排序序列的第一分片，按照前述明文合并算法获取合并排序乱序序列的第一分片；同时，第二参与方基于所述第一排序乱序序列和第二排序序列的第二分片，按照明文合并算法获取合并排序乱序序列的第二分片；

第一参与方基于所述合并排序乱序序列的第一分片，与第二参与方基于合并排序乱序序列的第二分片，通过第一秘密分享排列协议，获取合并排序序列的第一分片；第二参与方获得合并排序序列的第二分片；基于所述合并排序序列对等长序列进行排序的结果等于将基于所述第一排序序列和所述第二排序序列对所述等长序列进行迭代排序的结果。其中，第一秘密分享排列协议以及参与方基于第一排序序列的分片获取第一排序乱序序列的分片的详细内容可以在步骤320的相关说明中找到。

在一些实施例中，所述第一参与方基于所述合并排序乱序序列的第一分片，与第二参与方基于合并排序乱序序列的第二分片，通过第一秘密分享排列协议，获取合并排序序列的第一分片；第二参与方获得合并排序序列的第二分片，可以进一步包括：

第一参与方生成所述第一随机排序序列的逆序列；

第一参与方基于所述合并排序乱序序列的第一分片，与第二参与方基于合并排序乱序序列的第二分片以及所述第二随机排序序列的逆序列，通过第一秘密分享排列协议，获得合并还原中间序列的第一分片；第二参与方获得合并还原中间序列的第二分片，所述第二随机排序序列的逆序列由第二参与方生成；

第一参与方基于所述合并还原中间序列的第一分片以及第一随机排序序列的逆序列，与第二参与方基于合并还原中间序列的第二分片，通过第一秘密分享排列协议，获得所述合并排序序列的第一分片；第二参与方获得合并排序序列的第二分片。

在一些实施例中，生成某随机排序序列的逆序列，包括：生成与该随机排序序列等长的正序序列；基于该随机排序序列对所述正序序列进行排序，得到的结果序列即为该随机排序序列的逆序列。

正序序列可以是指元素按照从小到大的顺序进行排列的序列。作为示例，可以是将第一随机排序序列的元素按照从小到大的顺序进行排列得到的序列。第一参与方的处理设备使用第一随机排序序列对正序序列进行排序后即可得到对应的逆序列。例如，假设第一随机排序序列为R0=[3 2 0 1]，等长的正序序列为R=[0 1 2 3]，使用第一随机排序序列对等长的正序序列进行排序后可得逆序列R1=[2 3 1 0]。对其进行验证，假设待排序的序列X=[B C A D]，使用R0对X进行排序可得X1=[A D C B]，使用R1对X1进行排序还原可得[BC A D]=X。

基于上述秘密分享合并算法可以将第二排序向量

表示为

。

上述以第一轮迭代作为示例阐述了所述至少两轮迭代中的一轮迭代所包含的交互流程，为了更好的理解本说明书中的技术方案同时证明本方案的正确性，以下继续采用待排序数据列

作为明文示例，说明第二轮（即最后一轮）迭代，第二轮迭代中的基于秘密分享的处理方式与第一轮迭代相同，因此不再重复说明。

在一些实施例中，由步骤310A和步骤310B可知，在第二轮迭代中，将待排序数据列

对应最高位列作为第一位列

。在该轮中，第一排序向量为前一轮迭代得到的第二排序向量，即第一排序向量

。

进一步的，基于第一位列和第一排序向量得到第二轮的第一排序位列

，并基于第一排序位列得到拓展标志序列

，确定中间排序向量

。最后，基于第一排序向量和中间排序向量通过合并算法得到第二轮的第二排序向量

。由于第二轮为最后一轮迭代，因此

即为目标排序向量。此时，第一参与方持有目标排序向量的第一分片，第二参与方持有目标排序向量的第二分片。

结合图1算子接口定义，可以验证，利用目标向量

对待排序数据列

进行排序后，得到的数据列为

，即得到待排序数据列

的顺序（升序）排列。

应当注意的是，上述图3中流程300的描述仅仅是为了示例和说明，而不限定本说明书的适用范围。对于本领域技术人员来说，在本说明书的指导下可以对流程300进行各种修正和改变。然而，这些修正和改变仍在本说明书的范围之内。

图6是根据本说明书一些实施例所示的基于秘密分享的排序系统的示例性模块图。

如图6所示，该基于秘密分享的排序系统600可以包括第一位列分片获取模块610、第一排序位列分片获取模块620、拓展标志序列分片获取模块630、中间排序向量分片确定模块640和第二排序向量分片获取模块650。

第一位列分片获取模块610可以用于在待排序数据列第一分片的每个元素中取同一位的子元素，得到第一位列的第一分片。

在一些实施例中，关于第一位列的更多描述可以参考步骤310A，在此不再赘述。

所述第一排序位列分片获取模块620可以用于基于第一位列的第一分片和第一排序向量的第一分片，与第二参与方基于第一位列的第二分片和第一排序向量的第二分片，通过秘密分享排序算法，得到第一排序位列的第一分片，第二参与方获得第一排序位列的第二分片；所述第一排序位列等于使用第一排序向量对所述第一位列进行排序的结果序列；当所述一轮迭代为第一轮迭代时，所述第一排序向量为元素顺序排列的初始排序向量，否则所述第一排序向量为前一轮迭代得到的第二排序向量；

在一些实施例中，关于第一排序位列的更多描述可以参考步骤320A，在此不再赘述。

所述拓展标志序列分片获取模块630可以用于基于第一排序位列的第一分片得到拓展标志序列的第一分片；其中，所述拓展标志序列包括均与第一排序位列等长的第一子序列和第二子序列；所述第一子序列的元素反映所述第一排序位列中的对位元素是否为第一数值；所述第二子序列的元素反映所述第一排序位列中的对位元素是否为第二数值；

在一些实施例中，关于拓展标志序列的更多描述可以参考步骤330A，在此不再赘述。

所述中间排序向量分片确定模块640可以用于基于所述拓展标志序列的第一分片确定中间排序向量的第一分片，所述中间排序向量能够将第一位列中的元素进行顺序排列；

在一些实施例中，关于中间排序向量的更多描述可以参考步骤340A，在此不再赘述。

所述第二排序向量分片获取模块650可以用于基于第一排序向量的第一分片和所述中间排序向量的第一分片，与第二参与方基于第一排序向量的第二分片和所述中间排序向量的第二分片，通过秘密分享合并算法，得到第二排序向量的第一分片，第二参与方获得第二排序向量的第二分片；基于第二排序向量对等长序列进行排序的结果序列等于基于所述第一排序向量和中间排序向量对所述等长序列进行迭代排序的结果序列。

在一些实施例中，关于第二排序向量的更多描述可以参考步骤350A，在此不再赘述。

应当理解，图6所示的系统600及其模块可以利用各种方式来实现。例如，在一些实施例中，装置及其模块可以通过硬件、软件或者软件和硬件的结合来实现。其中，硬件部分可以利用专用逻辑来实现；软件部分则可以存储在存储器中，由适当的指令执行装置，例如微处理器或者专用设计硬件来执行。本领域技术人员可以理解上述的方法和装置可以使用计算机可执行指令和/或包含在处理器控制代码中来实现，例如在诸如磁盘、CD或DVD-ROM的载体介质、诸如只读存储器（固件）的可编程的存储器或者诸如光学或电子信号载体的数据载体上提供了这样的代码。本说明书的装置及其模块不仅可以有诸如超大规模集成电路或门阵列、诸如逻辑芯片、晶体管等的半导体、或者诸如现场可编程门阵列、可编程逻辑设备等的可编程硬件设备的硬件电路实现，也可以用例如由各种类型的处理器所执行的软件实现，还可以由上述硬件电路和软件的结合（例如，固件）来实现。

需要注意的是，以上对于系统600及其模块的描述，仅为描述方便，并不能把本说明书限制在所举实施例范围之内。可以理解，对于本领域的技术人员来说，在了解该系统的原理后，可能在不背离这一原理的情况下，对各个模块进行任意组合，或者构成子系统与其他模块连接。例如，在一些实施例中，例如，图6中披露的第一位列分片获取模块610、第一排序位列分片获取模块620、拓展标志序列分片获取模块630可以是一个系统中的不同模块，也可以是一个模块实现上述的两个或两个以上模块的功能。例如，各个模块可以共用一个存储模块，各个模块也可以分别具有各自的存储模块。诸如此类的变形，均在本说明书的保护范围之内。

本说明书实施例可能带来的有益效果包括但不限于：（1）各参与方可以在不暴露各自数据隐私的情况下，实现顺序排序；（2）顺序排序过程中不依赖复杂程度较高的算子，因此适用于大规模计算。

需要说明的是，不同实施例可能产生的有益效果不同，在不同的实施例里，可能产生的有益效果可以是以上任意一种或几种的组合，也可以是其他任何可能获得的有益效果。

上文已对基本概念做了描述，显然，对于本领域技术人员来说，上述详细披露仅仅作为示例，而并不构成对本说明书的限定。虽然此处并没有明确说明，本领域技术人员可能会对本说明书进行各种修改、改进和修正。该类修改、改进和修正在本说明书中被建议，所以该类修改、改进、修正仍属于本说明书示范实施例的精神和范围。

同时，本说明书使用了特定词语来描述本说明书的实施例。如“一个实施例”、“一实施例”、和/或“一些实施例”意指与本说明书至少一个实施例相关的某一特征、结构或特点。因此，应强调并注意的是，本说明书中在不同位置两次或多次提及的“一实施例”或“一个实施例”或“一个替代性实施例”并不一定是指同一实施例。此外，本说明书的一个或多个实施例中的某些特征、结构或特点可以进行适当的组合。

此外，除非权利要求中明确说明，本说明书所述处理元素和序列的顺序、数字字母的使用、或其他名称的使用，并非用于限定本说明书流程和方法的顺序。尽管上述披露中通过各种示例讨论了一些目前认为有用的发明实施例，但应当理解的是，该类细节仅起到说明的目的，附加的权利要求并不仅限于披露的实施例，相反，权利要求旨在覆盖所有符合本说明书实施例实质和范围的修正和等价组合。例如，虽然以上所描述的系统组件可以通过硬件设备实现，但是也可以只通过软件的解决方案得以实现，如在现有的服务器或移动设备上安装所描述的系统。

同理，应当注意的是，为了简化本说明书披露的表述，从而帮助对一个或多个发明实施例的理解，前文对本说明书实施例的描述中，有时会将多种特征归并至一个实施例、附图或对其的描述中。但是，这种披露方法并不意味着本说明书对象所需要的特征比权利要求中提及的特征多。实际上，实施例的特征要少于上述披露的单个实施例的全部特征。

一些实施例中使用了描述成分、属性数量的数字，应当理解的是，此类用于实施例描述的数字，在一些示例中使用了修饰词“大约”、“近似”或“大体上”来修饰。除非另外说明，“大约”、“近似”或“大体上”表明所述数字允许有±20%的变化。相应地，在一些实施例中，说明书和权利要求中使用的数值参数均为近似值，该近似值根据个别实施例所需特点可以发生改变。在一些实施例中，数值参数应考虑规定的有效数位并采用一般位数保留的方法。尽管本说明书一些实施例中用于确认其范围广度的数值域和参数为近似值，在具体实施例中，此类数值的设定在可行范围内尽可能精确。

针对本说明书引用的每个专利、专利申请、专利申请公开物和其他材料，如文章、书籍、说明书、出版物、文档等，特此将其全部内容并入本说明书作为参考。与本说明书内容不一致或产生冲突的申请历史文件除外，对本说明书权利要求最广范围有限制的文件（当前或之后附加于本说明书中的）也除外。需要说明的是，如果本说明书附属材料中的描述、定义、和/或术语的使用与本说明书所述内容有不一致或冲突的地方，以本说明书的描述、定义和/或术语的使用为准。

最后，应当理解的是，本说明书中所述实施例仅用以说明本说明书实施例的原则。其他的变形也可能属于本说明书的范围。因此，作为示例而非限制，本说明书实施例的替代配置可视为与本说明书的教导一致。相应地，本说明书的实施例不仅限于本说明书明确介绍和描述的实施例。

Claims (10)

1.一种基于秘密分享的排序方法，用于获取能够将待排序数据列的元素进行顺序排列的目标排序向量，排序向量用于标识对等长序列进行排序的操作，其元素指示所述等长序列中的对位元素在结果序列中的位置；第一参与方拥有二进制形式的待排序数据列的第一分片，第二参与方拥有二进制形式的待排序数据列的第二分片；该方法由第一参与方执行且包括至少两轮迭代，最后一轮迭代得到的第二排序向量的第一分片为所述目标排序向量的第一分片；其中一轮迭代包括：

在待排序数据列第一分片的每个元素中取同一位的子元素，得到第一位列的第一分片；

基于第一位列的第一分片和第一排序向量的第一分片，与第二参与方基于第一位列的第二分片和第一排序向量的第二分片，通过秘密分享排序算法，得到第一排序位列的第一分片，第二参与方获得第一排序位列的第二分片；所述第一排序位列等于使用第一排序向量对所述第一位列进行排序的结果序列；当所述一轮迭代为第一轮迭代时，所述第一排序向量为元素顺序排列的初始排序向量，否则所述第一排序向量为前一轮迭代得到的第二排序向量；所述秘密分享排序算法用于通过秘密分享的形式存在的排列函数对秘密分享的形式存在的序列进行秘密排列，得到仍然以秘密分享的形式存在的排列结果；

基于第一排序位列的第一分片得到拓展标志序列的第一分片；其中，所述拓展标志序列包括均与第一排序位列等长的第一子序列和第二子序列；所述第一子序列的元素反映所述第一排序位列中的对位元素是否为第一数值；所述第二子序列的元素反映所述第一排序位列中的对位元素是否为第二数值；

基于所述拓展标志序列的第一分片确定中间排序向量的第一分片，所述中间排序向量能够将第一位列中的元素进行顺序排列；

基于第一排序向量的第一分片和所述中间排序向量的第一分片，与第二参与方基于第一排序向量的第二分片和所述中间排序向量的第二分片，通过秘密分享合并算法，得到第二排序向量的第一分片，第二参与方获得第二排序向量的第二分片；基于第二排序向量对等长序列进行排序的结果序列等于基于所述第一排序向量和中间排序向量对所述等长序列进行迭代排序的结果序列；所述秘密分享合并算法用于将多个秘密分享的形式存在的排序向量，合并成一个新的秘密分享的形式存在的排序向量，使得新的排序向量对序列进行排序的结果等同于分别利用所述多个排序向量依次对该序列进行迭代排列的结果。

2.如权利要求1所述的方法，其中，所述第一数值为0，所述第二数值为1；所述基于第一排序位列的第一分片得到拓展标志序列的第一分片，包括：

对第一预设位列与第一排序位列的第一分片按位求差，得到所述拓展标志序列的第一子序列的第一分片；所述第一预设位列与第二参与方的第二预设位列按位求和的结果为全1序列；

将所述第一排序位列的第一分片作为所述拓展标志序列的第二子序列的第一分片。

3.如权利要求1所述的方法，其中，所述第一数值为1，所述第二数值为0；所述基于第一排序位列的第一分片得到拓展标志序列的第一分片，包括：

对第一预设位列与第一排序位列得到第一分片按位求差，得到所述拓展标志序列的第二子序列的第一分片；所述第一预设位列与第二参与方的第二预设位列按位求和的结果为全1序列；

将所述第一排序位列的第一分片作为所述拓展标志序列的第一子序列的第一分片。

4.如权利要求2或3所述的方法，其中，所述基于所述拓展标志序列的第一分片确定中间排序向量的第一分片，包括：

对所述拓展标志序列的第一分片进行前缀求和得到拓展求和序列的第一分片；

基于所述拓展标志序列的第一分片和所述拓展求和序列的第一分片，与第二参与方基于所述拓展标志序列的第二分片和所述拓展求和序列的第二分片，通过秘密分享乘法协议，得到拓展排序序列的第一分片，第二参与方获得拓展排序序列的第二分片；拓展排序序列等于所述拓展标志序列和所述拓展求和序列按位相乘的结果；

基于所述拓展排序序列的第一分片，得到所述中间排序向量的第一分片。

5.如权利要求4所述的方法，基于所述拓展排序序列的第一分片，得到所述中间排序向量的第一分片，包括：

将所述拓展排序序列中的第一子序列的第一分片和第二子序列的第一分片按位求和，以得到所述中间排序向量的第一分片。

6.如权利要求5所述的方法，所述初始排序向量为第一项为0，且公差为1的等差数列，或者为公差为-1，且最后一项为0的等差数列；

所述将所述拓展排序序列中的第一子序列的第一分片和第二子序列的第一分片按位求和，以得到所述中间排序向量的第一分片，包括：

将按位求和的结果中的每个元素分别减第一预设值，得到所述中间排序向量的第一分片；所述第一预设值与第二参与方的第二预设值的和为1。

7.如权利要求1所述的方法，其中，所述顺序包括降序或升序。

8.如权利要求1所述的方法，其中，当所述一轮迭代为第一轮迭代时，在待排序数据列第一分片的每个元素中取最低位的子元素，得到所述第一位列的第一分片；当所述一轮迭代为第二轮迭代时，在待排序数据列第一分片的每个元素中取次低位的子元素，得到所述第一位列的第一分片；以此类推，当所述一轮迭代为最后一轮迭代时，在待排序数据列第一分片的每个元素中取最高位的子元素，得到所述第一位列的第一分片。

9.一种基于秘密分享的排序系统，用于获取能够将待排序数据列的元素进行顺序排列的目标排序向量，排序向量用于标识对等长序列进行排序的操作，其元素指示所述等长序列中的对位元素在结果序列中的位置；第一参与方拥有二进制形式的待排序数据列的第一分片，第二参与方拥有二进制形式的待排序数据列的第二分片；该系统部署于第一参与方且用于进行至少两轮迭代，最后一轮迭代得到的第二排序向量的第一分片为所述目标排序向量的第一分片；所述系统包括第一位列分片获取模块、第一排序位列分片获取模块、拓展标志序列分片获取模块、中间排序向量分片确定模块和第二排序向量分片获取模块；在其中一轮迭代中：

所述第一位列分片获取模块，用于在待排序数据列第一分片的每个元素中取同一位的子元素，得到第一位列的第一分片；

所述第一排序位列分片获取模块，用于基于第一位列的第一分片和第一排序向量的第一分片，与第二参与方基于第一位列的第二分片和第一排序向量的第二分片，通过秘密分享排序算法，得到第一排序位列的第一分片，第二参与方获得第一排序位列的第二分片；所述第一排序位列等于使用第一排序向量对所述第一位列进行排序的结果序列；当所述一轮迭代为第一轮迭代时，所述第一排序向量为元素顺序排列的初始排序向量，否则所述第一排序向量为前一轮迭代得到的第二排序向量；所述秘密分享排序算法用于通过秘密分享的形式存在的排列函数对秘密分享的形式存在的序列进行秘密排列，得到仍然以秘密分享的形式存在的排列结果；

所述拓展标志序列分片获取模块，用于基于第一排序位列的第一分片得到拓展标志序列的第一分片；其中，所述拓展标志序列包括均与第一排序位列等长的第一子序列和第二子序列；所述第一子序列的元素反映所述第一排序位列中的对位元素是否为第一数值；所述第二子序列的元素反映所述第一排序位列中的对位元素是否为第二数值；

所述中间排序向量分片确定模块，用于基于所述拓展标志序列的第一分片确定中间排序向量的第一分片，所述中间排序向量能够将第一位列中的元素进行顺序排列；

所述第二排序向量分片获取模块，用于基于第一排序向量的第一分片和所述中间排序向量的第一分片，与第二参与方基于第一排序向量的第二分片和所述中间排序向量的第二分片，通过秘密分享合并算法，得到第二排序向量的第一分片，第二参与方获得第二排序向量的第二分片；基于第二排序向量对等长序列进行排序的结果序列等于基于所述第一排序向量和中间排序向量对所述等长序列进行迭代排序的结果序列；所述秘密分享合并算法用于将多个秘密分享的形式存在的排序向量，合并成一个新的秘密分享的形式存在的排序向量，使得新的排序向量对序列进行排序的结果等同于分别利用所述多个排序向量依次对该序列进行迭代排列的结果。

10.一种基于秘密分享的排序装置，包括处理器，所述处理器用于执行权利要求1~8中任一项所述的基于秘密分享的排序方法。

Images