實用安全兩方計算及其在基因組序列比對中的應(yīng)用*

趙 川,趙圣楠,賈忠田,張 波,張 斌

1.濟(jì)南大學(xué) 信息科學(xué)與工程學(xué)院,濟(jì)南 250022

2.山東省網(wǎng)絡(luò)環(huán)境智能計算技術(shù)重點實驗室,濟(jì)南 250022

3.山東大學(xué) 軟件學(xué)院,濟(jì)南 250101

4.山東青年政治學(xué)院 信息工程學(xué)院,濟(jì)南 250103

1 引言

作為密碼學(xué)領(lǐng)域的重要基礎(chǔ)理論,安全多方計算(secure multi-party computation)討論了分布式計算場景下數(shù)據(jù)擁有者各方以一種安全的方式進(jìn)行合作計算的問題.為了實現(xiàn)資源共享,不同組織或個人之間的合作計算日益頻繁,不同數(shù)據(jù)的擁有者通過合作計算,在不泄露自己保密數(shù)據(jù)的情況下整合資源,從而得到更有價值的信息.然而,由于計算不僅僅會發(fā)生在相互信任的各方之間,也有可能存在于部分信任的合作者之間,甚至存在于競爭者之間,因此在這種分布式計算場景中,必須考慮某些參與方企圖通過各種欺詐手段來獲得額外利益的情況.例如,潛在的惡意參與方可能會試圖獲取其他參與方的秘密輸入信息,或者讓其他參與方獲取的計算結(jié)果不正確,等等.安全多方計算所要達(dá)到的目標(biāo),正是在確保上述惡意參與方存在的情況下,參與分布式計算的各方依然能夠保證自己數(shù)據(jù)的秘密性并能獲得正確的計算結(jié)果.

自2003年人類基因組計劃宣告成功以來,基因組測序技術(shù)獲得了突飛猛進(jìn)的發(fā)展.如今,人們已經(jīng)可以用低廉的成本獲取非常詳盡的基因組數(shù)據(jù),并將其廣泛應(yīng)用于衛(wèi)生保健、生物醫(yī)學(xué)研究、司法鑒定以及直接面向消費者的基因檢測等各個領(lǐng)域.針對基因組數(shù)據(jù)的處理中,基因組序列比對最為基礎(chǔ)、應(yīng)用最為廣泛.例如,在醫(yī)療領(lǐng)域,需要對不同病人的基因組序列進(jìn)行比對,實現(xiàn)相似病人查詢,以便獲取充分的相似病人臨床資料,為患者制定最佳治療方案[1].

然而,與普通數(shù)據(jù)不同的是,人類基因組數(shù)據(jù)中蘊(yùn)涵了大量的個人隱私信息,包括個人特質(zhì)相關(guān)的信息、罹患特定疾病相關(guān)的信息和可用于身份鑒別的信息等.即便對數(shù)據(jù)進(jìn)行匿名化處理,仍然不能完全移除其中所包含的可鑒別信息,身份可能被重新識別[2].倘若基因組數(shù)據(jù)被不恰當(dāng)?shù)卮鎯?、使用和傳?將直接導(dǎo)致個人隱私信息的泄漏,對參與者造成嚴(yán)重的隱私困擾.基因組數(shù)據(jù)的這種敏感性與特殊性很大程度上阻礙了基因組數(shù)據(jù)的有效共享和充分利用,極大限制了基因組序列比對的開展.例如,兩個互不信任的參與方Alice 和Bob,希望完成二者基因組序列的比對,卻又不想將各自的私有數(shù)據(jù)暴露給對方.因此,亟需從技術(shù)層面提供一種機(jī)制,在保證雙方數(shù)據(jù)隱私性的前提下,以一種安全的方式完成基因組序列比對任務(wù).

