自適應安全的支持模式匹配的流加密方案

李一鳴,劉勝利

(1.上海交通大學 計算機科學與工程系,上海 200240;2.密碼科學技術全國重點實驗室,北京 100878)

1 引 言

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

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

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

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

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

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

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

表1 文中SEPM方案與現有方案的比較

3 預備知識

3.1 符號約定

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

(1) 初始化算法Setup(1κ,L):輸入安全參數κ∈N,關鍵字長度上限L∈N+,輸出公開參數P。

(2) 密鑰生成算法KeyGen(P):輸入公開參數P,輸出一對主公私鑰(Kmpk,Kmsk)。

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

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

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

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

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

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

3.3 函數加密方案

(1) 初始化算法Setup(1κ,λ):輸入參數κ,λ∈N,輸出公開參數P。

(2) 密鑰生成算法KeyGen(P):輸入公開參數P,輸出一對主公私鑰(Kmpk,Kmsk)。

函數加密方案具有以下性質:

3.4 BCC20消息分段技術

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

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

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

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

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

所以可知,任意k∈[n-+1]一定落在某個區間[(ι-1)nl+1,ιnl-+1]或者[ns+(ι-1)nl+1,ns+ιnl-+1]中。對于任意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ι內。同理可證,如果ns+(ι-1)nl+1≤k≤ns+ιnl-+1,那么子串S[k,k+-1]一定包含在段內。由此可證,S的任意一個長子串一定落在某一個段或者偏移段內。

4 基于FE的SEPM通用構造方案

文中介紹如何使用FE通用構造SEPM,并基于LWE假設對SEPM通用構造進行實例化。

4.1 SEPM通用構造方案

(1) 初始化算法P←Setup(1κ,L):調用算法Fe.Setup(1κ,2L)→P,并返回公開參數P。

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

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

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

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

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

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

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

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

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

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

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

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

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

關于SEPM的通用構造方案Sepm,有如下定理成立。

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

4.2 SEPM通用構造方案的正確性和可忽略錯誤接收證明

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

又根據SEPM通用構造方案Sepm中Issue算法的設計,有

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

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

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

4.3 SEPM通用構造方案自適應安全性證明

下證,如果Fe是安全的,那么兩兩相鄰實驗Gj-1和Gj,j∈[2nf],之間就是計算不可區分的。

引理2對任意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處不匹配,這與是合法敵手矛盾。所以,如果是合法敵手,那么也是合法敵手。綜上,如果合法敵手能夠以不可忽略的概率區分實驗Gj和Gj-1,那么就可以以同樣的優勢打破FE的安全性,所以引理得證。

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

2nfmax

4.4 SEPM通用構造方案實例化

本節介紹如何基于LWE假設對4.1節中的SEPM通用構造方案Sepm進行實例化。

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

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

5 結束語

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