可搜索公鑰加密研究進展

宋文帥，鄧淼磊，馬米米，李昊宸

（河南工業大學 信息科學與工程學院，鄭州 450001）

0 引言

隨著互聯網用戶數量的增加以及云計算技術的不斷成熟，全球數據量呈爆炸式增長趨勢。在當下大數據的時代背景下，云存儲服務［1］因具有數據的可伸縮性、共享性、可訪問性和高效備份性等特點而被廣泛應用。近年來，眾多云服務提供商紛紛涌現，從最初的亞馬遜、谷歌到現在的百度云、阿里云等。云服務器在給人們帶來便利的同時，云上數據安全［2］和用戶隱私也面臨極大挑戰。加密能夠有效保護數據安全和隱私，但數據被加密后，原有的結構將發生改變，已有的針對明文數據的檢索算法將不再適用，如何在密文數據上進行檢索成為亟待解決的難題。一種簡單的方法是用戶先下載全部數據，解密后再在明文數據上檢索。然而，下載全部數據一方面將占用大量網絡帶寬，另一方面將造成本地資源浪費。為實現對密文數據的高效檢索，可搜索加密技術被提出?？伤阉骷用艿墓ぷ髁鞒倘缦拢?）數據擁有者首先對數據和關鍵詞加密并上傳到云服務器；2）數據使用者使用私鑰產生關鍵詞搜索陷門并發送給云服務器；3）云服務器進行檢索匹配，匹配成功后把密文返回給數據使用者；4）數據使用者對密文進行解密。

2000 年，Song等［3］首次提出可搜索對稱加密概念。但基于對稱密碼體制的加密技術需要使用同一個密鑰進行加密和解密，不適合復雜的多用戶應用場景。為了解決該問題，Boneh等［4］首次提出可搜索公鑰加密（Public-key Encryption with Keyword Search，PEKS）并應用在郵件路由場景中。發送方通過接收方的公鑰對數據集和關鍵詞信息進行加密；接收方利用自身的私鑰產生關鍵詞搜索陷門并發送給服務器；服務器對關鍵詞進行檢索并返回包含關鍵詞的加密數據給接收方；接收方利用私鑰對密文進行解密。PEKS 通過公私鑰對實現明文的加密和密文檢索功能，適用場景比可搜索對稱加密更多、前景也更廣闊［5-8］。

本文關注近幾年PEKS 技術研究現狀，探討可搜索公鑰加密技術的安全性和擴展性，并進行各方案的安全和性能的對比分析，最后對未來可搜索公鑰加密技術領域進行展望。

1 可搜索公鑰加密定義

加密技術的本質是破解某個“極微本源”，即破解某個數學困難問題，分析算法構造時所用的數學知識和嵌入的困難問題。本章給出PEKS 的多項式時間算法構造、算法一致性描述和安全模型。

1.1 形式化定義

定義1PEKS 算法描述［9］。PEKS 方案一般由4 個概率多項式時間算法構成：

PEKS=(KeyGen，Encrypt，Trapdoor，Test)

KeyGen(λ)=(pk，sk)：輸入安 全參數λ，輸出公 私鑰對(pk，sk)。

Encrypt(pk，w)=Cw：輸入公鑰pk和關鍵詞w，輸出關鍵詞密文Cw。

Trapdoor(sk，w′)=Tw′：輸入私鑰sk和用戶感興趣的關鍵詞w′，輸出用戶關鍵詞搜索陷門Tw′。

Test(pk，Cw，Tw′)=0/1：輸入公鑰pk，關鍵詞密文Cw，用戶搜索陷門Tw′。若w=w′，輸出“1”；若w≠w′，則輸出“0”。

PEKS 系統模型如圖1 所示。

圖1 PEKS系統模型Fig.1 PEKS system model

定義2雙線性對［4］。設G1、G2是以素數q為階的循環群，g是G1的一個生成元。若映射e：G1×G2→G2滿足下列性質，則稱e為雙線性對。

2）非退化性：?g，?G1，使e(g，g)≠1。

3）可計算 性：對任意u，v∈G1，存在有 效的算法可計算e(u，v)。

定義3計算雙線性Diffie-Hellman（Computation Bilinear Diffie-Hellman，CBDH）困難問題［10］。給定g，ga，gb，gc∈G1，其中：a、b、c是屬于的隨機數，計算e(g，g)abc∈G2是困難的。

1.2 算法一致性描述

傳統PEKS 算法的一致性被定義為加密算法與解密算法互為逆過程。對PEKS 的完美一致性的定義描述為：隨機的任意兩個關鍵詞w1、w2，通過陷門生成關鍵詞w1的搜索陷門Tw1，由加密 算法生成關鍵詞w2的密文Cw2，如果w1≠w2，Pr[ Test(Cw2，Tw1)=1 ]=0。文獻［11］中指出PEKS 方案［4］只滿足計算一致性，并不滿足完美一致性和統計一致性，并給出三種一致性的定義。

