韓宗達(dá) 鄧宇濤 程祥
(北京郵電大學(xué)計(jì)算機(jī)學(xué)院(國家示范性軟件學(xué)院)網(wǎng)絡(luò)與交換技術(shù)國家重點(diǎn)實(shí)驗(yàn)室,北京 100876)
在信息技術(shù)高速發(fā)展的數(shù)字經(jīng)濟(jì)時代,數(shù)據(jù)的有效利用對推動經(jīng)濟(jì)發(fā)展、改善社會生活有著重大意義。中共中央、國務(wù)院《關(guān)于構(gòu)建更加完善的要素市場化配置體制機(jī)制的意見》明確指出數(shù)據(jù)將與土地、勞動力、資本、技術(shù)等傳統(tǒng)要素并列,成為一種新的生產(chǎn)要素。然而,數(shù)據(jù)中隱私信息的存在阻礙了數(shù)據(jù)價值的充分釋放。如何在滿足數(shù)據(jù)隱私保護(hù)約束的同時,有效促進(jìn)數(shù)據(jù)流通,成為當(dāng)今時代的關(guān)鍵問題。
隱私計(jì)算是解決數(shù)據(jù)流通與隱私保護(hù)之間矛盾的主要手段,其允許多方在隱藏各自敏感信息的前提下執(zhí)行協(xié)同計(jì)算,實(shí)現(xiàn)“數(shù)據(jù)可用不可見”。不經(jīng)意關(guān)鍵詞檢索(Oblivious Keyword Search,OKS)是在隱私保護(hù)下實(shí)現(xiàn)信息檢索的重要手段,也是隱私計(jì)算的基礎(chǔ)任務(wù)之一。該任務(wù)是隱私保護(hù)協(xié)同計(jì)算的關(guān)鍵步驟,為數(shù)據(jù)處理全流程的隱私保護(hù)提供了重要保障。本文對不經(jīng)意關(guān)鍵詞檢索的任務(wù)定義及其相關(guān)任務(wù)進(jìn)行了介紹;然后,結(jié)合對現(xiàn)有研究的調(diào)研,總結(jié)出三種不經(jīng)意關(guān)鍵詞檢索的典型技術(shù)路線,并分析了各個技術(shù)路線的優(yōu)劣勢;最后,對當(dāng)前不經(jīng)意關(guān)鍵詞檢索所面臨的主要技術(shù)挑戰(zhàn)和未來發(fā)展趨勢進(jìn)行了分析與探討。
關(guān)鍵詞檢索是信息檢索中的一項(xiàng)基本任務(wù)。在傳統(tǒng)的關(guān)鍵詞檢索任務(wù)中,數(shù)據(jù)庫端持有一組鍵值對,用戶端通過關(guān)鍵詞對數(shù)據(jù)庫發(fā)起檢索請求,數(shù)據(jù)庫端在接收到查詢請求后,通過查詢請求中的關(guān)鍵詞對持有數(shù)據(jù)進(jìn)行檢索,并將檢索結(jié)果反饋給用戶端。
然而,傳統(tǒng)的關(guān)鍵詞檢索需要向數(shù)據(jù)庫暴露查詢目標(biāo)的關(guān)鍵詞。在實(shí)際應(yīng)用中,查詢目標(biāo)的暴露可能導(dǎo)致隱私信息的泄露,從而使用戶利益受到損失。對此,最早由Ogata與Kurosawa[1]在2002年正式提出了不經(jīng)意關(guān)鍵詞檢索的定義與協(xié)議。該任務(wù)的場景設(shè)置包含一個數(shù)據(jù)庫端和用戶端,數(shù)據(jù)庫端持有一個存儲鍵值對的數(shù)據(jù)庫D={(x1,v1),(x2,v2),…,(xn,vn)},用戶端通過關(guān)鍵詞xi對數(shù)據(jù)庫進(jìn)行查詢,得到對應(yīng)的值vi。不經(jīng)意關(guān)鍵詞檢索要求同時保護(hù)數(shù)據(jù)庫端與用戶端的隱私,即數(shù)據(jù)庫端不能得到用戶端的查詢目標(biāo),而用戶端不能得到除了查詢目標(biāo)對應(yīng)值以外的其他信息。
隱私信息檢索(Private Information Retrieval,PIR)是一種密碼學(xué)原語,允許用戶端對數(shù)據(jù)庫進(jìn)行查詢而不會向數(shù)據(jù)庫暴露任何有關(guān)查詢目標(biāo)的信息。具體來說,數(shù)據(jù)庫端持有一個數(shù)據(jù)庫D={D1,D2,…,Dn},數(shù)據(jù)庫中有n個元素,接收者持有一個查詢索引i,協(xié)議執(zhí)行完成后,接收者可以得到查詢結(jié)果Di。在這個過程中,協(xié)議保證接收者不會得到查詢索引i的任何相關(guān)信息。Chor等[13]首次提出PIR協(xié)議,并隨后出現(xiàn)了大量的相關(guān)研究工作[14-26]。現(xiàn)有研究大多基于同態(tài)加密[14-21],核心思想是構(gòu)造密文二值向量w∈{0,1}n,若查詢索引存在,則向量中對應(yīng)位置的值為1,反之為0。該技術(shù)路線的通信復(fù)雜度可以達(dá)到對數(shù)復(fù)雜度,但是其計(jì)算代價較高[16,17,21]。對此,有一部分研究通過編碼理論對PIR協(xié)議的計(jì)算開銷與通信開銷進(jìn)行優(yōu)化[22-26],避免使用大量的密碼學(xué)原語。
不經(jīng)意傳輸(Oblivious Transfer,OT)是安全多方計(jì)算的基礎(chǔ)原語,廣泛應(yīng)用于安全多方計(jì)算中,如生成乘法三元組[47]、構(gòu)造混淆電路[48]等。OT允許一方從另一方的n個數(shù)據(jù)中,獲取其中的k個數(shù)據(jù)。在該過程中,持有數(shù)據(jù)的一方不應(yīng)知道另一方的查詢目標(biāo),而拿到查詢結(jié)果的一方不應(yīng)得到除了查詢結(jié)果以外的信息。傳統(tǒng)的OT協(xié)議基于公鑰密碼學(xué)構(gòu)造,如RSA[45]。為了降低OT的計(jì)算開銷,一方面研究者們相繼提出OT擴(kuò)展(Oblivious Transfer Extension,OTE)[40-42]以及SimplestOT[43,44],通過降低公鑰密碼學(xué)原語的使用次數(shù),大大提高協(xié)議的計(jì)算效率;另一方面研究者們提出Random OT[46],將大量計(jì)算與通信轉(zhuǎn)移到線下進(jìn)行,提高線上的計(jì)算與通信效率。
隱私集合求交(Private Set Intersection,PSI)的場景設(shè)置為:持有各自數(shù)據(jù)集合X、Y的兩方期望計(jì)算得到雙方數(shù)據(jù)的交集X∩Y,同時不暴露交集以外的其他信息。隱私集合求交具有很長的發(fā)展歷史,最早被提出用于解決兩個公司間尋找共同顧客的問題,目前廣泛應(yīng)用于密碼泄露的發(fā)現(xiàn)、隱私信息的數(shù)據(jù)對齊等場景。隱私集合交的現(xiàn)有研究按照技術(shù)路線可以劃分為基于公鑰密碼學(xué)的PSI[27-30]、基于電路的PSI[31,32]、基于OTE的PSI[12,33-39]以及基于全同態(tài)加密的PSI[4]?;诠€密碼學(xué)的PSI通過Diffie-Hellmann、RSA等公鑰密碼原語構(gòu)造OPRF協(xié)議,并在密文下完成集合求交?;贠TE的PSI通過OTE構(gòu)造OPRF協(xié)議,其計(jì)算開銷遠(yuǎn)遠(yuǎn)小于基于公鑰密碼學(xué)的PSI。兩者的共同缺陷在于協(xié)議執(zhí)行的通信復(fù)雜度與集合較大一方的集合大小呈線性復(fù)雜度關(guān)系,不適合于非平衡場景,即雙方的集合大小不相等的場景。針對該問題,基于全同態(tài)的PSI將協(xié)議的通信復(fù)雜度降低為與集合較大一方的集合大小呈對數(shù)復(fù)雜度關(guān)系,顯著降低了通信開銷。但是,基于全同態(tài)的PSI在執(zhí)行時會產(chǎn)生較大的計(jì)算開銷,使其難以應(yīng)用于大規(guī)模數(shù)據(jù)場景。
2.2.1 不經(jīng)意關(guān)鍵詞檢索、隱私信息檢索及不經(jīng)意傳輸
不經(jīng)意關(guān)鍵詞檢索、隱私信息檢索及不經(jīng)意傳輸在任務(wù)場景上非常類似,均為用戶端向持有數(shù)據(jù)的數(shù)據(jù)庫端發(fā)起查詢請求,以獲取指定數(shù)據(jù)。三個任務(wù)的區(qū)別在于查詢媒介以及隱私保護(hù)要求(見表1)。對于隱私保護(hù)要求,PIR僅保護(hù)用戶端的隱私,即數(shù)據(jù)庫端在協(xié)議執(zhí)行過程中不會得到查詢目標(biāo)的相關(guān)信息,OT與OKS會兼顧數(shù)據(jù)庫端的隱私,即用戶端僅能得到查詢目標(biāo)對應(yīng)的值,而無法得到其他位置的值。對于查詢媒介,PIR與OT將數(shù)組下標(biāo)作為查詢請求,而OKS則使用關(guān)鍵詞。因此,PIR和OT存在一個前置條件,用戶端在查詢前已得知查詢目標(biāo)在數(shù)據(jù)庫中的精確位置。
表1 不經(jīng)意關(guān)鍵詞檢索、隱私信息檢索以及不經(jīng)意傳輸?shù)年P(guān)系
2.2.2 不經(jīng)意關(guān)鍵詞檢索與隱私集合求交
不經(jīng)意關(guān)鍵詞檢索技術(shù)與隱私集合求交存在諸多共同之處,不經(jīng)意關(guān)鍵詞檢索可以視作一種特殊的攜帶標(biāo)簽的非平衡隱私集合求交。攜帶標(biāo)簽指為隱私集合求交中的數(shù)據(jù)集合元素添加相應(yīng)的標(biāo)簽,元素與標(biāo)簽的組合即可視作不經(jīng)意關(guān)鍵詞檢索中的鍵值對。在執(zhí)行不經(jīng)意關(guān)鍵詞檢索協(xié)議的過程中,隱私集合求交會隱式進(jìn)行。因此,部分隱私集合求交協(xié)議[4-6]也成為了現(xiàn)有不經(jīng)意關(guān)鍵詞檢索協(xié)議的基礎(chǔ)。
不經(jīng)意多項(xiàng)式評估(Oblivious Polynomial Evaluation,OPE)是一種兩方安全計(jì)算協(xié)議,最早由Naor與Pinkas[2]于1999年提出。OPE的場景設(shè)置中存在一個發(fā)送者以及接收者,發(fā)送者持有多項(xiàng)式P,接收者持有待評估的輸入x,協(xié)議執(zhí)行完成后,接受者獲得評估結(jié)果P(x)。OPE的安全要求是發(fā)送者不能得到輸入x的相關(guān)信息,接收者除了得到最終結(jié)果P(x),不能得到其他更多關(guān)于多項(xiàng)式P的信息。
不經(jīng)意偽隨機(jī)函數(shù)(Oblivious Pseudo Random Function,OPRF)是一種以偽隨機(jī)函數(shù)加密為基礎(chǔ)的兩方安全計(jì)算協(xié)議。OPRF的場景設(shè)置中存在一個發(fā)送者以及接收者,發(fā)送者持有偽隨機(jī)函數(shù)f的種子k,接收者持有輸入x。經(jīng)過OPRF協(xié)議之后,接收者得到得到偽隨機(jī)函數(shù)的計(jì)算結(jié)果f(x,k)。在協(xié)議執(zhí)行過程中,要求發(fā)送者不獲得有關(guān)x的任何信息,接收者也不會獲得有關(guān)k的任何信息。
基于OPRF的不經(jīng)意關(guān)鍵詞檢索協(xié)議的核心思想是雙方通過OPRF對關(guān)鍵詞完成加密,并保證相同的關(guān)鍵詞可以得到相同的密文,然后發(fā)送者利用密文關(guān)鍵詞構(gòu)造新的密文鍵值對,并將其發(fā)送給接收者,接收者通過密文鍵值進(jìn)行匹配與解密,從而完成信息檢索。Freedman[3]在2005年提出了一種基于寬松OPRF的不經(jīng)意關(guān)鍵詞檢索協(xié)議。由于嚴(yán)格的OPRF要求接收者不能獲取有關(guān)發(fā)送者密鑰的任何信息,F(xiàn)reedman認(rèn)為達(dá)到該安全強(qiáng)度需要付出過高的代價,從而放松了安全要求,使接收者允許獲得發(fā)送者的部分子密鑰。該協(xié)議的OPRF執(zhí)行過程如下:發(fā)送者擁有存放鍵值對的數(shù)據(jù)庫x,首先發(fā)送者生成一個由兩組隨機(jī)數(shù)作為密鑰種子的偽隨機(jī)函數(shù),然后其將關(guān)鍵詞xi∈X切分為兩個份額xi=(x1,x2),并將切分后的兩個份額作為索引分別在兩個密鑰集合r1,r2中選取對應(yīng)的密鑰r1,x1,r2,x2,最后利用選擇得到的密鑰對關(guān)鍵詞x進(jìn)行加密,得到fr1,x1(xi),fr2,x2(xi),再將兩份關(guān)鍵字密文的異或結(jié)果作為關(guān)鍵詞xi的加密結(jié)果fr(xi);發(fā)送者使用關(guān)鍵詞的密文對鍵值對中的值進(jìn)行加密,得到新的密文鍵值對X′;接收者在發(fā)起查詢請求時對查詢關(guān)鍵詞w進(jìn)行切分(w1,w2),通過不經(jīng)意傳輸[7]獲取發(fā)送者密鑰集合中特定的兩個子密鑰r1,w1,r2,w2,并使用與發(fā)送者一致的加密方法對查詢請求w進(jìn)行加密,得到fr(w)。在雙方完成OPRF后,接收者得到的關(guān)鍵詞密文僅能解密該關(guān)鍵詞所對應(yīng)的密文鍵值對,在實(shí)現(xiàn)信息檢索的同時不會對接收者暴露除查詢目標(biāo)以外更多的信息?;贠PRF的不經(jīng)意關(guān)鍵詞檢索協(xié)議的整體執(zhí)行流程如圖2所示。
Key-Value Store是一類可以存儲鍵值對的數(shù)據(jù)結(jié)構(gòu),包括布谷鳥哈希表[10]、混淆布隆過濾器[11]等,本質(zhì)是一個一維數(shù)組?;贙ey-Value Store的不經(jīng)意關(guān)鍵詞檢索的核心思想是將所有鍵值對插入到Key-Value Store中,完成關(guān)鍵詞到數(shù)組下標(biāo)的映射,從而將不經(jīng)意關(guān)鍵詞檢索問題轉(zhuǎn)化為隱私保護(hù)的信息檢索問題。
一般而言,會針對關(guān)鍵詞和值構(gòu)造兩個Key-Value Store結(jié)構(gòu),其中一個結(jié)構(gòu)K用于驗(yàn)證關(guān)鍵詞在數(shù)組中的具體位置,這是由于關(guān)鍵詞w會被映射為k個下標(biāo)(i1,…,ik),而接收者在協(xié)議執(zhí)行前無法得知關(guān)鍵詞在數(shù)組中的具體位置;另一個結(jié)構(gòu)V用于存儲關(guān)鍵詞對應(yīng)的值,以用于檢索操作。在執(zhí)行PIR的過程中,需要注意三個關(guān)鍵點(diǎn):接收者必須使用SPIR技術(shù)。這是由于PIR無法保證發(fā)送者的隱私安全,可能造成非查詢關(guān)鍵詞的相關(guān)信息的泄露;接收者首先通過k個下標(biāo)(i1,…,ik)執(zhí)行k次SPIR,以得到所有位置存儲的關(guān)鍵詞K[i1],…,K[ik],但是其暴露了非查詢關(guān)鍵詞的位置,使接收者獲得了額外信息。因此,為了避免上述信息的泄露,需要引入OPRF技術(shù),雙方同時對持有的關(guān)鍵詞進(jìn)行加密。接收者可以通過比較密文確定查詢關(guān)鍵詞在數(shù)組中的位置j,但是其無法通過密文反推出其余關(guān)鍵詞的位置。最后,接收者通過SPIR查詢數(shù)組V中第j個位置的值,獲得查詢結(jié)果V[j]。協(xié)議整體執(zhí)行流程如圖3所示。
基于OPE的不經(jīng)意關(guān)鍵詞檢索協(xié)議在通信復(fù)雜度上已達(dá)到O(logn),適用于通信資源較貧乏的場景。但是,其代價是計(jì)算開銷的增長。雖然,Chen等[5-6]利用SIMD、分箱等手段降低計(jì)算開銷,但總體上仍較高。因此,當(dāng)面臨大規(guī)模數(shù)據(jù)時,計(jì)算開銷的過大會限制該技術(shù)路線的實(shí)際應(yīng)用。
基于OPRF的不經(jīng)意關(guān)鍵詞檢索協(xié)議雖然在通信復(fù)雜度上為O(n),但隨著OPRF技術(shù)的發(fā)展,其計(jì)算開銷逐步降低。Chase等[12]提出了一種輕量級的OPRF協(xié)議,其啟發(fā)于OT擴(kuò)展,使用少量的非對稱加密生成大量的對稱加密密鑰,并利用對稱加密密鑰完成OPRF,降低了公鑰密碼系統(tǒng)的使用次數(shù),顯著提高了協(xié)議整體的計(jì)算開銷。因此,該技術(shù)路線適用于計(jì)算資源較為貧乏的場景,但缺陷在于需要承擔(dān)龐大的通信開銷,當(dāng)查詢較為頻繁時,信道壓力會過大。
基于Key-Value Store的不經(jīng)意關(guān)鍵詞檢索協(xié)議在計(jì)算開銷與通信開銷上取得了較好的平衡。與基于OPE的技術(shù)路線相比較,該技術(shù)路線的通信復(fù)雜度與其一致,均為O(logn);在計(jì)算開銷上,雖然仍為線性復(fù)雜度,但是,該技術(shù)路線無需花費(fèi)較大的計(jì)算資源代價生成插值多項(xiàng)式,因此,在計(jì)算開銷上優(yōu)于基于OPE的技術(shù)路線。而與基于OPRF的技術(shù)路線相比較,該技術(shù)路線雖然具備較小的通信開銷,但其所花費(fèi)的計(jì)算開銷仍較高。
不經(jīng)意關(guān)鍵詞檢索任務(wù)是隱私計(jì)算的基礎(chǔ)性任務(wù)之一。近年來,隨著隱私計(jì)算的發(fā)展,學(xué)術(shù)界與業(yè)界均對不經(jīng)意關(guān)鍵詞檢索逐漸引起重視。但是,該任務(wù)目前還存在許多挑戰(zhàn)亟待解決。本文總結(jié)了4個不經(jīng)意關(guān)鍵詞檢索任務(wù)面臨的挑戰(zhàn)及發(fā)展趨勢。
目前,已有的研究工作均集中于大批量檢索的場景,用戶端一次性查詢多個關(guān)鍵詞的值。但是,在實(shí)時檢索的場景下,查詢請求往往是小批量的,甚至是單目標(biāo)檢索。而此時,現(xiàn)有工作的大部分優(yōu)化措施將失效,導(dǎo)致協(xié)議的計(jì)算、通信資源代價過高,無法滿足實(shí)時檢索要求。因此,如何構(gòu)造效率較高的實(shí)時檢索協(xié)議是亟待解決的關(guān)鍵問題。
在實(shí)際應(yīng)用場景中,數(shù)據(jù)庫會實(shí)時更新鍵值對,比如增加新的鍵值對。而已有工作尚未考慮該場景設(shè)置,導(dǎo)致在多次檢索中,舊鍵值對會重復(fù)檢索,增加了不必要的計(jì)算開銷與通信開銷。因此,在數(shù)據(jù)庫動態(tài)變化的場景設(shè)置下,如何形成增量式動態(tài)檢索是一個亟待解決的關(guān)鍵問題。
現(xiàn)有的研究工作均聚焦于僅依賴關(guān)鍵詞的檢索方法,但在實(shí)際應(yīng)用中,用戶端可能希望采用多個屬性進(jìn)行組合檢索,以拓展協(xié)議的篩選能力。例如,信托機(jī)構(gòu)需要向銀行檢索一批用戶的信用評分,但對用戶存款設(shè)置下限,若低于下限,則無需返回信用評分。在該場景設(shè)置下,信托機(jī)構(gòu)不僅需要使用用戶的身份證進(jìn)行篩選,還需要同時考慮該用戶的存款是否低于已設(shè)置的下限。因此,如何在檢索時同時考慮多個查詢條件,是一個亟待解決的關(guān)鍵問題。
不經(jīng)意關(guān)鍵詞檢索經(jīng)常會作為數(shù)據(jù)處理的前置任務(wù),如計(jì)算一批用戶的平均信用評分前需要通過關(guān)鍵詞(比如身份證)取出對應(yīng)用戶的信用評分。從“數(shù)據(jù)可用不可見”的角度考慮,被檢索方可能只希望暴露數(shù)據(jù)處理結(jié)果,而檢索結(jié)果可以對用戶端隱藏。因此,如何在隱藏檢索結(jié)果的前提下,對檢索結(jié)果進(jìn)行后處理是一個亟待解決的關(guān)鍵問題。
隨著國家針對個人隱私保護(hù)頒布了包括《網(wǎng)絡(luò)安全法》《數(shù)據(jù)安全法》《個人信息保護(hù)法》《網(wǎng)絡(luò)數(shù)據(jù)安全管理?xiàng)l例》等在內(nèi)的多個法律法規(guī),隱私計(jì)算逐漸引起重視并廣泛應(yīng)用于各種應(yīng)用場景,包括數(shù)據(jù)聯(lián)合分析、機(jī)器學(xué)習(xí)聯(lián)合建模等。不經(jīng)意關(guān)鍵詞檢索作為隱私計(jì)算的基礎(chǔ)性任務(wù)之一,對隱私計(jì)算的實(shí)際部署及應(yīng)用有著至關(guān)重要的作用。相較于隱私信息檢索、不經(jīng)意傳輸?shù)让嫦驍?shù)組下標(biāo)的檢索方法而言,面向關(guān)鍵詞的不經(jīng)意關(guān)鍵詞檢索任務(wù)更貼近于實(shí)際應(yīng)用場景。因此,研究高效的不經(jīng)意關(guān)鍵詞檢索協(xié)議有助于促進(jìn)隱私計(jì)算的發(fā)展,拓展隱私計(jì)算的應(yīng)用邊界。
本文通過對現(xiàn)有研究工作進(jìn)行調(diào)研、分析與討論,將典型技術(shù)路線劃分為基于OTE的技術(shù)路線、基于OPRF的技術(shù)路線以及基于Key-Value Store的技術(shù)路線。三種技術(shù)路線均存在各自的優(yōu)勢與劣勢,并且適用于不同的應(yīng)用場景,而如何取得計(jì)算開銷與通信開銷的最佳平衡,使不經(jīng)意關(guān)鍵詞檢索協(xié)議的應(yīng)用場景不再受限,仍需要研究者們的不斷探索。進(jìn)一步地,本文還對現(xiàn)有研究尚未解決的技術(shù)挑戰(zhàn)進(jìn)行了分析與探討,并給出了未來發(fā)展趨勢:實(shí)時檢索協(xié)議、適應(yīng)數(shù)據(jù)庫動態(tài)變化的檢索協(xié)議、多條件檢索協(xié)議以及隱藏檢索結(jié)果的后處理技術(shù)。當(dāng)不經(jīng)意關(guān)鍵詞檢索任務(wù)的效率不斷提升、功能逐漸完備時,必將在隱私計(jì)算的發(fā)展潮流中充當(dāng)更為重要的角色,釋放更為巨大的價值。