面向用户隐私保护的高效基因比对方案

扫描整个基因组数据库并用混淆电路实现客户的基因序列与库中所有基因序列的比对。上述方案可以在保护双方

用户隐私的前提下，实现基因比对。不过该方案需要扫描整个基因组数据库，时间复杂度为0(\"),在基因组数据库

较大时效率较低。为了提高基因比对的效率,进一步提出了基于不经意随机存取(ORAM)的基因比对方案，先将基因 数据存储在ORAM上，然后只需把目标路径上的数据项取出并用混淆电路进行基因比对。该方案的比对次数和数据

库的大小呈亚线性关系，时间复杂度为O(log \")。实验结果表明，基于ORAM的基因比对方案在实现隐私保护的同 时,把比对次数由0(\")减小到了 O(logn),明显降低了比对操作的时间复杂度，可以用来进行疾病诊断，尤其适用于 基因组数据库较大的场景。关键词：基因比对;相似度计算；隐私保护；不经意随机存取;混淆电路中图分类号：TP309.2 文献标志码:AEfficient genetic comparison scheme for user privacy protectionLI Gongli1'2*, LI Yu1'2, ZHANG En1'2, YIN Tianyu1'2(1. College of Computer and Information Engineering, Henan Normal University, Xinxiang Henan 453007, China;2. Engineering Laboratory of Intelligence Business and Internet of Things cf Henan Province (Henan Normal University), Xinxiang Henan 453007, China)Abstract： Concerning the problem that current genetic comparison protocols generally require a trusted third party, which

may result in the leakage of a wide range of private data, a genetic comparison scheme based on linear scan was proposed. The gene sequences of two parties were first encoded based on Garbled Circuit (GC), and then the genome database was linearly

scanned and the garbled circuit was used to compare gene sequence of user with all gene sequences in database. The above scheme can achieve genetic comparison under the premise of protecting user privacy o£ both parties. However, the scheme needs to scan whole database with time complexity of 0( n), and is inefficient when the genome database is large. In order to

improve the efficiency of genetic comparison, a genetic comparison scheme based on Oblivious Random Access Memory (ORAM) was further proposed, in which genetic data was stored at ORAM first, then only the data blocks on target path were

picked out to perform genetic comparison by using garbled circuit. This scheme has the number of comparisons sub-linear to the size of database and time complexity of 0 (log n). The experimental results show that the genetic comparison scheme based on ORAM reduces the number of comparisons from 0( n) to 0( log n) while realizing privacy protection, significantly

decreases the time complexity of comparison operation. It can be used for disease diagnosis, especially in the case with large

genome database.Key words： genetic comparison; similarity calculation; privacy protection; Oblivious Random Access Memory

(ORAM); Garbled Circuit ( GC)23andme[I] 户将自己的基因信息提供给它,它通过对用户

0引言目前基因检测技术和各类检测平台是一把双刃剑，人们

的基因进行检测并反馈给用户一份健康报告，由于存在隐私

泄露的问题，被屡屡叫停，因此亟须设计一种既能实现基因序

既想要借助此类技术尽早诊断出疾病,但是又担心自己的基

因信息会泄露,而现有的基因检测平台,大多只是实现基因比

列比对又能保护用户隐私的方案。Bald等⑵利用隐私集合比较(Private Set Intersection,

对，无法保证用户隐私信息的安全。例如基因疾病检测平台

PSI)技术,提出了可以在亲子鉴定、定制医疗等方面提供隐私收稿日期：2019-06-24；修回日期=2019-08-15；录用日期：2019-09-llo 61602158);河南省科技攻关计划项目(172102210045, 192102210131)。基金项目：国家自然科学基金资助项目(U1604156 , 61772176,作者简介:李功丽(1981-)，女，河南信阳人，讲师，博士，主要研究方向：信息安全；李锤(1998—)，女，河南安阳人，主要研究方向:信息 安全、密码学；张恩(1974-),男，河南新乡人，副教授，博士,CCF会员，主要研究方向：信息安全、密码学；尹天宇(1999-),男，河南长垣 人，主要研究方向:安全多方计算。第1期李功丽等：面向用户隐私保护的高效基因比对方案137保护的安全协议，该协议可以统计出两条脱氧核糖核酸 (Deoxyribonucleic Acid, DNA)序列相同位点上相同碱基的数

目，但该方案不支持基因位点的插入、删除和修改等操作，缺

乏灵活性。De Cristofaro等⑶设计了一个基因组工具箱，提出

在基因检测时，先把数据逐个加密存储在智能设备上,再用于

后续计算，并对基因组工具箱的可用性进行研究，研究表明，

该方案在基因组测试时具备一定的可行性，但该方案着重介 绍了安全计算理论，缺乏有效的性能分析。Kim等⑷利用全

同态加密实现了近似编辑距离计算，它允许在密文上进行运

算而不用加解密数据，但它需要约28 s才能获得两条序列上

八对DNA的编辑距离，方案效率较低。基于安全多方计算的 隐私保护协议是另一个能够实现安全基因序列比对的工具,

因为安全多方计算的目标是使多个参与方协同完成某项任

务，同时不泄露除了计算结果外的用户隐私信息，所以它比较

适合用户之间进行安全的基因序列比对。目前,实现安全计

算的方法主要有Yao［5］的混淆电路(Garbled Circuit, GC)和

Goldreich等〔切 提出的秘密共享理论(Goldreich-Micali- Wigderson, GMW)协议，后来的安全多方计算协议大多

都是基于Yao［5］的混淆电路。目前安全计算协议有两种实现 方法:一种是把待计算的函数表示为布尔电路;另一种方法是

表示为算术电路。Huang等E在布尔电路上设计并实现了高 效的隐私集合比较协议，其研究结果表明，通过合理地设计电 路,基于混淆电路实现的安全多方计算的协议在某些情况下

的效率要高于一些自定义协议。编辑距离的计算可以实现基因序列的比对，从而预测两

条基因序列的相似度，基于安全多方计算实现的编辑距离方

案逐渐受到人们的关注,Jha等两提出了三种基于安全多方

计算设计的编辑距离协议，但这三种协议需要保存整个混淆 电路直到构造完成，了混淆电路中输入的大小。Huang 等‘刃针对该问题提出了 Pipelined Circuit Execution技术，可以 一边构造混淆电路一边计算混淆电路,即混淆电路的构造和

计算可以并行执行，因此可以支持大输入的场景。Blanton 等购基于混淆电路提出将基因序列的比对云外包给服务器,

避免了公钥加密操作，实现了在隐私保护下，编辑距离的快速 计算。Choi等实现了安全多方计算中的GMW协议，主要

用于待计算的函数可以被表示为布尔电路的场景，研究结果 表明，基于安全多方计算设计保护隐私的方案是可行的。由

于Choi等沖和Huang等呵的工作，使得安全地进行基因序

列比对成为了可能。现假设Alice (客户)怀疑自己得了某种基因疾病，而Bob

(服务器)有一个可以用来检测疾病的基因组数据库,Alice想

让Bob帮她诊断自己是否得这种疾病,设计隐私保护的比对

方案要实现以下两个安全目标：1) Alice不需要把自己的基因信息直接给Bob, Bob也不

需要直接将它的基因组数据库给Alice,这样可以避免双方数

据的泄漏。2) 比对结束后,Bob无法知道Alice是否得病的信息，即 Bob不能获得比对结果的信息。针对上述安全目标，首先，为了防止直接利用明文数据进

