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

李功丽，李 钰，张 恩，尹天宇

(1.河南师范大学 计算机与信息工程学院，河南 新乡 453007；2.“智慧商务与物联网技术” 河南省工程实验室(河南师范大学)，河南 新乡 453007)

0 引言

目前基因检测技术和各类检测平台是一把双刃剑，人们既想要借助此类技术尽早诊断出疾病，但是又担心自己的基因信息会泄露，而现有的基因检测平台，大多只是实现基因比对，无法保证用户隐私信息的安全。例如基因疾病检测平台23andme[1]，用户将自己的基因信息提供给它，它通过对用户的基因进行检测并反馈给用户一份健康报告，由于存在隐私泄露的问题，被屡屡叫停，因此亟须设计一种既能实现基因序列比对又能保护用户隐私的方案。

Bald等[2]利用隐私集合比较(Private Set Intersection, PSI)技术，提出了可以在亲子鉴定、定制医疗等方面提供隐私保护的安全协议，该协议可以统计出两条脱氧核糖核酸(Deoxyribonucleic Acid, DNA)序列相同位点上相同碱基的数目，但该方案不支持基因位点的插入、删除和修改等操作，缺乏灵活性。De Cristofaro等[3]设计了一个基因组工具箱，提出在基因检测时，先把数据逐个加密存储在智能设备上，再用于后续计算，并对基因组工具箱的可用性进行研究，研究表明，该方案在基因组测试时具备一定的可行性，但该方案着重介绍了安全计算理论，缺乏有效的性能分析。Kim等[4]利用全同态加密实现了近似编辑距离计算，它允许在密文上进行运算而不用加解密数据，但它需要约28 s才能获得两条序列上八对DNA的编辑距离，方案效率较低。基于安全多方计算的隐私保护协议是另一个能够实现安全基因序列比对的工具，因为安全多方计算的目标是使多个参与方协同完成某项任务，同时不泄露除了计算结果外的用户隐私信息，所以它比较适合用户之间进行安全的基因序列比对。目前，实现安全计算的方法主要有Yao[5]的混淆电路(Garbled Circuit， GC)和Goldreich等[6]提出的秘密共享理论(Goldreich-Micali-Wigderson, GMW)协议，后来的安全多方计算协议[7-9]大多都是基于Yao[5]的混淆电路。目前安全计算协议有两种实现方法：一种是把待计算的函数表示为布尔电路；另一种方法是表示为算术电路。Huang等[7]在布尔电路上设计并实现了高效的隐私集合比较协议，其研究结果表明，通过合理地设计电路，基于混淆电路实现的安全多方计算的协议在某些情况下的效率要高于一些自定义协议。

编辑距离的计算可以实现基因序列的比对，从而预测两条基因序列的相似度，基于安全多方计算实现的编辑距离方案逐渐受到人们的关注，Jha等[8]提出了三种基于安全多方计算设计的编辑距离协议，但这三种协议需要保存整个混淆电路直到构造完成，限制了混淆电路中输入的大小。Huang等[9]针对该问题提出了Pipelined Circuit Execution技术，可以一边构造混淆电路一边计算混淆电路，即混淆电路的构造和计算可以并行执行，因此可以支持大输入的场景。Blanton等[10]基于混淆电路提出将基因序列的比对云外包给服务器，避免了公钥加密操作，实现了在隐私保护下，编辑距离的快速计算。Choi等[11]实现了安全多方计算中的GMW协议，主要用于待计算的函数可以被表示为布尔电路的场景，研究结果表明，基于安全多方计算设计保护隐私的方案是可行的。由于Choi等[11]和Huang等[9]的工作，使得安全地进行基因序列比对成为了可能。

现假设Alice(客户)怀疑自己得了某种基因疾病，而Bob(服务器)有一个可以用来检测疾病的基因组数据库，Alice想让Bob帮她诊断自己是否得这种疾病，设计隐私保护的比对方案要实现以下两个安全目标：

1)Alice不需要把自己的基因信息直接给Bob，Bob也不需要直接将它的基因组数据库给Alice，这样可以避免双方数据的泄漏。

