劉 海,吳振強,彭長根,雷秀娟

1(陜西師范大學(xué) 計算機科學(xué)學(xué)院,陜西 西安 710119)

2(貴州省公共大數(shù)據(jù)重點實驗室(貴州大學(xué)),貴州 貴陽 550025)

基因數(shù)據(jù)是富含人類重要信息的生物大數(shù)據(jù)[1],并且是人類脫氧核糖核酸(deoxyribonucleic acid,簡稱DNA)序列的總稱.DNA是生物遺傳信息的攜帶者,與生物的繁殖、遺傳及變異密切相關(guān).DNA序列包含 30億由4種核苷酸(腺嘌呤A、鳥嘌呤G、胸腺嘧啶T、胞嘧啶C)組成的堿基對,人類有99.9%共同的DNA序列,其中,大約有 5 000萬單核苷酸多態(tài)性(single nucleotide polymorphism,簡稱 SNP).SNP是最常見的 DNA變異,SNP是指個體DNA序列同一位置單個核苷酸變異所引起的多態(tài)性.SNP變異由單個堿基的轉(zhuǎn)換(C?T,在其互補鏈上則為 C?A)或顛換(C?A,G?T,C?G,A?T)所引起,一般所說的 SNP變異由堿基轉(zhuǎn)換所致.通常對于每個 SNP位點具有兩個不同核苷酸(稱為等位基因),一個是高頻率的主要等位基因,一個是低頻率的次要等位基因.等位基因是同源染色體上的相同位點控制同一性狀的不同形式的基因.位點是染色體上一個基因或標(biāo)記的位置.SNP的連鎖不平衡(linkage disequilibrium,簡稱LD)是一種普遍存在的生物現(xiàn)象,指的是基因序列中任意兩個鄰近SNP之間的等位基因在多代遺傳中的非隨機組合現(xiàn)象.

隨著高通量基因測序技術(shù)的發(fā)展,測序成本大幅度降低,產(chǎn)生了海量高維的基因數(shù)據(jù).基因數(shù)據(jù)廣泛用于科學(xué)研究、面向消費者服務(wù)和法律與司法鑒定等[2].例如,在全基因組關(guān)聯(lián)研究(genome-wide association studies,簡稱GWAS)中可以識別與SNP相關(guān)的疾病[3].但是,SNP攜帶個體健康的隱私敏感信息,并且可以唯一標(biāo)識人類個體,基因數(shù)據(jù)使用不當(dāng)會導(dǎo)致敏感信息泄露[4],例如,載脂蛋白 E(apolipoprotein E)基因的兩個 SNP(rs7412和rs429358)會增加患老年癡呆癥(Alzheimer’s disease)的風(fēng)險.并且在連鎖不平衡下,可以從SNP相關(guān)的敏感信息推斷出其他SNP相關(guān)的敏感信息.因此,本文基于SNP連鎖不平衡相關(guān)系數(shù),提出基因隱私保護模型:矩陣差分隱私(matrix differential privacy,簡稱MDP).該模型既可以保護基因數(shù)據(jù)和SNP連鎖不平衡的隱私,同時確?；驍?shù)據(jù)具有一定的效用.

由于 SNP可以唯一標(biāo)識人類個體,并且關(guān)聯(lián)表型和血緣關(guān)系等隱私敏感信息.如果沒有適當(dāng)?shù)貙驍?shù)據(jù)進行隱私保護,將會阻礙科學(xué)研究的進步和發(fā)展,并給人類社會帶來巨大影響.例如,在基因組序列中只需 30～80個獨立的SNP位點就可以唯一重識別個體[5],進而導(dǎo)致其關(guān)聯(lián)的隱私敏感信息泄露.從GWAS中揭示個體的疾病狀態(tài)[6]可能會導(dǎo)致工作和保險中的基因歧視[7].考慮到具有血緣關(guān)系個體之間的基因數(shù)據(jù)非常相似,可以從GWAS中推斷個體的親戚及其相關(guān)的表型敏感信息[4].因此需要聯(lián)合法律法規(guī)和隱私保護技術(shù)來實現(xiàn)基因數(shù)據(jù)的隱私保護.目前國內(nèi)尚未有專門的基因隱私保護法律法規(guī),美國于 1996年頒布了 HIPAA(health insurance portability and accountability act)禁止基因歧視.

除了專門的基因隱私保護法律法規(guī)外,還需要隱私保護技術(shù)來實現(xiàn)基因數(shù)據(jù)的隱私保護.由于基因與人類的敏感信息密切相關(guān),基因-疾病關(guān)聯(lián)分析中目前主要有 3類基因隱私保護方法,包括密碼學(xué)[8-11]、安全計算[12,13]和差分隱私[14-18].