行比对会泄露基因信息,将基因序列进行编码混淆;其次，为 了确保基因比对过程不会泄露基因信息，将Alice的基因与

Bob方基因组数据库中的数据逐个进行比对，由此得出了第

一种基于线性扫描的基因比对方案。该方案可以实现隐私保 护下的基因比对。但是因为第一种方案需要线性扫描基因组数据库，时间 复杂度较高,当比对的目标数据库较大时，该方案的效率较 低。针对上述问题，本文利用不经意随机存取(Oblivious

Random Access Memory, ORAM )和混淆电路技术，提出了 一-

种基于ORAM的基因比对方案，在上述应用场景：客户想要

确定自己是否得了某种病，期望从服务器端的基因数据库中

取出该病的致病基因片段与自己的基因序列进行比对，根据

比对的结果来验证自己的判断。假设客户持有一个基因序列 服务器持有一个基因数据库0,基因数据已被加密存储在

ORAM上，客户期望在基因数据库中找到致病基因片段a，,同

时不想让服务器知道她期望得到什么数据，因为这可能泄漏

她的基因信息，而在客户访问基因序列a'的过程中，要保证

服务器端无法确定用户是否访问了 a',因为访问模式的泄漏

可能引起基因信息的泄漏，而ORAM可以抗访问模式泄漏， 它可以将一条ORAM指令转换为多条RAM指令去执行，最后

可以访问到期望的数据而不泄露自己的访问模式。利用 ORAM把目标数据\"所在路径上的数据全部取出后,双方再

利用混淆电路进行基因比对，在取数据和基因比对的整个过

程中,均不会泄漏双方的隐私信息。该方案是先取数据再进行