安全兩方計算(secure two-party computation)為完成這種隱私保護(hù)的基因組序列比對提供了有效方法[3].安全兩方計算作為安全多方計算中一個比較特殊的情形,參與計算的實體為兩方.在安全兩方計算場景中,兩個互不信任的參與方想要共同計算某個功能函數(shù)(functionality),該功能函數(shù)的輸入為各參與方本地的隱私數(shù)據(jù).參與方通過運行一個交互協(xié)議,在不借助可信第三方的情況下得到正確的計算結(jié)果.協(xié)議結(jié)束后,各參與方除各自的計算結(jié)果及從輸入輸出推算出的信息外,得不到其他任何信息.這正適用于隱私保護(hù)的基因組序列比對場景——互不信任的Alice 和Bob 通過運行安全兩方計算協(xié)議,在不泄漏自己基因組序列x和y的前提下,安全地計算出關(guān)于兩個序列的比對函數(shù)f(見圖1).

圖1 安全兩方基因組序列比對Figure 1 Secure two-party genomic sequence comparison

2 實用安全兩方計算研究進(jìn)展

自1982年被提出以來[4],安全多方計算就一直受到研究學(xué)者的廣泛關(guān)注.針對安全多方計算的研究涵蓋了從理論基礎(chǔ)到實際應(yīng)用的各個層面,包括安全模型、復(fù)雜性分類、通用協(xié)議構(gòu)造、基礎(chǔ)工具以及特定應(yīng)用協(xié)議等.早先的關(guān)注點主要在于安全模型的建立、可行性探究以及復(fù)雜性分類等理論基礎(chǔ)方面.近些年,伴隨著計算能力和通信能力的大幅提升,在安全多方計算基礎(chǔ)理論研究持續(xù)多年不衰的基礎(chǔ)上,安全多方計算的實用性又得到更加廣泛的關(guān)注.

實用安全多方計算主要關(guān)注的是通用協(xié)議的效率問題,研究提高通用協(xié)議效率的方法和技術(shù),從協(xié)議的計算代價、通信代價及交互輪數(shù)等方面綜合考慮,對基本運算及其組合的計算復(fù)雜度、通信復(fù)雜度和輪復(fù)雜度進(jìn)行討論,尋找復(fù)雜度的階并構(gòu)造復(fù)雜度盡量小的協(xié)議.構(gòu)造通用協(xié)議的方法一般是將所要計算的功能函數(shù)表示成算術(shù)電路或布爾電路,然后再利用秘密共享、同態(tài)加密、不經(jīng)意傳輸和混亂電路等密碼學(xué)工具對每個電路門進(jìn)行處理,并對電路逐層進(jìn)行計算,最終以一種安全的方式完成計算任務(wù).

安全兩方計算是姚期智院士1982年在計算機(jī)科學(xué)頂級國際會議FOCS 上提出的[4].相比于安全多方計算,安全兩方計算近年來在實用性領(lǐng)域的研究更加吸引研究學(xué)者的關(guān)注.一是因為安全兩方計算具有更高效的構(gòu)造技術(shù),如混亂電路;二是安全兩方計算具有更廣泛的應(yīng)用場景,如可搜索加密、私有信息檢索、茫然RAM 等;三是安全兩方計算具有更重要的理論意義,許多非常重要的密碼學(xué)原語都可以抽象為安全兩方計算,如零知識證明、不經(jīng)意傳輸、擲幣協(xié)議、承諾方案、密鑰協(xié)商等,研究安全兩方計算為各類密碼學(xué)原語的發(fā)展提供理論基礎(chǔ).

根據(jù)底層基礎(chǔ)工具的不同,構(gòu)造實用安全兩方計算通用協(xié)議的方法主要可以分為以下三類:基于混亂電路和不經(jīng)意傳輸、基于同態(tài)加密以及基于秘密共享.其中,以混亂電路和不經(jīng)意傳輸為底層工具的構(gòu)造方法,被研究學(xué)者視為構(gòu)造通用安全兩方計算協(xié)議的最高效的方法,引起了廣泛深入的研究.此外,為了構(gòu)造出高效的抵抗惡意敵手攻擊的安全協(xié)議,Lindell 等人提出對混亂電路采用cut-and-choose 技術(shù)來解決參與方不正確構(gòu)造電路的問題[5].該方法要求混亂電路構(gòu)造方P1不只構(gòu)造一個混亂電路,而是構(gòu)造s個(s為統(tǒng)計學(xué)安全參數(shù)).P2選擇其中一部分要求P1打開以進(jìn)行檢測.若都被驗證通過,則P2像半誠實模型下的協(xié)議中一樣對剩余電路進(jìn)行計算,獲得輸出結(jié)果.否則,P2中止協(xié)議.

