自適應(yīng)安全的支持模式匹配的流加密方案

李一鳴,劉勝利

(1.上海交通大學(xué) 計(jì)算機(jī)科學(xué)與工程系,上海 200240;2.密碼科學(xué)技術(shù)全國(guó)重點(diǎn)實(shí)驗(yàn)室,北京 100878)

1 引 言

隨著大數(shù)據(jù)時(shí)代的到來(lái),人們基于海量用戶數(shù)據(jù)開(kāi)發(fā)出了功能豐富的應(yīng)用。在某些應(yīng)用場(chǎng)景中,可能需要對(duì)采集到的數(shù)據(jù)進(jìn)行模式匹配操作,即檢測(cè)某個(gè)關(guān)鍵字是否出現(xiàn)在某條數(shù)據(jù)中,或者是出現(xiàn)在數(shù)據(jù)的哪些位置。如深度包檢測(cè) (Deep-Packet Inspection,DPI)、關(guān)鍵詞熱度分析、基因組數(shù)據(jù)檢索和數(shù)據(jù)庫(kù)數(shù)據(jù)檢索等,都可能使用到模式匹配。在這些場(chǎng)景中,數(shù)據(jù)的模式匹配操作可能由一個(gè)不被數(shù)據(jù)發(fā)送者信任的第三方(提供服務(wù)的廠商)來(lái)執(zhí)行。如果這些數(shù)據(jù),特別是包含了用戶隱私的數(shù)據(jù),都以明文的方式提交給第三方進(jìn)行處理,必然會(huì)有隱私泄露的風(fēng)險(xiǎn)。如果對(duì)明文數(shù)據(jù)進(jìn)行加密后發(fā)送,第三方又無(wú)法對(duì)其進(jìn)行模式匹配操作,從而無(wú)法提供服務(wù)。因此,如何在不影響模式匹配功能的同時(shí)為用戶提供隱私保護(hù),成為了一個(gè)需要解決的問(wèn)題。

目前對(duì)這一問(wèn)題的解決思路主要集中于研究(對(duì)稱(chēng)版本或公鑰版本)可搜索加密方案 (Searchable Encryption,SE)[1-3]。但是,根據(jù)文獻(xiàn)[3],現(xiàn)有的可搜索加密方案在應(yīng)用的靈活性上仍存在一些局限:① 部分可搜索加密方案需要提前固定待檢測(cè)關(guān)鍵字集合,如果出現(xiàn)新的關(guān)鍵字,就需要重新配置系統(tǒng),因此不適用于關(guān)鍵字頻繁更新的場(chǎng)景;② 部分可搜索加密方案要求關(guān)鍵字是某個(gè)固定的長(zhǎng)度,如文獻(xiàn)[4],而這在真實(shí)的應(yīng)用場(chǎng)景中很難滿足;③ 部分可搜索加密方案只能用于判斷關(guān)鍵字與消息是否匹配,而無(wú)法給出具體匹配的位置,如文獻(xiàn)[2,5];④ 部分可搜索加密方案無(wú)法支持帶通配符的模式匹配,如文獻(xiàn)[4,6];⑤ 部分可搜索加密方案只能處理固定長(zhǎng)度的消息,如文獻(xiàn)[5];這些方案需要等待所有消息輸入完畢后一起打包加密,且消息長(zhǎng)度需滿足方案設(shè)置;相比之下,比較理想的情況是能夠?qū)θ我饪勺冮L(zhǎng)度的數(shù)據(jù)流進(jìn)行處理。

2 支持模式匹配的流加密方案

為滿足更靈活的應(yīng)用需求,文獻(xiàn)[3]提出了帶有可調(diào)整陷門(mén)的可搜索加密 (Searchable Encryption with Shiftable Trapdoors,SEST) 方案。SEST方案允許第三方自由選擇關(guān)鍵字,而無(wú)需在加密前給定關(guān)鍵字集合;支持更靈活的關(guān)鍵字長(zhǎng)度以及待匹配消息長(zhǎng)度;可以給出關(guān)鍵字出現(xiàn)在消息中的所有位置,而不僅僅是“是否匹配”這一比特的結(jié)果。特別地,文獻(xiàn)[7]將支持任意待匹配消息長(zhǎng)度的模式匹配的方案叫作支持模式匹配的流加密方案(Stream Encryption supporting Pattern Matching,SEPM)。SEPM的語(yǔ)義和安全性定義與文獻(xiàn)[3]中的基本一致。文中采用文獻(xiàn)[7]中SEPM的叫法。

