基于同态加密隐私数据保护的编辑距离计算系统的制作方法
基于同态加密隐私数据保护的编辑距离计算系统的制作方法
【技术领域】
[0001] 本发明设及一种隐私保护的编辑距离计算方案，具体是一种基于同态加密隐私数 据保护的编辑距离(e d i t d i S化η C e)计算系统。
【背景技术】
[0002] 大数据时代对实验科学产生了很重大的影响。在生物医药领域，一个很重要的发 展趋势是通过对大量的数据进行研究来探索其中的规律。然而，一个单独机构不能满足研 究需要的存储空间和计算能力。依赖于数据共享的云计算的提出，给基于大数据基因运算 的研究带来了一个解决途径。研究人员可W依靠云端来减少运算所需要的时间和储存空 间。使用云空间的一个很大的弊端就是可能会造成隐私泄露。假定云端是"可靠的"，它不会 把数据分享出去，但它自己可能会对数据感兴趣。患者的基因数据是需要被保护的数据，不 能直接传输给云端，而其它的研究机构又需要运些数据来进行研究。同态加密的出现能够 很好的解决运个问题。同态加密是一种特殊的加密方法，两个通过同态加密得到的密文相 加，解密后等于两个对应的原文相加。两个通过同态加密得到的密文相乘，解密后等于对应 两个相应的原文相乘。通过同态加密，被信任的第Ξ方生成一个公钥跟密钥，并把公钥传输 给机构A，B。机构A和机构B通过运个公钥把要进行运算的数据进行加密，然后把密文传给云 端。云端对密文进行运算，然后将结果传回给用户。用户对密文进行解密，得到原文结果。在 运种情况下，科研人员可W利用其它机构的数据进行研究。不像其它添加噪声来保护隐私 的方法，使用同态加密的得到的结果是无误差的。而机构A和机构B又不担屯、自己的数据在 计算过程中被泄露。
[0003] 两段基因序列的编辑距离（edit distance)可W用来表示运两段基因之间的差 异。由于基因可能出现缺失，而导致无法比较汉明距离，所W求编辑距离。如果给定两段基 因数据的明文，可W用Wagner-Fischer方法来求解它们之间的编辑距离。基于对现有技术 的文献探索发现，Qieon JH等人在2015年的《3rd Workshop on lincrypted Computing and Applied Homomorphic Cryp tography》（WAHC ' 15 )会议上发表的"Homomorph i c Computation of Edit Distance" -文中提出了一种方法，基于二进制的表示方法，通过改 进Wagner-Fischer方法，得到可能的路径。然后再对可能的路径，计算对应的编辑距离。比 较运些编辑距离的值，取最小的值，作为两段基因序列的编辑距离。但是，基于二进制的表 示方式，使得对密文做加法的时候，时间代价很大。而且，运篇论文里面的最短路径的获取 方法，并不能获得所有可能的最短路径，最后算出来的只是编辑距离的一个估计值。运些不 足促使申请人针对同态加密下求解两段基因序列的编辑距离，提出了新的系统。
【发明内容】
[0004] 本发明针对现有技术的不足，提供了一种基于同态加密隐私数据保护的编辑距离 计算系统，可W提供基因序列的编辑距离计算的同时还保证了原始基因隐私数据的安全 性。
[0005] 本发明是通过W下技术方案实现的：
[0006] 本发明所述的基于同态加密隐私数据保护的编辑距离计算系统，包括:加密数据 比较模块、最短路径集计算模块和编辑距离计算模块，其中：
[0007] 所述加密数据比较模块，对加密后的密文利用同态加密（homomorPh i C enc巧ption)的性质构造函数，输入两个需要比较的密文的差，输出一个加密的标志位；
[0008] 所述最短路径集计算模块，首先计算所有可能的路径集，然后对每条路径进行校 验，排除掉不可能成为最后结果的路径，得到最短路径集；
[0009] 所述编辑距离计算模块，基于前面两个模块的结果，计算出每一个最短路径集中 的加密的路径值，再利用编辑距离只能在有限范围内取值运个性质，判断出其中的最短加 密路径值，作为结果。
[0010] 优选地，所述加密数据比较模块，利用全同态加密算法进行加密，得到的数据即同 态加密隐私数据。
[0011] 优选地，所述的加密数据比较模块，构造了一个函数，该函数可W完成:在加密状 态下，判断两个十进制整数是否相等。该函数的输入是加密状态下的两个整数之差，函数输 出的是加密状态的1(如果两个整数相等)或加密状态的〇(如果两个整数不等）。
[0012] 优选地，所述的最短路径集计算模块，通过对所有路径集运用排除法，对于一条路 径，如果还能找到另一条值不大于它的路径，就把它排除。经过排除法后得到是最短路径 集。
[0013] 优选地，所述的编辑距离计算模块，通过计算最短路径集里面的最短路径，得到加 密的编辑距离。
[0014] 进一步的，本发明所述系统还包括并行运算模块，所述并行运算模块运用同态加 密里面的多孔结构，可W同时计算多个基因对的编辑距离，并利用了多核CPU,同时计算最 短路径集里面的路径值，加快了计算速度。
[0015] 本发明上述系统中所有的运算均处于加密的状态下并且在云端运行，第Ξ方负责 提供公钥给机构和密钥给用户，机构负责提供加密的数据给云端来运算，密文结果由云端 返回给用户，用户解密后得到最终结果。
[0016] 与现有技术相比，本发明具有如下的有益效果：
[0017] 本发明所述系统计算编辑距离的同时，还保证了原始隐私数据的安全性，基于整 数的表示方法也提升了计算的效率。本发明采用云端-客户模式的福射式结构，其中加密数 据位于各个客户端，加密数据比较模块、最短路径集计算模块、编辑距离计算模块和并行运 算模块位于服务器云端，具备良好的安全性、实用性和扩展性。
【附图说明】
[0018] 通过阅读参照W下附图对非限制性实施例所作的详细描述，本发明的其它特征、 目的和优点将会变得更明显：
[0019] 图1为本发明一较优实施例的结构框图；
[0020] 图2为本发明一实施例最短路径集计算的示意图。
【具体实施方式】
[0021] 下面结合具体实施例对本发明进行详细说明。W下实施例将有助于本领域的技术 人员进一步理解本发明，但不W任何形式限制本发明。应当指出的是，对本领域的普通技术 人员来说，在不脱离本发明构思的前提下，还可W做出若干变形和改进。运些都属于本发明 的保护范围。
[0022] 图1所示，本发明一实施例系统的结构框图，包括:加密数据比较模块，最短路径集 计算模块，编辑距离计算模块和并行运算模块。其中：
[0023] 加密数据比较模块，基于整数的表示方法，比较两个密文是否相等。输出为密文0 (不相等)或密文1(相等）。
[0024] 最短路径集计算模块，通过排除在所有路径中值一定不可能是最小的路径，将剩 余的路径设定为最短路径集。
[0025] 编辑距离计算模块，首先计算出每一个最短路径集中的加密的路径值，再利用编 辑距离只能在有限范围内取值运个性质，判断出其中的最短加密路径值，作为结果，返回给 用户。
[0026] 并行运算模块，运用同态加密里面的多孔结构，可W同时计算多个基因对的编辑 距离，并利用了多核CPU,同时计算最短路径集里面的路径值，加快了计算速度。
[0027] 本实施例中，所述的最短路径集计算模块的具体实现如图2所示。在图中，向下走 一格或者向右走一格表示路径的值加1，斜向下走一个格路径可能增加0，也可能增加1。运 取决于对应位置的两个基因是否相等，相等增加0,不同增加1。每一条路径都是从左上角的 (〇,〇)走到右下角的(4,4)。图中有Ξ条实例路径，其中虚线路径不是一个有效的最短路径， 因为输入的运对基因序列的长度是4*4,所W编辑距离的最大可能值是4,而虚线路径最小 的可能是6,所W虚线路径不是可能的最短路径。遍历整个可能的路径集， 假设路径A的最小 的可能值为Lmin(A)，路径B的最大的可能值为Lmax(B)，如果Lmax(B) < Lmin(A)，就将路径A排除 掉。
[0028] 本实施例中，所述的加密数据比较模块，通过设计一个函数，使得输入是需要比较 的加密数据的差，输出是加密的1或0。如果需要比较的加密数据相等，则输入是加密的0,输 出是加密的1。若需要比较的加密数据不相等，则输入是任意非零的密文，输出是加密的0。 假设输入的差为~^符号^代表是密文，设计的函数为
[0029]
(1)
[0030] 其中，P为密文的模数且为素数。?是一个变量，取值从?:到/>-L当P确定W后，密 文的取值范围被限定在6到#-?之间。当输入…?]的时候，很明显，输出是δ。当输 入是1 = δ时，由素数的性质(p-l)!=-l(modp)可得到输出为L。
[0031] 本实施例中，所述的编辑距离计算模块，首先利用加密数据比较模块和最短路径 集计算模块，计算出最短路径集中的每一条路径的加密的值。对于输入基因序列长度为(m, η)的序列对，不妨设一共有t条可能的最短路径，每一条路径的值表示为Α，/·^ = 1，2，···，?。再通 过利用编辑距离在有限的范围内取值的运一限制条件，将原本需要通过比较大小才能得到 的最短路径集里面中的最小值，通过下面的函数
[0032]
(2)
[0033] 其中，s=max(m，n)表示两段基因序列可能的最大编辑距离值，w=|m-n|表示两段 基因序列可能的最小编辑距离值，?代表编辑距离的可能取值，t代表最短路径集中的路径 数量，P为密文的模数且为素数。在图2中，w = 0，s = 4。若../';= 0，则至少存在一条值为rj的路 径，使得r j = i。将名，? = M', W+1, W+2,..., 5分别带入等式（1)中，得到每Z. = W, M'十1, M'十2,...,互。 将玲,/= W, W+.1, W.+返回给用户，用户解酱之后，得到Fi, i =w,W+1,W+2,. . . , S。编每距 离就是最小的i，使得Fi=l。
[0034] 本实施例中，所述的并行运算模块，通过利用密文的多孔结构(multiple slots), 同时运算得到多个编辑距离，并且利用多核CPU,将最短路径集中的路径分解到多个CPU进 行运算。
[0035] 并行运算模块利用了同态加密产生的密文具有多孔结构的特点，可W把多组对应 长度相等的基因序列，加密到一个密文中。例如'AGC'，'GGC'和'CGA'，可W把'A'，'G'和'C' 加密到一个密文里面。进行编辑距离运算的时候，密文里面的对应孔中的数，都与其它密文 对应位置的孔中的数做运算，一个密文里面的不同孔中的数互不影响。运样就可W同时计 算多对的基因序列对的编辑距离。而利用多核屯、CPU,可W将最短路径集里面的路径，分别 用不同的核进行运算，按照编辑距离计算模块的算法，得到一个编辑距离。用户比较不同核 屯、得到的最短距离，选取最小的那个作为整个基因序列对的编辑距离。
[0036] 具体实施参数和实施效果：
[0037] 上述实施例中关键参数的设置为:实验所用数据来源于随机生成的基因序列。选 取了不同长度的基因序列对，例如9*10,8*8,11*8等等。鉴于设备限制，上述实施例只选取 了一台配置32核的服务器，使用了其中的30核。当基因对序列长度为8*11时，密钥产生时间 为34.7419s，数据加密时间为9.04633s，编辑距离计算时间为235.129s，由于运用了多孔结 构(multiple slots),可W同时计算1785组基因序列的编辑距离，平均到每一对的基因序 列的编辑距离运算时间为0.1317 S。将本发明和最新的方法比较，如C h e 0 η J Η的论文 "Homomo;rphic Computation of Edit Distance"计算的编辑距离只是一个估计值，而且论 文里只提供了最大长度为8*8的基因序列的编辑距离计算产生的时间花费W及加密电路深 度。对于8*8的基因序列，同样利用了多孔结构，并且同样不利用多核运算，比较了程序运行 的时间和加密电路的深度。本发明的时间是0.2998s，深度为15。而上述论文所提方法的时 间为25.4366s，深度为19。由此可见，在运算时间和深度上均有很大的提升。
[0038] 本发明在计算编辑距离的同时还保证了原始隐私数据的安全性，并行运算能更进 一步提升了方法性能。本发明具备良好的实用性和扩展性。
[0039] W上对本发明的具体实施例进行了描述。需要理解的是，本发明并不局限于上述 特定实施方式，本领域技术人员可W在权利要求的范围内做出各种变形或修改，运并不影 响本发明的实质内容。
【主权项】
1. 一种基于同态加密隐私数据保护的编辑距离计算系统，其特征在于，包括:加密数据 比较模块、最短路径集计算模块和编辑距离计算模块，其中： 所述加密数据比较模块，对加密后的密文利用同态加密的性质构造函数，输入两个需 要比较的密文的差，输出一个加密的标志位； 所述最短路径集计算模块，首先计算所有可能的路径集，然后对每条路径进行校验，排 除掉不可能成为最后结果的路径，得到最短路径集； 所述编辑距离计算模块，基于前面两个模块的结果，计算出每一个最短路径集中的加 密的路径值，再利用编辑距离只能在有限范围内取值这个性质，判断出其中的最短加密路 径值，作为结果。2. 根据权利要求1所述的基于同态加密隐私数据保护的编辑距离计算系统，其特征是， 所述加密数据比较模块，利用全同态加密算法进行加密，得到的数据即同态加密隐私数据。3. 根据权利要求1所述的基于同态加密隐私数据保护的编辑距离计算系统，其特征是， 所述的加密数据比较模块，构造一个函数，该函数完成:在加密状态下，判断两个十进制整 数是否相等;该函数的输入是加密状态下的两个整数之差，函数输出的是加密状态的1或加 密状态的0。4. 根据权利要求1所述的基于同态加密隐私数据保护的编辑距离计算系统，其特征是， 所述的最短路径集计算模块，对所有路径集运用排除法，对于一条路径，如果还能找到另一 条值不大于它的路径，就把它排除，经过排除法后得到是最短路径集。5. 根据权利要求1-4任一项所述的基于同态加密隐私数据保护的编辑距离计算系统， 其特征是，所述系统进一步包括并行运算模块，所述的并行运算模块，通过利用密文的多孔 结构，同时运算得到多个编辑距离，并且利用多核CPU，将最短路径集中的路径分解到多个 CHJ进行运算。6. 根据权利要求1-5任一项所述的基于同态加密隐私数据保护的编辑距离计算系统， 其特征是，所有的运算均处于加密的状态下并且在云端运行，第三方负责提供公钥给机构 和密钥给用户，机构负责提供加密的数据给云端来运算，密文结果由云端返回给用户，用户 解密后得到最终结果。
【专利摘要】本发明提供了一种基于同态加密隐私数据保护的编辑距离计算系统，其中：加密数据比较模块对加密后的密文，利用同态加密的性质构造函数，输入两个需要比较的密文的差，输出一个加密的标志位；最短路径集计算模块，首先计算所有可能的路径集，然后对每条路径进行校验，排除掉不可能成为最后结果的路径，得到最短路径集；编辑距离计算模块基于前面两个模块的结果，计算出每一个最短路径集中的加密的路径值，再利用编辑距离只能在有限范围内取值这个性质，判断出其中的最短加密路径值，作为结果。本发明在计算编辑距离的同时还保证了原始隐私数据的安全性，并行运算能更进一步提升了方法性能。本发明具备良好的实用性和扩展性。
【IPC分类】G06F21/62, G06F21/60
【公开号】CN105488422
【申请号】CN201510807824
【发明人】熊红凯, 张宇辰
【申请人】上海交通大学
【公开日】2016年4月13日
【申请日】2015年11月19日
【技术领域】
[0001] 本发明设及一种隐私保护的编辑距离计算方案，具体是一种基于同态加密隐私数 据保护的编辑距离(e d i t d i S化η C e)计算系统。
【背景技术】
[0002] 大数据时代对实验科学产生了很重大的影响。在生物医药领域，一个很重要的发 展趋势是通过对大量的数据进行研究来探索其中的规律。然而，一个单独机构不能满足研 究需要的存储空间和计算能力。依赖于数据共享的云计算的提出，给基于大数据基因运算 的研究带来了一个解决途径。研究人员可W依靠云端来减少运算所需要的时间和储存空 间。使用云空间的一个很大的弊端就是可能会造成隐私泄露。假定云端是"可靠的"，它不会 把数据分享出去，但它自己可能会对数据感兴趣。患者的基因数据是需要被保护的数据，不 能直接传输给云端，而其它的研究机构又需要运些数据来进行研究。同态加密的出现能够 很好的解决运个问题。同态加密是一种特殊的加密方法，两个通过同态加密得到的密文相 加，解密后等于两个对应的原文相加。两个通过同态加密得到的密文相乘，解密后等于对应 两个相应的原文相乘。通过同态加密，被信任的第Ξ方生成一个公钥跟密钥，并把公钥传输 给机构A，B。机构A和机构B通过运个公钥把要进行运算的数据进行加密，然后把密文传给云 端。云端对密文进行运算，然后将结果传回给用户。用户对密文进行解密，得到原文结果。在 运种情况下，科研人员可W利用其它机构的数据进行研究。不像其它添加噪声来保护隐私 的方法，使用同态加密的得到的结果是无误差的。而机构A和机构B又不担屯、自己的数据在 计算过程中被泄露。
[0003] 两段基因序列的编辑距离（edit distance)可W用来表示运两段基因之间的差 异。由于基因可能出现缺失，而导致无法比较汉明距离，所W求编辑距离。如果给定两段基 因数据的明文，可W用Wagner-Fischer方法来求解它们之间的编辑距离。基于对现有技术 的文献探索发现，Qieon JH等人在2015年的《3rd Workshop on lincrypted Computing and Applied Homomorphic Cryp tography》（WAHC ' 15 )会议上发表的"Homomorph i c Computation of Edit Distance" -文中提出了一种方法，基于二进制的表示方法，通过改 进Wagner-Fischer方法，得到可能的路径。然后再对可能的路径，计算对应的编辑距离。比 较运些编辑距离的值，取最小的值，作为两段基因序列的编辑距离。但是，基于二进制的表 示方式，使得对密文做加法的时候，时间代价很大。而且，运篇论文里面的最短路径的获取 方法，并不能获得所有可能的最短路径，最后算出来的只是编辑距离的一个估计值。运些不 足促使申请人针对同态加密下求解两段基因序列的编辑距离，提出了新的系统。
【发明内容】
[0004] 本发明针对现有技术的不足，提供了一种基于同态加密隐私数据保护的编辑距离 计算系统，可W提供基因序列的编辑距离计算的同时还保证了原始基因隐私数据的安全 性。
[0005] 本发明是通过W下技术方案实现的：
[0006] 本发明所述的基于同态加密隐私数据保护的编辑距离计算系统，包括:加密数据 比较模块、最短路径集计算模块和编辑距离计算模块，其中：
[0007] 所述加密数据比较模块，对加密后的密文利用同态加密（homomorPh i C enc巧ption)的性质构造函数，输入两个需要比较的密文的差，输出一个加密的标志位；
[0008] 所述最短路径集计算模块，首先计算所有可能的路径集，然后对每条路径进行校 验，排除掉不可能成为最后结果的路径，得到最短路径集；
[0009] 所述编辑距离计算模块，基于前面两个模块的结果，计算出每一个最短路径集中 的加密的路径值，再利用编辑距离只能在有限范围内取值运个性质，判断出其中的最短加 密路径值，作为结果。
[0010] 优选地，所述加密数据比较模块，利用全同态加密算法进行加密，得到的数据即同 态加密隐私数据。
[0011] 优选地，所述的加密数据比较模块，构造了一个函数，该函数可W完成:在加密状 态下，判断两个十进制整数是否相等。该函数的输入是加密状态下的两个整数之差，函数输 出的是加密状态的1(如果两个整数相等)或加密状态的〇(如果两个整数不等）。
[0012] 优选地，所述的最短路径集计算模块，通过对所有路径集运用排除法，对于一条路 径，如果还能找到另一条值不大于它的路径，就把它排除。经过排除法后得到是最短路径 集。
[0013] 优选地，所述的编辑距离计算模块，通过计算最短路径集里面的最短路径，得到加 密的编辑距离。
[0014] 进一步的，本发明所述系统还包括并行运算模块，所述并行运算模块运用同态加 密里面的多孔结构，可W同时计算多个基因对的编辑距离，并利用了多核CPU,同时计算最 短路径集里面的路径值，加快了计算速度。
[0015] 本发明上述系统中所有的运算均处于加密的状态下并且在云端运行，第Ξ方负责 提供公钥给机构和密钥给用户，机构负责提供加密的数据给云端来运算，密文结果由云端 返回给用户，用户解密后得到最终结果。
[0016] 与现有技术相比，本发明具有如下的有益效果：
[0017] 本发明所述系统计算编辑距离的同时，还保证了原始隐私数据的安全性，基于整 数的表示方法也提升了计算的效率。本发明采用云端-客户模式的福射式结构，其中加密数 据位于各个客户端，加密数据比较模块、最短路径集计算模块、编辑距离计算模块和并行运 算模块位于服务器云端，具备良好的安全性、实用性和扩展性。
【附图说明】
[0018] 通过阅读参照W下附图对非限制性实施例所作的详细描述，本发明的其它特征、 目的和优点将会变得更明显：
[0019] 图1为本发明一较优实施例的结构框图；
[0020] 图2为本发明一实施例最短路径集计算的示意图。
【具体实施方式】
[0021] 下面结合具体实施例对本发明进行详细说明。W下实施例将有助于本领域的技术 人员进一步理解本发明，但不W任何形式限制本发明。应当指出的是，对本领域的普通技术 人员来说，在不脱离本发明构思的前提下，还可W做出若干变形和改进。运些都属于本发明 的保护范围。
[0022] 图1所示，本发明一实施例系统的结构框图，包括:加密数据比较模块，最短路径集 计算模块，编辑距离计算模块和并行运算模块。其中：
[0023] 加密数据比较模块，基于整数的表示方法，比较两个密文是否相等。输出为密文0 (不相等)或密文1(相等）。
[0024] 最短路径集计算模块，通过排除在所有路径中值一定不可能是最小的路径，将剩 余的路径设定为最短路径集。
[0025] 编辑距离计算模块，首先计算出每一个最短路径集中的加密的路径值，再利用编 辑距离只能在有限范围内取值运个性质，判断出其中的最短加密路径值，作为结果，返回给 用户。
[0026] 并行运算模块，运用同态加密里面的多孔结构，可W同时计算多个基因对的编辑 距离，并利用了多核CPU,同时计算最短路径集里面的路径值，加快了计算速度。
[0027] 本实施例中，所述的最短路径集计算模块的具体实现如图2所示。在图中，向下走 一格或者向右走一格表示路径的值加1，斜向下走一个格路径可能增加0，也可能增加1。运 取决于对应位置的两个基因是否相等，相等增加0,不同增加1。每一条路径都是从左上角的 (〇,〇)走到右下角的(4,4)。图中有Ξ条实例路径，其中虚线路径不是一个有效的最短路径， 因为输入的运对基因序列的长度是4*4,所W编辑距离的最大可能值是4,而虚线路径最小 的可能是6,所W虚线路径不是可能的最短路径。遍历整个可能的路径集， 假设路径A的最小 的可能值为Lmin(A)，路径B的最大的可能值为Lmax(B)，如果Lmax(B) < Lmin(A)，就将路径A排除 掉。
[0028] 本实施例中，所述的加密数据比较模块，通过设计一个函数，使得输入是需要比较 的加密数据的差，输出是加密的1或0。如果需要比较的加密数据相等，则输入是加密的0,输 出是加密的1。若需要比较的加密数据不相等，则输入是任意非零的密文，输出是加密的0。 假设输入的差为~^符号^代表是密文，设计的函数为
[0029]
(1)
[0030] 其中，P为密文的模数且为素数。?是一个变量，取值从?:到/>-L当P确定W后，密 文的取值范围被限定在6到#-?之间。当输入…?]的时候，很明显，输出是δ。当输 入是1 = δ时，由素数的性质(p-l)!=-l(modp)可得到输出为L。
[0031] 本实施例中，所述的编辑距离计算模块，首先利用加密数据比较模块和最短路径 集计算模块，计算出最短路径集中的每一条路径的加密的值。对于输入基因序列长度为(m, η)的序列对，不妨设一共有t条可能的最短路径，每一条路径的值表示为Α，/·^ = 1，2，···，?。再通 过利用编辑距离在有限的范围内取值的运一限制条件，将原本需要通过比较大小才能得到 的最短路径集里面中的最小值，通过下面的函数
[0032]
(2)
[0033] 其中，s=max(m，n)表示两段基因序列可能的最大编辑距离值，w=|m-n|表示两段 基因序列可能的最小编辑距离值，?代表编辑距离的可能取值，t代表最短路径集中的路径 数量，P为密文的模数且为素数。在图2中，w = 0，s = 4。若../';= 0，则至少存在一条值为rj的路 径，使得r j = i。将名，? = M', W+1, W+2,..., 5分别带入等式（1)中，得到每Z. = W, M'十1, M'十2,...,互。 将玲,/= W, W+.1, W.+返回给用户，用户解酱之后，得到Fi, i =w,W+1,W+2,. . . , S。编每距 离就是最小的i，使得Fi=l。
[0034] 本实施例中，所述的并行运算模块，通过利用密文的多孔结构(multiple slots), 同时运算得到多个编辑距离，并且利用多核CPU,将最短路径集中的路径分解到多个CPU进 行运算。
[0035] 并行运算模块利用了同态加密产生的密文具有多孔结构的特点，可W把多组对应 长度相等的基因序列，加密到一个密文中。例如'AGC'，'GGC'和'CGA'，可W把'A'，'G'和'C' 加密到一个密文里面。进行编辑距离运算的时候，密文里面的对应孔中的数，都与其它密文 对应位置的孔中的数做运算，一个密文里面的不同孔中的数互不影响。运样就可W同时计 算多对的基因序列对的编辑距离。而利用多核屯、CPU,可W将最短路径集里面的路径，分别 用不同的核进行运算，按照编辑距离计算模块的算法，得到一个编辑距离。用户比较不同核 屯、得到的最短距离，选取最小的那个作为整个基因序列对的编辑距离。
[0036] 具体实施参数和实施效果：
[0037] 上述实施例中关键参数的设置为:实验所用数据来源于随机生成的基因序列。选 取了不同长度的基因序列对，例如9*10,8*8,11*8等等。鉴于设备限制，上述实施例只选取 了一台配置32核的服务器，使用了其中的30核。当基因对序列长度为8*11时，密钥产生时间 为34.7419s，数据加密时间为9.04633s，编辑距离计算时间为235.129s，由于运用了多孔结 构(multiple slots),可W同时计算1785组基因序列的编辑距离，平均到每一对的基因序 列的编辑距离运算时间为0.1317 S。将本发明和最新的方法比较，如C h e 0 η J Η的论文 "Homomo;rphic Computation of Edit Distance"计算的编辑距离只是一个估计值，而且论 文里只提供了最大长度为8*8的基因序列的编辑距离计算产生的时间花费W及加密电路深 度。对于8*8的基因序列，同样利用了多孔结构，并且同样不利用多核运算，比较了程序运行 的时间和加密电路的深度。本发明的时间是0.2998s，深度为15。而上述论文所提方法的时 间为25.4366s，深度为19。由此可见，在运算时间和深度上均有很大的提升。
[0038] 本发明在计算编辑距离的同时还保证了原始隐私数据的安全性，并行运算能更进 一步提升了方法性能。本发明具备良好的实用性和扩展性。
[0039] W上对本发明的具体实施例进行了描述。需要理解的是，本发明并不局限于上述 特定实施方式，本领域技术人员可W在权利要求的范围内做出各种变形或修改，运并不影 响本发明的实质内容。
【主权项】
1. 一种基于同态加密隐私数据保护的编辑距离计算系统，其特征在于，包括:加密数据 比较模块、最短路径集计算模块和编辑距离计算模块，其中： 所述加密数据比较模块，对加密后的密文利用同态加密的性质构造函数，输入两个需 要比较的密文的差，输出一个加密的标志位； 所述最短路径集计算模块，首先计算所有可能的路径集，然后对每条路径进行校验，排 除掉不可能成为最后结果的路径，得到最短路径集； 所述编辑距离计算模块，基于前面两个模块的结果，计算出每一个最短路径集中的加 密的路径值，再利用编辑距离只能在有限范围内取值这个性质，判断出其中的最短加密路 径值，作为结果。2. 根据权利要求1所述的基于同态加密隐私数据保护的编辑距离计算系统，其特征是， 所述加密数据比较模块，利用全同态加密算法进行加密，得到的数据即同态加密隐私数据。3. 根据权利要求1所述的基于同态加密隐私数据保护的编辑距离计算系统，其特征是， 所述的加密数据比较模块，构造一个函数，该函数完成:在加密状态下，判断两个十进制整 数是否相等;该函数的输入是加密状态下的两个整数之差，函数输出的是加密状态的1或加 密状态的0。4. 根据权利要求1所述的基于同态加密隐私数据保护的编辑距离计算系统，其特征是， 所述的最短路径集计算模块，对所有路径集运用排除法，对于一条路径，如果还能找到另一 条值不大于它的路径，就把它排除，经过排除法后得到是最短路径集。5. 根据权利要求1-4任一项所述的基于同态加密隐私数据保护的编辑距离计算系统， 其特征是，所述系统进一步包括并行运算模块，所述的并行运算模块，通过利用密文的多孔 结构，同时运算得到多个编辑距离，并且利用多核CPU，将最短路径集中的路径分解到多个 CHJ进行运算。6. 根据权利要求1-5任一项所述的基于同态加密隐私数据保护的编辑距离计算系统， 其特征是，所有的运算均处于加密的状态下并且在云端运行，第三方负责提供公钥给机构 和密钥给用户，机构负责提供加密的数据给云端来运算，密文结果由云端返回给用户，用户 解密后得到最终结果。
【专利摘要】本发明提供了一种基于同态加密隐私数据保护的编辑距离计算系统，其中：加密数据比较模块对加密后的密文，利用同态加密的性质构造函数，输入两个需要比较的密文的差，输出一个加密的标志位；最短路径集计算模块，首先计算所有可能的路径集，然后对每条路径进行校验，排除掉不可能成为最后结果的路径，得到最短路径集；编辑距离计算模块基于前面两个模块的结果，计算出每一个最短路径集中的加密的路径值，再利用编辑距离只能在有限范围内取值这个性质，判断出其中的最短加密路径值，作为结果。本发明在计算编辑距离的同时还保证了原始隐私数据的安全性，并行运算能更进一步提升了方法性能。本发明具备良好的实用性和扩展性。
【IPC分类】G06F21/62, G06F21/60
【公开号】CN105488422
【申请号】CN201510807824
【发明人】熊红凯, 张宇辰
【申请人】上海交通大学
【公开日】2016年4月13日
【申请日】2015年11月19日
最新回复(0)