基于密碼學的致病基因安全定位方案

黃秀珍 周潭平 李寧波

0 引言

基因是指導人類生命活動的密碼，人類的一切生命活動和生理現(xiàn)象都幾乎與基因直接相關[1]。基因數(shù)據(jù)可以被廣泛應用于醫(yī)療保健、生物醫(yī)學研究及身份鑒定等領域[2-3]，具備很高的研究價值。隨著生物醫(yī)學的不斷發(fā)展及基因組測序成本的不斷下降[4]，越來越多的人有能力獲取自己的基因數(shù)據(jù)。個體的基因數(shù)據(jù)帶有濃厚的個人隱私特征[5]，如果保護不當，可能會引發(fā)基因歧視[6]、司法犯罪等問題。同態(tài)加密能夠?qū)驍?shù)據(jù)進行加密保護，且大部分的同態(tài)加密方案都基于格上的困難問題構造，具備較好的安全性，因此，利用同態(tài)加密開展對基因數(shù)據(jù)的保護和安全分析，近些年逐漸引起了學者們的關注。

2014年，Lauter等[6]利用同態(tài)加密對基因數(shù)據(jù)進行保護，并研究了如何利用一些常用的基因分析算法對密態(tài)的基因數(shù)據(jù)進行分析。同年，Bos等[3]研究了同態(tài)加密在處理敏感的私人醫(yī)療數(shù)據(jù)和基因數(shù)據(jù)方面的應用，并利用同態(tài)加密對密態(tài)數(shù)據(jù)進行預測分析，從而預測一些疾病的發(fā)病概率，文獻[3,6]基于NTRU[7]型類同態(tài)加密方案進行密態(tài)運算，可能受到子域攻擊，無法保證基因數(shù)據(jù)安全。2015年，Lu等[8]利用基于環(huán)上的誤差學習問題(ring learning with error problem，RLWE)的同態(tài)加密來開展全基因組關聯(lián)研究(genome-wide association studies，GWAS)上的安全外包計算。同年，Kim等[9]利用同態(tài)加密方案BGV12[10]等方案對基因數(shù)據(jù)進行保護，對密態(tài)的基因數(shù)據(jù)進行GWAS上的最小等位基因頻率計算，以及DNA序列間的漢明距離和近似編輯距離計算。2016年，Wang等[11]利用同態(tài)加密對基因數(shù)據(jù)進行保護，對密態(tài)的基因數(shù)據(jù)進行邏輯回歸分析，并提出一個治療框架，利用小的樣本數(shù)量來進行安全的罕見變異分析，上述文獻[3,6,9,11]基于單密鑰全同態(tài)加密方案，無法應用于多方來源基因數(shù)據(jù)場景下的密態(tài)運算。2017年，Kim等[12]利用多項式環(huán)上的同態(tài)加密對基因數(shù)據(jù)庫進行加密，并研究了如何對基因數(shù)據(jù)庫進行密態(tài)的查詢和匹配，但該方案無法對基因數(shù)據(jù)進行統(tǒng)計分析。

2017年，Jagadeesh等[13]在《Science》上發(fā)表JWB+17方案。該方案利用現(xiàn)代密碼學中的安全多方計算技術：Yao混淆電路[14-16]+不經(jīng)意傳輸[17-19]，以及基于頻率的臨床遺傳學相關內(nèi)容，利用對稱加密對患者的基因數(shù)據(jù)進行保護，并利用兩云模型將兩方參與的安全計算擴展到多方參與的安全多方計算，從而在不泄露患者基因隱私的前提下，實現(xiàn)對單基因疾病[20-22]患者的致病基因定位。能否定位致病基因，對一些基因疾病的預防和治療具有重大意義。JWB+17方案中用來對致病基因定位的電路有3個：Intersection電路、MAX電路和SET DIFF電路，并通過兩云模型將兩方參與的安全計算擴展到多方參與的安全計算。經(jīng)過對該方案進行分析，發(fā)現(xiàn)其存在以下缺陷。(1)致病基因定位電路方面：原方案中3種電路僅適用于單基因疾病致病基因定位，應用范圍較窄；SET DIFF電路雖然實現(xiàn)了相應功能，但是不夠精簡，影響方案效率。(2)為避免Yao協(xié)議的運行過程中參與方需實時在線且通信量大的問題，JWB+17方案使用了兩云模型。一方面，兩云模型中需要一個比較強的假設：即兩個云之間不會合謀，這個假設對于實際情況而言較強，安全隱患較大。另一方面，兩云模型的引入，需要使用比平凡Yao協(xié)議更加復雜的gabled電路[23-24]，降低了方案效率。此外，兩云模型在執(zhí)行Yao協(xié)議過程中，gabled電路不能重復使用，這會造成較大的通信量[25-26]。

