一种基于字典树的安全求交方法及系统

摘要

本发明提出了一种基于字典树的安全求交方法及系统，涉及计算机技术领域。首先，利用字典树的编码方式将所有参与方的原始集合编码成对应的字典树。然后，依照字典序对字典树的所有节点进行遍历，并调用预设的安全求交协议进行安全求交，得到所有参与方共同的字典树。最后，将得到的所有参与方共同的字典树进行解码，得到交集。通过采用字典树表示集合，空间利用率相对传统集合表示方式更优，特别是对于存在很长公共前缀的情况下。其次，在字典树上添加、删除、查询元素的复杂度均为0/1，易于维护集合。此外，由于同一路径下不同子树之间是相互独立的，所以在遍历子节点的过程中，可以由不同的线程并发执行，易于并行优化。

说明书

技术领域

本发明涉及计算机技术领域，具体而言，涉及一种基于字典树的安全求交方法及系统。

背景技术

安全求交协议旨在解决这样一类问题：不同实体各自持有自己的集合数据，它们需要共同计算出各自集合之间的交集，由于他们不信任彼此，因而不能暴露自己的集合。在数据保护法规日益严格的今天，这一问题在现实生活中有重要的应用场景，如金融机构之间求黑名单用户的交集，每一家金融机构都不想暴露自己的黑名单，但是又想了解共有的黑名单用户。

当前主流的安全求交协议，例如基于RSA、OT的安全求交协议，都使用非对称的密码学工具来实现集合间的求交。其底层均使用相对原始、低效率的方法表示集合，如数组、链表、哈希表等。集合中元素经过非对称加密后与参与方的元素进行匹配碰撞，最终保留双方共有的元素形成交集。这些主流的安全求交方案往往把研究的重点放在非对称密码算法和匹配算法上，在底层集合的表示方法上没有创新。而当前的非对称密码算法普遍耗时很高，且加密后的密文所占空间会大幅膨胀，这就导致当前安全求交算法往往占用很大的内存、运行耗时长、网络通信量大且并行优化困难。

发明内容

本发明的目的在于提供一种基于字典树的安全求交方法及系统，通过从底层集合的表示上进行改进，减少系统内存开销、缩短系统运行耗时，有利于提升安全求交的效率，并且易于进行并行优化。

本发明的实施例是这样实现的：

第一方面，本申请实施例提供一种基于字典树的安全求交方法，其包括：

利用字典树的编码方式将所有参与方的原始集合编码成对应的字典树；

依照字典序对字典树的所有节点进行遍历，并调用预设的安全求交协议进行安全求交，得到所有参与方共同的字典树；

将得到的所有参与方共同的字典树进行解码，得到交集。

基于第一方面，在本发明的一些实施例中，上述利用字典树的编码方式将所有参与方的原始集合编码成对应的字典树的步骤包括：

根据选择的安全求交协议确定编码参数；

基于编码参数，利用互不相同的字符串表示各参与方的原始集合；

将原始集合中的字符串编码成对应的字典树。

基于第一方面，在本发明的一些实施例中，上述依照字典序对字典树的所有节点进行遍历，并调用预设的安全求交协议进行安全求交，得到所有参与方共同的字典树的步骤包括：

依照字典序对字典树的所有节点进行遍历，得到当前节点对应的出边集合；

调用预设的安全求交协议对参与方的出边集合进行安全求交，保留共有的出边，剪除其它出边；

在共有的出边上递归遍历，直到处理完所有的节点，得到所有参与方共同的字典树。

基于第一方面，在本发明的一些实施例中，还包括：在对字典树进行遍历时，基于子树之间相互独立的特性，启用不同的线程对同一路径下的子树进行并发执行求交。

第二方面，本申请实施例提供一种基于字典树的安全求交系统，其包括：

编码模块，用于利用字典树的编码方式将所有参与方的原始集合编码成对应的字典树；

安全求交模块，用于依照字典序对字典树的所有节点进行遍历，并调用预设的安全求交协议进行安全求交，得到所有参与方共同的字典树；

解码模块，用于将得到的所有参与方共同的字典树进行解码，得到交集。

第三方面，本申请实施例提供一种电子设备，其包括存储器，用于存储一个或多个程序；处理器。当上述一个或多个程序被上述处理器执行时，实现如上述第一方面中任一项上述的方法。

第四方面，本申请实施例提供一种计算机可读存储介质，其上存储有计算机程序，该计算机程序被处理器执行时实现如上述第一方面中任一项上述的方法。

相对于现有技术，本发明的实施例至少具有如下优点或有益效果：