在防止惡意P1構(gòu)造錯誤電路的同時,cut-and-choose 的引入也產(chǎn)生了新的問題,如需要確保參與方在各電路中的輸入相一致,以及處理由不經(jīng)意傳輸協(xié)議帶來的選擇性失敗攻擊問題等.另外,cut-and-choose技術(shù)的使用并不能保證敵手一定無法作弊成功,利用該方法構(gòu)造的方案雖然較為高效,但是有一定的錯誤概率.為了進(jìn)一步降低錯誤概率,提高協(xié)議效率和安全性,研究學(xué)者給出了一系列更為巧妙的構(gòu)造方案.

針對實用安全兩方計算領(lǐng)域的研究進(jìn)展,蔣瀚等人[6,7]給出了較為完善的總結(jié)與展望.近兩年,研究學(xué)者除了繼續(xù)研究混亂電路優(yōu)化[8–12]、cut-and-choose 技術(shù)[13–16]以及不經(jīng)意傳輸擴(kuò)展技術(shù)[17–19]之外,也開始關(guān)注批處理環(huán)境下通用協(xié)議的優(yōu)化[20–25]、大規(guī)?？蓴U(kuò)展的安全計算協(xié)議[26–28]、預(yù)處理模型下的高效協(xié)議構(gòu)造[29–31],以及在惡意敵手模型下構(gòu)造解決某些具體問題的安全計算協(xié)議,例如,安全兩方簽名協(xié)議[32]、安全兩方加密協(xié)議[33,34]、加密交換協(xié)議[35,36]等.這些研究成果無不表明:安全多方計算已經(jīng)在某些特定領(lǐng)域逐步邁向?qū)嵱没?并將在不久的將來真正應(yīng)用于各個領(lǐng)域中解決實際的問題.

3 基于安全兩方計算的基因組序列比對研究進(jìn)展

近年來,基因組數(shù)據(jù)的隱私保護(hù)逐漸引起國內(nèi)外研究學(xué)者的廣泛關(guān)注[37–39].信息安全頂級國際會議ACM CCS 在2016年將題為“Privacy and Security in the Genomic Era” 的報告[1]作為會議的主要教程之一;加州大學(xué)圣地亞哥分校、印第安納大學(xué)等聯(lián)合主辦了2015–2018 四屆iDASH Privacy & Security Challenge[40],通過競賽的方式,在國際頂級密碼學(xué)與信息安全團(tuán)隊提供的基因組數(shù)據(jù)安全計算方案中選拔出性能最好的成果.這些科研課題與學(xué)術(shù)活動表明:隱私保護(hù)的基因組數(shù)據(jù)處理已經(jīng)成為信息安全領(lǐng)域的熱門研究內(nèi)容.

在基因組數(shù)據(jù)處理中,最為基礎(chǔ)、應(yīng)用最為廣泛的操作是基因組序列比對.早在1987年,Gribskov等人[41]就提出了鑒別兩條序列之間相似性的序列比對方法.在基因組序列比對隱私保護(hù)方面,主要采用的技術(shù)是安全兩方計算.安全實現(xiàn)兩個基因組序列的比對是安全兩方計算的一種特定場景.目前,安全兩方計算協(xié)議主流的通用構(gòu)造方法分為同態(tài)加密和混亂電路兩種.所謂通用構(gòu)造方法,是指基于此類方法所構(gòu)造的協(xié)議可以安全計算任意可計算的函數(shù).由于通用構(gòu)造相比于專用協(xié)議本身具有諸多優(yōu)勢,設(shè)計更直觀、安全性更強(qiáng)且多數(shù)情況下效率更高,因此,學(xué)界對于安全兩方基因組序列比對的研究也主要圍繞這兩種通用構(gòu)造方法展開.

