面向用戶隱私保護的高效基因比對方案

李功麗，李 鈺，張 恩，尹天宇

(1.河南師范大學 計算機與信息工程學院，河南 新鄉(xiāng) 453007；2.“智慧商務與物聯(lián)網(wǎng)技術” 河南省工程實驗室(河南師范大學)，河南 新鄉(xiāng) 453007)

0 引言

目前基因檢測技術和各類檢測平臺是一把雙刃劍，人們既想要借助此類技術盡早診斷出疾病，但是又擔心自己的基因信息會泄露，而現(xiàn)有的基因檢測平臺，大多只是實現(xiàn)基因比對，無法保證用戶隱私信息的安全。例如基因疾病檢測平臺23andme[1]，用戶將自己的基因信息提供給它，它通過對用戶的基因進行檢測并反饋給用戶一份健康報告，由于存在隱私泄露的問題，被屢屢叫停，因此亟須設計一種既能實現(xiàn)基因序列比對又能保護用戶隱私的方案。

Bald等[2]利用隱私集合比較(Private Set Intersection, PSI)技術，提出了可以在親子鑒定、定制醫(yī)療等方面提供隱私保護的安全協(xié)議，該協(xié)議可以統(tǒng)計出兩條脫氧核糖核酸(Deoxyribonucleic Acid, DNA)序列相同位點上相同堿基的數(shù)目，但該方案不支持基因位點的插入、刪除和修改等操作，缺乏靈活性。De Cristofaro等[3]設計了一個基因組工具箱，提出在基因檢測時，先把數(shù)據(jù)逐個加密存儲在智能設備上，再用于后續(xù)計算，并對基因組工具箱的可用性進行研究，研究表明，該方案在基因組測試時具備一定的可行性，但該方案著重介紹了安全計算理論，缺乏有效的性能分析。Kim等[4]利用全同態(tài)加密實現(xiàn)了近似編輯距離計算，它允許在密文上進行運算而不用加解密數(shù)據(jù)，但它需要約28 s才能獲得兩條序列上八對DNA的編輯距離，方案效率較低?；诎踩喾接嬎愕碾[私保護協(xié)議是另一個能夠實現(xiàn)安全基因序列比對的工具，因為安全多方計算的目標是使多個參與方協(xié)同完成某項任務，同時不泄露除了計算結果外的用戶隱私信息，所以它比較適合用戶之間進行安全的基因序列比對。目前，實現(xiàn)安全計算的方法主要有Yao[5]的混淆電路(Garbled Circuit， GC)和Goldreich等[6]提出的秘密共享理論(Goldreich-Micali-Wigderson, GMW)協(xié)議，后來的安全多方計算協(xié)議[7-9]大多都是基于Yao[5]的混淆電路。目前安全計算協(xié)議有兩種實現(xiàn)方法：一種是把待計算的函數(shù)表示為布爾電路；另一種方法是表示為算術電路。Huang等[7]在布爾電路上設計并實現(xiàn)了高效的隱私集合比較協(xié)議，其研究結果表明，通過合理地設計電路，基于混淆電路實現(xiàn)的安全多方計算的協(xié)議在某些情況下的效率要高于一些自定義協(xié)議。

編輯距離的計算可以實現(xiàn)基因序列的比對，從而預測兩條基因序列的相似度，基于安全多方計算實現(xiàn)的編輯距離方案逐漸受到人們的關注，Jha等[8]提出了三種基于安全多方計算設計的編輯距離協(xié)議，但這三種協(xié)議需要保存整個混淆電路直到構造完成，限制了混淆電路中輸入的大小。Huang等[9]針對該問題提出了Pipelined Circuit Execution技術，可以一邊構造混淆電路一邊計算混淆電路，即混淆電路的構造和計算可以并行執(zhí)行，因此可以支持大輸入的場景。Blanton等[10]基于混淆電路提出將基因序列的比對云外包給服務器，避免了公鑰加密操作，實現(xiàn)了在隱私保護下，編輯距離的快速計算。Choi等[11]實現(xiàn)了安全多方計算中的GMW協(xié)議，主要用于待計算的函數(shù)可以被表示為布爾電路的場景，研究結果表明，基于安全多方計算設計保護隱私的方案是可行的。由于Choi等[11]和Huang等[9]的工作，使得安全地進行基因序列比對成為了可能。

現(xiàn)假設Alice(客戶)懷疑自己得了某種基因疾病，而Bob(服務器)有一個可以用來檢測疾病的基因組數(shù)據(jù)庫，Alice想讓Bob幫她診斷自己是否得這種疾病，設計隱私保護的比對方案要實現(xiàn)以下兩個安全目標：

1)Alice不需要把自己的基因信息直接給Bob，Bob也不需要直接將它的基因組數(shù)據(jù)庫給Alice，這樣可以避免雙方數(shù)據(jù)的泄漏。