基因序列比对，为了取出期望得到的序列，需要取出 0(log “)(\"是数据库的大小)个数据，再利用混淆电路将a

与这。(1喝“)个数据进行比对;而第一种方案是直接利用混 淆电路进行基因比对，为了实现保护隐私的目的，需线性扫描

整个基因数据库0中所有的序列与a进行比对，比对次数为 0(n) o实验结果表明，改进后的方案不仅可以实现上述的两个

安全目标，而且可以有效地降低比对次数，特别是当基因组数

据库中数据量较大时，该方案的效率相比传统方案将会明显 提高。在最后的性能对比中，用包含不同数据量的基因组数

据库进行基因比对的时间测试，比较了基础方案和改进后的

方案的性能，证明了所提方案的有效性和可行性。1 基础知识1.1 ORAMORAM最早是由Goldreich等凹在1996年提出的，用来

解决软件逆向工程问题，后来Shi等〔切提出了一种基于二叉 树的ORAM方案，被广泛应用于软件保护、安全计算、密文搜

索等方面。ORAM是一种抗访问模式泄露的隐私保护技术， 它主要涉及用户和服务器两个主体，用户既可以将数据存储

到服务器上，也可以向服务器提出检索数据的请求，数据在 服务器上以二叉树形式存储，二叉树的每一层由若干个节点

组成，每个节点可以存储。(1昭\")个数据项。它的基本思想 是:用户要访问某个数据时，查找索引表得到该数据对应的叶

子节点,为该数据重新分配叶子节点和更新索引表,并将对应 的路径提供给服务器,服务器把该路径上所有的数据给用户，

用户依次解密这些数据,最终可以得到期望的数据。用户和

服务器通过网络协议实现交互访问数据的同时,服务器不能 推测出用户访问的数据。在基础的基于二叉树的ORAM方

案之后，为了提升ORAM的效率，文献［14-16］中提出了一 系列改进的ORAM方案。Gordon等旳首次提出，ORAM和 安全多方计算结合可以实现时间复杂度为亚线性的安全算

法，文献［18-20 ］中提出了一系列与安全计算相结合的

ORAM方案。在基于二叉树的ORAM方案中，假设用户的访存请求序

138计算机应用第40卷列为：y：= ( (0P1 ,argj ,(op2,arg2)，…，(op”，。猪“))

其中,op代表一次read或者write操作，若op = read,则＜irg；=

血;反之,op = write,arg； = ( ic/x,data；) ,idx 表示当前欲访问 数据项的标识符,data,表示该数据项对应的真正数据。以一 次访存请求Access (op)为例,ORAM操作的主要过程如下：1) 如图1所示，当用户想要访问标识符为idx的数据时,

首先查找本地的索引表PositionMap，得到数据项idx对应的

叶子节点2,并为数据项idx重新分配叶子节点V，更新索引 表中 PositionMap[ idx~\\ 的值，即 PositionMap[ idx] = Z* 02) 用户依次读取路径p(Z)上(图1中虚线指示的路径)

的每个数据，解密这些数据，若读到idx对应的数据项

(idx || PositionMap[idx] || data) 记录下该数据并用无效 数据项丄代替加密写回；反之将读到的数据重新加密写回。

最后如果读出了 id”对应的数据,返回该数据;反之返回丄。3) 若op = read,贝lj把idx所对应的数据data取出,更新数

据项内容为(讷龙 || PositionMap[ idx] || data)，若op = write,则 更新数据内容(血|| PositionMap[_idx] || data* )。最后将该数

据重新加密写入根节点root。4) 在每次将数据写入根节点之后,用户需从服务器端二

叉树的每一层挑选两个节点进行下移操作,若该节点中都是

无效数据项丄，则选取两个无效数据项丄，重新加密向它的

左右孩子节点各写入一个加密后的丄；否则,选取一个有效

数据项和一个无效数据项丄，将它们重新加密，根据PQ),将

有效数据写入指定的孩子节点，将无效数据丄写入另一孩子

节点。Fig. 1 Schematic diagram of searching for

a data item idx

1.2混淆电路混淆电路(GC)是Ya。⑸在1982年提出的，在安全两方

计算中，如果两方的输入可以转换为布尔值时,混淆电路可以 高效地解决此类安全计算问题,最开始用于解决经典的百万 富翁问题。它的基本思想是：发送方对输入值进行混淆，并 根据待计算的函数/构造混淆电路G(C)，将混淆表和发送方

输入的混淆值发送给接收方，接收方通过与发送方运行不经

意传输(Oblivious Transfer, 0T)协议归」来得到它的混淆值，

从而接收方能够正确地计算该混淆电路。使用混淆电路方案

来解决安全两方计算问题时主要分为构造混淆电路、计算混 淆电路和恢复真正的输出结果三个阶段。混淆电路方案的过 程如下。1)混淆电路构造阶段。设函数/对应的电路为C,发送方通过以下两个步骤来构

造混淆电路G(C)。① 假设C是由AND、OR、XOR等门组成的电路,对于电

路C中每一根线吗，产生两个长为“的随机串附，附e )0, 卄“,称为线叫的混淆值。② 若&为电路C的第i个门，门gi的两条输入线分别表

示为\"”丿和叫」，输出线被表示为叫丿,E( •)是一个加密函数,

用输入线和wh.对应的混淆值阀八閱丿分别作为密钥加密

输出线叫的混淆值確警,P,q e {0,1},得到以下4个密文：

仏。=&化(々”(磴严))S =叱;(气,(磴严)) 仏。=&匕(咼紅(磴严＞))

c “ =佗](纠[(镖」)))

将这4个爺文谥机排列,构成门gi的混淆表。发送方还应

构造一个电路的输出转换表，其中硯表示0,昭表示lo2) 混淆电路的计算。① 发送方将构造的混淆表、输出转换表给接收方(假设

接收方负责将整个混淆电路G(C)的输出的混淆值转换为真

值)。发送方的输入X被表示为Wj ,w2,…,WU1，接收方的输入y 可以表示为\"”1+1 ,\"”1+2,…,\"”1+吃，发送方将与它的输入坷，…，叫相对应的混淆值跆,於，…，磴1直接发给接收方。② 对于每个ie

,发送方执行0T协议，在执行这个协议时,发送方的输入是(春 心),接收方的输入 是％小最终接收方会得到町嘗。③ 按照拓扑序列计算电路的每个门。对于门g；,用赵八

见作为密钥解密门gi的混淆表中的4个密文c。,。,c。」,cl 0, c“，只能将一个密文解密成功得到確響，即〉即为门gi输

出的混淆值。④ 对于门g；的输出，女保门gi是中间某个门时，将门gi

输出的混淆值继续作为另一个门的输入重复上述操作进行计

算,直至计算完整个混淆电路。3) 恢复真正的输出结果。接收方根据输出转换表，将混淆电路G(C)输出的混淆 值转换为真正的输出结果,再将结果给发送方。在上述混淆电路方案中，实现隐私数据的传输采用的是

0T协议。在t ~ \"0T协议中，接收者持有t个索引值6 e 10, 1!，同时发送者拥有\"个信息mJ。在执行0T协