本申请实施例提供一种基于字典树的安全求交方法及系统，首先，利用字典树的编码方式将所有参与方的原始集合编码成对应的字典树。然后，依照字典序对字典树的所有节点进行遍历，并调用预设的安全求交协议进行安全求交，得到所有参与方共同的字典树。最后，将得到的所有参与方共同的字典树进行解码，得到交集。本申请通过采用字典树表示参与方的集合，空间利用率相对传统集合表示方式更优，特别是对于存在很长公共前缀的情况下。因为每次在调用安全求交协议时，仅针对每一节点的出边集合，所以每次安全求交的规模非常小，不会占用很多的内存空间。其次，在字典树上添加、删除、查询元素的复杂度均为0/1，易于维护集合。此外，由于同一路径下不同子树之间是相互独立的，所以在遍历子节点的过程中，可以由不同的线程并发执行，易于并行优化。

附图说明

为了更清楚地说明本发明实施例的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，应当理解，以下附图仅示出了本发明的某些实施例，因此不应被看作是对范围的限定，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他相关的附图。

图1为本发明提供的一种基于字典树的安全求交方法一实施例的流程框图；

图2为本发明提供的一种基于字典树的安全求交方法一实施例中参与方A所持集合的字典树表示；

图3为本发明提供的一种基于字典树的安全求交方法一实施例中参与方B所持集合的字典树表示；

图4为本发明提供的一种基于字典树的安全求交方法一实施例中遍历节点a后参与方A所持集合的字典树；

图5为本发明提供的一种基于字典树的安全求交方法一实施例中遍历节点a后参与方B所持集合的字典树；

图6为本发明提供的一种基于字典树的安全求交方法一实施例中遍历完所有节点后参与方A剩余集合的字典树；

图7为本发明提供的一种基于字典树的安全求交方法一实施例中遍历完所有节点后参与方B剩余集合的字典树；

图8为本发明提供的一种基于字典树的安全求交方法一实施例中同时调用多个线程并行求交的示意图；

图9为本发明提供的一种基于字典树的安全求交系统一实施例的结构框图；

图10为本发明实施例提供的一种电子设备的结构框图。

图标：1、存储器；2、处理器；3、通信接口；11、编码模块；12、安全求交模块；13、解码模块。

具体实施方式

为使本申请实施例的目的、技术方案和优点更加清楚，下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本申请一部分实施例，而不是全部的实施例。通常在此处附图中描述和示出的本申请实施例的组件可以以各种不同的配置来布置和设计。

因此，以下对在附图中提供的本申请的实施例的详细描述并非旨在限制要求保护的本申请的范围，而是仅仅表示本申请的选定实施例。基于本申请中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本申请保护的范围。

实施例

下面结合附图，对本申请的一些实施方式作详细说明。在不冲突的情况下，下述的各个实施例及实施例中的各个特征可以相互组合。

当前主流的安全求交协议多使用非对称的密码学工具来实现集合间的求交。其底层使用相对原始、低效率的方法来表示集合。集合中的元素经过非对称加密后与参与方的元素进行匹配碰撞，最终保留双方共有的元素形成交集。这些主流的安全求交方案往往把研究的重点放在非对称密码算法和匹配算法上，在底层集合的表示方法上没有创新。

鉴于此，请参照图1，图1所示为本申请实施例提供的一种基于字典树的安全求交方法的流程框图，该方法包括以下步骤：

步骤S1：利用字典树的编码方式将所有参与方的原始集合编码成对应的字典树。

上述步骤中，首先需要考虑选择何种已有的安全求交协议进行处理，例如基于RSA的安全求交协议和基于OT-OPRF的安全求交协议等。并且根据选择的安全求交协议确定编码参数。然后基于编码参数，利用互不相同的字符串表示各参与方的原始集合。最后，将原始集合中的字符串编码成对应的字典树。通过使用字典树的编码方式，将传统方法表示的集合，如表格、数组、哈希表、链表等，编码成一棵字典树，从而减少占用的内存空间，提高空间利用率。

具体的，请参照图2和图3，先用互不相同的字符串表示参与方的原始集合。例如，参与方A持有的原始集合为{adce，adcf，adec，abcd，abec}，参与方B持有的原始集合为{aceg，abec，adec}。然后将其编码成两棵字典树，参与方A的字典树如图2所示，参与方B的字典树如图3所示。其中，最左侧的空白节点为字典树的根节点，最右侧的节点为字典树的叶子节点，分别表示一个集合中的字符串。

需说明的是，如果安全求交一次所求集合较大，则字典树在编码时可以选择将多个字母进行分割。如选择3个字母编码一次，则每个节点的出边集合大小最多为26*26*26＝17576。

步骤S2：依照字典序对字典树的所有节点进行遍历，并调用预设的安全求交协议进行安全求交，得到所有参与方共同的字典树。

上述步骤中，在求交集时，从字典树的根节点开始，调用预设的安全求交协议对每个节点的出边集合与对方节点的出边集合进行安全求交，保留共有的出边，剪除其它的出边。然后按照字典序的顺序遍历子节点，重复以上操作，直到遍历完字典树的所有节点，得到参与方共同的字典树。