2)比对结束后，Bob无法知道Alice是否得病的信息，即Bob不能获得比对结果的信息。

针对上述安全目标，首先，为了防止直接利用明文数据进行比对会泄露基因信息，将基因序列进行编码混淆；其次，为了确保基因比对过程不会泄露基因信息，将Alice的基因与Bob方基因组数据库中的数据逐个进行比对，由此得出了第一种基于线性扫描的基因比对方案。该方案可以实现隐私保护下的基因比对。

但是因为第一种方案需要线性扫描基因组数据库，时间复杂度较高，当比对的目标数据库较大时，该方案的效率较低。针对上述问题，本文利用不经意随机存取(Oblivious Random Access Memory, ORAM)和混淆电路技术，提出了一种基于ORAM的基因比对方案，在上述应用场景：客户想要确定自己是否得了某种病，期望从服务器端的基因数据库中取出该病的致病基因片段与自己的基因序列进行比对，根据比对的结果来验证自己的判断。假设客户持有一个基因序列α，服务器持有一个基因数据库β，基因数据已被加密存储在ORAM上，客户期望在基因数据库中找到致病基因片段α′，同时不想让服务器知道她期望得到什么数据，因为这可能泄漏她的基因信息，而在客户访问基因序列α′的过程中，要保证服务器端无法确定用户是否访问了α′，因为访问模式的泄漏可能引起基因信息的泄漏，而ORAM可以抗访问模式泄漏，它可以将一条ORAM指令转换为多条RAM指令去执行，最后可以访问到期望的数据而不泄露自己的访问模式。利用ORAM把目标数据α′所在路径上的数据全部取出后，双方再利用混淆电路进行基因比对，在取数据和基因比对的整个过程中，均不会泄漏双方的隐私信息。该方案是先取数据再进行基因序列比对，为了取出期望得到的序列，需要取出O(logn)(n是数据库的大小)个数据，再利用混淆电路将α与这O(logn)个数据进行比对；而第一种方案是直接利用混淆电路进行基因比对，为了实现保护隐私的目的，需线性扫描整个基因数据库β中所有的序列与α进行比对，比对次数为O(n)。

实验结果表明，改进后的方案不仅可以实现上述的两个安全目标，而且可以有效地降低比对次数，特别是当基因组数据库中数据量较大时，该方案的效率相比传统方案将会明显提高。在最后的性能对比中，用包含不同数据量的基因组数据库进行基因比对的时间测试，比较了基础方案和改进后的方案的性能，证明了所提方案的有效性和可行性。

1 基础知识

1.1 ORAM

ORAM最早是由Goldreich等[12]在1996年提出的，用来解决软件逆向工程问题，后来Shi等[13]提出了一种基于二叉树的ORAM方案，被广泛应用于软件保护、安全计算、密文搜索等方面。ORAM是一种抗访问模式泄露的隐私保护技术，它主要涉及用户和服务器两个主体，用户既可以将数据存储到服务器上，也可以向服务器提出检索数据的请求，数据在服务器上以二叉树形式存储，二叉树的每一层由若干个节点组成，每个节点可以存储O(logn)个数据项。它的基本思想是：用户要访问某个数据时，查找索引表得到该数据对应的叶子节点，为该数据重新分配叶子节点和更新索引表，并将对应的路径提供给服务器，服务器把该路径上所有的数据给用户，用户依次解密这些数据，最终可以得到期望的数据。用户和服务器通过网络协议实现交互访问数据的同时，服务器不能推测出用户访问的数据。在基础的基于二叉树的ORAM方案之后，为了提升ORAM的效率，文献[14-16]中提出了一系列改进的ORAM方案。Gordon等[17]首次提出，ORAM和安全多方计算结合可以实现时间复杂度为亚线性的安全算法，文献[18-20]中提出了一系列与安全计算相结合的ORAM方案。

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

y:=((op1,arg1),(op2,arg2),…,(opM,argM))