為了從分布式基因數(shù)據(jù)中分析罕見疾病,Chen等人[8]提出隱私保護分布式協(xié)作框架 PRINCESS,并使用AES-GCM(advanced encryption standard in galois counter mode)加密所有基因數(shù)據(jù),PRINCESS為了保護健康信息的隱私對加密數(shù)據(jù)執(zhí)行安全的分布式計算.在使用 AES-GCM 加密基因數(shù)據(jù)時,由于密鑰分發(fā)通信代價高而使加解密受限,并且不可信用戶解密后通過分析基因數(shù)據(jù)導(dǎo)致患者隱私泄露.因此,為了防止不可信用戶解密后分析基因數(shù)據(jù)導(dǎo)致的隱私泄露,使用同態(tài)加密直接對密文進行計算.Ayday[9]使用Paillier密碼系統(tǒng)和Honey加密方法保護基因數(shù)據(jù)的隱私.為了發(fā)現(xiàn)罕見變異與疾病易感性的關(guān)系,基于懲罰似然的確切邏輯回歸(exact logistic regression)減少偏差的方法,Wang等人[10]在同態(tài)加密的確切邏輯回歸的基礎(chǔ)上提出HEALER框架,便于在 GWAS中安全地實現(xiàn)小抽樣的罕見疾病變異分析.為了實現(xiàn)查詢和結(jié)果的隱私保護,Shimizu等人[11]基于加法同態(tài)加密的不經(jīng)意傳輸(oblivious transfer)隱藏序列查詢和感興趣的基因區(qū)域.由于同態(tài)加密基于有限域數(shù)學(xué)理論,計算效率非常低,并且在不可信用戶解密后同樣面臨隱私泄露的問題.

在人類基因序列之間,安全計算編輯距離(edit distance)在醫(yī)學(xué)的個人基因數(shù)據(jù)和公共健康領(lǐng)域呈現(xiàn)出許多有趣的應(yīng)用.Wang等人[12]結(jié)合基因編輯距離近似算法和隱私集合差大小協(xié)議設(shè)計隱私編輯距離協(xié)議,并基于此,設(shè)計全基因組安全相似患者查詢系統(tǒng)GenSets.最近的工作表明,個體的微生物DNA序列與人類個體標(biāo)識相符合,并且可以關(guān)聯(lián)基因數(shù)據(jù)集中敏感屬性的實際身份.目前,DNA隱私保護分析工具不滿足微生物測序研究的要求.為了解決微生物測序的隱私問題,Wagner等人[13]使用安全計算實現(xiàn)宏基因組分析.基因數(shù)據(jù)的安全計算中計算效率低,而且通信代價高.

從基因數(shù)據(jù)選擇到GWAS統(tǒng)計值的隱私保護,差分隱私[14]已經(jīng)廣泛應(yīng)用于基因數(shù)據(jù).例如,在DNA數(shù)據(jù)選擇過程中,Zhao等人[15]利用連鎖不平衡對高維單體型降維到單體型塊,并通過對單體型塊的次要等位基因計數(shù)加噪音產(chǎn)生差分隱私實驗數(shù)據(jù)集,不但保護了患者的隱私,而且保證了 DNA數(shù)據(jù)的效用.在隱私保護數(shù)據(jù)選擇中僅僅通過對次要等位基因計數(shù)加噪音來實現(xiàn)差分隱私.由于隱私攻擊對參與 GWAS患者的隱私具有潛在的威脅,Cai等人[16]提出了差分隱私技術(shù)是一個有希望的研究方向,差分隱私通過注入隨機噪音到基因型頻率、基因型-疾病關(guān)聯(lián)性和基因型-基因型關(guān)聯(lián)性統(tǒng)計值.但并未考慮SNP的連鎖不平衡性質(zhì).假設(shè)GWAS的基因數(shù)據(jù)是不相關(guān)的,Tramèr等人[17]考慮更多合理的背景知識作為先驗分布,提出有界先驗差分隱私用于 GWAS中每個SNP列聯(lián)表的χ2-統(tǒng)計值達到效用與隱私的平衡.不過,同樣沒有考慮基因數(shù)據(jù)中SNP的連鎖不平衡性質(zhì).然而,在挖掘最重要的SNP的所有差分隱私方法中都具有準(zhǔn)確度或計算效率的缺點,為此,Simmons和Berger[18]使用等位基因檢測統(tǒng)計值的輸入擾動和自適應(yīng)邊界的方法來克服準(zhǔn)確性問題.總的來說,在GWAS中的差分隱私保護研究僅僅考慮添加噪音到統(tǒng)計值,而沒有考慮 SNP的連鎖不平衡性質(zhì),并且沒有對原始基因數(shù)據(jù)進行隱私保護.