具体的，该步骤主要包括：

步骤S2-1：依照字典序对字典树的所有节点进行遍历，得到当前节点对应的出边集合。

步骤S2-2：调用预设的安全求交协议对参与方的出边集合进行安全求交，保留共有的出边，剪除其它出边。

步骤S2-3：在共有的出边上递归遍历，直到处理完所有的节点，得到所有参与方共同的字典树。

上述步骤中，以上述参与方A和参与方B的集合为例，进行安全求交。首先，从根节点开始遍历，得到参与方的根节点的出边集合。例如，如图2和图3所示，参与方A的根节点出边集合为{a}，参与方B的根节点出边集合也为{a}，两者进行安全求交后得到的集合为{a}，故出边a得到保留，此时参与方A和参与方B的字典树均没有剪枝。

之后，按照字典序的顺序遍历到了子节点a，此时参与方A的出边集合为{b,d}，参与方B的出边集合为{b,c,d}，两者安全求交后得到的集合为{b,d}，故参与方B需要剪除出边c。从而经过此次遍历剪枝后，得到的参与方A的字典树如图4所示，参与方B的字典树如图5所示。

以此类推，遍历完所有子节点后双方的字典树如图6和图7所示。显然这两棵字典树互相等价，且表示了双方的交集。

上述步骤中，通过采用字典树表示参与方的集合，空间利用率相对传统集合表示方式更优，特别是对于存在很长公共前缀的情况下。因为每次在调用安全求交协议时，仅针对每一节点的出边集合，所以每次安全求交的规模非常小，不会占用很多的内存空间。其次，在字典树上添加、删除、查询元素的复杂度均为0/1，易于维护集合。

步骤S3：将得到的所有参与方共同的字典树进行解码，得到交集。

上述步骤中，经过安全求交后，参与方会得到相同的字典树，表示了双方的交集。此时可以根据需要将其解码为传统方法表示的集合，如表格、数组、哈希表、链表等。

基于第一方面，在本发明的一些实施例中，还包括：在对字典树进行遍历时，基于子树之间相互独立的特性，启用不同的线程对同一路径下的子树进行并发执行求交。

上述实施例中，由字典树的性质可知，不同子树所对应的子集之间的交集是空集。因而，在对字典树求交集时，不同路径上的不同子树之间不需要求交，只需要考虑同一路径下的对应子树之间的求交。因此，不同路径下的求交过程之间互相完全独立，没有需要共享的内存和数据。于是，在不同路径的子树上求交时，可以使用不同的线程，且线程之间几乎不需要同步。这样的特性能够最大限度地利用多核多线程资源和通信带宽，达到最优的并行优化效果。

示例性的，如图8所示，ab路径下的两棵子树可以调用线程1来执行求交，ad路径下的两棵子树可以调用线程2来执行求交。从而，在遍历子节点的过程中，可以由不同的线程或协程并发执行。由于子树互相独立，并发粒度极低，并行优化的优势较大。

基于同样的发明构思，本发明还提出一种基于字典树的安全求交系统，请参照图9，图9为本申请实施例提供的一种基于字典树的安全求交系统的结构框图。该系统包括：

编码模块11，用于利用字典树的编码方式将所有参与方的原始集合编码成对应的字典树；

安全求交模块12，用于依照字典序对字典树的所有节点进行遍历，并调用预设的安全求交协议进行安全求交，得到所有参与方共同的字典树；

解码模块13，用于将得到的所有参与方共同的字典树进行解码，得到交集。

请参照图10，图10为本申请实施例提供的一种电子设备的结构框图。该电子设备包括存储器1、处理器2和通信接口3，该存储器1、处理器2和通信接口3相互之间直接或间接地电性连接，以实现数据的传输或交互。例如，这些元件相互之间可通过一条或多条通讯总线或信号线实现电性连接。存储器1可用于存储软件程序及模块，如本申请实施例所提供的一种基于字典树的安全求交系统对应的程序指令/模块，处理器2通过执行存储在存储器1内的软件程序及模块，从而执行各种功能应用以及数据处理。该通信接口3可用于与其他节点设备进行信令或数据的通信。

以上所述仅为本申请的优选实施例而已，并不用于限制本申请，对于本领域的技术人员来说，本申请可以有各种更改和变化。凡在本申请的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本申请的保护范围之内。

对于本领域技术人员而言，显然本申请不限于上述示范性实施例的细节，而且在不背离本申请的精神或基本特征的情况下，能够以其它的具体形式实现本申请。因此，无论从哪一点来看，均应将实施例看作是示范性的，而且是非限制性的，本申请的范围由所附权利要求而不是上述说明限定，因此旨在将落在权利要求的等同要件的含义和范围内的所有变化囊括在本申请内。不应将权利要求中的任何附图标记视为限制所涉及的权利要求。