2)比對結束后，Bob無法知道Alice是否得病的信息，即Bob不能獲得比對結果的信息。

針對上述安全目標，首先，為了防止直接利用明文數(shù)據(jù)進行比對會泄露基因信息，將基因序列進行編碼混淆；其次，為了確保基因比對過程不會泄露基因信息，將Alice的基因與Bob方基因組數(shù)據(jù)庫中的數(shù)據(jù)逐個進行比對，由此得出了第一種基于線性掃描的基因比對方案。該方案可以實現(xiàn)隱私保護下的基因比對。

但是因為第一種方案需要線性掃描基因組數(shù)據(jù)庫，時間復雜度較高，當比對的目標數(shù)據(jù)庫較大時，該方案的效率較低。針對上述問題，本文利用不經(jīng)意隨機存取(Oblivious Random Access Memory, ORAM)和混淆電路技術，提出了一種基于ORAM的基因比對方案，在上述應用場景：客戶想要確定自己是否得了某種病，期望從服務器端的基因數(shù)據(jù)庫中取出該病的致病基因片段與自己的基因序列進行比對，根據(jù)比對的結果來驗證自己的判斷。假設客戶持有一個基因序列α，服務器持有一個基因數(shù)據(jù)庫β，基因數(shù)據(jù)已被加密存儲在ORAM上，客戶期望在基因數(shù)據(jù)庫中找到致病基因片段α′，同時不想讓服務器知道她期望得到什么數(shù)據(jù)，因為這可能泄漏她的基因信息，而在客戶訪問基因序列α′的過程中，要保證服務器端無法確定用戶是否訪問了α′，因為訪問模式的泄漏可能引起基因信息的泄漏，而ORAM可以抗訪問模式泄漏，它可以將一條ORAM指令轉換為多條RAM指令去執(zhí)行，最后可以訪問到期望的數(shù)據(jù)而不泄露自己的訪問模式。利用ORAM把目標數(shù)據(jù)α′所在路徑上的數(shù)據(jù)全部取出后，雙方再利用混淆電路進行基因比對，在取數(shù)據(jù)和基因比對的整個過程中，均不會泄漏雙方的隱私信息。該方案是先取數(shù)據(jù)再進行基因序列比對，為了取出期望得到的序列，需要取出O(logn)(n是數(shù)據(jù)庫的大小)個數(shù)據(jù)，再利用混淆電路將α與這O(logn)個數(shù)據(jù)進行比對；而第一種方案是直接利用混淆電路進行基因比對，為了實現(xiàn)保護隱私的目的，需線性掃描整個基因數(shù)據(jù)庫β中所有的序列與α進行比對，比對次數(shù)為O(n)。

實驗結果表明，改進后的方案不僅可以實現(xiàn)上述的兩個安全目標，而且可以有效地降低比對次數(shù)，特別是當基因組數(shù)據(jù)庫中數(shù)據(jù)量較大時，該方案的效率相比傳統(tǒng)方案將會明顯提高。在最后的性能對比中，用包含不同數(shù)據(jù)量的基因組數(shù)據(jù)庫進行基因比對的時間測試，比較了基礎方案和改進后的方案的性能，證明了所提方案的有效性和可行性。

1 基礎知識

1.1 ORAM