但是,基于GWAS中的統(tǒng)計值和SNP的連鎖不平衡,可以推斷出患者的隱私信息.因為SNP連鎖不平衡是同一染色體上相互鄰近的等位基因可能同時遺傳到后代.那么從一個 SNP位點的敏感信息可以推斷出其他SNP位點相關(guān)的敏感信息.例如,在SNP連鎖不平衡下,觀察到的SNP越多,基因隱私保護強度越低[4].現(xiàn)有的工作主要有兩方面的局限性:(1) 沒有從基因數(shù)據(jù)而僅僅是從GWAS中的統(tǒng)計值上實現(xiàn)患者的差分隱私；(2) 沒有考慮SNP連鎖不平衡下的基因數(shù)據(jù)隱私保護.另外,由于基因型數(shù)據(jù)只包含數(shù)值0、1和2,如果對基因數(shù)據(jù)直接使用差分隱私機制將導(dǎo)致基因數(shù)據(jù)效用災(zāi)難,詳見第4.4節(jié)基因數(shù)據(jù)的效用分析.

為了解決此問題,本文提出基因數(shù)據(jù)和SNP連鎖不平衡的矩陣差分隱私保護模型.首先將單核苷酸多態(tài)性二倍體基因數(shù)據(jù)進行矩陣存儲,然后在連鎖不平衡下基于嚴(yán)格的差分隱私定義實現(xiàn)二倍體基因數(shù)據(jù)以及 SNP連鎖不平衡的不可區(qū)分性,最后運用模余運算進行二倍體基因數(shù)據(jù)的置換.矩陣差分隱私保護模型不僅滿足差分隱私,而且確保一定的基因數(shù)據(jù)效用.同時,矩陣差分隱私保護模型可以擴展到基因數(shù)據(jù)的其他應(yīng)用領(lǐng)域.本文主要貢獻如下.

(1) 結(jié)合SNP二倍體基因數(shù)據(jù)的矩陣存儲、SNP連鎖不平衡下嚴(yán)格的差分隱私定義和模余運算,提出矩陣差分隱私保護模型作為基因隱私保護的新方法.

(2) 基于拉普拉斯機制和高斯機制,在 SNP連鎖不平衡相關(guān)系數(shù)下,設(shè)計矩陣差分隱私保護模型的算法,實現(xiàn)基因數(shù)據(jù)與SNP連鎖不平衡的隱私保護.

(3) 矩陣差分隱私保護模型確?；驍?shù)據(jù)效用在區(qū)間[R0,1]中,其中,R0表示當(dāng)隱私預(yù)算最小時矩陣差分隱私下噪音矩陣中模3余0元素數(shù)量的百分比值.

本文第1節(jié)介紹基因背景知識以及矩陣計算、模余運算和差分隱私的預(yù)備知識.第2節(jié)提出矩陣差分隱私保護模型.第 3節(jié)對矩陣差分隱私進行理論分析.第 4節(jié)分別對矩陣差分隱私的隱私保護和基因數(shù)據(jù)效用進行實驗分析.第5節(jié)對全文進行總結(jié).

1 預(yù)備知識

首先介紹基因的背景知識.然后介紹矩陣計算、模余運算和差分隱私的預(yù)備知識.

1.1 基因組

盡管人類的DNA大部分是相同的,但是產(chǎn)生的變異大約有5 000萬,其中SNP是人類最常見的DNA變異.由于每個SNP位點的兩個核苷酸分別從父親和母親的基因中遺傳而來,因此可能是高頻率的主要等位基因,也可能是低頻率的次要等位基因.每個SNPgi具有次要等位基因的頻率為,對于一個個體的基因型SNP的次要等位基因頻率表示為m維向量.用B表示主要等位基因,b表示次要等位基因,B,b∈{A,C,G,T},并且編碼BB為0,Bb為1,bb為2.考慮SNP序列作為個體的基因數(shù)據(jù),稱為二倍體基因型,其中,每個基因型取值屬于集合{0,1,2}.因此,單倍體基因型對應(yīng)一條染色體,而二倍體基因型對應(yīng)一組染色體.

