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

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

0 引言

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

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

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

現(xiàn)假設(shè)Alice(客戶(hù))懷疑自己得了某種基因疾病，而B(niǎo)ob(服務(wù)器)有一個(gè)可以用來(lái)檢測(cè)疾病的基因組數(shù)據(jù)庫(kù)，Alice想讓Bob幫她診斷自己是否得這種疾病，設(shè)計(jì)隱私保護(hù)的比對(duì)方案要實(shí)現(xiàn)以下兩個(gè)安全目標(biāo)：

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

2)比對(duì)結(jié)束后，Bob無(wú)法知道Alice是否得病的信息，即Bob不能獲得比對(duì)結(jié)果的信息。

針對(duì)上述安全目標(biāo)，首先，為了防止直接利用明文數(shù)據(jù)進(jìn)行比對(duì)會(huì)泄露基因信息，將基因序列進(jìn)行編碼混淆；其次，為了確?；虮葘?duì)過(guò)程不會(huì)泄露基因信息，將Alice的基因與Bob方基因組數(shù)據(jù)庫(kù)中的數(shù)據(jù)逐個(gè)進(jìn)行比對(duì)，由此得出了第一種基于線(xiàn)性?huà)呙璧幕虮葘?duì)方案。該方案可以實(shí)現(xiàn)隱私保護(hù)下的基因比對(duì)。

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

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

1 基礎(chǔ)知識(shí)

1.1 ORAM

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

在基于二叉樹(shù)的ORAM方案中，假設(shè)用戶(hù)的訪存請(qǐng)求序列為：

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

其中，op代表一次read或者write操作，若op=read，則argi=idx；反之,op=write，argi=(idx，datai)，idx表示當(dāng)前欲訪問(wèn)數(shù)據(jù)項(xiàng)的標(biāo)識(shí)符，datai表示該數(shù)據(jù)項(xiàng)對(duì)應(yīng)的真正數(shù)據(jù)。以一次訪存請(qǐng)求Access(op)為例，ORAM操作的主要過(guò)程如下：

1)如圖1所示，當(dāng)用戶(hù)想要訪問(wèn)標(biāo)識(shí)符為idx的數(shù)據(jù)時(shí)，首先查找本地的索引表PositionMap，得到數(shù)據(jù)項(xiàng)idx對(duì)應(yīng)的葉子節(jié)點(diǎn)l，并為數(shù)據(jù)項(xiàng)idx重新分配葉子節(jié)點(diǎn)l*，更新索引表中PositionMap[idx]的值，即PositionMap[idx]=l*。

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

3)若op=read，則把idx所對(duì)應(yīng)的數(shù)據(jù)data取出，更新數(shù)據(jù)項(xiàng)內(nèi)容為(idx‖PositionMap[idx]‖data)，若op=write，則更新數(shù)據(jù)內(nèi)容(idx‖PositionMap[idx]‖data*)。最后將該數(shù)據(jù)重新加密寫(xiě)入根節(jié)點(diǎn)root。

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

1.2 混淆電路

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

1) 混淆電路構(gòu)造階段。

設(shè)函數(shù)f對(duì)應(yīng)的電路為C，發(fā)送方通過(guò)以下兩個(gè)步驟來(lái)構(gòu)造混淆電路G(C)。

2)混淆電路的計(jì)算。

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

3)恢復(fù)真正的輸出結(jié)果。

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

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

1.3 編輯距離

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

α=GTTACTTTGG

β=CTTACCTTT

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

在初始化時(shí)，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個(gè)位點(diǎn)到序列β的前j個(gè)位點(diǎn)的編輯距離。如果α[i]≠β[j]，t(i,j)的值為1，否則為0。具體的編輯距離計(jì)算過(guò)程如算法1所示。

算法1 基因序列編輯距離計(jì)算過(guò)程。

輸入：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)性?huà)呙璧幕虮葘?duì)方案

為了實(shí)現(xiàn)隱私保護(hù)下的基因序列比對(duì)，本文首先提出了基于線(xiàn)性?huà)呙璧幕虮葘?duì)方案。該方案的基本思想是：先對(duì)基因序列進(jìn)行混淆編碼，然后根據(jù)基因序列比對(duì)程序設(shè)計(jì)相應(yīng)的布爾電路并構(gòu)造混淆電路，進(jìn)而采取線(xiàn)性?huà)呙璧姆绞綄⒖蛻?hù)的基因序列和服務(wù)器端的基因組數(shù)據(jù)庫(kù)中的基因序列逐個(gè)利用混淆電路進(jìn)行比對(duì)。在整個(gè)比對(duì)過(guò)程中，首先因?yàn)閷?duì)基因數(shù)據(jù)進(jìn)行了混淆編碼，所以雙方不會(huì)泄漏自己的基因數(shù)據(jù)，而且因?yàn)槭桥c服務(wù)器中的每個(gè)基因序列進(jìn)行比對(duì)，每次只有客戶(hù)得到真正的比對(duì)結(jié)果，因此服務(wù)器無(wú)法確定用戶(hù)與哪個(gè)基因序列的相似度高，所以也無(wú)法根據(jù)用戶(hù)的比較對(duì)象推測(cè)比較結(jié)果。