3.1 基于同態(tài)加密的構(gòu)造

同態(tài)加密是一種特殊的加密方案,它允許人們對密文進(jìn)行特定的運算,得到一個密文結(jié)果,將該結(jié)果解密所得到的值,與對明文進(jìn)行同樣的運算所得到的值相同.換句話說,這項技術(shù)可以使人們直接在加密的數(shù)據(jù)上進(jìn)行檢索、比較、運算等操作,整個處理過程中無需對數(shù)據(jù)進(jìn)行解密即可得到正確結(jié)果的密文,從而保證了數(shù)據(jù)的安全性和隱私性.根據(jù)加密方案所支持函數(shù)的限制條件的不同,可以將同態(tài)加密分為somewhat 同態(tài)和全同態(tài).Somewhat 同態(tài)表示加密算法僅支持一些特定的函數(shù)(比如有限的加法和乘法運算),功能不強(qiáng),但容易實現(xiàn),且計算開銷較小,已經(jīng)可以實際使用;全同態(tài)則可以支持任意給定的函數(shù)[42],功能很強(qiáng),但是計算開銷極大,目前離實際應(yīng)用還有一定距離.

基于同態(tài)加密可以構(gòu)造安全兩方計算的通用協(xié)議.Somewhat 同態(tài)加密構(gòu)造的方案中[29,43–45],參與方本地的計算代價較低,但為了完成任意的函數(shù)計算,參與方之間需要進(jìn)行大量的交互,因此協(xié)議的輪復(fù)雜度和通信復(fù)雜度較高;全同態(tài)加密可以與云計算結(jié)合,構(gòu)造云輔助的通用安全計算協(xié)議[46–48],將參與方本地的計算和通信代價降至最優(yōu).但是,由于目前的全同態(tài)加密方案較為低效,所以即便引入云服務(wù)器來輔助進(jìn)行安全計算任務(wù),協(xié)議的效率仍然不高.

在安全兩方基因組序列比對這一具體問題方面,主要方法是將同態(tài)加密與編輯距離相結(jié)合來構(gòu)造安全計算協(xié)議[3].編輯距離指的是將一個字符串編輯為另一個字符串所需要的最小操作次數(shù)[49],它在生物信息學(xué)、搜索引擎、抄襲檢測、語音辨識等領(lǐng)域具有非常廣泛的應(yīng)用,可以有效、定量地判定兩個字符串的相似度有多高.Atallah 等人[3]基于加法同態(tài)加密,利用動態(tài)規(guī)劃來安全計算兩個基因組序列的編輯距離,構(gòu)造了半誠實敵手模型下安全的協(xié)議.但由于動態(tài)規(guī)劃算法的計算復(fù)雜度較高,基于同態(tài)加密的協(xié)議構(gòu)造并不高效.利用現(xiàn)有的同態(tài)加密算法,計算一個8×8 的動態(tài)規(guī)劃需要16.4 s.提高協(xié)議運行效率的有效方法之一是利用安全外包計算來降低參與方本地的計算代價[50,51].許多國內(nèi)學(xué)者對安全外包計算進(jìn)行了較為深入的研究.Chen 等人[52,53]、Wang 等人[54]和Ye 等人[55]構(gòu)造的模冪外包計算方案、Nie等人[56]構(gòu)造的線性規(guī)劃外包計算方案、胡杏等人[57]構(gòu)造的矩陣外包計算方案、孫茂華等人[58]構(gòu)造的集合并集外包計算方案、李順東等人[59]構(gòu)造的云輔助集合隱私計算方案等,均有效推動了安全外包計算研究領(lǐng)域的發(fā)展.但是,這些方案并不適用于序列比對算法,很難直接應(yīng)用于安全兩方基因組序列比對中.Ma 等人[60]對序列比對算法的安全外包進(jìn)行了研究,引入多個服務(wù)器分擔(dān)參與方的計算任務(wù),構(gòu)造了可以抵抗惡意服務(wù)器攻擊的安全外包協(xié)議.