文獻(xiàn)[3]給出了配對(duì)群上基于交互式通用Diffie-Hellman (interactive General Diffie-Hellman,i-GDH) 假設(shè)的SEST構(gòu)造方案。該方案支持無(wú)通配符的模式匹配,滿足選擇安全性(文獻(xiàn)[3]中還給出了一種更強(qiáng)的安全性定義——自適應(yīng)安全性,并沒(méi)有實(shí)現(xiàn)自適應(yīng)安全性)。在此基礎(chǔ)上,文獻(xiàn)[3]又給出了支持帶通配符模式匹配的SEST方案,同樣實(shí)現(xiàn)了選擇安全性。除了對(duì)明文信息的保護(hù)外,文獻(xiàn)[6]進(jìn)一步考慮如何對(duì)關(guān)鍵字進(jìn)行保護(hù)。文獻(xiàn)[6]給出了配對(duì)群上基于i-GDH假設(shè)的公鑰版本流密文模式匹配方案AS3E。該方案同時(shí)具有選擇安全性和關(guān)鍵字不可區(qū)分性,但只支持不帶通配符的模式匹配。文獻(xiàn)[6]提出了一種分段技術(shù),用于支持任意長(zhǎng)度的消息加密。文獻(xiàn)[7]提出了配對(duì)群上基于i-GDH假設(shè)的SEPM方案。該方案具有選擇安全性、支持帶通配符的模式匹配。與已有方案相比,文獻(xiàn)[7]中的方案在效率方面進(jìn)行了提升。注意到,前述方案都依賴(lài)于i-GDH假設(shè),該假設(shè)是一個(gè)交互式安全假設(shè),目前其困難性僅在一般群模型(Generic Group Model,GGM)下有分析[8],因此i-GDH并不是一個(gè)很理想的安全假設(shè)。為了改進(jìn)這一點(diǎn),文獻(xiàn)[7]提出了基于一種非交互式安全假設(shè)的SEPM方案。

目前,尚沒(méi)有SEPM構(gòu)造能夠同時(shí)滿足基于非交互式安全假設(shè)實(shí)現(xiàn),具有自適應(yīng)安全性,以及支持帶通配符的模式匹配。此外,隨著量子算法的興起,基于離散對(duì)數(shù)家族假設(shè)和大整數(shù)族假設(shè)的密碼方案在量子攻擊下將喪失其安全性,因此密碼學(xué)界對(duì)如何設(shè)計(jì)后量子密碼算法進(jìn)行了大量研究,并在諸多領(lǐng)域取得了成果,如文獻(xiàn)[9-12]。然而,目前仍然沒(méi)有能夠抵抗量子攻擊的SEPM方案。

筆者針對(duì)上述問(wèn)題進(jìn)行了研究,提出了新的SEPM方案,能夠基于非交互式后量子假設(shè)證明自適應(yīng)安全性,且支持帶通配符的模式匹配。文中以支持匹配函數(shù)的函數(shù)加密方案 (Functional Encryption,FE)為組件,提出了一個(gè)SEPM的通用構(gòu)造。該通用構(gòu)造具有自適應(yīng)安全性,且支持帶通配符的模式匹配。進(jìn)一步結(jié)合已有的基于容錯(cuò)學(xué)習(xí) (Learning With Errors,LWE) 假設(shè)的FE實(shí)例化方案[13-14],文中得到了基于LWE假設(shè)的SEPM實(shí)例化方案。其中,LWE假設(shè)是非交互式安全假設(shè),且是廣泛認(rèn)可的抗量子攻擊的安全假設(shè),因此基于LWE假設(shè)的SEPM實(shí)例化方案具有抗量子攻擊的可能。表1給出了文中SEPM通用構(gòu)造及其實(shí)例化與現(xiàn)有SEPM方案的比較。

表1 文中SEPM方案與現(xiàn)有方案的比較

3 預(yù)備知識(shí)

3.1 符號(hào)約定

3.2 支持模式匹配的流加密方案

(1) 初始化算法Setup(1κ,L):輸入安全參數(shù)κ∈N,關(guān)鍵字長(zhǎng)度上限L∈N+,輸出公開(kāi)參數(shù)P。

(2) 密鑰生成算法KeyGen(P):輸入公開(kāi)參數(shù)P,輸出一對(duì)主公私鑰(Kmpk,Kmsk)。

(3) 密鑰派生算法Issue(Kmsk,W):輸入主私鑰Kmsk以及長(zhǎng)度為任意≤L的關(guān)鍵字W=(w1,…,w)∈,輸出陷門(mén)TW。