目前，對于基因數(shù)據(jù)的密態(tài)處理解決方案中，存在安全性薄弱、無法處理多方來源的基因數(shù)據(jù)或者通信代價高的缺陷。密碼學中，多密鑰全同態(tài)加密(multi-key fully homomorphic encryption,MKFHE)支持對不同用戶(不同密鑰)的密文進行任意的同態(tài)運算，運算之后的結果由參與計算的用戶聯(lián)合解密[4]，具備強大的密態(tài)計算能力(支持對基因的密文數(shù)據(jù)直接運算，因此可以保證患者的密文數(shù)據(jù)計算過程中的安全)，且通信代價較低。基于以上分析，本文考慮利用密碼學中新興技術MKFHE對患者的基因數(shù)據(jù)進行密態(tài)操作，實現(xiàn)對多方來源的數(shù)據(jù)進行密態(tài)處理的致病基因安全高效定位。

1 致病基因定位方案整體結構和基礎部件

方案擬解決如下問題：多家醫(yī)院的研究人員希望定位某個疾病的致病基因的位置信息，但是每家醫(yī)院的基因數(shù)據(jù)樣本都太少，無法進行有效的統(tǒng)計分析，因此考慮將所有合作醫(yī)院的基因數(shù)據(jù)進行匯總并分析?；驍?shù)據(jù)的分享對患者的隱私帶來嚴重的安全隱患，有助于醫(yī)療數(shù)據(jù)的共享[27-28]，本文使用MKFHE技術構造了致病基因安全定位方案，可保證基因數(shù)據(jù)在統(tǒng)計計算過程中的安全性。實際場景的整體流程如圖1(兩家醫(yī)院數(shù)據(jù)整合為例)。

圖1 致病基因安全定位整體流程Figure 1 The overall process of secure location scheme of pathogenic genes

(1) 患者到醫(yī)療機構進行基因測序，獲取各自的基因數(shù)據(jù)。具體過程見1.1節(jié)。

(2) 醫(yī)療機構將患者的基因數(shù)據(jù)進行同態(tài)加密后，上傳到云服務器。

(3) 醫(yī)療機構對云上的加密基因數(shù)據(jù)進行分析處理(通過對加密數(shù)據(jù)同態(tài)運行相關的函數(shù)布爾電路實現(xiàn))，得到最終的分析結果(密態(tài))。

(4) 醫(yī)療機構對最終的分析結果進行解密，得到有關致病基因變異位置的信息。

1.1 基因數(shù)據(jù)預處理

將參與者的基因數(shù)據(jù)轉化為MKFHE方案所能處理的數(shù)據(jù)類型，是執(zhí)行本方案的前提，對參與者的基因數(shù)據(jù)進行預處理的方法如下[13]。

研究對象首先到醫(yī)療機構進行基因測序，獲取各自的基因數(shù)據(jù)。醫(yī)療機構根據(jù)當前已研究發(fā)現(xiàn)的所有的基因變異數(shù)據(jù)庫(數(shù)據(jù)庫中包含了基因變異的位置信息和變異信息)，將研究對象的基因數(shù)據(jù)與其進行比對，若其在相應的位置發(fā)生變異，則將該位置的值設定為“1”，反之則設定為“0”，由此每個研究對象可以得到一個關于自身基因變異信息的比特串[13]。預處理的過程見圖2。

圖2 基因數(shù)據(jù)預處理示意圖Figure 2 Schematic diagram of the pre-processing of genetic data

1.2 底層多密鑰全同態(tài)加密方案

密碼技術是信息安全的核心技術，早期密碼技術研究的重點在于保證信息存儲和傳輸過程中的安全。而MKFHE是對不同用戶(不同密鑰)的密文進行任意的同態(tài)運算，運算之后的結果由參與計算的用戶聯(lián)合解密[28]，因此可以較好地解決多用戶密文進行同態(tài)計算的問題。