定義4假設存在一名敵手A，定義算法一致性的安全游戲。

敵手A贏得上述游戲的優勢為：AdvA(λ)=

當任意的敵手A贏得上述安全游戲的概率AdvA(λ)=0，即視為該PEKS 方案具有完美一致性。

當任意的敵手A贏得上述安全游戲的概率AdvA(λ)關于ε可忽略，即視為該PEKS 方案具有統計一致性。

對任意的敵手A在多項式時間內贏得上述游戲的概率AdvA(λ)是關于ε可忽略的，即視為該PEKS 方案滿足計算一致性。

1.3 安全模型

Boneh 基于身份加密（Identity-Based Encryption，IBE）［12］定義了PEKS 的安全性并提出了選擇關鍵詞攻擊下的不可區分性（INDistinguishability against Chosen Keyword Attack，INDCKA）安全模型，安全模型通過挑戰者C和敵手A之間的博弈游戲進行定義［13］。

如圖2 所示：1）挑戰者C執行KeyGen(λ)算法生成公鑰pk和私鑰sk，并把公鑰pk發送給敵手A。2）敵手A自適應地查詢搜索陷門預言機OTrapdoor，獲得關鍵詞w∈{0，1}*的陷門Tw。3）敵手A隨機選取兩個關鍵詞w0、w1發送給挑戰者C，要求選取兩個未被詢問的關鍵詞。挑戰者C隨機選取一個比特b∈{0，1}，通過算法Encrypt(pk，wb)生成挑戰密文C并發送給敵手A。4）當A再次詢問搜索陷門預言機OTrapdoor時不能詢問關鍵詞w0、w1的陷門信息。5）敵手A針對關鍵詞進行猜測，選取一個比特b′∈{0，1}輸出：如果b=b′則敵手A攻擊成功；否則敵手A攻擊失敗。

圖2 PEKS安全模型中的博弈過程Fig.2 Game process in PEKS security model

敵手A贏得博弈游戲的攻擊優勢為：AdvA(λ)=

定義5如果敵手A贏得博弈游戲的優勢關于ε可忽略，即AdvA(λ) ＜negl(ε)，則PEKS 方案是語義安全的。

2 PEKS典型構造方案

本章對三個具有代表性的PEKS 方案進行分析陳述，列出它們的算法模型，最后對三者的通信量、服務端存儲量、性能效率以及安全性進行對比分析。

2.1 BDOP-PEKS方案

2004 年Boneh等［4］基于BF-IBE（Boneh-Franklin IBE）系統構造了適用于郵件路由系統的PEKS 方案BDOP-PEKS（Boneh-Di-Ostrovsky-Persiano PEKS），并在雙線性Diffie-Hellman（Bilinear Diffie-Hellman，BDH）困難問題假設下證明了方案的安全性。具體構造如下：

1）KeyGen(λ)：輸入安 全參數λ，生成公鑰pk=[g，h=gα]和私鑰sk=α。其中是循環群；g是循環群G1的生成元。

2）PEKS(pk，w)：輸入公鑰pk和關鍵詞w，生成關鍵詞密文，其中；H為哈希函數。

3）Trapdoor(Sk，w′)：輸入私鑰sk和用戶待查詢的關鍵詞w′，輸出關鍵詞搜索陷門Tw′=H1(w′)α∈G1。

4）Test(pk，Tw′，Cw)：令Cw=[A，B]，驗證H2(e(Tw′A))=B是否成立，成立則輸出1 并返回密文給用戶，否則輸出0。

BDOP-PEKS 方案存在一些缺點［13］：1）雙線性對運算導致算法計算開銷大、效率低，不適合用于大批量加密數據的檢索查詢；2）需要建立安全信道來抵御網絡攻擊者獲取搜索陷門信息；3）由于搜索陷門生成算法不滿足陷門不可區分性，所以無法抵抗關鍵詞猜測攻擊。

2.2 KR-PEKS方案

2006 年，Khader等［14］基于BDOP-PEKS 方案進行改進，設計出基于K-Resilient IBE 的PEKS 方案（KR-PEKS），并在標準模型下證明了方案的安全性。具體構造如下。

1）KeyGen。

步驟1 選取q階群G，其中：g1，g2∈G。

步驟4 隨機選取抗碰撞的哈希函數H：G→{0，1}λ和H′：G→{ 0，1}k。

步驟5 輸出公鑰PkR=(g1，g2，A0，…，Ak，B0，…，Bk，D0，…，Dk，H，H′)和私鑰SkR=(f1，f2，h1，h2，p1，p2)。

2）KR-PEKS。