ORAM最早是由Goldreich等[12]在1996年提出的，用來解決軟件逆向工程問題，后來Shi等[13]提出了一種基于二叉樹的ORAM方案，被廣泛應用于軟件保護、安全計算、密文搜索等方面。ORAM是一種抗訪問模式泄露的隱私保護技術，它主要涉及用戶和服務器兩個主體，用戶既可以將數(shù)據(jù)存儲到服務器上，也可以向服務器提出檢索數(shù)據(jù)的請求，數(shù)據(jù)在服務器上以二叉樹形式存儲，二叉樹的每一層由若干個節(jié)點組成，每個節(jié)點可以存儲O(logn)個數(shù)據(jù)項。它的基本思想是：用戶要訪問某個數(shù)據(jù)時，查找索引表得到該數(shù)據(jù)對應的葉子節(jié)點，為該數(shù)據(jù)重新分配葉子節(jié)點和更新索引表，并將對應的路徑提供給服務器，服務器把該路徑上所有的數(shù)據(jù)給用戶，用戶依次解密這些數(shù)據(jù)，最終可以得到期望的數(shù)據(jù)。用戶和服務器通過網(wǎng)絡協(xié)議實現(xiàn)交互訪問數(shù)據(jù)的同時，服務器不能推測出用戶訪問的數(shù)據(jù)。在基礎的基于二叉樹的ORAM方案之后，為了提升ORAM的效率，文獻[14-16]中提出了一系列改進的ORAM方案。Gordon等[17]首次提出，ORAM和安全多方計算結合可以實現(xiàn)時間復雜度為亞線性的安全算法，文獻[18-20]中提出了一系列與安全計算相結合的ORAM方案。

在基于二叉樹的ORAM方案中，假設用戶的訪存請求序列為：

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

其中，op代表一次read或者write操作，若op=read，則argi=idx；反之,op=write，argi=(idx，datai)，idx表示當前欲訪問數(shù)據(jù)項的標識符，datai表示該數(shù)據(jù)項對應的真正數(shù)據(jù)。以一次訪存請求Access(op)為例，ORAM操作的主要過程如下：

1)如圖1所示，當用戶想要訪問標識符為idx的數(shù)據(jù)時，首先查找本地的索引表PositionMap，得到數(shù)據(jù)項idx對應的葉子節(jié)點l，并為數(shù)據(jù)項idx重新分配葉子節(jié)點l*，更新索引表中PositionMap[idx]的值，即PositionMap[idx]=l*。

2)用戶依次讀取路徑p(l)上(圖1中虛線指示的路徑)的每個數(shù)據(jù)，解密這些數(shù)據(jù)，若讀到idx對應的數(shù)據(jù)項(idx‖PositionMap[idx]‖data)時，記錄下該數(shù)據(jù)并用無效數(shù)據(jù)項⊥代替加密寫回；反之將讀到的數(shù)據(jù)重新加密寫回。最后如果讀出了idx對應的數(shù)據(jù)，返回該數(shù)據(jù)；反之返回⊥。

3)若op=read，則把idx所對應的數(shù)據(jù)data取出，更新數(shù)據(jù)項內容為(idx‖PositionMap[idx]‖data)，若op=write，則更新數(shù)據(jù)內容(idx‖PositionMap[idx]‖data*)。最后將該數(shù)據(jù)重新加密寫入根節(jié)點root。

4)在每次將數(shù)據(jù)寫入根節(jié)點之后，用戶需從服務器端二叉樹的每一層挑選兩個節(jié)點進行下移操作，若該節(jié)點中都是無效數(shù)據(jù)項⊥，則選取兩個無效數(shù)據(jù)項⊥，重新加密向它的左右孩子節(jié)點各寫入一個加密后的⊥；否則，選取一個有效數(shù)據(jù)項和一個無效數(shù)據(jù)項⊥，將它們重新加密，根據(jù)p(l)，將有效數(shù)據(jù)寫入指定的孩子節(jié)點，將無效數(shù)據(jù)⊥寫入另一孩子節(jié)點。

1.2 混淆電路