(5) 測(cè)試算法Test(TW,W,C):輸入陷門(mén)TW、關(guān)鍵字W以及密文C,輸出匹配集合?[n]。

支持模式匹配的流加密方案具有以下性質(zhì):

(Match(W,S[k,k+-1])=1)?(Pr[k∈]=1-negl(κ)) 。

(2) 可忽略錯(cuò)誤接收?？珊雎藻e(cuò)誤接收要求對(duì)于任意k∈[n],如果S和W在k處不匹配,那么k以極大概率不在中,即?k∈[n],有

(Match(W,S[k,k+-1])=0)?(Pr[k∈]=negl(κ)) 。

3.3 函數(shù)加密方案

(1) 初始化算法Setup(1κ,λ):輸入?yún)?shù)κ,λ∈N,輸出公開(kāi)參數(shù)P。

(2) 密鑰生成算法KeyGen(P):輸入公開(kāi)參數(shù)P,輸出一對(duì)主公私鑰(Kmpk,Kmsk)。

函數(shù)加密方案具有以下性質(zhì):

3.4 BCC20消息分段技術(shù)

圖1 BCC 20分段技術(shù)示例,取n=14,L=2,nl=4,ns=2,nf=3

(1) 存在ι∈[nf],使得(ι-1)nl+1≤k≤ιnl-+1,此時(shí)子串S[k,k+-1]落在Sι段。

(2) 存在ι∈[nf],使得ns+(ι-1)nl+1≤k≤ns+ιnl-+1,此時(shí)子串S[k,k+-1]落在段。

證明:易知,S的所有長(zhǎng)子串為S[1,],S[2,+1],…,S[n-+1,n]。首先證明對(duì)于任意子串S[k,k+-1],一定能找到滿足(1)或(2)要求的ι∈[nf]。因?yàn)椤躄,所以對(duì)于任意ι∈[nf],有ιnl-+1=(ι-1)nl+nl-+1≥(ι-1)nl+nl-L+1=ns+(ι-1)nl+1 以及ns+ιnl-+1=ιnl+(L-)+1≥ιnl+1成立。進(jìn)而可得

[(nf-1)nl+1,ns+(nf-1)nl+1]∪[ns+(nf-1)nl+1,n-+1]=[n-+1] 。

所以可知,任意k∈[n-+1]一定落在某個(gè)區(qū)間[(ι-1)nl+1,ιnl-+1]或者[ns+(ι-1)nl+1,ns+ιnl-+1]中。對(duì)于任意k∈[n-+1],如果(ι-1)nl+1≤k≤ιnl-+1,那么有k≥(ι-1)nl+1,且k+-1≤ιnl。又Sι=S[(ι-1)nl+1,ιnl]=(s(ι-1)nl+1,…,sιnl),可知S[k,k+-1]一定包含在段Sι內(nèi)。同理可證,如果ns+(ι-1)nl+1≤k≤ns+ιnl-+1,那么子串S[k,k+-1]一定包含在段內(nèi)。由此可證,S的任意一個(gè)長(zhǎng)子串一定落在某一個(gè)段或者偏移段內(nèi)。

4 基于FE的SEPM通用構(gòu)造方案

文中介紹如何使用FE通用構(gòu)造SEPM,并基于LWE假設(shè)對(duì)SEPM通用構(gòu)造進(jìn)行實(shí)例化。

4.1 SEPM通用構(gòu)造方案

(1) 初始化算法P←Setup(1κ,L):調(diào)用算法Fe.Setup(1κ,2L)→P,并返回公開(kāi)參數(shù)P。

(2) 密鑰生成算法(Kmpk,Kmsk)←KeyGen(P):調(diào)用算法Fe.KeyGen(P)→(Kmpk,Kmsk),并返回公私鑰對(duì)(Kmpk,Kmsk)。

(3) 密鑰派生算法TW←Issue(Kmsk,W),其中W=(w1,…,w)∈

① 對(duì)任意d∈[0,2L-],置*2L。

② 對(duì)任意d∈[0,2L-],構(gòu)造函數(shù)fWd∈2L,其中fWd(S)∶=Match2L(Wd,S)。

③ 對(duì)任意d∈[0,2L-],調(diào)用算法Fe.KeyDer(Kmsk,fWd)→KWd。

④ 返回陷門(mén)TW∶=(KW0,…,KW2L-l)。

(4) 加密算法C←Enc(Kmpk,S),其中S=(s1,…,s)∈n：