3.2 基于混亂電路的構(gòu)造

1986年,姚期智院士提出混亂電路的概念及其構(gòu)造方法,并將混亂電路與不經(jīng)意傳輸相結(jié)合,構(gòu)造了第一個安全兩方計算的通用協(xié)議——Yao 協(xié)議[61].混亂電路是對布爾電路的一種加密形式,它允許參與方在不知道電路真實輸入值的情況下以一種茫然的方式逐層計算出正確的電路輸出結(jié)果,計算過程中除電路輸出外不泄漏任何額外信息.混亂電路可以在保證輸入隱私性的前提下高效、安全地完成任意可計算的計算任務(wù).

Yao 協(xié)議的出現(xiàn)引起了國際密碼學(xué)領(lǐng)域的廣泛關(guān)注.近年來,學(xué)界主要從以下三個方面對基于混亂電路的安全兩方計算進(jìn)行研究.一是對混亂電路構(gòu)造方法進(jìn)行優(yōu)化,有效提高混亂電路的計算效率[62–66];二是提出使用cut-and-choose 技術(shù)[5,67],將僅能抵抗半誠實敵手的Yao 協(xié)議高效編譯為惡意敵手模型下安全的構(gòu)造,這在密碼學(xué)界掀起了一股研究熱潮[20,22,68–75];三是將混亂電路的構(gòu)造任務(wù)或計算任務(wù)外包到云服務(wù)器,利用云計算技術(shù)來輔助完成安全兩方計算[76–82],但由于該框架下的安全模型和構(gòu)造技術(shù)等方面尚不成熟,因此實際應(yīng)用較少.

在安全兩方基因組序列比對方面,Jha 等人[83]基于混亂電路技術(shù),在半誠實敵手模型下給出了三個安全的序列比對協(xié)議:協(xié)議一直接基于Yao 混亂電路進(jìn)行構(gòu)造;協(xié)議二將協(xié)議一中的電路進(jìn)行分割,并將各電路結(jié)果在參與方之間進(jìn)行共享;協(xié)議三對前兩個協(xié)議進(jìn)行融合,在協(xié)議效率和可擴(kuò)展性等方面進(jìn)行了優(yōu)化.該方案的主要缺點是其在應(yīng)對大規(guī)模計算任務(wù)時表現(xiàn)不足.Huang 等人[65]對Jha 等人的方案進(jìn)行進(jìn)一步的優(yōu)化,給出的協(xié)議降低了參與方的計算代價,但參與方之間的交互代價仍然較高.Blanton 等人對基因組序列比對任務(wù)進(jìn)行擴(kuò)展和外包[84],并分別討論了參與方作為半誠實敵手、服務(wù)器作為惡意敵手以及相反情況下協(xié)議的構(gòu)造方法和運行效率[85].Wang 等人[86]和Asharov 等人[87]將編輯距離計算問題正式定義為相似病人查詢問題,并引入公共參考序列來對基因組數(shù)據(jù)集進(jìn)行預(yù)處理,通過計算近似編輯距離,大大提高了在大數(shù)據(jù)集上進(jìn)行序列比對的效率.然而,這種方式也帶來了一些問題.首先,公共參考序列的引入會導(dǎo)致泄漏一些有關(guān)數(shù)據(jù)分布的信息;第二,根據(jù)參考序列進(jìn)行計算在一定程度上降低了準(zhǔn)確度.Al Aziz 等人[88]基于保密集合求交和帶狀對齊算法給出了更高效和準(zhǔn)確度更高的方案.最近,Zhu等人[89]研究了更加一般化的編輯距離算法,包括加權(quán)編輯距離、最長公共子序列及最重公共子序列等,并且在不丟失精確度的情況下,利用一種特殊的混亂電路構(gòu)造方法極大地提高了序列比對的效率.

4 發(fā)展動態(tài)分析

我們對安全兩方計算及安全兩方基因組序列比對的研究現(xiàn)狀進(jìn)行了歸納和分析,在圖2 中展示主要研究成果的發(fā)展脈絡(luò),并標(biāo)注了可能的研究方向.