KR-PEKS 方案避免了雙線性對的使用，顯著減小了計算開銷。但是此方案生成的搜索陷門數量不能大于K，所以K值的選取十分重要。

2.3 DS-PEKS方案

2007 年，Di Crescenzo等［15］基于二次剩余問題的變體構造了DS-PEKS（Di-Saraswat PEKS）方案，具體構造如下。

1）M-KeyGen(1m)：輸入一元參數1m，其中：m∈Z*，隨機選取長度為2/m的素數p、q，使p和q模4 同余3，令n=pq。生成公鑰ui∈，私鑰Apriv=(p，q)。

DS-PEKS 方案的構造形式使關鍵詞密文長度較短，提高了加密和查詢的效率，但該方案在服務器和用戶之間進行通信時會占用大量帶寬。

以上三種方案都通過計算關鍵詞陷門對關鍵詞進行匹配的基本PEKS 構建策略，測試文件是否包含待查詢的關鍵字。表1 是三種方案的性能對比，其中：k為安全參數；|g|為G中元素所占用的存儲空間；p為循環群G的階；n為數據總數目；li為第i個數據中的關鍵詞個數；N為關鍵詞字典中的關鍵詞字數。表中假設包括二次不可區分性問題（Quadratic Indistinguishability Problem，QIP）、BDH 與決策Diffie-Hellman（Decisional Diffie-Hellman，DDH）問題。

表1 PEKS典型方案對比Tab.1 Comparison of typical PEKS schemes

3 安全性擴展研究

3.1 關鍵詞猜測攻擊

Byun等［16］指出當用戶選取的關鍵詞是對自己有特殊意義的單詞時，關鍵詞信息熵就會變小，而用戶在實際應用中大多會如此選擇，導致關鍵詞空間不夠大。當關鍵詞字典的空間遠小于密鑰空間且用戶喜歡用跟自己有關聯的關鍵詞進行檢索時，攻擊者利用窮舉策略就能實現關鍵詞猜測攻擊（Keyword Guessing Attack，KGA）。外部攻擊者發起的攻擊稱為外部關鍵詞猜測攻擊，而由云服務器代理商或服務器中其他任意角色發起為內部關鍵詞猜測攻擊。此外，惡意云服務器為識別陷門和關鍵字之間的關系，利用關鍵詞統計分布概率知識和常用謂詞進行統計關鍵詞猜測攻擊也被包含在KGA 中。Jeong等［17］證明了在KGA 下不存在PEKS 方案滿足算法一 致性和 安全性。為了抵 抗KGA，Baek等［18］、Rhee等［19-20］先后進行研究，證明了PEKS 方案抗擊KGA 的充分條件是關鍵詞搜索陷門的不可區分性。

Baek等［18］提出的指定服務器的PEKS（designated server PEKS，dPEKS）方案可以保證除用戶指定的服務器以外所有服務器都無法判斷關鍵詞密文和陷門是否匹配，但安全性提高甚微。隨后抗外部離線關鍵詞猜測攻擊的dPEKS 方案［21-25］陸續被提出。2011 年，Wang等［26］指出Rhee 的dPEKS方案只能抵抗從外部發起的關鍵詞猜測攻擊，無法抵抗從惡意服務器內部引發的關鍵詞猜測攻擊。2014 年，Wang等［27］提出雙服務器概念模型以實現抵抗內部關鍵詞猜測攻擊，但由于雙服務器的計算開銷非常大，所以沒有廣泛應用。2016年，Chen等［28］提出DS-PEKS（Dual-Server PEKS）方案，由兩個獨立的服務器聯合執行測試算法，能有效抵抗惡意的內部關鍵詞猜測攻擊。Huang等［29］在2017 年設計出一種可認證的PEKS 方案，采用發送方的私鑰和接收方的公鑰進行關鍵詞加密，通過發送方的公鑰和接收方的私鑰生成關鍵詞搜索陷門，有效抵抗了內部關鍵詞猜測攻擊。2019 年王少輝等［30］基于變形線性決策困難問題（modified Decisional LINinear assumption，mDLIN）構建了滿足陷門和密文不可區分性的加密算法，并在隨機預言機模型下證明了方案的安全性。雖然文獻［30］的方案具有更小的開銷，但是不具有普適性，密文和搜索陷門生成算法一樣，即采用對稱雙線性對，被破解的概率增大，并且方案在標準模型下的安全性亟須解決。2018年，徐海琳等［31］構造一個無安全信道的PEKS 方案，并在標準模型下證明了方案的安全性，但該方案基于雙線性，計算開銷很大，所以實用性不強。2020 年，Yu等［32］為抵御內部KGA 提出了一種基于格的PEKS 方案，采用基于格的簽名技術對關鍵詞加密，以防止惡意服務器偽造有效密文。對于離線的內部/外部KGA 已有大部分研究，但在線的KGA 卻較少，文獻［33］采用密文隨機化技術設計出可以抵抗在線和離線的KGA 方案，并在隨機模型下證明了方案的安全性。