混淆電路(GC)是Yao[5]在1982年提出的，在安全兩方計算中，如果兩方的輸入可以轉換為布爾值時，混淆電路可以高效地解決此類安全計算問題，最開始用于解決經(jīng)典的百萬富翁問題。它的基本思想是：發(fā)送方對輸入值進行混淆，并根據(jù)待計算的函數(shù)f構造混淆電路G(C)，將混淆表和發(fā)送方輸入的混淆值發(fā)送給接收方，接收方通過與發(fā)送方運行不經(jīng)意傳輸(Oblivious Transfer, OT)協(xié)議[21]來得到它的混淆值，從而接收方能夠正確地計算該混淆電路。使用混淆電路方案來解決安全兩方計算問題時主要分為構造混淆電路、計算混淆電路和恢復真正的輸出結果三個階段。混淆電路方案的過程如下。

1) 混淆電路構造階段。

設函數(shù)f對應的電路為C，發(fā)送方通過以下兩個步驟來構造混淆電路G(C)。

2)混淆電路的計算。

④對于門gi的輸出，如果門gi是中間某個門時，將門gi輸出的混淆值繼續(xù)作為另一個門的輸入重復上述操作進行計算，直至計算完整個混淆電路。

3)恢復真正的輸出結果。

接收方根據(jù)輸出轉換表，將混淆電路G(C)輸出的混淆值轉換為真正的輸出結果，再將結果給發(fā)送方。

在上述混淆電路方案中，實現(xiàn)隱私數(shù)據(jù)的傳輸采用的是OT協(xié)議。在t～nOT協(xié)議中，接收者持有t個索引值b∈{0,1}，同時發(fā)送者擁有n個信息{m1,m2,…,mn}。在執(zhí)行OT協(xié)議時，接收者能夠根據(jù)索引值從發(fā)送者的n個信息中獲取對應的t條信息，但是無從知道其他的n-t條信息，而發(fā)送者也不知道接收者的索引值，因此無法知道接收者接收的信息。在本文中，使用的是1～2 OT協(xié)議，即發(fā)送者擁有兩條信息，接收者持有一個選擇位b，b∈{0,1}。執(zhí)行1～2 OT協(xié)議之后，接收者會獲取與選擇位b相對應的信息。OT協(xié)議是實現(xiàn)安全計算的重要工具，通過執(zhí)行OT協(xié)議，可以實現(xiàn)隱私信息的安全傳輸。

1.3 編輯距離

編輯距離(Levenshtein Distance)可以用來檢測兩條基因序列的相似度，文獻[22]中提出了一種改進的編輯距離算法。其基本原理是計算至少需要多少次操作才能將一條基因序列轉換為另一條基因序列，操作主要包括堿基的插入、刪除和替換。例如，有如下兩條基因序列α和β：

α=GTTACTTTGG

β=CTTACCTTT

為了將α變?yōu)棣?，需要在?個位置將堿基G變?yōu)镃，在第6個位置插入堿基C，在第9和第10個位置刪除兩個堿基G，可得編輯距離為4。

在初始化時，D數(shù)組的初值表述為如下：

(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 基于線性掃描的基因比對方案

為了實現(xiàn)隱私保護下的基因序列比對，本文首先提出了基于線性掃描的基因比對方案。該方案的基本思想是：先對基因序列進行混淆編碼，然后根據(jù)基因序列比對程序設計相應的布爾電路并構造混淆電路，進而采取線性掃描的方式將客戶的基因序列和服務器端的基因組數(shù)據(jù)庫中的基因序列逐個利用混淆電路進行比對。在整個比對過程中，首先因為對基因數(shù)據(jù)進行了混淆編碼，所以雙方不會泄漏自己的基因數(shù)據(jù)，而且因為是與服務器中的每個基因序列進行比對，每次只有客戶得到真正的比對結果，因此服務器無法確定用戶與哪個基因序列的相似度高，所以也無法根據(jù)用戶的比較對象推測比較結果。

2.1 基因序列編碼

先將客戶的基因序列和服務器端基因組數(shù)據(jù)庫的基因序列作如下處理：

1)確定編碼規(guī)則并編碼。用兩個比特位對堿基A，T，C，G進行編碼，分別編碼為00，01，10，11。將DNA序列按照編碼規(guī)則進行編碼，每個DNA序列最后被編碼成一個二進制串。