在人類基因組序列中,每個序列可以表示為有序的SNP序列g(shù)1,g2,…,gm序列,其中,每個gi∈{0,1,2}.假設(shè)gi與gj相互連鎖不平衡,(B,b)和(D,d)分別是gi和gj的等位基因.假設(shè)(p1,1-p1)和(p2,1-p2)分別是(B,b)和(D,d)的等位基因概率.這里,等位基因頻率即是等位基因的概率.如果gi和gj相互獨立,那么個體在gi和gj的主要等位基因是B和D的概率為p1p2.然而,由于gi和gj的關(guān)聯(lián)性,因此連鎖不平衡系數(shù)為LD=P(BD)-P(B)P(D),其中,在連鎖不平衡下,P(BD)等于在 SNP位點i和j的等位基因B和D共同出現(xiàn)在群體中的頻率,并使用作為SNP連鎖不平衡的相關(guān)系數(shù),當(dāng)rij=1時,表示最強的SNP連鎖不平衡[4].

1.2 矩陣計算

對于兩個n×m矩陣S=(sij)n×m和T=(tij)n×m,其中,1≤i≤n,1≤j≤m.S和T之間的加運算定義為(cij)n×m=(sij)n×m+(tij)n×m,其中,cij=sij+tij.另外,round(S)表示運用四舍五入規(guī)則將矩陣S中的元素取整的近似運算.

1.3 模余運算