其中，op代表一次read或者write操作，若op=read，则argi=idx；反之,op=write，argi=(idx，datai)，idx表示当前欲访问数据项的标识符，datai表示该数据项对应的真正数据。以一次访存请求Access(op)为例，ORAM操作的主要过程如下：

1)如图1所示，当用户想要访问标识符为idx的数据时，首先查找本地的索引表PositionMap，得到数据项idx对应的叶子节点l，并为数据项idx重新分配叶子节点l*，更新索引表中PositionMap[idx]的值，即PositionMap[idx]=l*。

2)用户依次读取路径p(l)上(图1中虚线指示的路径)的每个数据，解密这些数据，若读到idx对应的数据项(idx‖PositionMap[idx]‖data)时，记录下该数据并用无效数据项⊥代替加密写回；反之将读到的数据重新加密写回。最后如果读出了idx对应的数据，返回该数据；反之返回⊥。

3)若op=read，则把idx所对应的数据data取出，更新数据项内容为(idx‖PositionMap[idx]‖data)，若op=write，则更新数据内容(idx‖PositionMap[idx]‖data*)。最后将该数据重新加密写入根节点root。

4)在每次将数据写入根节点之后，用户需从服务器端二叉树的每一层挑选两个节点进行下移操作，若该节点中都是无效数据项⊥，则选取两个无效数据项⊥，重新加密向它的左右孩子节点各写入一个加密后的⊥；否则，选取一个有效数据项和一个无效数据项⊥，将它们重新加密，根据p(l)，将有效数据写入指定的孩子节点，将无效数据⊥写入另一孩子节点。

1.2 混淆电路

混淆电路(GC)是Yao[5]在1982年提出的，在安全两方计算中，如果两方的输入可以转换为布尔值时，混淆电路可以高效地解决此类安全计算问题，最开始用于解决经典的百万富翁问题。它的基本思想是：发送方对输入值进行混淆，并根据待计算的函数f构造混淆电路G(C)，将混淆表和发送方输入的混淆值发送给接收方，接收方通过与发送方运行不经意传输(Oblivious Transfer, OT)协议[21]来得到它的混淆值，从而接收方能够正确地计算该混淆电路。使用混淆电路方案来解决安全两方计算问题时主要分为构造混淆电路、计算混淆电路和恢复真正的输出结果三个阶段。混淆电路方案的过程如下。

1) 混淆电路构造阶段。

设函数f对应的电路为C，发送方通过以下两个步骤来构造混淆电路G(C)。

2)混淆电路的计算。

④对于门gi的输出，如果门gi是中间某个门时，将门gi输出的混淆值继续作为另一个门的输入重复上述操作进行计算，直至计算完整个混淆电路。

3)恢复真正的输出结果。

接收方根据输出转换表，将混淆电路G(C)输出的混淆值转换为真正的输出结果，再将结果给发送方。

在上述混淆电路方案中，实现隐私数据的传输采用的是OT协议。在t～nOT协议中，接收者持有t个索引值b∈{0,1}，同时发送者拥有n个信息{m1,m2,…,mn}。在执行OT协议时，接收者能够根据索引值从发送者的n个信息中获取对应的t条信息，但是无从知道其他的n-t条信息，而发送者也不知道接收者的索引值，因此无法知道接收者接收的信息。在本文中，使用的是1～2 OT协议，即发送者拥有两条信息，接收者持有一个选择位b，b∈{0,1}。执行1～2 OT协议之后，接收者会获取与选择位b相对应的信息。OT协议是实现安全计算的重要工具，通过执行OT协议，可以实现隐私信息的安全传输。

1.3 编辑距离

编辑距离(Levenshtein Distance)可以用来检测两条基因序列的相似度，文献[22]中提出了一种改进的编辑距离算法。其基本原理是计算至少需要多少次操作才能将一条基因序列转换为另一条基因序列，操作主要包括碱基的插入、删除和替换。例如，有如下两条基因序列α和β：

α=GTTACTTTGG

β=CTTACCTTT