將KGA 設計在內已是現在PEKS 方案必須要考慮的內容。從最初的使用雙服務器，指定服務器到使用私鑰和認證聯合加密關鍵詞再到基于格和區塊鏈的技術，抵抗惡意關鍵詞猜測攻擊一直沒有得到有效解決。未來面對高性能計算機和龐大個人隱私數據，設計出通用并且可以抵抗全面KGA 的方案值得深究。

3.2 文件注入攻擊

文件注入攻擊（File-Injection Attack，FIA）是可搜索公鑰加密要面臨的另一個安全性挑戰。Zhang等［34］首次發現了可搜索加密中的文件注入攻擊形式，并對此展開研究。文件注入攻擊通過惡意服務器向客戶端注入一組文件以獲取關鍵詞的搜索陷門信息，文件注入攻擊會對數據隱私產生不可逆的破壞，攻擊者很容易獲取大量跟用戶相關的、特定的敏感 關鍵詞信息。Li等［35］為解決FIA 對保序加密（Order-Preserving Encryption，OPE）和逆序加密（Order-Revealing Encryption，ORE）的威脅，通過逆向思維首先針對兩類加密技術的FIA 方案進行挑戰，敵手在只擁有明文空間和一些之前的加密順序或查詢范圍時實現了FIA，并由此提高加密算法的安全性。Huang等［36］就非自適應文件注入攻擊（Non-Adaptive File Injection Attack，NAFIA）進行研究，設計了一種新型文件更新模式，對文件存儲和關鍵詞索引進行調整，采用隨機數異或的方法設計密鑰。該方法兼顧文件存儲和索引安全性，有效防止服務器識別文件插入的時間和位置，在抵抗FIA 的同時提高了通信效率。

4 應用性擴展性研究

4.1 查詢方式擴展

關鍵詞查詢方式一直是重點問題，針對單關鍵詞不連續的問題，Boneh等［10］提出支持連接關鍵詞查詢和關鍵詞比較查詢的PEKS 方案，通過使用隱藏向量加密技術檢索關鍵詞密文。出現多關鍵詞查詢后，關鍵詞之間的聯系又出現一系列難題，如關鍵字之間的順序、多關鍵字存儲結構、關鍵詞集合子集查詢等。為了提高用戶得到密文的正確率并提高云服務器的效率，Hu等［37］提出支持排序的多關鍵詞PEKS 方案，對查詢結果進行排序，返回給用戶最相關的k個文件，節約了大量的計算開銷。但基于雙線性對的加密方案效率提升較小，楊寧濱等［38］提出一種無需雙線性對且無需安全信道的多關鍵詞可認證PEKS 方案，在減少計算雙性對時產生的大量開銷的同時也省去了建設安全信道付出的通信代價，并證明了方案滿足密文不可區分性。

為了進一步提高檢索能力，Li等［39］首次提出支持模糊關鍵詞查詢的可搜索加密方案，通過使用編輯距離測量關鍵詞的相似度并構造模糊關鍵詞集合，使用戶在錯誤拼寫或者相近單詞下也能搜索到想要的內容。Liu等［40］在文獻［39］的基礎上進一步減小索引空間的大小。Vaanchig等［41］基于模糊函數和加密樹技術提出一種支持模糊關鍵詞查詢的PEKS方案，并在隨機預言機模型下證明該方案可以抵抗關鍵詞猜測攻擊，保證了服務端和用戶端更高效的檢索操作。樹形結構在檢索關鍵詞時能夠極大降低檢索時間，Shen等［42］為了實現多關鍵字搜索和搜索結果排序的目標，采用B+樹的索引結構，為關鍵詞集建立相似的集合作為樹的節點，與線性搜索相比效率更加出色。

除上述方式外，目前主流的檢索方式還有可驗證關鍵詞搜索［43］、相似度關鍵詞搜索、語義關鍵詞搜索、范圍查詢、子集查詢［44］等高效的查詢方式。

4.2 結構擴展

云時代環境下，大量無接觸、便攜式物聯網設備與互聯網融合導致大量數據在云端存儲。傳統PEKS 方案在面對當下熱點應用場景如電子醫療、視頻直播、區塊鏈、元宇宙時，方案的效率以及適用性捉襟見肘。本節針對PEKS 方案在新背景下歸納出的三大熱點需求，即：用戶權限代理分發、密鑰管理問題、細粒度搜索和訪問控制能力，給出相應功能擴展方案介紹，并對列出的方案進行性能和安全分析。

4.2.1 代理可搜索公鑰加密方案

