![](https://csdnimg.cn/release/download_crawler_static/19569138/bg1.jpg)
收稿日期:20151222;修回日期:20160203 基金项目:国家自然科学基金面上资助项目(61271280);国家青年科学基金资助项目(61001100)
作者简介:王立昌(1990),男,甘肃天水人,硕士研究生,主要研究方向为通信与编码、信息安全;方勇(1979),男(通信作者),博导,博士,主
要研究方向为通信与编码、压缩感知、图像处理(yfang79@gmail.com).
基于安全多方计算的分布式基因序列相似性计算
王立昌,方 勇
(西北农林科技大学 信息工程学院,陕西 杨凌 712100)
摘 要:编辑距离作为一种重要的相似性度量方法被广泛应用于基因序列的相关分析研究中。针对现有的安
全基因序列编辑距离计算方案效率很低没有实用性的问题,利用基于秘密共享理论
GoldreichMicaliWigderson
(GMW)的安全多方计算协议(securemultipartycomputation,SMC)设计了一个安全的分布式基因序列近似编辑
距离计算方案。它能够使多个参与单位同时进行序列之间的距离计算而不泄露任何一方的基因数据信息。实
验结果表明,该方案能够安全有效地实现分布式的基因序列相似性计算。
关键词:编辑距离;安全多方计算;信息安全;基因序列对比;隐私保护分析;分布式计算
中图分类号:TP301.5 文献标志码:A 文章编号:10013695(2016)12368105
doi:10.3969/j.issn.10013695.2016.12.036
Distributedgenomesimilaritycalculationbasedonsecuremultipartycomputation
WangLichang,FangYong
(CollegeofInformationEngineering,NorthwestA&FUniversity,YanglingShaanxi712100,China)
Abstract:Asoneofimportantsimilaritymeasurements,editdistanceiswidelyusedinrelevantgenomesequenceanalysis
studies.Consideringtheproblemofinefficiencyandimpracticabilityofexistingsolutionsforsecureeditdistancecomputations
,
thispaperdesignedasecuredistributedsequenceapproximateeditdistancecalculationschemeutilizingsecretsharingtheory
GoldreichMicaliWigderson
(GMW) basedsecuremultipartycomputation(SMC) protocol.Itwasimplementedforthe
scenariothatmultiplepartiescouldsimultaneouslycomputeeditdistancebetweensequenceswithoutleakinganyparty’sgene
information.Theexperimentalresultsdemonstratethattheproposedschemecanefficientlyandsecurelyperformdistributedse
quencesimilaritycalculation.
Keywords:editdistance;securemultipartycomputation; informationsecurity; genomecomparison; privacypreserving
analysis;distributedcomputing
!
引言
人类基因组数据的迅速产生和累积使科研工作者可以容
易地访 问 大 量 基 因 序 列 数 据 集。一 些 科 技 公 司 如 华 大 基
因
[1]
、23andMe
[2]
已经开始提供面向用户的测序和 DNA特征
提取服务。在学术研究领域,科学家们正在努力建立更多的开
放基因 数 据 存 储 平 台,如 PGP(personalgenomeproject)
[3]
、
1000GenomesProject
[4]
,这些开放平台有力地促进了人类基因
组数据共享。编辑距离作为一种重要的序列相似性测量方法,
被广泛地应用于基因研究中
[5,6]
。
计算机相关技术无疑在现代基因数据共享与分析中扮演
了重要角色,如跨平台数据分析
[7]
以及数据挖掘
[8]
等技术在
基因研究中都有成功的应用。然而个人隐私信息的安全问题
在基因数据的共享分析中一直存在。因为基因序列中所包含
的可鉴别的个人信息不能被完全消除,而攻击者甚至能够从很
小的基因片段中提取出个人序列中独有的特征从而进一步追
踪个人隐私信息
[9,10]
,所以急需发展隐私保护相关技术来共享
和分析基因数据而不损失任何敏感的个人信息。
基于同态加密
[11,12]
的隐私保护方案允许在密文上直接进
行运算而不用解密数据,因此被认为是理想的加密方案,在数
据分析、安全计算等方面受到研究者们的广泛关注
[13]
。Kim
等人
[14]
利用全同态加密实现了近似编辑距离计算,但是它需
要 27s才能获得两条序列上八对 DNA的 编 辑 距离。基 于
SMC的隐私保护运算是另一个有希望实现安全基因序列共享
与分析的途径。由于 SMC的目标是使多个参与方协同完成任
何计算而不泄露除了标准输出之外的更多用户输入信息
[15]
,
所以它很适合在不同拥有者的基因数据集上进行安全的对比
分析。在当前的 SMC研究中有两种基础理论,即 乱 码电 路
(
garbledcircuit)和秘密共享(secretsharing)。Yao
[16]
的乱码电
路是乱码电路理论中的典型协议,而 Goldreich等人
[17]
的安全
运算协议 GMW 则是秘密共享中比较有代表性的实现方案。
许多后续 SMC的实现
[18~20]
都是基于 Yao的协议,因此只支持
两个参与方之间的安全计算。而最近的研究
[21,22]
表明经过优
化之后的 GMW 协议明显在运算效率上优于 Yao的乱码电路,
而且支持多个参与方之间的安全运算。
文献[19]在两个参与方的情景下通过 Yao的电路实现了
安全的基因序列编辑距离计算,可是这个方案需要几个小时去
比较长度上千的两个序列。因此,通过 SMC实现基因序列比
较的可行方法仍在探索之中。似乎即使在只有两个参与方的
情况下,安全的编辑距离计算都面临着许多挑战。而考虑到安
全性和运算效率的要求,在一个 SMC电路中实现多个参与方之
间的基因序列对比则应该难度更大。由于 Choi等人
[21]
的工
第 33卷第 12期
2016年 12月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol33No12
Dec.2016