为了将α变为β，需要在第1个位置将碱基G变为C，在第6个位置插入碱基C，在第9和第10个位置删除两个碱基G，可得编辑距离为4。

在初始化时，D数组的初值表述为如下：

(1)

初始化后，两条基因序列的编辑距离可以用式(2)得到：

D[i][j] ← min(D[i-1][j]+1,D[i][j-1])+1,

D[i-1][j-1]+t)

(2)

其中，D[i][j]表示序列α的前i个位点到序列β的前j个位点的编辑距离。如果α[i]≠β[j]，t(i,j)的值为1，否则为0。具体的编辑距离计算过程如算法1所示。

算法1 基因序列编辑距离计算过程。

输入：DNA序列α和β。

输出：α和β的编辑距离D。

la←α.length,lb←β.length;

D← 0;

Foriinlado:

D[i][0] ←i;

End

Forjinlbdo:

D[0][j] ←j;

End

Foriinlado:

Forjinlbdo:

t← (α[i]=β[j])?0:1;

D[i][j] ← min(D[i-1][j]+1,D[i][j-1])+1,

D[i-1][j-1]+t)

End

End

ReturnD

2 基于线性扫描的基因比对方案

为了实现隐私保护下的基因序列比对，本文首先提出了基于线性扫描的基因比对方案。该方案的基本思想是：先对基因序列进行混淆编码，然后根据基因序列比对程序设计相应的布尔电路并构造混淆电路，进而采取线性扫描的方式将客户的基因序列和服务器端的基因组数据库中的基因序列逐个利用混淆电路进行比对。在整个比对过程中，首先因为对基因数据进行了混淆编码，所以双方不会泄漏自己的基因数据，而且因为是与服务器中的每个基因序列进行比对，每次只有客户得到真正的比对结果，因此服务器无法确定用户与哪个基因序列的相似度高，所以也无法根据用户的比较对象推测比较结果。

2.1 基因序列编码

先将客户的基因序列和服务器端基因组数据库的基因序列作如下处理：

1)确定编码规则并编码。用两个比特位对碱基A，T，C，G进行编码，分别编码为00，01，10，11。将DNA序列按照编码规则进行编码，每个DNA序列最后被编码成一个二进制串。

2.2 布尔电路设计

为了减小混淆电路的规模，先对算法1进行分析，提出只有需要协同计算来保护隐私的操作才采用Yao[5]的混淆电路实现，这样可以有效地减少混淆电路带来的开销。根据分析，将算法1转换为图2的布尔电路，主要用到以下4种门电路：MIN门、ADD门、MUX门、EDT门。

MIN门 该门以两个mbit的数据S和T作为输入。若S>T，则输出mbit的数据T；反之，则输出mbit的数据S。

ADD门 该门以一个mbit的数据S和一个1 bit的数据q，q∈{0,1}作为输入。输出S加上q后的mbit数据。

MUX门 该门以两个长度为mbit的数据S和T以及1位的选择位b作为输入。若b=0，则输出S；反之输出T。

EDT门 该门以两个mbit的数据S和T作为输入。若S=T，则输出0；反之输出1。

具体计算过程如图2所示，先比较D[i-1][j]和D[i][j-1]，选出最小值，再与D[i-1][j-1]比较，产生1位的b。若min(D[i-1][j],D[i][j-1])大于D[i-1][j-1]，则b为0，MUX门的输出为t，否则MUX门的输出为1，最后取第二个MIN门的输出值加MUX门的输出值为整个电路的输出。

图2 基因比对的核心布尔电路Fig.2 Core Boolean circuit of genetic comparison

2.3 基因序列比对

将客户的基因序列与服务器端基因组数据库中每个序列依次进行比对。在每一次的比对操作时，根据产生的混淆编码值和设计的布尔电路构造出混淆电路，然后将混淆电路交由服务器方进行计算，最后服务器方将基因比对的结果返回给客户，而此时的结果是混淆编码值，只有客户端才能解码转换为真正的明文结果，避免了服务器获得真正的比对结果。