當用戶A給用戶B發送一個由用戶B公鑰加密的密文郵件，但是用戶B由于某種原因無法接收到密文郵件，于是B通過授權服務器把搜索和解密密文郵件的權限授權給用戶C，C就可以使用自己的私鑰進行搜索和解密A發送給B的密文郵件。因此，數據之間的授權和共享功能在PEKS 方案中成為熱點。在過去共享數據明文信息時，需要授權服務器全程參與，導致效率低下?！按怼钡母拍钍状斡葿laze等［45］提出，代理指通過一個可信的代理服務器將數據所有者上傳至云服務器的密文運用包含被授權用戶密鑰的信息進行二次加密，數據所有者就可以授權給他想要分享的數據使用者，數據使用者可以通過自己私鑰產生搜索陷門。Shao等［46］在2010 年基于“代理”的概念首次結合PEKS 加密特性，提出可搜索代理重加密（Proxy Re-Encryption with Keyword Search，PREKS）概念，PREKS 模型如圖3 所示。與原始的代理重加密方案不同，PREKS 模型中被授權的數據使用者可以給云服務器提供關鍵詞搜索功能，發送關鍵詞陷門對重加密密文進行關鍵詞檢索。文獻［46］中構造了一種能夠從發送方到接收方和從接收方到發送方的雙向代理PREKS 方案，并在隨機預言機模型下證明了方案的安全性。

圖3 PREKS系統模型Fig.3 PREKS system model

Wang等［47］進一步擴展文獻［46］的研究，提出了支持連接關鍵詞搜索的受限單向代理重加密的方案，查詢能力顯著提高，并在隨機預言機模型下證明了方案的安全性。Guo等［48］又進一步在標準模型而并非隨機預言機模型下設計了雙向的指定服務器代理重加密方案，該方案支持搜索結果正確性的驗證。如今量子計算機的出現對密碼安全性產生極大挑戰，為進一步提高方案安全性，能夠抵抗量子計算機攻擊，Yang等［49］也在標準模型下給出安全證明，提出一個新的抗量子的PREKS 方案。對以往只針對指定親近的單個用戶授權的場景下，Hong等［50］提出一種基于屬性的PREKS 方案，提高了在多用戶場景下的靈活性。牛淑芬等［51］和Xu等［52］就電子醫療應用場景，提出了具有指定關鍵詞的代理重加密方案，數據方通過指定的關鍵詞進行代理共享，而不是把權限全部移交給被授權用戶。在授權多用戶的同時還指定每個用戶的權限范圍，提高了密文數據的安全性。PREKS 中涉及到三個實體，構造者通過實施不同目標的安全模型以更好地抵御安全攻擊，但針對不同目標的安全性缺少通用的方案。未來PREKS 的研究趨勢是設計一個通用的安全模型以抵抗現有的攻擊，并在不進行重加密的模式下對被授權用戶撤銷權限。

表2 為比較有代表性的方案之間的性能對比。其中：E為模冪運算時間；e為雙線性對運算時間；h為一般哈希運算時間；H為哈希到點運算時間；l為關鍵詞數量；n為密文數量；m為用戶查詢關鍵詞數量。表中的假設包括：決策雙線性Diffie-Hellman（Decisional Bilinear Diffie-Hellman，DBDH）、q-雙線性Diffie-Hellman反演（q-Bilinear Diffie-Hellman Inversion，q-BDHI）、商決策 雙線性Diffie-Hellman（quotient Decisional Bilinear Diffie-Hellman，qDBDH）、哈 希Diffie-Hellman（Hash Diffie-Hellman，HDH）、改進雙線性Diffie-Hellman（modified Bilinear Diffie-Hellman，mBDH）、qDBDHI（q-Decisional Bilinear Diffie-Hellman Inversion）、l-ABDHE（l-Augmented Bilinear Diffie-Hellman Exponent）、wIND-CCA（weakly IND Chosen Ciphertext Attack）。

表2 PREKS方案對比Tab.2 PREKS scheme comparison

4.2.2 基于身份的可搜索公鑰加密方案

基于身份加密（IBE）的概念最早由Shamir［53］在1984 年提出，“身份”的概念指加密公鑰中包含能夠證明用戶身份的信息，這些信息可以是電子郵箱、電話號碼、IP 地址、或者身份識別碼等，私鑰則可以通過密鑰生成中心根據用戶的身份信息生成?；谏矸莸目伤阉鞴€加密（PEKS based on Identity-Based Encryption，PEKS-IBE）解決了傳統的基于PKI（Public Key Infrastructure）加密中的證書管理問題。PEKSIBE 的基本模型如圖4 所示。

圖4 PEKS-IBE系統模型Fig.4 PEKS-IBE system model