2.2 布爾電路設計

為了減小混淆電路的規(guī)模，先對算法1進行分析，提出只有需要協(xié)同計算來保護隱私的操作才采用Yao[5]的混淆電路實現(xiàn)，這樣可以有效地減少混淆電路帶來的開銷。根據(jù)分析，將算法1轉換為圖2的布爾電路，主要用到以下4種門電路：MIN門、ADD門、MUX門、EDT門。

MIN門 該門以兩個mbit的數(shù)據(jù)S和T作為輸入。若S>T，則輸出mbit的數(shù)據(jù)T；反之，則輸出mbit的數(shù)據(jù)S。

ADD門 該門以一個mbit的數(shù)據(jù)S和一個1 bit的數(shù)據(jù)q，q∈{0,1}作為輸入。輸出S加上q后的mbit數(shù)據(jù)。

MUX門 該門以兩個長度為mbit的數(shù)據(jù)S和T以及1位的選擇位b作為輸入。若b=0，則輸出S；反之輸出T。

EDT門 該門以兩個mbit的數(shù)據(jù)S和T作為輸入。若S=T，則輸出0；反之輸出1。

具體計算過程如圖2所示，先比較D[i-1][j]和D[i][j-1]，選出最小值，再與D[i-1][j-1]比較，產(chǎn)生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 基因序列比對

將客戶的基因序列與服務器端基因組數(shù)據(jù)庫中每個序列依次進行比對。在每一次的比對操作時，根據(jù)產(chǎn)生的混淆編碼值和設計的布爾電路構造出混淆電路，然后將混淆電路交由服務器方進行計算，最后服務器方將基因比對的結果返回給客戶，而此時的結果是混淆編碼值，只有客戶端才能解碼轉換為真正的明文結果，避免了服務器獲得真正的比對結果。

具體過程：客戶持有DNA序列α，服務器端有一個包含n條基因序列的基因組數(shù)據(jù)庫β，令α與β中的n條序列逐個進行比對，在每次比對時，采用混淆電路來計算兩條序列的相似程度，根據(jù)相似度來確定客戶是否患有這種DNA疾病，若某次比對時兩條序列相似度達到96%的時候，即判定兩條序列同源。利用Huang等[9]提出的Pipelined Circuit Execution技術對代碼進行優(yōu)化，每構造一個門的混淆表和輸入的混淆值之后，就可以發(fā)送給服務器進行計算，并行執(zhí)行整個電路，這樣可以大幅度減少構造混淆電路時占用的內存，提高混淆電路的執(zhí)行效率。同時利用Kolesnikov等[23]提出的Free-XOR技術來減少混淆電路的開銷。

在實驗測試時，安全參數(shù)k定為80，執(zhí)行的”base” OT的次數(shù)為k。將兩方的基因序列長定為32時,一次基因比對所需門的數(shù)量為1 664個，平均需要的總時間為5.31 s，其中，OT所占的時間為0.24 s。

在上述方案中，客戶的基因序列與服務器端基因組數(shù)據(jù)庫里面所有的基因序列逐個進行比對。每次比對都使用混淆電路來實現(xiàn)，因此可以保證每次比對過程中基因信息的安全，且因為是比對了基因組數(shù)據(jù)庫中的所有序列，所以服務器無法確定客戶到底與哪個DNA序列相似度高，從而可以在保護雙方隱私的前提下，讓客戶得到診斷結果，但上述方案的時間復雜度為O(n)，且需要使用的門和OT的數(shù)量與比對次數(shù)成正比。在基因組數(shù)據(jù)庫較大時，需要較大的計算開銷和通信開銷，因此當數(shù)據(jù)庫中數(shù)據(jù)量n逐漸增加時，該方案將不再適用?？梢姡m然該方案可以保護隱私，但效率不高。為了減少比對次數(shù)，提高基因比對的效率，本文利用ORAM和混淆電路提出了一種基于ORAM的基因比對方案，該方案不僅降低了時間復雜度，同時減少了比對次數(shù)和整體的開銷。