议时,接收者能够根据索引值从发送者的\"个信息中获取对

应的t条信息，但是无从知道其他的n - t条信息，而发送者也

不知道接收者的索引值個此无法知道接收者接收的信息。在

本文中，使用的是1 ~ 2 0T协议，即发送者拥有两条信息，接 收者持有一个选择位e {0,1}。执行1 ~2 0T协议之后， 接收者会获取与选择位b相对应的信息。0T协议是实现安全

计算的重要工具,通过执行0T协议，可以实现隐私信息的安

全传输。1.3编辑距离编辑距离(Levenshtein Distance)可以用来检测两条基因

序列的相似度，文献[22]中提出了一种改进的编辑距离算

法。其基本原理是计算至少需要多少次操作才能将一条基因 序列转换为另一条基因序列，操作主要包括碱基的插入、删除

和替换。例如，有如下两条基因序列a和0:a = GTTACTTTGG0 = CTTACCTTT为了将a变为0,需要在第1个位置将碱基G变为C,在

第6个位置插入碱基C,在第9和第10个位置删除两个碱基

G,可得编辑距离为4。在初始化时,Q数组的初值表述为如下：rZ)(i,0)(D(0, j) == i,j, 00 WjW i WmW n第1期李功丽等：面向用户隐私保护的高效基因比对方案139初始化后,两条基因序列的编辑距离可以用式(2)得到：

+ 1 ,Z)[i] [j - 1 ] ) +1,+t)