Boneh等［4］設計出BF-IBE 系統構造了實用的PEKS-IBE方案，為證書管理提供了緩解方案；但該方案基于雙線性對構造，在性能上達到實際生產比較困難。Di Crescenzo等［15］在文獻［54］的基礎上提出第一個不需要雙線性對的PEKSIBE 方案，并在隨機預言機模型下證明了方案的安全性。針對通信上帶來的開銷，Wang等［25］給出了無安全信道的PEKS-IBE，允許多用戶在點對點組中共享云服務器的數據，降低了網絡中的通信代價。Emura等［55］提出了一種支持關鍵詞可撤銷的匿名身份加密的PEKS 方案，在一定程度上抵抗陷門泄露帶來的安全隱患。Wu等［56］首先提出支持連接關鍵詞的PEKS-IBE，但該方案不滿足密文的不可區分性。王少輝等［57］基于文獻［56］提出了指定測試者的PEKS-IBE 方案，解決了不完全滿足密文不可區分性的問題，證明了抵抗離線關鍵詞猜測攻擊的充分條件是密文不可區分性。牛淑芬等［58］針對電子郵件加密系統中存在的離線關鍵詞猜測攻擊問題，采用加密關鍵詞和生成搜索陷門同時認證的方式，提出了具有陷門和密文不可區分性安全的指定服務器的PEKS-IBE。IBE 對密鑰和證書管理提供解決策略，但目前PEKS-IBE 面對動態更新的密鑰，如何設計出計算代價更小、更適合便攜式物聯網設備的方案成為新的需求。

表3 為上述幾種方案的計算開銷對比。其中：Tsm為標量乘法運算時間；l為關鍵詞數量；n為共享數據的用戶數；λ為安全參數；J為雅可比符號。表中假設包括：QIP、DBDH、BDH 和計算性Diffie-Hellman（Computational Diffie-Hellman，CDH）。

表3 PEKS-IBE方案對比Tab.3 PEKS-IBE scheme comparison

4.2.3 無證書可搜索公鑰加密方案

AI-Riyami等［59］在2003 年首次提出無證書公鑰密碼體制。在無證書公鑰密碼體制中，用戶私鑰由密鑰生成中心（Key Generate Center，KGC）和用戶共同生成，是另一種有效解決基于公鑰的密碼體制中存在的密鑰托管和證書管理問題的途徑。無證書PEKS 模型如圖5 所示，私鑰由KGC 和用戶共同生成，數據擁有者將密文上傳者至云中，擁有檢索權限的數據用戶根據想搜索的關鍵詞生成陷門，云服務器執行匹配操作返回給數據用戶。

圖5 無證書PEKS系統模型Fig.5 Certificateless PEKS system model

Peng等［60］首次將無證書密碼體制引入PEKS 方案中，提出一種不需要安全信道的無證書PEKS 方案。Zheng等［61］基于線性決策問題提出一種高效的標準模型下可證明安全的無證書PEKS 方案。面對關鍵詞查詢功能的擴展問題，Ma等［62］提出無安全信道的支持多關鍵詞的無證書可搜索加密方案，并在隨機預言機模型下證明了方案的安全性。隨后Ma等［63-64］在智慧醫療和移動醫療背景下又提出兩種高效的無證書加密方案，解決了密鑰托管難題，并在隨機預言機模型下證明該方案可以抵抗關鍵詞猜測攻擊。Wu等［65］在醫療物聯網（medical Internet of Things，mIoT）應用場景下，提出一種指定服務器的可認證的無證書可搜索公鑰加密方案，在醫療云物聯場景下給出了密鑰和證書管理的新思路。Lu等［66］提出了一種無需雙線性對的無證書可搜索公鑰加密方案，極大提高了方案的計算效率，并在隨機預言機模型下證明了方案的安全性。張玉磊等［67］基于公鑰加密等值測試，實現密文的等值比較，提出支持關鍵詞搜索的無證書密文等值測試加密方案。方案在檢索時自動判斷是否接收者需要的信息，根據判斷結果進行等值測試，避免了無效測試，提高了檢索效率。

表4 給出了上述幾種無證書PEKS 方案的性能比較。其中：CI 是Ciphertext Indistinguishability假設，DLIN 是Decisional Linear 假設。

表4 無證書PEKS方案對比Tab.4 Certificateless PEKS scheme comparison

4.2.4 基于屬性的可搜索公鑰加密方案