3 基于ORAM的基因比對方案

在基于線性掃描的基因比對方案中，為了保護隱私，客戶的基因序列必須與服務器端數(shù)據(jù)庫中的基因序列逐個進行比對，否則便會泄露自己的基因序列甚至自己的健康狀況(疾病)，當服務器端數(shù)據(jù)庫較大時，該方案明顯不再適用，因此，本文利用ORAM和混淆電路技術，提出了一種高效的基于ORAM的基因比對方案。

本文設計的基于ORAM的基因序列診斷方案采用Circuit ORAM。在該方案中，客戶端被表示為電路，相比于其他ORAM方案，構造Circuit ORAM需要的電路規(guī)模更小。

假設客戶有一條基因序列α，服務器端有一個基因組數(shù)據(jù)庫β,數(shù)據(jù)庫的大小為n，數(shù)據(jù)庫中每一個數(shù)據(jù)項長為d,λ和k為安全參數(shù)，ORAM上每個節(jié)點可存儲B個數(shù)據(jù)項，ORAM的高度為logn，α′的標識符為x?；贠RAM的基因比對方案分為以下3個階段。

1)初始化階段。

①初始化ORAM：兩方運行安全計算協(xié)議，根據(jù)協(xié)商好的參數(shù)初始化ORAM結構，即ORAM ← Initial(λ,n,d)，設shareGen()為秘密產(chǎn)生函數(shù)，在該函數(shù)中，若秘密為s，則利用shareGen()隨機產(chǎn)生一個串作為一個子份額r1，另一個子份額r2=r1⊕s，則s=r1⊕r2。初始化ORAM之后，根據(jù)ORAM并利用shareGen函數(shù)產(chǎn)生子份額分發(fā)給兩方，即(ORAMa,ORAMb) ← shareGen(ORAM,1λ)，則兩方各存有空ORAM的子份額。

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

c)執(zhí)行每條指令Ii并更新兩方存儲的ORAM的子份額：

ORAMa,ORAMb← Exec(Ii,ORAM)

每執(zhí)行一條指令，可將數(shù)據(jù)庫β中的一項寫到ORAM上，同時兩方存儲的ORAM的子份額會一直更新，直至將所有數(shù)據(jù)存到ORAM上，在執(zhí)行n次寫操作之后，兩方各存有一份最終的ORAM的子份額。

2)基因序列比對階段。

③雙方根據(jù)葉子節(jié)點l和存儲在兩方的ORAM子份額，運行安全計算協(xié)議將路徑p(l)上所有數(shù)據(jù)取出來，即(v1,v2,…,α′,…,vB log n) ← readPath(l)，然后將客戶的基因序列α與取出的Blogn個數(shù)據(jù)逐個利用混淆電路進行基因比對。當訪問到數(shù)據(jù)α′，且α與α′的相似度達到96%時認為α與α′同源，返回比對結果。

④在所有比對操作之后，重新產(chǎn)生新的葉子節(jié)點l*，執(zhí)行寫指令I*:=(“write”,l*,β[i])，將數(shù)據(jù)重新寫入到ORAM中，并更新兩方持有的ORAM子份額。

3)返回結果階段。

根據(jù)基因序列比對的結果，將結果返回給客戶。如果客戶需要繼續(xù)進行基因比對，則重復以上步驟。

在上述方案中，因為只需將目標數(shù)據(jù)所在路徑上的數(shù)據(jù)取出進行比對，因此可以將比對次數(shù)減小到Blogn次。當n=1 024，B=3時，基礎方案需要比對1 024次，而該方案只需比對30次。

4 安全性證明和性能對比

4.1 安全性證明

針對半誠實模型下提出的基于線性掃描的基因比對方案，以下證明了不同參與方被腐敗時的安全性。