(2)其中,Q[订[j]表示序列a的前i个位点到序列0的前j个位点 的编辑距离。如果a[i]兴的值为1,否则为0。具

体的编辑距离计算过程如算法1所示。算法1基因序列编辑距离计算过程。输入:DNA序列a和0。输出:a和0的编辑距离。。1(1 •<— a. length,lh •<— 0. length；D jO；For i in la do：。[订[0] -i;EndFor j in lh do：£*[0][；] -j,EndFor i in la do：For j in lh do：

t •(— (a[i] = BL/'])?。：】；

D[Q[n ^min(D[i -l][j] + 1 i] [; - 1 ] ) +1,

-1山一1] +门EndEndReturn D2基于线性扫描的基因比对方案为了实现隐私保护下的基因序列比对，本文首先提出了

基于线性扫描的基因比对方案。该方案的基本思想是:先对

基因序列进行混淆编码,然后根据基因序列比对程序设计相

应的布尔电路并构造混淆电路,进而采取线性扫描的方式将

客户的基因序列和服务器端的基因组数据库中的基因序列逐 个利用混淆电路进行比对。在整个比对过程中，首先因为对 基因数据进行了混淆编码，所以双方不会泄漏自己的基因数

据，而且因为是与服务器中的每个基因序列进行比对,每次只

有客户得到真正的比对结果，因此服务器无法确定用户与哪

个基因序列的相似度高,所以也无法根据用户的比较对象推

测比较结果。2.1基因序列编码先将客户的基因序列和服务器端基因组数据库的基因序

列作如下处理：1) 确定编码规则并编码。用两个比特位对碱基a,t,c, G进行编码，分别编码为00,01,10,11。将DNA序列按照编

码规则进行编码，每个DNA序列最后被编码成一个二进制 串。2) 混淆输入。对一串二进制数的每一位\"e {0,1},产生 2个混淆值疋盘，分别对应于\"=0和\"=1。对于每一个输

入为。和b的g门,依次用k：X作为密钥加密输出的混淆值

脖，可得4个密文g = E$々(即、))o2.2布尔电路设计为了减小混淆电路的规模，先对算法1进行分析,提出只 有需要协同计算来保护隐私的操作才采用Yao[5]的混淆电路 实现，这样可以有效地减少混淆电路带来的开销。根据分析，

将算法1转换为图2的布尔电路,主要用到以下4种门电路:

MIN 门、ADD 门、MUX 门、EDT 门。MIN n 该门以两个mbit的数据S和T作为输入。若S > T,则输出m bit的数据T;反之,则输出m bit的数据S。ADD n 该门以一个mbit的数据S和一个1 bit的数据

q,q e (0,11作为输入。输出S加上g后的mbit数据。MUX门 该门以两个长度为m bit的数据S和T以及1

位的选择位b作为输入。若b = 0,则输出S；反之输出ToEDT |'： 该门以两个mbit的数据S和T作为输入。若S =T,则输出0；反之输出1。具体计算过程如图2所示，先比较D[i - l][j]和 Q[订[j-1],选出最小值，再与Q[i - 1 ] [j - 1 ]比较，产生1

位的 6。若 min(Q[ i - 1 ] [j] [订[j - 1 ])大于 D[i - 1] [j -

1],则b为0,MUX门的输出为t,否则MUX门的输出为1,最

后取第二个MIN门的输出值加MUX门的输出值为整个电路 的输出。m bit 称 £>[!-!][/]bit ] £>[<■][/-I]bit

2 bita[i] J, p\\j]J, 2 bit| 2-MT越

| EDT |% blilbittI 2V知 1,I |----------------------彳 4MUX |m bit

-----------------T- ---------ADDlbit| m bit图2基因比对的核心布尔电路Fig. 2 Core Boolean circuit of genetic comparison2.3基因序列比对将客户的基因序列与服务器端基因组数据库中每个序列

依次进行比对。在每一次的比对操作时，根据产生的混淆编

码值和设计的布尔电路构造出混淆电路，然后将混淆电路交

由服务器方进行计算，最后服务器方将基因比对的结果返回 给客户，而此时的结果是混淆编码值，只有客户端才能解码转

换为真正的明文结果，避免了服务器获得真正的比对结果。具体过程:客户持有DNA序列a,服务器端有一个包含n

条基因序列的基因组数据库0,令a与0中的\"条序列逐个进

行比对，在每次比对时,采用混淆电路来计算两条序列的相 似程度，根据相似度来确定客户是否患有这种DNA疾病，若

某次比对时两条序列相似度达到96%的时候，即判定两条序

列同源。利用 Huang 等切提出的 Pipelined Circuit Execution

技术对代码进行优化,每构造一个门的混淆表和输入的混淆

值之后，就可以发送给服务器进行计算,并行执行整个电路,

这样可以大幅度减少构造混淆电路时占用的内存，提高混淆 电路的执行效率。同时利用Kolesnikov等旳提出的Free- XOR技术来减少混淆电路的开销。在实验测试时，安全参数&定为80,执行的”base” 0T的

次数为ko将两方的基因序列长定为32时，一次基因比对所

需门的数量为16个,平均需要的总时间为5.31s,其中,0T 所占的时间为0.24 s。在上述方案中，客户的基因序列与服务器端基因组数据

库里面所有的基因序列逐个进行比对。每次比对都使用混淆 电路来实现,因此可以保证每次比对过程中基因信息的安全， 且因为是比对了基因组数据库中的所有序列,所以服务器无

法确定客户到底与哪个DNA序列相似度高，从而可以在保护

双方隐私的前提下,让客户得到诊断结果,但上述方案的时间 复杂度为0(n)，且需要使用的门和0T的数量与比对次数成

正比。在基因组数据库较大时,需要较大的计算开销和通信

开销，因此当数据库中数据量n逐渐增加时，该方案将不再适

用。可见，虽然该方案可以保护隐私，但效率不高。为了减少

140计算机应用第40卷比对次数,提高基因比对的效率，本文利用ORAM和混淆电 路提出了一种基于ORAM的基因比对方案,该方案不仅降低 了时间复杂度，同时减少了比对次数和整体的开销。3基于ORAM的基因比对方案在基于线性扫描的基因比对方案中，为了保护隐私，客户

的基因序列必须与服务器端数据库中的基因序列逐个进行比

对，否则便会泄露自己的基因序列甚至自己的健康状况(疾

病)，当服务器端数据库较大时，该方案明显不再适用，因此, 本文利用ORAM和混淆电路技术，提出了一种高效的基于 ORAM的基因比对方案。本文设计的基于ORAM的基因序列诊断方案采用 Circuit ORAMo在该方案中,客户端被表示为电路，相比于其

他ORAM方案，构造Circuit ORAM需要的电路规模更小。假设客户有一条基因序列a,服务器端有一个基因组数

据库0,数据库的大小为\"，数据库中每一个数据项长为 I

和k为安全参数,ORAM上每个节点可存储B个数据项,

ORAM的高度为log n,a'的标识符为\"。基于ORAM的基因比

对方案分为以下3个阶段。1) 初始化阶段。① 初始化ORAM：两方运行安全计算协议，根据协商好

的参数初始化ORAM结构，即ORAM j Initial( A ,“,d),设 shareGen()为秘密产生函数，在该函数中，若秘密为s,则利

用shareGen()随机产生一个串作为一个子份额\"，另一个子

份额r2 = “㊉s,则s =九㊉％。初始化ORAM之后，根据 ORAM并利用shareGen函数产生子份额分发给两方，即

(ORAM a, ORAMb) j shareGen( ORAM,1*),则两方各存有空 ORAM的子份额。② 将数据存储到ORAM上：在初始化ORAM后,ORAM

的存储为空。服务器方设置n条写指令/('write”，2, 0[ i]),

并利用shareGen函数将这\"条指令拆分成子份额给两方，即

(4,4) shareGen(7; ,1A)。两方运行安全计算协议执行n条

写指令人在执行每一条写指令时，分为以下3个步骤：a) 重构 ORAM：OR4M = ORAM” ㊉ ORAMbob) 重构指令『J =乙㊉人。c) 执行每条指令r并更新两方存储的ORAM的子份额:ORAM”, ORAMb — Exec (F, ORAM)每执行一条指令，可将数据库0中的一项写到ORAM上, 同时两方存储的ORAM的子份额会一直更新，直至将所有数

据存到ORAM上,在执行n次写操作之后，两方各存有一份最 终的ORAM的子份额。2) 基因序列比对阶段。① 在初始化阶段之后，对于数据库0每一个基因数据项

\"，两方各有v对应的叶子节点的子份额,表示为i'a和rlo② 客户欲查找某个基因数据项a'对应的标识符为x,双

方根据子份额和石将所有叶子节点卩重构出来，即卩=㊉

石,并查找得到％对应的叶子节点lo③ 双方根据叶子节点I和存储在两方的ORAM子份额,