2.1 基因序列編碼

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

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

2.2 布爾電路設(shè)計(jì)

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

MIN門(mén) 該門(mén)以?xún)蓚€(gè)mbit的數(shù)據(jù)S和T作為輸入。若S>T，則輸出mbit的數(shù)據(jù)T；反之，則輸出mbit的數(shù)據(jù)S。

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

MUX門(mén) 該門(mén)以?xún)蓚€(gè)長(zhǎng)度為mbit的數(shù)據(jù)S和T以及1位的選擇位b作為輸入。若b=0，則輸出S；反之輸出T。

EDT門(mén) 該門(mén)以?xún)蓚€(gè)mbit的數(shù)據(jù)S和T作為輸入。若S=T，則輸出0；反之輸出1。

具體計(jì)算過(guò)程如圖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門(mén)的輸出為t，否則MUX門(mén)的輸出為1，最后取第二個(gè)MIN門(mén)的輸出值加MUX門(mén)的輸出值為整個(gè)電路的輸出。

圖2 基因比對(duì)的核心布爾電路Fig.2 Core Boolean circuit of genetic comparison

2.3 基因序列比對(duì)

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

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

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

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

3 基于ORAM的基因比對(duì)方案

在基于線(xiàn)性?huà)呙璧幕虮葘?duì)方案中，為了保護(hù)隱私，客戶(hù)的基因序列必須與服務(wù)器端數(shù)據(jù)庫(kù)中的基因序列逐個(gè)進(jìn)行比對(duì)，否則便會(huì)泄露自己的基因序列甚至自己的健康狀況(疾病)，當(dāng)服務(wù)器端數(shù)據(jù)庫(kù)較大時(shí)，該方案明顯不再適用，因此，本文利用ORAM和混淆電路技術(shù)，提出了一種高效的基于ORAM的基因比對(duì)方案。

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

假設(shè)客戶(hù)有一條基因序列α，服務(wù)器端有一個(gè)基因組數(shù)據(jù)庫(kù)β,數(shù)據(jù)庫(kù)的大小為n，數(shù)據(jù)庫(kù)中每一個(gè)數(shù)據(jù)項(xiàng)長(zhǎng)為d,λ和k為安全參數(shù)，ORAM上每個(gè)節(jié)點(diǎn)可存儲(chǔ)B個(gè)數(shù)據(jù)項(xiàng)，ORAM的高度為logn，α′的標(biāo)識(shí)符為x。基于ORAM的基因比對(duì)方案分為以下3個(gè)階段。

1)初始化階段。

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

a)重構(gòu)ORAM：ORAM=ORAMa⊕ORAMb。

c)執(zhí)行每條指令I(lǐng)i并更新兩方存儲(chǔ)的ORAM的子份額：

ORAMa,ORAMb← Exec(Ii,ORAM)

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

2)基因序列比對(duì)階段。

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

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

3)返回結(jié)果階段。

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

在上述方案中，因?yàn)橹恍鑼⒛繕?biāo)數(shù)據(jù)所在路徑上的數(shù)據(jù)取出進(jìn)行比對(duì)，因此可以將比對(duì)次數(shù)減小到Blogn次。當(dāng)n=1 024，B=3時(shí)，基礎(chǔ)方案需要比對(duì)1 024次，而該方案只需比對(duì)30次。

4 安全性證明和性能對(duì)比

4.1 安全性證明

針對(duì)半誠(chéng)實(shí)模型下提出的基于線(xiàn)性?huà)呙璧幕虮葘?duì)方案，以下證明了不同參與方被腐敗時(shí)的安全性。

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

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

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

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

(3)

客戶(hù)被腐敗的場(chǎng)景與服務(wù)器被腐敗的場(chǎng)景類(lèi)似，不再贅述。綜上，方案1達(dá)到了理想與現(xiàn)實(shí)不可區(qū)分的目標(biāo)，證明方案1在不同參與方被腐敗時(shí)均是安全的。

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

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

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

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

(4)