① 計(jì)算nl∶=2L,ns=L,nf=(n-ns)/nl。

② 對(duì)任意i∈[nf],置段Si=S[(i-1)nl+1,inl],調(diào)用Fe.Enc(Kmpk,Si)→Ci。

② 對(duì)任意i∈[nf]以及任意d∈[0,2L-],如果Fe.Dec(KWd,Ci)=1,計(jì)算k∶=(i-1)nl+1+d,置∶=∪{k}。

③ 對(duì)任意i∈[nf]以及任意d∈[0,2L-],如果計(jì)算k∶=ns+(i-1)nl+1+d,置∶=∪{k}。

(1) 初始化算法Setup僅調(diào)用1次Fe.Setup,其時(shí)間復(fù)雜度為tSetup=t′Setup。

(2) 密鑰生成算法KeyGen僅調(diào)用1次Fe.KeyGen,其時(shí)間復(fù)雜度為tKeyGen=t′KeyGen。

關(guān)于SEPM的通用構(gòu)造方案Sepm,有如下定理成立。

定理1如果Fe是支持匹配函數(shù)族的自適應(yīng)安全的函數(shù)加密方案,那么通用構(gòu)造方案Sepm具有正確性、可忽略錯(cuò)誤接收以及自適應(yīng)安全性。

4.2 SEPM通用構(gòu)造方案的正確性和可忽略錯(cuò)誤接收證明

證明(正確性):下證對(duì)任意關(guān)鍵字W=(w1,…,wl)∈S和消息S=(s1,…,sl)∈n,如果S和W在k∈[n]處匹配,有Pr[k∈]=1-negl(κ)。對(duì)于任意k∈[n],S和W在k處匹配等價(jià)于Match(W,S[k,k+-1])=1。易知S[k,k+-1]是S的一個(gè)長(zhǎng)度為≤L的子串。根據(jù)引理1可知,S[k,k+-1]一定在某個(gè)段或者偏移段內(nèi),假設(shè)S[k,k+-1]落在段Sι=S[(ι-1)nl+1,ιnl]內(nèi),即(ι-1)nl+1≤k≤ιnl-+1(如落在偏移段內(nèi),可類(lèi)似證明)。計(jì)算S[k,k+-1]在段Sι內(nèi)的偏移量為Δ=k-(ι-1)nl-1,且0≤Δ≤nl-?？芍?/p>

又根據(jù)SEPM通用構(gòu)造方案Sepm中Issue算法的設(shè)計(jì),有

易知, Match2L(WΔ,Sι)=Match(W,S[k,k+-1])=1 成立。進(jìn)而由FE方案Fe的正確性可知,Fe.Dec(KWΔ,Cι)=fWΔ(Sι)=Match2L(WΔ,Sι)=1以1-negl(κ)概率成立。根據(jù)方案Sepm的設(shè)計(jì),如果Fe.Dec(KWΔ,Cι)=1,那么k′∶=(ι-1)nl+1+Δ=k會(huì)被加入集合T中,所以Pr[k∈]=1-negl(κ)。方案的正確性得證。

證明(可忽略錯(cuò)誤接收):下證對(duì)任意關(guān)鍵字W=(w1,…,wl)∈S和消息S=(s1,…,sn)∈n,如果S和W在k∈[n-+1]處不匹配,有Pr[k∈]=negl(κ)(根據(jù)構(gòu)造,當(dāng)k∈[n-+2,n],S和W在k處不匹配且k不會(huì)被加入集合)。使用反證法,假設(shè)S和W在k∈[n-+1]處不匹配,但是k∈以不可忽略概率成立,證矛盾。如果k∈,根據(jù)構(gòu)造一定有ι∈[nf],Δ∈[0,2L-]使得k=(ι-1)nl+1+Δ且Fe.Dec(KWΔ,Cι)=1,或k=ns+(ι-1)nl+1+Δ且設(shè)k是通過(guò)第1種情況被加入到集合中的,即k=(ι-1)nl+1+Δ且Fe.Dec(KWΔ,Cι)=1(如果是第2種情況,可類(lèi)似證明)。設(shè)Sι是密文Cι對(duì)應(yīng)的明文消息段,有

因?yàn)镾和W在k處不匹配,所以Match(W,S[k,k+-1])=0,進(jìn)而Match2L(WΔ,Sι)=0?；诖?如果k∈以不可忽略概率成立,就以不可忽略概率找到WΔ和Sι,使得Fe.Dec(KWΔ,Cι)=1≠fWΔ(Sι)=Match2L(WΔ,Sι)=0,這與Fe的正確性矛盾。方案的可忽略錯(cuò)誤接收得證。