Sahai等［68］在2005 年提出基于屬性的加密（Attribute-Based Encryption，ABE）概念，把用戶的信息元素作為屬性，形成一系列屬性集。PEKS 方案大多采用傳統公鑰加密實現，需要發送方使用每一個接收方的公鑰加密數據，生成多個密文，造成資源浪費，如圖6（a）所示。在ABE 中，發送方將滿足所有用戶的訪問策略嵌入密鑰，然后通過滿足所有用戶的公共參數對數據加密生成唯一的密文，如圖6（b）所示。接收方私鑰和屬性相關聯形成新的私鑰，如果接收方的屬性與訪問策略集中的信息匹配時，就可以解密。根據與訪問策略集相關的是密文還是私鑰，基于屬性加密還可分為密鑰策略屬性基加密（Key-Policy Attribute-Based Encryption，KPABE）和密文策略屬性基加密（Ciphertext-Policy Attribute-Based Encryption，CP-ABE）兩種方式。

圖6 傳統公鑰加密和ABE的對比Fig.6 Comparison of traditional public key encryption and ABE

Han等［69］基于弱匿名ABE 的概念設計了一個多用戶下的基于屬性公鑰可搜索加密（PEKS bsed on Attribute-Based Encryption，ABEKS）方案。Zheng等［70］引入可驗證屬性基，設計了可以通過訪問策略進行檢索外包數據和驗證服務器是否進行正確檢索的ABEKS。但是此方案需要建立安全信道，開銷成本較大。Li等［71］設計了將密鑰分發外包的ABEKS 方案，只有當用戶的訪問策略滿足相應的屬性時，用戶才能解密密文，減少了開銷成本。2017 年Zhu等［72］設計實現支持模糊關鍵詞搜索和密文策略屬性基的ABEKS 方案。Cao等［73］提出基于模糊密文策略屬性的可搜索加密方案，減小了抵抗服務器提供商和數據用戶之間碰撞攻擊程度，提高了安全性。Miao等［74］設計了可以抵抗離線關鍵詞猜測攻擊的ABEKS 方案。ABE 的引入給PEKS 方案提供了細粒度的訪問控制功能，在會員付費頻道、用戶權限控制、移動物聯網等場景都有很好的應用前景。目前ABEKS 大多基于CPABE 提出，未來針對KP-ABE 的方案應用也是一種趨勢。

表5 給出了上述方案的性能和安全性的分析比較。其中：BDH 是雙線性 Diffie-Hellman 假設；SeS 為Selective Security；N為數據所有者的訪問控制策略中涉及的屬性數量；S為數據用戶的屬性編號。

表5 ABEKS方案對比Tab.5 ABEKS schemes comparison

4.3 應用領域擴展

4.3.1 區塊鏈

由于區塊鏈的去中心化、透明、可溯源、不可篡改等特性，越來越多的學者將可搜索公鑰加密技術與區塊鏈技術結合以提高加密的安全性。2019 年，劉格昌等［75］提出一種基于可搜索加密的區塊鏈數據隱私保護機制，把加密數據放在鏈上，在交易單中增加關鍵詞的加密信息以進行關鍵詞檢索，用戶使用私鑰生成關鍵詞搜索陷門。將此方案運用到個人醫療數據區塊鏈系統的應用場景中，解決了個人醫療隱私信息的泄露等問題。同年，高夢婕等［76］也針對醫療場景提出了一種結合區塊鏈的可搜索加密方案，在密鑰分發時嵌入Shamir 秘密共享技術，利用智能合約技術進行密鑰的驗證和恢復，并給出了方案的安全性證明。牛淑芬等［77］針對密文檢索效率低的問題，提出一種基于B+樹結構的密文排序可搜索加密方案。通過區塊鏈技術解決多方信任的問題，利用B+樹的索引結構結合加權統計算法實現了多關鍵詞查詢結果的排序，提高了鏈上密文數據檢索的效率，并在隨機預言機模型下證明了該方案的安全性。

2020 年，杜瑞忠等［78］針對可搜索公鑰加密方案中常見的陷門安全問題，結合智能合約技術與PEKS 方案提出了基于區塊鏈的可搜索公鑰加密方案，解決了陷門不可區分性問題，證明了方案可以抵抗內部關鍵詞猜測攻擊。同年，閆璽璽等［79］提出了基于區塊鏈的可驗證的屬性基可搜索加密方案，實現了檢索結果的可驗證性，并依據區塊鏈的不可篡改性，保證了用戶不需要額外的驗證操作就可以得到正確結果，大幅提高檢索效率并降低計算開銷。Yang等［80］在加密文件上傳至云上的同時將加密索引放在區塊鏈中，保證了加密索引的防篡改、完整性和可追溯性；同時也保證了用戶在不需要任何第三方驗證的情況下即可獲得準確的搜索結果；此外，該方案在隨機預言機模型下證明可以抵抗內部關鍵詞猜測攻擊。2021 年，Sun等［81］為了在保護物流信息隱私安全的同時快速查詢物流信息，提出了可搜索和加密的物流信息區塊鏈數據查詢算法，解決了在時間更新后無法查詢加密數據的問題。PEKS 方案將密文、公鑰、用戶關鍵詞集或關鍵詞陷門等內容進行上鏈，將它擴展功能與區塊鏈領域技術相結合是當下和未來研究的熱點之一［82-83］。