給定整數(shù)s、t、q和r,余數(shù)r=s-qt表示為r≡smodt(0

1.4 差分隱私

根據(jù)兩個相同的概率分布是不可區(qū)分的,對于個體數(shù)據(jù)的集合,差分隱私[14]確保一個攻擊者的能力是相同的,獨立于任何個體是否在數(shù)據(jù)集中.因此,在同樣大小的數(shù)據(jù)集之間,鄰近數(shù)據(jù)集僅只有一個不同.也就是說,兩個鄰近數(shù)據(jù)集X1和X2的漢明距離(Hamming distance)為d(X1,X2)=1.其中,差分隱私定義如下.

定義1(差分隱私).給定ε≥0,如果有任意兩個鄰近數(shù)據(jù)集X1和X2,對于擁有全背景知識的攻擊者,隨機機制M的任意輸出S?Range(M)使得 P r[M(X1) ∈S] ≤eεPr[M(X2)∈S]+δ,那么M是(ε,δ)-差分隱私.

其中,1-δ∈[0,1]是M滿足(ε,δ)-差分隱私的概率,并且,如果δ=0,那么M是ε-差分隱私.

為了實現(xiàn)差分隱私機制,需要計算查詢函數(shù)f的敏感度,查詢函數(shù)f:X→Rk的敏感度是

另外,差分隱私具有后處理(post-processing)和并行組合(parallel composition)[19]的性質(zhì).

性質(zhì)1(后處理).隨機機制M:X→R關(guān)于數(shù)據(jù)集X是(ε,δ)-差分隱私,f:R→R′是一個隨機映射,那么f?M:X→R′是(ε,δ)-差分隱私.

性質(zhì) 2(并行組合).隨機機制Mi滿足(εi,δ)-差分隱私,數(shù)據(jù)集Xi是X的子集,且，那么Mi的并行組合滿足(max{εi},δ)-差分隱私.

2 基因隱私保護模型

首先引入SNP連鎖不平衡下對基因數(shù)據(jù)的攻擊模型,接下來提出基因隱私保護模型:矩陣差分隱私.

2.1 攻擊模型

因為通過 SNP可以識別個體及其相關(guān)的敏感信息.假設(shè)攻擊者已經(jīng)觀察到隱藏的 SNP,并且攻擊者是honest-but-curious.攻擊者可以通過成對的SNP連鎖不平衡獲得敏感信息,例如相鄰兩個位點i和j的SNPgi和gj,它們之間存在SNP連鎖不平衡,如果gi與某種疾病易感性相關(guān),那么gj也與該疾病相關(guān).

2.2 矩陣差分隱私保護模型

在SNP連鎖不平衡下,由于基因數(shù)據(jù)的隱私保護需求,我們首先給出基因隱私保護模型——矩陣差分隱私,如圖1所示,該模型主要包括3部分.第1部分為編碼SNP二倍體基因數(shù)據(jù)并用矩陣存儲.第2部分為對已編碼的SNP二倍體基因數(shù)據(jù)進行隨機擾動,同時滿足基于SNP連鎖不平衡下的差分隱私.第3部分為使用模余運算置換隨機擾動的SNP基因數(shù)據(jù).其中,各個部分的主要思想如下.

在第1部分,B表示主要等位基因,b表示次要等位基因,根據(jù)等位基因的頻率,將主要等位基因B編碼為0,次要等位基因b編碼為1,并且B,b∈{A,C,G,T},編碼基因型BB為0,Bb為1,bb為2.那么對于n個個體,每個個體有m個 SNP,用矩陣表示為X=(xij)n×m(1≤i≤n,1≤j≤m),且xij∈{0,1,2}表示第i個個體第j個位點的 SNP基因型.

第 2部分是對 SNP二倍體基因數(shù)據(jù)進行隨機擾動,并且滿足 SNP連鎖不平衡下的差分隱私.圖 2所示為SNP二倍體基因型數(shù)據(jù)隨機擾動的主要思想,根據(jù)SNP連鎖不平衡下的差分隱私擾動機制,將SNP二倍體基因型矩陣元素xij∈{0,1,2}分別以概率p1、p2和p3進行隨機擾動.這里,p1、p2和p3是SNP連鎖不平衡下差分隱私隨機噪音對應(yīng)的概率.

如圖2所示,第3部分對隨機擾動的二倍體基因型數(shù)據(jù)進行模余運算,使其具有SNP二倍體基因型數(shù)據(jù)的語義,并根據(jù)等位基因頻率和基因型編碼置換為相應(yīng)的基因型.

Fig.1 The genomic privacy preserving framework for SNP linkage disequilibrium圖1 SNP連鎖不平衡下的基因隱私保護模型

Fig.2 The differential privacy perturbation mechanism for SNP linkage disequilibrium圖2 SNP連鎖不平衡下的差分隱私擾動機制

2.3 矩陣差分隱私

矩陣X=(xij)n×m表示n個個體的SNP,每個個體的DNA序列有m個SNP,其中,xij∈{0,1,2}表示個體i的SNPgj的隨機變量.特別地,Xi=(xi1,xi2,…,xim)表示個體i的SNP序列取值.

因為xij∈{0,1,2},所以查詢函數(shù)f的敏感度為Δf=2.

下面結(jié)合矩陣加運算、SNP連鎖不平衡下的差分隱私定義和模余運算,給出矩陣差分隱私的定義.

定義 2(矩陣差分隱私).給定ε≥0,任意兩個鄰近矩陣,對于具有全背景知識的攻擊者,M的任意輸出S=(sij)n×m?Range(M),使得.那么,隨機機制

另外,由于個體i的SNP序列值表示為向量Xi=(xi1,xi2,…,xim).類似地,下面我們來定義向量差分隱私.

定義3(向量差分隱私).給定ε≥0,任意兩個鄰近向量,對于具有全背景知識的攻擊者,M的任意輸出Si=(sij)1×m?Range(M),使得.那么,隨機機制

因此,向量差分隱私是矩陣差分隱私的特例.下面給出矩陣差分隱私的通用算法1.其中,概率分布π(Δfc/max可以是拉普拉斯分布和高斯分布,即噪音矩陣(yij)n×m是由拉普拉斯機制(Laplace mechanism,簡稱LM)和高斯機制(Gaussian mechanism,簡稱GM)[20]產(chǎn)生的.相應(yīng)的常數(shù)c分別為1和.由于SNP二倍體基因型矩陣存儲(xij)n×m中元素xij∈{0,1,2},這里暫且將xij看作字符型,簡單地定義基因型xij的效用函數(shù)為u:xij→xij,也就是說,u(xij=0)=0,u(xij=1)=1和u(xij=2)=2,那么效用函數(shù)的敏感度為Δu=2,因此在指數(shù)機制下選取基因型值0、1和2的概率分別正比于1、eε/4和eε/2.因為SNP基因型矩陣及其對應(yīng)的效用矩陣的元素都是0、1和2,所以通過指數(shù)機制選擇基因型值 0、1和 2的隨機性較差,那么在 SNP基因型數(shù)據(jù)的這種效用函數(shù)定義方式下,使用指數(shù)機制將導(dǎo)致基因型數(shù)據(jù)及其相關(guān)的敏感信息泄露,因此本文沒有考慮指數(shù)機制(exponential mechanism,簡稱EM)[20].

算法1.在SNP連鎖不平衡下的矩陣差分隱私.

3 矩陣差分隱私的分析

下面從理論上分析矩陣差分隱私的性質(zhì).

定理1.矩陣差分隱私是差分隱私.

為了分析矩陣差分隱私的效用,因為S= (sij)n×m?Range(M),本文使用度量矩陣差分隱私機制的效用[18].

定理 2.矩陣差分隱私的效用在[R0,1]區(qū)間,R0表示隱私預(yù)算ε最小時矩陣差分隱私下噪音矩陣中模 3余 0元素數(shù)量的百分比值.

證明:首先考慮3種極端的情況.

(1) 當(dāng)噪音矩陣Y=(yij)n×m的所有元素滿足round(yij) mod 3=0時,round((yij)n×m)的所有元素都模 3同余 0.因此,在(xij)n×m與(sij)n×m?Range(M)之間的所有 SNP二倍體基因型數(shù)據(jù)相同.因此,矩陣差分隱私機制的最大效用為1.

(2) 當(dāng)噪音矩陣Y=(yij)n×m的所有元素滿足round(yij) mod 3≡1時,(0+1) mod 3≡1,(1+1) mod 3≡2和(2+1) mod 3≡0.因此,(xij)n×m與(sij)n×m?Range(M)之間的所有 SNP二倍體基因型取值都不相同,此時矩陣差分隱私機制的效用是0.

(3) 當(dāng)噪音矩陣Y=(yij)n×m的所有元素滿足round(yij) mod 3≡2時,(0+2) mod 3≡2,(1+2) mod 3≡0和(2+2) mod 3≡1.因此,(xij)n×m與(sij)n×m?Range(M)之間的所有 SNP二倍體基因型取值也都不相同,此時矩陣差分隱私機制的效用是0.

上述證明中考慮(2)和(3)兩種極端情況,使矩陣差分隱私下基因數(shù)據(jù)的效用為 0.然而,由于噪音的隨機性,矩陣差分隱私下基因數(shù)據(jù)的最小效用是大于0的,詳見第4.4節(jié)基因數(shù)據(jù)的效用分析.下面考慮第4種情況.

(4) 在矩陣差分隱私中,由于隱私預(yù)算ε越小,鄰近基因數(shù)據(jù)矩陣的不可區(qū)分性越好,進而矩陣差分隱私保護越強,那么基因數(shù)據(jù)的效用達到最低.在矩陣差分隱私中基因數(shù)據(jù)的效用與模 3余 0的噪音數(shù)量的百分比值是一致的.也就是說,如果隱私預(yù)算ε最小,矩陣差分隱私產(chǎn)生模 3余 0的噪音數(shù)量百分比值為R0(1＞R0＞0),那么基因數(shù)據(jù)的最小效用為R0.反之,隱私預(yù)算ε越大,基因數(shù)據(jù)效用可達到百分比值1.

綜上,由于噪音的隨機性,矩陣差分隱私機制的效用屬于區(qū)間[R0,1]. □

定理3.考慮連鎖不平衡、矩陣加運算和模余運算的計算復(fù)雜度分別為O(n×m2)、O(n×m)和O(n×m).矩陣差分隱私的計算復(fù)雜度如下:(1) 當(dāng)n=m時,矩陣差分隱私的計算復(fù)雜度為O(n3)；(2) 當(dāng)n＞m時,矩陣差分隱私的計算復(fù)雜度為O(nm2)；(3) 當(dāng)n

證明:在矩陣差分隱私中,產(chǎn)生隨機噪音是有效的,忽略其計算復(fù)雜度,而計算連鎖不平衡、矩陣加運算和模余運算分別需要8n×(m2-m)、n×m和n×m次運算,考慮3種情況.

(1) 當(dāng)n=m時,矩陣差分隱私的計算復(fù)雜度為O(n3).

(2) 當(dāng)n＞m時,矩陣差分隱私的計算復(fù)雜度為O(nm2).

(3) 當(dāng)n

總之,矩陣差分隱私滿足差分隱私的定義,同時具有效用屬于區(qū)間[R0,1],其中,R0是矩陣差分隱私下隱私預(yù)算最小時噪音矩陣中模3余0元素數(shù)量的百分比值,并且矩陣差分隱私的計算復(fù)雜度是多項式時間的.

4 實驗分析

本文在矩陣差分隱私下選擇拉普拉斯分布和高斯分布來進行實驗分析.首先進行噪音分析,然后與拉普拉斯機制和高斯機制比較分析矩陣差分隱私保護模型的隱私和效用.在所有的實驗分析中,考慮SNP二倍體基因型數(shù)據(jù)的特點,初始化SNP連鎖不平衡的相關(guān)系數(shù)為rij=1和敏感度Δf=2.另外,分別初始化隱私預(yù)算ε=0.001和概率值δ=0.01.

4.1 數(shù)據(jù)集

國際人類基因組單體型圖計劃(Int’l Hapmap Project)的數(shù)據(jù)是公開可用的[21],本文使用2010年5月發(fā)布的階段III的165個CEU(utah residents with northern and Western European ancestry from the CEPH collection)群體的22號染色體的基因型和頻率數(shù)據(jù)集.在實驗分析之前,基于頻率數(shù)據(jù)集預(yù)處理基因型數(shù)據(jù)集,將 SNP二倍體基因型數(shù)據(jù)編碼為0、1和2.在CEU基因型數(shù)據(jù)集中,將丟失的數(shù)據(jù)’NN’用0代替.本文分別選擇500、1 000和1 500個SNP位點進行實驗分析.

4.2 噪音分析

Fig.3 The percentage of noises matrix entries module 3 satisfying the residue to be 0 for matrix differential privacy圖3 矩陣差分隱私下噪音矩陣模3余0的元素數(shù)量的百分比值

4.3 隱私分析

為了評估基因隱私保護模型的隱私,對于擁有全背景知識的攻擊者,本文定義標(biāo)準(zhǔn)化期望估計誤差作為隱私度量.因為元素xij在矩陣差分隱私下的隨機擾動元素為sij,因此,定義基因數(shù)據(jù)的隱私度量為

通過比較,我們來分析矩陣差分隱私與拉普拉斯機制、高斯機制的標(biāo)準(zhǔn)化期望估計誤差.如圖 4和圖 5所示,矩陣差分隱私、拉普拉斯機制和高斯機制的標(biāo)準(zhǔn)化期望估計誤差都隨隱私預(yù)算的增大而減小.主要原因是,隱私預(yù)算越大,拉普拉斯分布和高斯分布的方差越小,矩陣差分隱私產(chǎn)生模3余0的噪音越多.因此拉普拉斯機制和高斯機制直接添加噪音到 SNP基因型數(shù)據(jù)會導(dǎo)致效用災(zāi)難,而矩陣差分隱私通過噪音模余運算提高了SNP基因型數(shù)據(jù)的效用,見第4.4節(jié)矩陣差分隱私的效用分析.由此,矩陣差分隱私實現(xiàn)了基因數(shù)據(jù)的隱私保護,不過,隱私保護強度顯然低于拉普拉斯機制和高斯機制.另外,由圖4和圖5可知,隨著隱私預(yù)算的增加,高斯機制的標(biāo)準(zhǔn)化期望誤差較拉普拉斯機制要大,為了更好地權(quán)衡隱私和效用,可以選擇拉普拉斯機制實現(xiàn)矩陣差分隱私.

Fig.4 The normalized expected estimation error for matrix differential privacy圖4 矩陣差分隱私下的標(biāo)準(zhǔn)化期望估計誤差

Fig.5 The normalized expected estimation error for Laplace mechanism and Gaussian mechanism圖5 拉普拉斯機制和高斯機制下的標(biāo)準(zhǔn)化期望估計誤差

因此,根據(jù)SNP連鎖不平衡下差分隱私的不可區(qū)分性,矩陣差分隱私實現(xiàn)了SNP基因型數(shù)據(jù)和SNP連鎖不平衡的隱私保護.

4.4 效用分析

盡管矩陣差分隱私可以實現(xiàn)SNP基因型數(shù)據(jù)的隱私保護,考慮到SNP基因型數(shù)據(jù)的分析,因此還需要分析SNP基因型數(shù)據(jù)的效用.在矩陣差分隱私中,對于原始的 SNP基因型數(shù)據(jù)(xij)n×m和擾動后的 SNP基因型數(shù)據(jù)(sij)n×m,根據(jù)作為效用度量方法實驗分析基因數(shù)據(jù)的效用.

如圖6所示,隨著隱私預(yù)算的增加,矩陣差分隱私保護模型下的基因數(shù)據(jù)效用遞增,并且增長到100%保持不變.這是因為,隨著隱私預(yù)算增大,拉普拉斯分布和高斯分布的方差變小,矩陣差分隱私產(chǎn)生模3余0的噪音就更多.當(dāng)隱私預(yù)算較小時,基于拉普拉斯機制的矩陣差分隱私可以實現(xiàn)更好的基因數(shù)據(jù)效用,以此保證較好的計算不可區(qū)分性,進而實現(xiàn)更好的差分隱私保護.例如,當(dāng)ε=7時,基于拉普拉斯機制的基因數(shù)據(jù)效用可以達到80%,而基于高斯機制的基因數(shù)據(jù)效用為40%,這與圖3中拉普拉斯機制和高斯機制產(chǎn)生噪音矩陣的四舍五入近似值模3余0的噪音數(shù)量的百分比值是一致的.而圖7中隨著隱私預(yù)算的增加,基因組數(shù)據(jù)的效用保持0不變.這是因為,拉普拉斯機制和高斯機制直接添加噪音到基因數(shù)據(jù),破壞了基因數(shù)據(jù)效用,導(dǎo)致基因數(shù)據(jù)效用災(zāi)難.由此可知,矩陣差分隱私比拉普拉斯機制和高斯機制更適合于基因數(shù)據(jù)的隱私保護.

Fig.6 The genome data utility for matrix differential privacy圖6 矩陣差分隱私下的基因數(shù)據(jù)效用

Fig.7 The genome data utility for Laplace mechanism and Gaussian mechanism圖7 拉普拉斯機制和高斯機制下的基因數(shù)據(jù)效用

因此,矩陣差分隱私相比于拉普拉斯機制和高斯機制更適合于基因數(shù)據(jù)的隱私保護,保證了基因數(shù)據(jù)和SNP連鎖不平衡的隱私保護與基因數(shù)據(jù)效用之間的權(quán)衡.在表1中,通過比較分析,總結(jié)矩陣差分隱私與拉普拉斯機制、高斯機制的相關(guān)性質(zhì).其中,最小效用R0表示矩陣差分隱私在最小隱私預(yù)算下所有模3余0的噪音數(shù)量的百分比值.

Table 1 The comparison among matrix differential privacy,Laplace mechansim and Gaussian mechanism表1 矩陣差分隱私與拉普拉斯機制、高斯機制的比較

5 結(jié) 論

為了保護SNP連鎖不平衡下基因關(guān)聯(lián)的敏感信息,本文提出了矩陣差分隱私保護模型.該模型滿足差分隱私,同時保證基因數(shù)據(jù)效用在[R0,1]區(qū)間,其中,R0是矩陣差分隱私在隱私預(yù)算最小時噪音矩陣中模3余0的噪音數(shù)量的百分比值,并且矩陣差分隱私是多項式時間計算有效的.

對于基因數(shù)據(jù),基因隱私保護模型在連鎖不平衡下保證隱私是可行的.通過結(jié)合矩陣加運算、SNP連鎖不平衡下差分隱私的定義和模余運算,提出了向量差分隱私和矩陣差分隱私,并且向量差分隱私是矩陣差分隱私的特例.根據(jù)矩陣差分隱私的性質(zhì),為了疾病標(biāo)記發(fā)現(xiàn),基因隱私保護模型可以用于 DNA數(shù)據(jù)集的差分隱私選擇[15]；在 GWAS中,矩陣差分隱私也可以對基于隱私編輯距離相似患者查詢提供隱私保護[12]；矩陣差分隱私阻止從GWAS統(tǒng)計值中識別特定的個體[16]；并且,矩陣差分隱私可以實現(xiàn)隱私保護罕見疾病變異分析[8]；矩陣差分隱私在基因組串搜索中是有效的隱私保護方法[11].更進一步說,在矩陣差分隱私下可以實現(xiàn)宏基因組分析[13].因此,矩陣差分隱私可以推廣到基因數(shù)據(jù)收集、搜索和序列配對等應(yīng)用的隱私保護中.

在矩陣差分隱私中,可以通過行劃分、列劃分或者其他快速矩陣計算方法[22]降低其計算復(fù)雜度,進而提高計算效率.另外,考慮高階的SNP連鎖不平衡,Samani等人[23]表明了對隱藏SNP的個體基因數(shù)據(jù)具有更強的推斷攻擊.Tramèr等人[17]考慮有界先驗知識的差分隱私,并應(yīng)用于GWAS.通過孟德爾定律、基因變異之間的統(tǒng)計關(guān)系和基因與表型之間的統(tǒng)計關(guān)系,在個體的基因組或表型被觀察到的情況下,Humbert等人[4]詳述了重構(gòu)攻擊推斷該個體的親戚的基因組.相比較考慮攻擊者的背景知識,本文僅考慮了SNP連鎖不平衡下基因隱私保護.在下一步的工作中,研究SNP連鎖不平衡下具有先驗知識的基因隱私保護模型,除了考慮成對SNP連鎖不平衡外,還需要考慮高階的SNP連鎖不平衡,并考慮攻擊者更多的先驗知識,包括可利用的基因數(shù)據(jù)、個體的血緣關(guān)系以及重組規(guī)則等.