在安全兩方基因組序列比對研究領(lǐng)域,一個主要的研究趨勢是將序列比對任務(wù)安全外包到云服務(wù)器.這是因為基因組序列比對算法的計算復(fù)雜度很高(O(mn),m和n分別為兩個序列的長度),僅依靠兩個參與方獨立完成安全計算任務(wù)所需花費的代價很大,而借助云的計算資源輔助兩個參與方進(jìn)行安全計算則可以較大程度提高協(xié)議的運行效率.但是,從目前研究現(xiàn)狀來看,該領(lǐng)域的研究中仍然存在以下兩個比較突出的問題:

(1)現(xiàn)有云輔助安全兩方計算方案的安全模型和構(gòu)造方法尚不成熟,導(dǎo)致無法充分發(fā)揮云計算模型的優(yōu)勢,協(xié)議效率有待進(jìn)一步提升.

云輔助安全兩方計算的安全模型和構(gòu)造方法中仍有許多問題沒有解決,遇到一些理論和技術(shù)上的瓶頸:安全模型過弱會導(dǎo)致協(xié)議不足以保證實際中的安全性,過強(qiáng)則會造成參與方本地的計算代價太高,失去云輔助計算的優(yōu)勢;構(gòu)造方法不完善,且不能跟安全模型很好地結(jié)合,以構(gòu)造高效的云輔助安全計算協(xié)議.因此,一個有效的研究方向是:研究新型云輔助的安全兩方基因組序列比對,探究新的安全模型和構(gòu)造方法,進(jìn)一步提高安全兩方序列比對的效率.

圖2 研究發(fā)展脈絡(luò)Figure 2 Roadmap to research

(2)現(xiàn)有方案主要關(guān)注半誠實敵手模型,協(xié)議安全性有待進(jìn)一步增強(qiáng).

現(xiàn)有方案大多只考慮半誠實敵手模型,雖然這樣構(gòu)造的協(xié)議運行效率較高,但該模型要求參與方嚴(yán)格按照協(xié)議規(guī)定執(zhí)行,這種假設(shè)在現(xiàn)實中是過強(qiáng)的.尤其是面對基因組序列這種蘊(yùn)含大量隱私信息的數(shù)據(jù),考慮能力更強(qiáng)的敵手——惡意敵手成為迫切需求和必然趨勢.在惡意敵手模型中,潛在的惡意方可能采取任意的策略和行為以獲取額外利益.構(gòu)造惡意敵手模型下安全的計算協(xié)議非常復(fù)雜且低效,再加上序列比對算法的計算復(fù)雜度很高,這就為構(gòu)造惡意敵手模型下高效的序列比對協(xié)議帶來了更大的挑戰(zhàn).另外,全模擬安全性是惡意敵手模型下最嚴(yán)格的安全等級,研究構(gòu)造惡意敵手模型下滿足全模擬安全性的安全兩方序列比對協(xié)議是非常必要的,但也是非常困難的.因此,一個可行的研究方向是:研究強(qiáng)安全模型下可證安全的安全兩方基因組序列比對,探究新的高效構(gòu)造機(jī)制,進(jìn)一步增強(qiáng)安全兩方序列比對的安全性.

5 結(jié)束語

本文總結(jié)了實用安全兩方計算的研究進(jìn)展,并較為詳細(xì)地介紹并分析了安全兩方計算在基因組序列比對中的應(yīng)用.由于基因組數(shù)據(jù)本身的特殊性以及序列比對算法的復(fù)雜性,在利用安全兩方計算實現(xiàn)基因組序列比對隱私保護(hù)方面,目前已有的研究工作面臨協(xié)議效率低、安全模型弱等問題.后續(xù)的研究可以從提高協(xié)議效率和增強(qiáng)協(xié)議安全性兩個角度出發(fā),利用云輔助計算模型提高協(xié)議效率,考慮惡意敵手攻擊強(qiáng)化安全模型,利用新的安全性定義和高效構(gòu)造機(jī)制,探索構(gòu)造高效、安全的兩方基因組序列比對的方法和技術(shù).