具体过程：客户持有DNA序列α，服务器端有一个包含n条基因序列的基因组数据库β，令α与β中的n条序列逐个进行比对，在每次比对时，采用混淆电路来计算两条序列的相似程度，根据相似度来确定客户是否患有这种DNA疾病，若某次比对时两条序列相似度达到96%的时候，即判定两条序列同源。利用Huang等[9]提出的Pipelined Circuit Execution技术对代码进行优化，每构造一个门的混淆表和输入的混淆值之后，就可以发送给服务器进行计算，并行执行整个电路，这样可以大幅度减少构造混淆电路时占用的内存，提高混淆电路的执行效率。同时利用Kolesnikov等[23]提出的Free-XOR技术来减少混淆电路的开销。

在实验测试时，安全参数k定为80，执行的”base” OT的次数为k。将两方的基因序列长定为32时,一次基因比对所需门的数量为1 664个，平均需要的总时间为5.31 s，其中，OT所占的时间为0.24 s。

在上述方案中，客户的基因序列与服务器端基因组数据库里面所有的基因序列逐个进行比对。每次比对都使用混淆电路来实现，因此可以保证每次比对过程中基因信息的安全，且因为是比对了基因组数据库中的所有序列，所以服务器无法确定客户到底与哪个DNA序列相似度高，从而可以在保护双方隐私的前提下，让客户得到诊断结果，但上述方案的时间复杂度为O(n)，且需要使用的门和OT的数量与比对次数成正比。在基因组数据库较大时，需要较大的计算开销和通信开销，因此当数据库中数据量n逐渐增加时，该方案将不再适用。可见，虽然该方案可以保护隐私，但效率不高。为了减少比对次数，提高基因比对的效率，本文利用ORAM和混淆电路提出了一种基于ORAM的基因比对方案，该方案不仅降低了时间复杂度，同时减少了比对次数和整体的开销。

3 基于ORAM的基因比对方案

在基于线性扫描的基因比对方案中，为了保护隐私，客户的基因序列必须与服务器端数据库中的基因序列逐个进行比对，否则便会泄露自己的基因序列甚至自己的健康状况(疾病)，当服务器端数据库较大时，该方案明显不再适用，因此，本文利用ORAM和混淆电路技术，提出了一种高效的基于ORAM的基因比对方案。

本文设计的基于ORAM的基因序列诊断方案采用Circuit ORAM。在该方案中，客户端被表示为电路，相比于其他ORAM方案，构造Circuit ORAM需要的电路规模更小。

假设客户有一条基因序列α，服务器端有一个基因组数据库β,数据库的大小为n，数据库中每一个数据项长为d,λ和k为安全参数，ORAM上每个节点可存储B个数据项，ORAM的高度为logn，α′的标识符为x。基于ORAM的基因比对方案分为以下3个阶段。

1)初始化阶段。

①初始化ORAM：两方运行安全计算协议，根据协商好的参数初始化ORAM结构，即ORAM ← Initial(λ,n,d)，设shareGen()为秘密产生函数，在该函数中，若秘密为s，则利用shareGen()随机产生一个串作为一个子份额r1，另一个子份额r2=r1⊕s，则s=r1⊕r2。初始化ORAM之后，根据ORAM并利用shareGen函数产生子份额分发给两方，即(ORAMa,ORAMb) ← shareGen(ORAM,1λ)，则两方各存有空ORAM的子份额。

a)重构ORAM：ORAM=ORAMa⊕ORAMb。

c)执行每条指令Ii并更新两方存储的ORAM的子份额：

ORAMa,ORAMb← Exec(Ii,ORAM)

每执行一条指令，可将数据库β中的一项写到ORAM上，同时两方存储的ORAM的子份额会一直更新，直至将所有数据存到ORAM上，在执行n次写操作之后，两方各存有一份最终的ORAM的子份额。

2)基因序列比对阶段。