2019年亞洲密碼學年會上，Chen等[29]提出并實現(xiàn)了MKFHE方案CCS19。相對于其他類型的MKFHE方案(NTRU型、GSW型、BGV型)，CCS19具有加解密和自舉過程速度快，支持高效處理比特數(shù)據(jù)，同態(tài)邏輯電路，密文規(guī)模隨用戶數(shù)量呈線性增長的優(yōu)點，更加適合致病基因定位。對于安全參數(shù)l，令C為深度為L的運算電路，CCS19多密鑰全同態(tài)加密方案E=(Setup,KeyGen,Enc,Extend,Eval,Dec)由以下算法組成。

(1) 初始化算法pp←MKFHE.Setup(1λ,1K,1L)：輸入安全參數(shù)l，參與計算的用戶數(shù)量的上界K，電路深度的上界L，輸出公共參數(shù)pp。

(2) 密鑰生成算法(pki,ski,eki,evki)←MKFHE.Key Gen (pp)：輸入公共參數(shù)pp，輸出每個參與方的公鑰pki，私鑰ski，密文擴展所需的密鑰eki，以及同態(tài)運算所需的密鑰evki(i=1,…,K)。

(3) 加密算法ci←MKFHE.Enc (pki,mi)：以第i個參與方為例，輸入其公鑰pki以及待加密的明文mi，輸出密文ci，該密文包含了相關的私鑰以及電路層級信息。

CCS19方案的正確性：輸入t個對應著相同用戶集S的密文序列(ci,S,evki)i∈[t]和任意的深度為L的電路C，令μi= Dec (skS,ci,S)，則以下公式表達了MKFHE方案的正確性。

1.3 致病基因定位函數(shù)

本節(jié)對JWB+17方案中的3種致病基因定位函數(shù)進行介紹[13]。

1.3.1 MAX函數(shù)

MAX函數(shù)[13]用來定位所有的患者中發(fā)生變異次數(shù)最多的突變基因。該函數(shù)對所有患者(預處理之后)的基因數(shù)據(jù)進行求和，求和結果中最大的數(shù)值所對應的基因位置標為1，其余標為0，見圖3。

圖3 MAX函數(shù)示例Figure 3 Example of MAX function

以兩名患者為例，分別輸入各自的n比特的基因數(shù)據(jù)x=(x1,…,xn)和y=(y1,…,yn)，MAX函數(shù)輸出b=(b1,…,bn)，其中：

bi=EQ(MAX(ADD(x1,y1),…,

ADD(xn,yn)),ADD(xi,yi))

(2)

ADD函數(shù)對輸入的基因數(shù)據(jù)進行算術求和，MAX函數(shù)輸出所有輸入數(shù)據(jù)中的最大值，EQ函數(shù)對輸入的兩個數(shù)據(jù)進行比較操作(若相等，輸出1，反之，輸出0)。

1.3.2 Intersection函數(shù)

Intersection函數(shù)[13]用來定位患者中共同發(fā)生的突變基因，即只有在某個基因位置所有的患者都發(fā)生變異，則該位置被標記為1，反之，標記為0，見圖4。

圖4 Intersection函數(shù)示例Figure 4 Example of Intersection function

以兩名患者為例，分別輸入各自的n比特的基因數(shù)據(jù)x=(x1,…,xn)和y=(y1,…,yn)，Intersection函數(shù)輸出b=(b1,…,bn)，其中bi= AND (xi,yi)，AND函數(shù)表示對輸入的基因數(shù)據(jù)進行“與”運算。

1.3.3 SET DIFF函數(shù)

SET DIFF電路[13]研究對象為父母正常，子代患病的家庭，用來定位父母未發(fā)生而子代發(fā)生的突變基因，即只有父母均發(fā)生變異，而孩子發(fā)生變異的位置，才會輸出1，見圖5。

圖5 SET DIFF函數(shù)示例Figure 5 Example of SET DIFF function

以三口之家為例(父母和1個孩子)，分別輸入父母的基因數(shù)據(jù)x=(x1,…,xn)和y=(y1,…,yn)，以及孩子的數(shù)據(jù)z=(z1,…,zn)，SET DIFF函數(shù)輸出b=(b1,…,bn)，其中bi= AND (zi,EQ(0,ADD(xi,yi)))。

SET DIFF函數(shù)可以通過加法器、比較相等電路以及與門電路實現(xiàn)[13]。其電路實現(xiàn)形式見圖6。

圖6 SET DIFF函數(shù)電路結構示意圖Figure 6 Schematic diagram of SET DIFF function circuit structure

2 研究方案

2.1 定位電路設計