證明 Π1代表方案1，分析在現(xiàn)實場景下執(zhí)行Π1和在理想場景下執(zhí)行f。

構建一個模擬器SimS，調用敵手A腐敗服務器，接收α,β,n。對于i=1,2,…,n，SimS根據(jù)α和βi,由可信第三方調用混淆電路進行比對，并記錄比對結果。最后SimS將比對結果給A，產(chǎn)生和A一致的輸出。

對于模擬器SimS和安全參數(shù)k，REALΠ1(α, β),Sims(k)表示SimS在現(xiàn)實場景下執(zhí)行Π1的輸出，IDEALf(α, β),SimS(k)表示SimS在理想場景下執(zhí)行f的輸出。

定義1 方案Π1是安全的，如果對于任意非均勻的多項式時間敵手A腐敗參與方，并在現(xiàn)實場景下運行Π1，則存在一個非均勻的多項式時間對手A腐敗參與方，并在理想場景下中運行f，表示為：

(3)

客戶被腐敗的場景與服務器被腐敗的場景類似，不再贅述。綜上，方案1達到了理想與現(xiàn)實不可區(qū)分的目標，證明方案1在不同參與方被腐敗時均是安全的。

以下是針對半誠實模型下提出的基于ORAM的基因比對方案，證明了不同參與方被腐敗時的安全性。

證明 Π2代表方案2，分析在現(xiàn)實場景下執(zhí)行Π2和在理想場景下執(zhí)行F。

對于模擬器SimS、安全參數(shù)λ和k，REALΠ2(α, β),SimS(λ,k)表示SimS在現(xiàn)實場景下執(zhí)行Π2的輸出，IDEALF(α, β),SimS(λ,k)表示SimS在理想場景下執(zhí)行F的輸出。

定義2 方案Π2是安全的，如果對于任意非均勻的多項式時間敵手A腐敗參與方，并在現(xiàn)實場景下運行Π2，則存在一個非均勻的多項式時間對手A腐敗參與方，并在理想場景下中運行F，表示為：

(4)

客戶被腐敗的場景與服務器被腐敗的場景類似，不再贅述。綜上所述，方案2達到了理想與現(xiàn)實不可區(qū)分的目標，證明方案2在不同參與方被腐敗時均是安全的。

4.2 性能對比

本文所有實驗均在局域網(wǎng)內兩臺配置相同的PC上模擬執(zhí)行。其中，一臺PC模擬服務器，一臺模擬客戶，內存為8 GB，操作系統(tǒng)為Windows 10，CPU類型為Intel Xeon，主頻為3.00 GHz，4核心。本文中所處理的基因序列均是來自NCBI(National Center for Biotechnology Information)[25]。

在實驗時，基因序列長度定為32，ORAM中節(jié)點的容量B定為3。為了確定本文所提出的基因比對方案的性能，首先將本文所提出的兩個方案進行縱向比較，在服務器端基因組數(shù)據(jù)庫中基因序列個數(shù)n為28、29和210時，得出了方案1和方案2的運行時間并比較了兩種方案的性能，實驗結果如表1和表2所示。之后進一步與其他文獻中的同類方案進行橫向比較。由于在整個基因序列比對中，比對時間即編輯距離占總運行時間的比例最大，因此在相同環(huán)境下，針對不同長度的基因序列，分別測試了本文的編輯距離方案、Jha等[8]和Blanton等[10]提出的編輯距離協(xié)議的運行時間，并對4種編輯距離方案進行比較分析，結果如圖3所示。

圖3 四種編輯距離方案的運行時間對比Fig.3 Running time comparison of four Levenshtein distance schemes

1)縱向對比：方案1和方案2的運行時間對比。

表1顯示了在不同數(shù)據(jù)庫大小的情況下，第1種方案平均需要的OT的時間、門的數(shù)量以及總運行時間。可以看出，在第1種方案中，OT的時間、門的數(shù)量和總運行時間隨基因組數(shù)據(jù)庫中數(shù)據(jù)量n的增大線性增長，且增長速度明顯。