③双方根据叶子节点l和存储在两方的ORAM子份额，运行安全计算协议将路径p(l)上所有数据取出来，即(v1,v2,…,α′,…,vB log n) ← readPath(l)，然后将客户的基因序列α与取出的Blogn个数据逐个利用混淆电路进行基因比对。当访问到数据α′，且α与α′的相似度达到96%时认为α与α′同源，返回比对结果。

④在所有比对操作之后，重新产生新的叶子节点l*，执行写指令I*:=(“write”,l*,β[i])，将数据重新写入到ORAM中，并更新两方持有的ORAM子份额。

3)返回结果阶段。

根据基因序列比对的结果，将结果返回给客户。如果客户需要继续进行基因比对，则重复以上步骤。

在上述方案中，因为只需将目标数据所在路径上的数据取出进行比对，因此可以将比对次数减小到Blogn次。当n=1 024，B=3时，基础方案需要比对1 024次，而该方案只需比对30次。

4 安全性证明和性能对比

4.1 安全性证明

针对半诚实模型下提出的基于线性扫描的基因比对方案，以下证明了不同参与方被腐败时的安全性。

证明 Π1代表方案1，分析在现实场景下执行Π1和在理想场景下执行f。

构建一个模拟器SimS，调用敌手A腐败服务器，接收α,β,n。对于i=1,2,…,n，SimS根据α和βi,由可信第三方调用混淆电路进行比对，并记录比对结果。最后SimS将比对结果给A，产生和A一致的输出。

对于模拟器SimS和安全参数k，REALΠ1(α, β),Sims(k)表示SimS在现实场景下执行Π1的输出，IDEALf(α, β),SimS(k)表示SimS在理想场景下执行f的输出。

定义1 方案Π1是安全的，如果对于任意非均匀的多项式时间敌手A腐败参与方，并在现实场景下运行Π1，则存在一个非均匀的多项式时间对手A腐败参与方，并在理想场景下中运行f，表示为：

(3)

客户被腐败的场景与服务器被腐败的场景类似，不再赘述。综上，方案1达到了理想与现实不可区分的目标，证明方案1在不同参与方被腐败时均是安全的。

以下是针对半诚实模型下提出的基于ORAM的基因比对方案，证明了不同参与方被腐败时的安全性。

证明 Π2代表方案2，分析在现实场景下执行Π2和在理想场景下执行F。

对于模拟器SimS、安全参数λ和k，REALΠ2(α, β),SimS(λ,k)表示SimS在现实场景下执行Π2的输出，IDEALF(α, β),SimS(λ,k)表示SimS在理想场景下执行F的输出。

定义2 方案Π2是安全的，如果对于任意非均匀的多项式时间敌手A腐败参与方，并在现实场景下运行Π2，则存在一个非均匀的多项式时间对手A腐败参与方，并在理想场景下中运行F，表示为：

(4)

客户被腐败的场景与服务器被腐败的场景类似，不再赘述。综上所述，方案2达到了理想与现实不可区分的目标，证明方案2在不同参与方被腐败时均是安全的。

4.2 性能对比

本文所有实验均在局域网内两台配置相同的PC上模拟执行。其中，一台PC模拟服务器，一台模拟客户，内存为8 GB，操作系统为Windows 10，CPU类型为Intel Xeon，主频为3.00 GHz，4核心。本文中所处理的基因序列均是来自NCBI(National Center for Biotechnology Information)[25]。

在实验时，基因序列长度定为32，ORAM中节点的容量B定为3。为了确定本文所提出的基因比对方案的性能，首先将本文所提出的两个方案进行纵向比较，在服务器端基因组数据库中基因序列个数n为28、29和210时，得出了方案1和方案2的运行时间并比较了两种方案的性能，实验结果如表1和表2所示。之后进一步与其他文献中的同类方案进行横向比较。由于在整个基因序列比对中，比对时间即编辑距离占总运行时间的比例最大，因此在相同环境下，针对不同长度的基因序列，分别测试了本文的编辑距离方案、Jha等[8]和Blanton等[10]提出的编辑距离协议的运行时间，并对4种编辑距离方案进行比较分析，结果如图3所示。

图3 四种编辑距离方案的运行时间对比Fig.3 Running time comparison of four Levenshtein distance schemes