定位電路的設計是本文核心內(nèi)容。在設計定位電路時，一方面需要考慮電路具有實現(xiàn)基因定位的功能，另一方面需要結合使用的具體密碼方案特點。兼顧這兩個方面才能更加安全準確地實現(xiàn)致病基因定位。

2.1.1 SET DIFF函數(shù)電路實現(xiàn)形式優(yōu)化

SET DIFF函數(shù)可以由相對較為復雜的加法門電路、與門電路以及比較相等電路來實現(xiàn)，為了提高SET DIFF函數(shù)的門電路實現(xiàn)效率，本方案對該函數(shù)的電路實現(xiàn)結構進行了簡化，通過3個簡單的“與”門電路、“或”門電路和“非”門電路，即可實現(xiàn)原有函數(shù)的功能，從而較大程度地降低了電路的復雜度，提高了電路的實現(xiàn)效率。經(jīng)過優(yōu)化后的SET DIFF函數(shù)如下。

以三口之家為例(父母和1個孩子)，分別輸入父母的基因數(shù)據(jù)x=(x1,…,xn)和y=(y1,…,yn)，以及孩子的數(shù)據(jù)z=(z1,…,zn)，輸出b=(b1,…,bn)，其中bi=AND (NOT(OR(xi,yi)),zi)。優(yōu)化后的電路實現(xiàn)結構圖見圖7。

圖7 優(yōu)化后的SET DIFF函數(shù)電路結構示意圖Figure 7 Schematic diagram of optimised SET DIFF function circuit structure

2.1.2 ITH-intersection(門限定位)函數(shù)

基因中的一個或者多個位置的惡性變異，都有可能會引發(fā)基因疾病，以帕金森病為例，該疾病可能由135個基因位置的惡性變異引起，任何幾個基因位置的突變都可能會引發(fā)疾病。原JWB+17方案中所使用的3種致病基因定位函數(shù)，只能針對單基因疾病進行定位診斷，適用范圍較窄。為了能夠針對多基因疾病進行分析研究，本研究設計了ITH-intersection函數(shù)(門限定位函數(shù))，該函數(shù)的研究對象為患同一種基因疾病的患者，通過設置合適的閾值，能夠輸出可能導致患病的多個基因數(shù)據(jù)的位置以及該位置具體變異的患者個數(shù)，擴展了致病基因定位的適用范圍。

輸入m個患者的基因數(shù)據(jù)yj=(yj,1,…,yj,n)，其中j∈{1,…,m}。輸出Z=(z1,…,zm)，其中zj=(zj,1,…,zj,n)，zj,i= MULT(ADD (y1,i,…,ym,i),LT (l,ADD (y1,i,…,ym,i)))，j∈{1,…,m}，i∈{1,…,n}，LT 函數(shù)表示當左側的輸入小于右側輸入時，輸出1，否則輸出0，LT (x,y)函數(shù)可以通過加法函數(shù)ADD(y,-x)構造，ADD(y,-x)輸出的最高位就是需要的結果。ITH-intersection電路的具體實現(xiàn)形式如圖8所示。在實際實驗過程中使用AND函數(shù)代替MULT函數(shù)以提升效率，令s=ADD (y1,i,…,ym,i)，si表示s的第i個比特，則zj,i=AND(si,LT (l,ADD (y1,i,…,ym,i)))。

圖8 ITH-intersection(門限定位)函數(shù)電路結構示意圖Figure 8 Schematic diagram of function circuit structure of ITH-intersection

2.1.3 ITop-k 函數(shù)

除了門限定位函數(shù)，本文還設計了ITop-k函數(shù)，該函數(shù)能夠輸出所有患者中變異次數(shù)最多的前k個基因位置以及該位置對應的變異次數(shù)排序值(當多個位置變異次數(shù)相同時，輸出相同的排序)，可以用于多基因疾病的致病基因定位。

輸入h個患者的基因數(shù)據(jù)xj=(xj,1,…,xj,n)，j∈{1,…,h}，輸出b=(btop-k,1,…,btop-k,n)。ITop-k函數(shù)對應的電路實現(xiàn)結構較復雜，很難用圖形展示，其具體過程見算法1。