运行安全计算协议将路径PQ)上所有数据取出来，即(％，如， …,a',…,\"叫”)<—readPath(Z)，然后将客户的基因序列a

与取出的B log “个数据逐个利用混淆电路进行基因比对。当

访问到数据a',且a与a'的相似度达到96%时认为a与/同 源，返回比对结果。④ 在所有比对操作之后，重新产生新的叶子节点广，执

行写指令八：=(“write”\"，0[订)，将数据重新写入到

ORAM中，并更新两方持有的ORAM子份额。3)返回结果阶段。根据基因序列比对的结果,将结果返回给客户。如果客

户需要继续进行基因比对，则重复以上步骤。在上述方案中，因为只需将目标数据所在路径上的数据 取出进行比对，因此可以将比对次数减小到B log \"次。当\"= 1024,5 = 3时，基础方案需要比对1024次，而该方案只需比

对30次。4安全性证明和性能对比4.1安全性证明针对半诚实模型下提出的基于线性扫描的基因比对方

案，以下证明了不同参与方被时的安全性。证明 n”弋表方案1，分析在现实场景下执行IL和在理 想场景下执行/。构建一个模拟器Sims，调用敌手4服务器，接收a, 0,\"。对于；=1,2,••- ,n,Sims根据a和0”由可信第三方调用

混淆电路进行比对，并记录比对结果。最后Sims将比对结果

给4,产生和4 一致的输出。对于模拟器Si%和安全参数k,REALmg』n 表示

Si叫在现实场景下执行巧的输出JDEALwsgs⑷表示

Sims在理想场景下执行/'的输出。定义1方案nx是安全的,如果对于任意非均匀的多项

式时间敌手d参与方,并在现实场景下运行E,则存在

一个非均匀的多项式时间对手4参与方,并在理想场景

下中运行/，表示为：REALES, a,zg wIDEALfgaz® (3)客户被的场景与服务器被的场景类似,不再赘 述。综上，方案1达到了理想与现实不可区分的目标，证明方

案1在不同参与方被时均是安全的。以下是针对半诚实模型下提出的基于ORAM的基因比

对方案，证明了不同参与方被时的安全性。证明IL代表方案2,分析在现实场景下执行n?和在理

想场景下执行F。构建一个模拟器Sims，调用敌手4服务器，接收a, 0,noSims初始化ORAM之后，由可信第三方计算shareGen,均

匀随机选择ORAM”和0RAMboSims将0RAMh给4,作为

shareGen的输出，产生和人一致的输出。然后Sims设置『,由可

信第三方计算shareGen,均匀随机选择佥和rb,Sims将几给4,

作为shareGen的输出，产生和A 一致的输出oSims收到A的

ORAMb和A ,并根据0RAMa和£执行\"条写指令，将\"个数据 写入ORAM中。对于i = 1,2,••- ,n,Sims收到4的2；,根据2：,和 计算V，并得到x对应的2,将I所对应的路径上的数据块取

出。最后对于i = 1,2,…,B log \"，模拟器Si%根据a和％，由

可信第三方调用混淆电路进行比对，记录比对结果。在迭代结

束后,Sims随机挑选广，设置指令厂并执行指令厂.Sims将

更新后的ORAMb给4,产生和d —致的输出。对于模拟器Sims、安全参数入和k,REAL^g a

表示Si%在现实场景下执行巧的输出，血已人匚““』〉』％。®表

示Sims在理想场景下执行F的输出。定义2方案n2是安全的,如果对于任意非均匀的多项

式时间敌手a参与方,并在现实场景下运行n2,则存在

第1期李功丽等：面向用户隐私保护的高效基因比对方案141一个非均匀的多项式时间对手4参与方,并在理想场景

下中运行F,表示为：REALn2（a m iims（AM =IDEALF（a ⑷客户被的场景与服务器被的场景类似,不再赘

述。综上所述，方案2达到了理想与现实不可区分的目标，证 明方案2在不同参与方被时均是安全的。4.2性能对比本文所有实验均在局域网内两台配置相同的PC上模拟

执行。其中，一台PC模拟服务器，一台模拟客户，内存为

8 GB,操作系统为Windows 10,CPU类型为Intel Xeon,主频为 3.00 GHz,4核心。本文中所处理的基因序列均是来自NCBI

（National Center for Biotechnology Information）o在实验时，基因序列长度定为32,ORAM中节点的容量B

定为3。为了确定本文所提出的基因比对方案的性能，首先

将本文所提出的两个方案进行纵向比较，在服务器端基因组

数据库中基因序列个数\"为2*⑵和2\"时，得出了方案1和

方案2的运行时间并比较了两种方案的性能,实验结果如表 1和表2所示。之后进一步与其他文献中的同类方案进行横

向比较。由于在整个基因序列比对中，比对时间即编辑距离

占总运行时间的比例最大，因此在相同环境下,针对不同长度

的基因序列，分别测试了本文的编辑距离方案、Jha等⑷和

Blanton等〔回提出的编辑距离协议的运行时间，并对4种编辑距离方案进行比较分析，结果如图3所示。・Tha° Jha-3・l

-°-Blanton本文方案

DNA序列中碱基的个数图3四种编辑距离方案的运行时间对比Fig. 3 Running time comparison of four Levenshtein distance schemes1）纵向对比:方案1和方案2的运行时间对比。表1显示了在不同数据库大小的情况下，第1种方案平 均需要的0T的时间、门的数量以及总运行时间。可以看出， 在第1种方案中,0T的时间、门的数量和总运行时间随基因

组数据库中数据量\"的增大线性增长，且增长速度明显。表1基于线性扫描的基因比对方案的运行时间Tab. 1 Running time of genetic comparison scheme based on linear scan数据库大小0T的时间/s门的数*/104总运行时间/S28.0142.591339.3629105.0385.192678.51210213.50170.395 370.43表2显示了第2种方案在不同大小的数据库下,平均需 要构造ORAM的时间、读路径时间、取出基因数据之后的比

对时间以及总运行时间。在计算第2种方案的总运行时间

时，并未将构造ORAM的时间计算在内，因为在构造一次

ORAM之后，客户可以进行无数次比对,这样分摊到每一次的

时间可以忽略。从表2中可以看出，在第2种方案中，构造 ORAM的时间和读路径时间随着数据量n的增大线性增长,

且相比于读路径时间，比对时间占总运行时间的比例较大,而 比对次数为B log “，因此比对时间亚线性于数据库大小，所以总运行时间随着数据量n的增长也呈现亚线性增长的趋

势。表2基于ORAM的基因比对方案的运行时间单位:sTab. 2 Running time of genetic comparison scheme based onORAMunit: s数据库大小构造ORAM时间读路径时间比对时间总运行时间2862.082.38127.12129.5029120.584.42143.16147.58210253.438.57159.168.11另一方面，在表1中，当数据库大小\"为2\"时，比对时间

平均需要1.5 h,而在表2中，当数据库大小\"为2\"时，总运

行时间平均只需要16& 11 s。综合表1和表2可以看出，当

数据量为28时，第1种方案时间约是第2种方案的10倍;数

据量为29时，第1种方案时间约是第2种方案时间的18倍; 而当数据量为2\"时，第1种方案时间约是第2种方案时间的 31倍，因此，第2种方案的执行效率明显优于第1种方案，而

且当数据库中数据量越大时，这种优势会更加明显。2）横向对比:与其他文献中编辑距离方案的时间对比。根据纵向实验结果可知,本文提出的第2种方案明显地 减少了基因序列比对时所需要的比对次数。为了进一步验证

本文所提方案的性能，将本文方案与其他基因比对方案的性 能进行了比较。因为比对时间占总运行时间比例最大，因此

在相同的环境下，将本文的编辑距离方案与Jha等两提出的

三种基因编辑距离协议中性能较好的协议一、协议三和

Blanton等〔回提出的基因编辑距离方案进行对比，在图3中

分别表示为本文方案Jha-1 Jha-3和Blanton。测试时基因序

列长分别为8、12、16、20、25和32个时,不同方案的运行时间

如图3所示。从图3中可以看出，在DNA序列长度为32时， Jha-3的运行时间约为28.6 s, Jha-1的运行时间约为14.1 s,

Blanton的运行时间约为6. s,而本文的编辑距离方案中的

运行时间仅需要5.31 s,这表明本文方案中的基因编辑距离

的运行时间明显小于Jha和Blanton提出的协议，而计算编辑

距离的时间占方案的总运行时间比例最大，因此本文所提出 的基因序列比对方案具有更高的比对效率。为了验证本文比对方性,进一步测试了本文方 案中基因序列比对的误差率，因为在不同的编码长度＜7,编码

原理是一样的，理论上误差率是相同的,所以在实验时，采用 ＜7 = 2进行基因序列比对,发现在＜7 = 2时，与普通实现（基于

基因数据的明文比对方案）的结果相同，即本文方案在实现

基因比对隐私性的同时，保证了基因序列比对的准确性（误

差率为0）。文献［25］也分析了在不同编码参数下所提方案 的误差率，误差率位于0. 01%到0. 36%之间，高于本文所提

的方案的误差率,表明本文方案满足基因序列比对时对准确

性的要求。5结语如何在高效地进行基因序列比对时实现隐私信息的保护

是目前亟须解决的问题，本文利用ORAM技术抗访问模式泄 露的特性，提出了一种基于ORAM的基因比对方案,具有保

护用户隐私信息、时间复杂度低和高效安全等特点，解决了传

统的基因比对方案中存在的隐私信息泄露和效率低下的问

题。从实验结果和性能分析上看，本文所提方案的硬件和时

间开销均较小，该方案对于个人医疗和医学的研究具有重要

142计算机应用第40卷的应用价值。接下来的工作将考虑如何把ORAM存储结构 放置在云服务器上，并进一步探究如何放置更长的基因数据

项，利用并行计算技术实现更大规模的基因存储和比对。参考文献(References)[1] 23andMe. Find out what your DNA says about you and your family

[EB/OL]. [2019-01-09] . https://www. 23andme. com/en-inM.[2]

BALD P, BARONIO R, DE CRISTOFARO E, et al. Efficient and secure testing of fully-sequenced human genomes[ J]. Biological Sci­

ences Initiative, 2000, 470: 7 - 10.[3]

DE CRISTOFARO E, FABER S, GASTI P, et al. Genodroid: are privacy-preserving genomic tests ready for prime time? [ C] // Pro­

ceedings of the 2012 ACM Workshop on Privacy in the Electronic Society. New York： ACM, 2012： 97 -108.[4]

KIM M, LAUTER K. Private genome analysis through homomorphic

encryption [ J]. BMC Medical Informatics and Decision Making,

2015, 15( S5)： No. S3.[5]

YAO A C. Protocols for secure computations[ C]// Proceeding of the 23rd Annual Symposium on Foundations of Computer Science.

Piscataway: IEEE, 1982: 160 - 1.[6]

GOLDREICH 0, MICAU S, WIGDERSON A. How to play ANY

mental game[ C] // Proceedings of the 9th Annual ACM Symposium

on Theory of Computing. New York: ACM, 1987: 218 -229.[7]

HUANG Y, EVANS D, KATZ J. Private set intersection: are gar­bled circuits better than custom protocols?[ C]// Proceedings of the

19th Annual Network and Distributed System Security Symposium. Reston, VA: The Internet Society, 2012: 1 - 15.[8]

JHA S, KRUGER L, SHMATIKOV V. Towards practical privacy for genomic computation[ C] // Proceedings of the 2008 IEEE Sym­posium on Security and Privacy. Piscataway: IEEE, 2008: 216 -

230.[9]

HUANG Y, EVANS D, KATZ J, et al. Faster secure two-party computation using garbled circuits [ C ] // Proceedings of the 20the

USENIX Conference on Security. Berkeley, CA: USENIX Associa­tion, 2011： 35 -35.[10]

BLANTON M, ATALLAH M J, FRIKKEN K B, et al. Secure and

efficient outsourcing of sequence comparisons] C] // Proceedings of the 2012 European Symposium on Research in Computer Security,