4.3.2 智能電網

智能電網作為物聯網的新型應用受到學術界的廣泛關注。智能電網系統不僅可以通過傳感器和智能電表測量和收集用戶用電量數據，還可以通過強大的云計算平臺存儲和利用能源使用數據。隨著電力信息上傳到云端，這些數據的安全性和隱私性至關重要，于是越來越多的公司選擇將數據加密后外包到云服務器。2013 年，Wen等［84］提出一種基于加密計量數據的隱私保護范圍查詢（Privacy-preserving Range Query，PaRQ）方案以解決智能電網財務審計中的隱私問題。PaRQ 構造了基于隱藏向量加密的范圍查詢謂詞來加密數據的可搜索屬性和會話密鑰。2014 年，Li等［85］提出一種支持多關鍵詞范圍查詢的可搜索加密方案，解決了智能電網能源拍賣中買家和賣家的信息隱私和能源數據加密檢索的問題。2019 年Uwizeye等［86］為智能電網場景設計了一種新的連接關鍵詞搜索的無證書可搜索公鑰加密方案，降低了通信成本并在隨機預言機模型下證明了方案的安全性。同年，Eltayieb等［87］提出一種基于屬性的可搜索加密方案。此方案的加密階段和生成屬性控制策略階段均在離線狀態下執行，并且證明了能夠抵抗關鍵詞猜測攻擊。2021 年，Tur等［88］將混沌密碼和搜索加密技術嵌入電力系統之間的通信指令，實現了在線抵御網絡攻擊和關鍵詞猜測攻擊。

5 結語

本文對現有PEKS 方案的典型構造、安全問題、表達方式、功能擴展和應用領域展開敘述。在云計算和物聯網的時代大背景下，PEKS 的研究越來越成熟，但依然是學者們研究的熱點。各種PEKS 方案仍然有許多缺點或問題待解決。

1）搜索表達方式：在現有的PEKS 方案上構造更加高效且復雜的搜索查詢方式，不僅支持單關鍵詞，還要支持多關鍵詞、字符串、模糊關鍵詞、語義關鍵詞、子集搜索等檢索方式。然而大多數搜索方式的改進都是以效率和安全性為代價，致力于協調統一將是未來研究的重點之一。

2）安全性和效率：現有的PEKS 方案大都在隨機預言機模型下進行安全性證明，具有局限性，在實際應用中不一定安全。未來的PEKS 方案將著重在標準模型下給出安全性證明，不僅要求滿足離線關鍵詞猜測攻擊，還要滿足在線的關鍵詞猜測攻擊。同時，現有的大部分PEKS 方案都基于雙線性對困難問題設計，計算開銷較大，如何構建一個高效的無雙線性對的PEKS 方案且在標準模型下給出普適的安全性證明仍是一個亟待解決的問題。

3）抗量子安全：隨著量子計算機的發展，許多基于傳統數學困難問題的PEKS 方案的安全性將受到威脅。如何設計能夠抵抗量子攻擊的PEKS 方案將是未來重點研究的方向。

面對中央處理器（Central Processing Unit，CPU）算力不斷提升和數據量飛速增長，對PEKS 技術進行幾個方面的展望。

1）多源數據：隨著多媒體信息以爆炸式的速度增長，尤其是以視頻和圖像為代表的多媒體信息。為了保護數據隱私，包含敏感內容的數據信息在上傳到云端之前需要進行加密。然而，如何在加密數據上查詢所需的視頻或圖像成為一個棘手的問題，未來可以考慮應用PEKS 處理此類問題。

2）基于格的PEKS：隨著量子計算的發展，傳統的密碼算法將面臨巨大的挑戰，很容易被量子計算機攻擊，因此，有必要設計一種能夠抵抗量子攻擊的密碼算法?；诟竦拿艽a系統由于效率和概念上的簡單性，在后量子算法中變得越來越流行。學術界對此已有研究［89-90］，未來迫切需要構建一種高效、安全的基于格的PEKS 方案。

3）輕量級的PEKS：在實際的工業物聯網應用中，大多數的設備均為輕量級的物聯網設備，例如，傳感器、集線器或微型移動設備等，這些設備大多僅具有有限的硬件計算能力和信號傳輸能力?？紤]到這些輕量級設備的計算能力，加入加密算法時必須采用輕量級的加密標簽生成算法，使算法具備較低的計算開銷和通信開銷，從而達到降低能耗、延長電池使用時間的目的。因此，設計出符合物聯網環境下的輕量級可搜索加密方案將是可搜索加密未來的研究任務之一。