算法1:ITop-k電路輸入:h個用戶的比特串xj=(xj,1,…,xj,n),j∈{1,…,h}。輸出:b=(btop-k,1,…,btop-k,n)。1:xtop-1,i=ADD(x1,i,…,xh,i), 1≤i≤n2:for r=1,…,k-1btop-r,i=1btop-r,i = EQ(MAX (xtop-r,1,…,xtop-r,n),xtop-r,i ),1≤i≤nbtop-r,i=ADD(btop-r,i,-btop-j,i)xtop-(r+1),i=MULT(btop-r,i,xtop-r,i),1≤i≤n3:btop-k,i = EQ(MAX (xtop-k,1 ,…,xtop-k,n),xtop-k,i),1≤i≤n4:btop-k,i=ADDkj=1(MULT(j,btop-j,i)),1≤i≤n5:b=(btop-k,1,…,btop-k,n)6:end for

2.2 基于MKFHE的致病基因定位方案計算流程

按照MKFHE方案密態(tài)計算的框架，結合具體的定位函數(shù)，得到基于MKFHE的致病基因定位方案計算流程，整體流程見圖9，偽代碼見算法2。

(2) 基因數(shù)據(jù)預處理。將參與者的基因數(shù)據(jù)轉化為MKFHE方案所能處理的數(shù)據(jù)類型，具體方法見1.1節(jié)。

(3) 數(shù)據(jù)加密。研究對象i利用公鑰pki對基因數(shù)據(jù)xi進行逐比特同態(tài)加密，得到密文序列{ci,j←MKFHE.Enc(xi,j)}j = 1,…,N，并將密文數(shù)據(jù)上傳到云端。

算法2:基于MKFHE的致病基因定位算法輸入:xi={xi,j},pki,eki,evki,i∈[N],j∈[n] 。輸出:{c′j}j=1,…,N。1:for i=1,2,…,N,j=1,2,…,n ci,j ←MKFHE .Enc (xi,j )2:for i=1,2,…,N,j=1,2,…,n ci,j ←MKFHE.Extend(ci,j ,(pk1 ,…,pkN ),eki )3:for j=1,2,…,n c′j←MKFHE.Eval(C,(c1,j ,pk1,evk1),…, (cN,j ,pkN ,evkN ))4:for j=1,2,…,n mj←MKFHE.Dec(sks=sk1,…,skN),c′j)5:end for

圖9 云環(huán)境下致病基因安全定位計算流程Figure 9 Computation process of secure location scheme of pathogenic genes in Cloud

表1 本方案與JWB+17方案在效率方面的對比Table 1 Efficiency comparison of our scheme with JWB+17 scheme

3 實驗分析

本文對兩方參與的Intersection電路、SET DIFF電路，每個用戶輸入48比特的信息進行了測試；對三方參與的ITH-intersection電路，每個用戶輸入48比特的信息進行了測試。主要測量了計算的時間及通信量。實驗環(huán)境如下，筆記本：DELL precision 7530，系統(tǒng)：Ubuntu 18.04 STL，CPU：Intel(R) Core(TM) i7-8750H 2.20 GHz，內(nèi)存：16 GB。實驗結果見表1，本文方案與JWB+17方案[13]整體的對比見表2。

表2 本文方案與JWB+17方案整體對比Table 2 Functional comparison of our scheme with JWB+17 scheme

測試結果顯示，本文方案的通信量相比JWB+17方案大幅降低，但運行的時間更長。因此，本文方案更加適用于帶寬受限的系統(tǒng)。雖然JWB+17也嘗試通過兩云模型的方式，降低帶寬，但是這種模式無法抵抗兩云的合謀攻擊，安全性假設太強。此外，JWB+17方案中的混淆電路無法重復使用，每次進行新的運算時需要重新構造混淆電路。而在本文方案中，用戶密文可以重復使用，只需要上傳一次密文即可。因此，相比于JWB+17方案中各個機構需要實時在線運行協(xié)議，本文方案可以支持離線操作，操作更加便利。

4 討論與結論

本文基于密碼學中的多密鑰全同態(tài)加密技術，結合基于頻率的臨床遺傳學相關內(nèi)容，提出一種對不同患者基因數(shù)據(jù)進行致病基因安全定位的方法，該方法可以支持對多方來源的數(shù)據(jù)進行密態(tài)處理，在一定程度上解決了不同醫(yī)療機構希望共享基因數(shù)據(jù)又希望保護本機構中患者隱私的矛盾。

實驗結果表明，相對于JWB+17方案，本方案可以支持對多基因疾病進行分析，擴大了目前基因數(shù)據(jù)密態(tài)處理的應用范圍，方案大幅降低了數(shù)據(jù)通信量，更加適用于帶寬受限的系統(tǒng)。后期，擬進一步優(yōu)化底層方案，使得方案可以應用于對大規(guī)模用戶的場景。