LNCS 7459. Berlin: Springer, 2012: 505 -522.[11]

CHOI S G, HWANG K W, KATZ J, et al. Secure multi-party computation of Boolean circuits with applications to privacy in on­

line marketplaces [ C ] // Proceedings of the 2012 Cryptographers' Track at the RSA Conference, LNCS 7178. Berlin: Springer,

2012： 416 -432.[12]

GOLDREICH 0, OSTROVSKY R. Software protection and simula­

tion on oblivious RAMs[ J]. Journal of the ACM, 1996, 43(3): 431 -473.[13] SHI E, CHAN T H H, STEFANOV E, et al. Oblivious RAM with 0( (log N) 3) worst-case cost[ C]// Proceedings of the 2011 Inter­

national Conference on the Theory and Application of Cryptology

and Information Security, LNCS 7073. Berlin: Springer, 2011: 197 -214.[14] 孙晓妮，蒋瀚，徐秋亮.基于二叉树存储的多用户ORAM方案

[J].软件学报，2016, 27(6): 1475 -1486. (SUN X N, JIANG

H, XU Q L. Multi-user binary tree based ORAM scheme [ J ]. Journal of Software, 2016, 27(6): 1475 - I486.)[15]

GORDON S, HUANG X, MIYAJI A, et al. Recursive matrix ob­