客戶(hù)被腐敗的場(chǎng)景與服務(wù)器被腐敗的場(chǎng)景類(lèi)似，不再贅述。綜上所述，方案2達(dá)到了理想與現(xiàn)實(shí)不可區(qū)分的目標(biāo)，證明方案2在不同參與方被腐敗時(shí)均是安全的。

4.2 性能對(duì)比

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

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

圖3 四種編輯距離方案的運(yùn)行時(shí)間對(duì)比Fig.3 Running time comparison of four Levenshtein distance schemes

1)縱向?qū)Ρ龋悍桨?和方案2的運(yùn)行時(shí)間對(duì)比。

表1顯示了在不同數(shù)據(jù)庫(kù)大小的情況下，第1種方案平均需要的OT的時(shí)間、門(mén)的數(shù)量以及總運(yùn)行時(shí)間?？梢钥闯?，在第1種方案中，OT的時(shí)間、門(mén)的數(shù)量和總運(yùn)行時(shí)間隨基因組數(shù)據(jù)庫(kù)中數(shù)據(jù)量n的增大線(xiàn)性增長(zhǎng)，且增長(zhǎng)速度明顯。

表1 基于線(xiàn)性?huà)呙璧幕虮葘?duì)方案的運(yùn)行時(shí)間 Tab. 1 Running time of genetic comparison scheme based on linear scan

表2顯示了第2種方案在不同大小的數(shù)據(jù)庫(kù)下，平均需要構(gòu)造ORAM的時(shí)間、讀路徑時(shí)間、取出基因數(shù)據(jù)之后的比對(duì)時(shí)間以及總運(yùn)行時(shí)間。在計(jì)算第2種方案的總運(yùn)行時(shí)間時(shí)，并未將構(gòu)造ORAM的時(shí)間計(jì)算在內(nèi)，因?yàn)樵跇?gòu)造一次ORAM之后，客戶(hù)可以進(jìn)行無(wú)數(shù)次比對(duì)，這樣分?jǐn)偟矫恳淮蔚臅r(shí)間可以忽略。從表2中可以看出，在第2種方案中，構(gòu)造ORAM的時(shí)間和讀路徑時(shí)間隨著數(shù)據(jù)量n的增大線(xiàn)性增長(zhǎng)，且相比于讀路徑時(shí)間，比對(duì)時(shí)間占總運(yùn)行時(shí)間的比例較大，而比對(duì)次數(shù)為Blogn，因此比對(duì)時(shí)間亞線(xiàn)性于數(shù)據(jù)庫(kù)大小，所以總運(yùn)行時(shí)間隨著數(shù)據(jù)量n的增長(zhǎng)也呈現(xiàn)亞線(xiàn)性增長(zhǎng)的趨勢(shì)。

表2 基于ORAM的基因比對(duì)方案的運(yùn)行時(shí)間 單位：s Tab. 2 Running time of genetic comparison scheme based on ORAM unit:s

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

2)橫向?qū)Ρ龋号c其他文獻(xiàn)中編輯距離方案的時(shí)間對(duì)比。

根據(jù)縱向?qū)嶒?yàn)結(jié)果可知，本文提出的第2種方案明顯地減少了基因序列比對(duì)時(shí)所需要的比對(duì)次數(shù)。為了進(jìn)一步驗(yàn)證本文所提方案的性能，將本文方案與其他基因比對(duì)方案的性能進(jìn)行了比較。因?yàn)楸葘?duì)時(shí)間占總運(yùn)行時(shí)間比例最大，因此在相同的環(huán)境下，將本文的編輯距離方案與Jha等[8]提出的三種基因編輯距離協(xié)議中性能較好的協(xié)議一、協(xié)議三和Blanton等[10]提出的基因編輯距離方案進(jìn)行對(duì)比，在圖3中分別表示為本文方案、Jha- 1、Jha- 3和Blanton。測(cè)試時(shí)基因序列長(zhǎng)分別為8、12、16、20、25和32個(gè)時(shí)，不同方案的運(yùn)行時(shí)間如圖3所示。從圖3中可以看出，在DNA序列長(zhǎng)度為32時(shí)，Jha- 3的運(yùn)行時(shí)間約為28.6 s，Jha- 1的運(yùn)行時(shí)間約為14.1 s，Blanton的運(yùn)行時(shí)間約為6.64 s，而本文的編輯距離方案中的運(yùn)行時(shí)間僅需要5.31 s，這表明本文方案中的基因編輯距離的運(yùn)行時(shí)間明顯小于Jha和Blanton提出的協(xié)議，而計(jì)算編輯距離的時(shí)間占方案的總運(yùn)行時(shí)間比例最大，因此本文所提出的基因序列比對(duì)方案具有更高的比對(duì)效率。

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

5 結(jié)語(yǔ)

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