1)纵向对比：方案1和方案2的运行时间对比。

表1显示了在不同数据库大小的情况下，第1种方案平均需要的OT的时间、门的数量以及总运行时间。可以看出，在第1种方案中，OT的时间、门的数量和总运行时间随基因组数据库中数据量n的增大线性增长，且增长速度明显。

表1 基于线性扫描的基因比对方案的运行时间 Tab. 1 Running time of genetic comparison scheme based on linear scan

表2显示了第2种方案在不同大小的数据库下，平均需要构造ORAM的时间、读路径时间、取出基因数据之后的比对时间以及总运行时间。在计算第2种方案的总运行时间时，并未将构造ORAM的时间计算在内，因为在构造一次ORAM之后，客户可以进行无数次比对，这样分摊到每一次的时间可以忽略。从表2中可以看出，在第2种方案中，构造ORAM的时间和读路径时间随着数据量n的增大线性增长，且相比于读路径时间，比对时间占总运行时间的比例较大，而比对次数为Blogn，因此比对时间亚线性于数据库大小，所以总运行时间随着数据量n的增长也呈现亚线性增长的趋势。

表2 基于ORAM的基因比对方案的运行时间 单位：s Tab. 2 Running time of genetic comparison scheme based on ORAM unit:s

另一方面，在表1中，当数据库大小n为210时，比对时间平均需要1.5 h，而在表2中，当数据库大小n为210时，总运行时间平均只需要168.11 s。综合表1和表2可以看出，当数据量为28时，第1种方案时间约是第2种方案的10倍；数据量为29时，第1种方案时间约是第2种方案时间的18倍；而当数据量为210时，第1种方案时间约是第2种方案时间的31倍，因此，第2种方案的执行效率明显优于第1种方案，而且当数据库中数据量越大时，这种优势会更加明显。

2)横向对比：与其他文献中编辑距离方案的时间对比。

根据纵向实验结果可知，本文提出的第2种方案明显地减少了基因序列比对时所需要的比对次数。为了进一步验证本文所提方案的性能，将本文方案与其他基因比对方案的性能进行了比较。因为比对时间占总运行时间比例最大，因此在相同的环境下，将本文的编辑距离方案与Jha等[8]提出的三种基因编辑距离协议中性能较好的协议一、协议三和Blanton等[10]提出的基因编辑距离方案进行对比，在图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.64 s，而本文的编辑距离方案中的运行时间仅需要5.31 s，这表明本文方案中的基因编辑距离的运行时间明显小于Jha和Blanton提出的协议，而计算编辑距离的时间占方案的总运行时间比例最大，因此本文所提出的基因序列比对方案具有更高的比对效率。

为了验证本文比对方案的准确性，进一步测试了本文方案中基因序列比对的误差率，因为在不同的编码长度σ，编码原理是一样的，理论上误差率是相同的，所以在实验时，采用σ=2进行基因序列比对，发现在σ=2时，与普通实现(基于基因数据的明文比对方案)的结果相同，即本文方案在实现基因比对隐私性的同时，保证了基因序列比对的准确性(误差率为0)。文献[25]也分析了在不同编码参数下所提方案的误差率，误差率位于0.01%到0.36%之间，高于本文所提的方案的误差率，表明本文方案满足基因序列比对时对准确性的要求。

5 结语

如何在高效地进行基因序列比对时实现隐私信息的保护是目前亟须解决的问题，本文利用ORAM技术抗访问模式泄露的特性，提出了一种基于ORAM的基因比对方案，具有保护用户隐私信息、时间复杂度低和高效安全等特点，解决了传统的基因比对方案中存在的隐私信息泄露和效率低下的问题。从实验结果和性能分析上看，本文所提方案的硬件和时间开销均较小，该方案对于个人医疗和医学的研究具有重要的应用价值。接下来的工作将考虑如何把ORAM存储结构放置在云服务器上，并进一步探究如何放置更长的基因数据项，利用并行计算技术实现更大规模的基因存储和比对。