表1 基于線性掃描的基因比對方案的運行時間 Tab. 1 Running time of genetic comparison scheme based on linear scan

表2顯示了第2種方案在不同大小的數(shù)據(jù)庫下，平均需要構造ORAM的時間、讀路徑時間、取出基因數(shù)據(jù)之后的比對時間以及總運行時間。在計算第2種方案的總運行時間時，并未將構造ORAM的時間計算在內，因為在構造一次ORAM之后，客戶可以進行無數(shù)次比對，這樣分攤到每一次的時間可以忽略。從表2中可以看出，在第2種方案中，構造ORAM的時間和讀路徑時間隨著數(shù)據(jù)量n的增大線性增長，且相比于讀路徑時間，比對時間占總運行時間的比例較大，而比對次數(shù)為Blogn，因此比對時間亞線性于數(shù)據(jù)庫大小，所以總運行時間隨著數(shù)據(jù)量n的增長也呈現(xiàn)亞線性增長的趨勢。

表2 基于ORAM的基因比對方案的運行時間 單位：s Tab. 2 Running time of genetic comparison scheme based on ORAM unit:s

另一方面，在表1中，當數(shù)據(jù)庫大小n為210時，比對時間平均需要1.5 h，而在表2中，當數(shù)據(jù)庫大小n為210時，總運行時間平均只需要168.11 s。綜合表1和表2可以看出，當數(shù)據(jù)量為28時，第1種方案時間約是第2種方案的10倍；數(shù)據(jù)量為29時，第1種方案時間約是第2種方案時間的18倍；而當數(shù)據(jù)量為210時，第1種方案時間約是第2種方案時間的31倍，因此，第2種方案的執(zhí)行效率明顯優(yōu)于第1種方案，而且當數(shù)據(jù)庫中數(shù)據(jù)量越大時，這種優(yōu)勢會更加明顯。

2)橫向對比：與其他文獻中編輯距離方案的時間對比。

根據(jù)縱向實驗結果可知，本文提出的第2種方案明顯地減少了基因序列比對時所需要的比對次數(shù)。為了進一步驗證本文所提方案的性能，將本文方案與其他基因比對方案的性能進行了比較。因為比對時間占總運行時間比例最大，因此在相同的環(huán)境下，將本文的編輯距離方案與Jha等[8]提出的三種基因編輯距離協(xié)議中性能較好的協(xié)議一、協(xié)議三和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提出的協(xié)議，而計算編輯距離的時間占方案的總運行時間比例最大，因此本文所提出的基因序列比對方案具有更高的比對效率。

為了驗證本文比對方案的準確性，進一步測試了本文方案中基因序列比對的誤差率，因為在不同的編碼長度σ，編碼原理是一樣的，理論上誤差率是相同的，所以在實驗時，采用σ=2進行基因序列比對，發(fā)現(xiàn)在σ=2時，與普通實現(xiàn)(基于基因數(shù)據(jù)的明文比對方案)的結果相同，即本文方案在實現(xiàn)基因比對隱私性的同時，保證了基因序列比對的準確性(誤差率為0)。文獻[25]也分析了在不同編碼參數(shù)下所提方案的誤差率，誤差率位于0.01%到0.36%之間，高于本文所提的方案的誤差率，表明本文方案滿足基因序列比對時對準確性的要求。

5 結語

如何在高效地進行基因序列比對時實現(xiàn)隱私信息的保護是目前亟須解決的問題，本文利用ORAM技術抗訪問模式泄露的特性，提出了一種基于ORAM的基因比對方案，具有保護用戶隱私信息、時間復雜度低和高效安全等特點，解決了傳統(tǒng)的基因比對方案中存在的隱私信息泄露和效率低下的問題。從實驗結果和性能分析上看，本文所提方案的硬件和時間開銷均較小，該方案對于個人醫(yī)療和醫(yī)學的研究具有重要的應用價值。接下來的工作將考慮如何把ORAM存儲結構放置在云服務器上，并進一步探究如何放置更長的基因數(shù)據(jù)項，利用并行計算技術實現(xiàn)更大規(guī)模的基因存儲和比對。