livious RAM: an ORAM construction for constrained storage de- vices[ J]. IEEE Transactions on Information Forensics and Securi­ty, 2017, 12(12)： 3024-3038.[16] GORDON S D, KATZ J, WANG X. Simple and efficient two-serv-

er 0RAM[ C] // Proceedings of the 2018 International Conference

on the Theory and Application of Cryptology and Information Secur­ity, LNCS 11274. Cham: Springer, 2018:141 -157.[17]

GORDON S D, KATZ J, KOLESNIKOV V, et al. Secure two-par­

ty computation in sublinear (amortized) time[ C]// Proceedings of the 2012 ACM Conference on Computer and Communications Secu­

rity. New York: ACM, 2012: 513 -524.[18] LU S, OSTROVSKY R. Distributed oblivious RAM for secure two- party computation[ C] // Proceedings of the 10th Theory of Cryptog­

raphy Conference. Berlin: Springer, 2013: 377 -396.[19]

WANG X S, HUANG Y, CHAN T H H, et al. SCORAM： oblivi­ous RAM for secure computation[ C]// Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Secur­

ity. New York： ACM, 2014： 191 -202.[20] WANG X, CHAN H, SHI E. Circuit ORAM: on tightness of the Goldreich-Ostrovsky lower bound[ C]// Proceedings of the 22nd

ACM SIGSAC Conference on Computer and Communications Secur­

ity. New York： ACM, 2015: 850 -861.[21] NAOR M, PINKAS B. Efficient oblivious transfer protocols[ C]//

Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied

Mathematics, 2001: 448 -457.[22]

赵作鹏，尹志民,王潜平，等.一种改进的编辑距离算法及其在

数据处理中的应用计算机应用，2009, 29(2)： 424 -426.(ZHAO Z P, YIN Z M, WANG Q P, et al. An improved algorithm

of Levenshtein distance and its application in data processing[ J]. Journal of Computer Applications, 2009, 29( 2): 424 -426.)[23]

KOLESNIKOV V, SCHNEIDER T. Improved garbled circuit: Free XOR gates and applications[ C]// Proceedings of the 2008 Interna­

tional Colloquium on Automata, Languages, and Programming,

LNCS 5126. Berlin: Springer, 2008: 486 -498.[24] NCBI. National Center for Biotechnology Information [ EB/OL].

[2019-02-18]. https: //www. ncbi. nlm. nih. gov/.[25]

王立昌，方勇.基于安全多方计算的分布式基因序列相似性计

算□]•计算机应用研究，2016, 33(12)： 3681 -3685, 3704. (WANG L C, FANG Y. Distributed genome similarity calculation based on secure multiparty computation [ J]. Application Research

of Computers, 2016, 33(12)： 3681-3685, 3704.)This work is partially supported by the National Natural Science Foun­dation of China ( U1604156, 61772176, 61602158), the Science and

Technology Research Project of Henan Province ( 172102210045, 192102210131).LI Gongli, bom in 1981, Ph. D. , lecturer. Her research interests include information security.LI Yu, bom in 1998. Her research interests include information se­

curity, cryptography.ZHANG En, bom in 1974, Ph. D., associate professor. His re­

search interests include information security, cryptography.YIN Tianyu, bom in 1999. His research interests include secure multiparty computation.