4.3 SEPM通用構(gòu)造方案自適應(yīng)安全性證明

下證,如果Fe是安全的,那么兩兩相鄰實(shí)驗(yàn)Gj-1和Gj,j∈[2nf],之間就是計(jì)算不可區(qū)分的。

引理2對(duì)任意j∈[2nf],有|Pr[Gj?1]-Pr[Gj-1?1]|≤max

易知,有Match(W(ι),S(1)[(j-1)nl+Δ+1,(j-1)nl+Δ+ι])=1且Match(W(ι),S(0)[(j-1)nl+Δ+1,(j-1)nl+Δ+ι])=0成立。由此可知W(ι)與S(1)在(j-1)nl+Δ+1處匹配,但是與S(0)在(j-1)nl+Δ+1處不匹配,這與是合法敵手矛盾。所以,如果是合法敵手,那么也是合法敵手。綜上,如果合法敵手能夠以不可忽略的概率區(qū)分實(shí)驗(yàn)Gj和Gj-1,那么就可以以同樣的優(yōu)勢(shì)打破FE的安全性,所以引理得證。

|Pr[G0?1]-Pr[G2nf?1]|≤∑i∈[2nf]|Pr[Gi-1?1]-Pr[Gi?1]|≤

2nfmax

4.4 SEPM通用構(gòu)造方案實(shí)例化

本節(jié)介紹如何基于LWE假設(shè)對(duì)4.1節(jié)中的SEPM通用構(gòu)造方案Sepm進(jìn)行實(shí)例化。

根據(jù)文獻(xiàn)[16],對(duì)于任意n,m=poly(κ),q≤2poly(n),χ是參數(shù)為σ的離散高斯分布,且2n1/2≤σ≤q,<=q,求解判定性LWE-{n,q,chi,m}問(wèn)題至少與求解最壞情況匯報(bào)格上的困難問(wèn)題GapSVP_gamma和SIVP_gamma一樣難,其中漸進(jìn)參數(shù)γ=O(nq/σ)。這些格上的困難假設(shè)是公認(rèn)的可抵抗量子攻擊的,因此,LWE假設(shè)也是廣泛認(rèn)可的抗量子攻擊假設(shè)。

文獻(xiàn)[13-14]分別提出了基于LWE假設(shè)的支持任意多項(xiàng)式大小電路的自適應(yīng)安全的FE。易知對(duì)任意λ=poly(κ),模式匹配函數(shù)λ是多項(xiàng)式大小電路可實(shí)現(xiàn)的。使用文獻(xiàn)[13-14]中的FE實(shí)例化方案對(duì)4.1節(jié)中的SEPM通用構(gòu)造方案Sepm進(jìn)行實(shí)例化可以得到基于LWE假設(shè)的SEPM實(shí)例化方案。事實(shí)上,在對(duì)SEPM通用構(gòu)造進(jìn)行實(shí)例化時(shí),只需要使用支持匹配函數(shù)族的自適應(yīng)安全的FE作為組件。但遺憾的是,目前尚沒(méi)有針對(duì)這種函數(shù)族的滿足要求的FE實(shí)例化方案,因此文中使用了支持更通用函數(shù)族的FE實(shí)例化方案。但是這樣會(huì)使得最終的SEPM實(shí)例化方案在效率方面的表現(xiàn)不盡如人意。如果后續(xù)能夠有滿足實(shí)例化要求的更高效的FE實(shí)例化方案,那么相應(yīng)地,套用文中的SEPM通用構(gòu)造,就可以得到更高效的SEPM方案。

5 結(jié)束語(yǔ)

筆者基于LWE假設(shè)提出了具有自適應(yīng)安全性的、支持帶通配符模式匹配的SEPM方案。具體地,以支持匹配函數(shù)的FE作為組件,提出了SEPM的通用構(gòu)造方法,該通用構(gòu)造具有自適應(yīng)安全性且支持帶通配符的模式匹配。通過(guò)對(duì)FE組件進(jìn)行實(shí)例化,進(jìn)一步得到了基于LWE假設(shè)的SEPM實(shí)例化方案。但是因?yàn)镕E組件實(shí)例化的局限性,文中SEPM的最終實(shí)例化在效率方面仍有待提升。如何構(gòu)造效率更高的滿足實(shí)例化要求的FE是一個(gè)值得進(jìn)一步研究的問(wèn)題。