可證明安全的基于SGX 的公鑰認證可搜索加密方案

劉永志 秦桂云 劉蓬濤 胡程瑜,3,4 郭山清,3,4

1 （山東大學網絡空間安全學院 山東青島 266237）

2 （山東政法學院網絡空間安全學院 濟南 250014）

3 （密碼技術與信息安全教育部重點實驗室（山東大學） 濟南 250100）

4 （泉城實驗室 濟南 250103）（liuyongzhi@mail.sdu.edu.cn）

云存儲具有低成本、可擴展、部署快、容量大等優勢，越來越多的企業和組織傾向于把數據存放在云端，這使云存儲成為未來數據存儲的發展方向.然而，為了保護數據隱私，數據發送到云服務器存儲之前，通常需要進行加密處理.為了解決在密文數據上的搜索問題，可搜索加密（searchable encryption, SE）技術應運而生.作為可搜索加密的一個分支，公鑰可搜索加密（public key encryption with keyword search, PEKS）體制[1]主要用于解決對稱可搜索加密（symmetric searchable encryption, SSE）中復雜的密鑰管理問題，以滿足接收方對存儲在云服務器中的不同發送方的數據進行關鍵詞搜索的需求.

PEKS 方案的框架如圖1 所示，在這個場景中，有云服務器、文件發送方和文件接收方3 個行為主體.一個完整的搜索過程為：文件發送方使用文件接收方的公鑰生成關鍵詞的PEKS密文，并將PEKS密文連同文件密文一起發送給云服務器；文件接收方通過自己的私鑰生成對某個關鍵詞的搜索陷門，將其發送給云服務器；由云服務器執行匹配算法進行搜索，最后將搜索結果返回給文件接收方；根據搜索結果，文件接收方可以選擇性地下載文件密文，并在本地進行解密以獲取原文件.

Fig.1 PEKS system framework圖1 PEKS 系統框架

雖然已有大量的研究工作在一定程度上解決了PEKS 在效率、安全性方面的問題，但PEKS 仍然面臨一些安全性和實用性方面的挑戰.在安全性方面，PEKS 方案容易受到關鍵詞猜測攻擊（keyword guessing attack，KGA）[2]，也較少考慮確定性陷門生成算法導致的搜索模式泄露以及前向安全等安全問題.在實用性方面，由于數據需要在云用戶之間共享，例如，一個接收方可能會將從發送方得到的數據分享給另一個用戶，因此，有必要考慮關鍵詞搜索能力的轉移，在多用戶環境下構建PEKS 方案，即需要考慮關鍵詞密文的重加密.總之，如何提高當前PEKS 方案的安全性和實用性，是研究人員必須考慮的問題.

針對PEKS 方案面臨的安全性和實用性問題，本文提出了一種基于軟件防護擴展（software guard extensions，SGX）的公鑰認證可搜索加密（public key authenticated encryption with keyword search，PAEKS）方案，主要貢獻有4 個方面：

1）修改了PAEKS 原始模型中的陷門生成算法定義，使之更符合云存儲的實際應用場景；給出了PAEKS 方案的增強安全性定義，包括一個允許敵手詢問挑戰關鍵詞密文的密文不可區分性定義、一個陷門不可區分性定義和一個搜索模式隱私性定義.滿足這3 種安全性定義的PAEKS 方案可抵抗關鍵詞猜測攻擊并能對外部攻擊者隱藏陷門中的關鍵詞隱私信息.

2）設計了一個基于SGX 的支持單關鍵詞搜索的公鑰認證可搜索加密方案PAEKS-SGX.該方案借鑒Naor-Yung 構造選擇密文攻擊下的不可區分（indistinguishability under chosen ciphertext attack，IND-CCA）安全性的公鑰加密方案的范式[3]，關鍵詞密文由關鍵詞、文件發送方對關鍵詞的簽名在2 個不同公鑰下的公鑰加密（public key encryption，PKE）密文以及一個零知識證明構成.驗證階段由運行在云服務器的飛地搜索程序完成，文件接收方私鑰經過可信信道傳遞到飛地中.我們對方案進行了正式的安全性分析，通過分析證明，當所使用的公鑰加密方案具有選擇消息攻擊下的不可區分性（indistinguishability under chosen message attack，IND-CPA）、簽名方案具有選擇消息攻擊下的存在不可偽造性（existential unforgeability under chosen message attack，EUF-CMA）以及零知識證明方案具有完備性、可靠性和零知識性等特性時，本文方案具有密文不可區分性、陷門不可區分性以及搜索模式隱私性等.

3）在真實環境中進行了完整的實驗，并和其他方案進行了全方面的對比.實驗結果表明，PAEKSSGX 是可行且有效的，同時在效率方面表現出色.

4） PAEKS-SGX 可以很方便地進行擴展，從而支持多關鍵詞搜索等復雜搜索、搜索能力的分享傳遞以及一些更高的安全性.作為示例，本文介紹了如何擴展方案支持多關鍵詞搜索、如何擴展方案到多用戶場景以及如何支持前向安全性.

1 相關工作

1.1 公鑰（認證）可搜索加密

2004 年，Boneh 等人[1]將SE 技術應用到公鑰場景中，提出了PEKS 的概念，并基于身份基加密（identity-based encryption， IBE）方 案 構 造 了 第1 個PEKS 方案.2005 年，Abdalla 等人[4]完善了PEKS 的一致性定義，提出了PEKS 方案與匿名IBE 方案之間的轉化關系，并探討了IBE 和PEKS 之間的安全關系.

2006 年，Byun 等人[2]指出PEKS 體制存在的關鍵詞猜測攻擊隱患，即當關鍵詞空間遠小于密鑰空間時，攻擊者可以用自行生成的PEKS 密文來匹配用戶的搜索陷門，以獲知用戶搜索的關鍵詞.之后，Baek 等人[5]在2008 年提出指定驗證人的PEKS 方案（searchable public-key encryption scheme with a designated tester，dPEKS），在生成關鍵詞密文的同時使用了云服務器公鑰，使得只有指定的云服務器具有進行關鍵詞密文和陷門匹配的權限.該方案在隨機預言機模型中被證明是安全的.Fang 等人[6]提出了一個更加高效的dPEKS 方案，并在標準模型下證明其安全性.2012 年，Xu 等人[7]提出使用模糊關鍵詞陷門進行初次搜索，并對返回的結果再利用精確關鍵詞陷門進行2 次匹配來抵御關鍵詞猜測攻擊.2010 年，Rhee 等人[8]在dPEKS 中引入陷門不可區分的概念，給出了dPEKS 的正式安全模型.但是，dPEKS 方案并不是通過阻止攻擊者構造關鍵詞密文來抵抗關鍵詞猜測攻擊，其安全性定義中一般假設指定驗證人是可信的，因此，在實際使用中，dPEKS 方案無法阻止內部攻擊者（指定驗證人）自己構造關鍵詞密文來進行關鍵詞猜測攻擊.

為了在無需指定驗證人的情形下解決PEKS 方案面臨的關鍵詞猜測攻擊問題，并解決dPEKS 方案無法抵抗內部攻擊者（指定驗證人）的關鍵詞猜測攻擊問題，2017 年，Huang 等人[9]提出了一個新的PAEKS的概念，即在生成關鍵詞密文時使用接收方公鑰和發送方私鑰，以保證服務器無法自己生成關鍵詞密文，從而有效地抵御關鍵詞猜測攻擊.隨后，Qin 等人[10]指出，Huang 等人[9]的PAEKS 的密文不可區分安全性不夠合理，不同于之前的PEKS，dPEKS 等，PAEKS 在關鍵詞密文生成時使用了發送方私鑰，而其單密文不可區分性不允許敵手在挑戰完之后繼續詢問挑戰關鍵詞的密文，所以并不能保證多密文不可區分性，從而存在安全隱患.因此，有必要重新考慮PAEKS 方案的密文不可區分性定義.Qin 等人[10]提出了多密文不可區分性定義.Huang 等人[9]和Qin等人[10]的PAEKS 方案的陷門生成算法都是確定性的，外部攻擊者可以通過2 個陷門是否相同來判斷搜索的關鍵詞是否相同.另外，文獻[9-10]中所使用的PAEKS 原始模型定義中，陷門生成算法需要用到發送方的公鑰.這并不符合云存儲的實際應用場景，因為接收方并不知道具體都有誰給他發送過數據（比如電子郵件），也就無法在生成搜索陷門時針對性地使用發送方公鑰.

在搜索能力共享（多用戶）方面，其基本的思路是利用代理重加密（proxy re-encryption, PRE）將關鍵詞密文轉換為新用戶的公鑰下的關鍵詞密文.Shao等人[11]將代理重加密和公鑰可搜索加密相結合，提出關鍵詞搜索代理重加密（proxy re-encryption with keyword search, PREKS）的加密原語，并在隨機預言機模型中證明了它的安全性.但是，該方案不能抵抗關鍵詞猜測攻擊.隨后，郭麗峰等人[12]給出一個有效的PAEKS 方案，該方案能夠抵制關鍵詞猜測攻擊，但需要指定驗證人.在Shao 等人[11]的方案中，擁有重加密密鑰的代理能夠將所有關鍵詞密文進行重加密，為了限制代理的權限，Fang 等人[13]結合條件代理重加密（conditional proxy re-encryption, C-PRE），提出了關鍵詞搜索條件代理重加密（conditional proxy reencryption with keyword search, C-PREKS）的概念，然而文獻[13]的方案也無法抵御關鍵詞猜測攻擊.為了更進一步限制代理的權限，實現細粒度的數據訪問控制，Chen 等人[14]將PREKS 與閾值密碼系統相結合，提出了關鍵詞搜索受限代理重加密（restricted proxy re-encryption with keyword search）的方案，但是此方案易受到關鍵詞猜測攻擊且陷門生成算法是確定的.

另外，很多方案不考慮針對外部攻擊者的陷門隱私性，關鍵詞陷門生成算法是確定性的，假如接收方和服務器之間不存在安全信道，這會導致外部攻擊者僅從2 次搜索的陷門就可以判斷接收方是否搜索的是同一關鍵詞.

1.2 軟件防護擴展

可信執行環境（trusted execution environment, TEE）是指通過軟硬件方法在中央處理器中構建的一個安全區域，提供一個隔離的、安全的執行環境，可以保證加載到該環境內部的代碼和數據的安全性、機密性和完整性[15].常見的TEE[16]包括Intel 軟件防護擴展、Intel 管理引擎（management engine, ME）、x86 系統管理模式（system management mode, SMM）、AMD內存加密（memory encryption）技術、AMD 平臺安全處理器（platform security processor, PSP）和ARM TrustZone技術.

軟件防護擴展是Intel 推出的指令集擴展，旨在以硬件安全為強制性保障，為用戶空間提供TEE[17].在SGX 中， 應 用 程 序 運 行 的TEE 被 稱 為 飛 地（enclave）.enclave 使 用 的 頁 面 和 數 據 結 構 由CPU 內部的內存加密引擎（memory encryption engine，MEE）[18]加密存儲在安全區頁面緩存（enclave page cache，EPC）中，這是系統內一塊被保護的物理內存區域，EPC 的訪問控制由安全區頁面緩存映射（enclave page cache map，EPCM）負責，除enclave 外的任何軟硬件都無法直接訪問.

Intel SGX 定 義 了 一 個 新 的CPU 模 式.叫 作enclave 模式.當CPU 訪問enclave 中的數據時，首先需要切換到enclave 模式，該模式下所有對內存的訪問都會被嚴格檢查；當enclave 主動退出時，CPU 就會退回到non-enclave 模式，并清空CPU 寄存器以防止數據泄露，這2 種模式的切換通過調用ecall/ocall接口來實現.當enclave 被中斷或被異常打斷時，CPU也會強制退回到non-enclave 模式，并可以在中斷或異常處理完成之后重新進入enclave.

Intel SGX 提供了一種enclave 安全性證明的技術，叫作SGX 遠程認證（SGX remote attestation）.通過 該技術，用戶不僅可以遠程驗證云服務器上enclave 的正確性和完整性，還可以和云服務器上enclave 通過Diffie-Hellman 密鑰交換協議建立一個安全的信道，實現秘密共享.

Intel SGX 還提 供了密封（sealing）策略，以確保在enclave 退出后保護數據的機密性和完整性.本質上來講，密封策略是一種數據加密技術，它提供了2種加密策略：基于enclave 身份的策略MRENCLAVE和基于signing 身份的策略MRSIGNER.前者會生成該enclave 獨有的密鑰，該密鑰密封的數據只有同一版本的同一enclave 才能解密；后者會基于enclave 密封授權方的簽名密鑰來生成一個密鑰，該密鑰密封的數據可以在同一授權方授權的多個不同版本的enclave 之間共享.需要注意的是，這2 種密鑰的生成都需要輸入當前設備的信息，這意味著密封的數據是無法從一臺設備共享給另一臺設備的.

1.3 基于Intel SGX 的公鑰可搜索加密方案

為了克服傳統的PEKS 方案存在的多方面安全隱患，Yoon 等人[19]提出了一種基于Intel SGX 的前向安全的PEKS 方案，他們定義了一個前向安全的PEKS 安全模型，并進行了安全性證明.然而他們的方案存在5 點不足：

1）其安全模型不是標準的PEKS 安全模型，而僅僅是SSE 安全模型的平凡遷移；

2）生成PEKS 密文時使用了SSE 場景下的索引作為文件的標識，這顯然是不合理的，因為文件發送方將文件共享給文件接收方之后，文件的標識應該由云服務器來管理，而不是文件發送方；

3）生成陷門的用戶私鑰和該用戶的公鑰沒有任何關系，因此該方案并不能被稱作標準的PEKS 方案；

4）該方案的搜索算法只匹配了一個PEKS 密文，并不是完整的搜索過程，而即使修改完整，該過程也需要對系統中所有文件的所有PEKS 密文進行遍歷，而不是在當某個文件的某個PEKS 密文匹配成功后就不再對該文件剩余的PEKS 密文進行匹配，因此在具體實現中該方案的效率很低；

5）在安全性上，該方案無法抵御關鍵詞猜測攻擊.

本文方案要充分考慮Yoon 等人[19]方案的不足，此外在具體方案實現上，我們還需要兼顧3 個問題：

1）兼容.enclave 是否支持本文方案所需的加密庫，比如OpenSSL，PBC 等.目 前Intel SGX 已 支 持Intel SGX SSL 和Intel GMP 這2 種庫，最終我們選擇使用Intel SGX SSL（集成了OpenSSL 1.1.1n）來實現本文方案.

2）內存.enclave 可使用的EPC 被限制到128 MB，并且只有93 MB 能夠被應用程序所使用，一旦超出這個限制大小，SGX 就會把一些EPC 頁轉化成不受保護的DRAM，這會引起很高的性能開銷.因此，需要在實驗中進一步降低應用程序的內存，具體的改進方案在4.2 節有詳細介紹.

3）性能.non-enclave 模式切換到enclave 模式時，需要將enclave 外部應用程序的上下文保存到TCS（thread control structure）數據結構中.enclave 模式切換回non-enclave 模式時，也會釋放TCS 數據結構，并清空CPU 寄存器.這2 種模式之間的切換會引起很高的運行開銷，因此要嚴格控制這種切換的次數.

2 預備知識

2.1 公鑰加密

公鑰加密方案[3]由3 個多項式時間算法組成，分別 為PKE.KeyGen，PKE.Enc，PKE.Dec.其 中，PKE.KeyGen是隨機密鑰生成算法，它以一個安全參數作為輸入，然后輸出一個公私鑰對（pk, sk）.PKE.Enc是概率加密算法，它接收消息m∈M和公鑰pk，并選擇隨機性，然后計算出密文c并輸出.PKE.Dec是確定性解密算法，它接收密文c和私鑰sk，解密成功是指輸出消息m；解密失敗，則輸出錯誤符號“ ⊥”.

IND-ATK（ATK 為CPA 或 CCA）安全是指選擇明文攻擊下的不可區分性和選擇密文攻擊下的不可區分性，是公鑰加密體制下的2 個安全定義.對于一個公鑰加密方案PKE的敵手 A=（A1,A2），其優勢是可忽略的（如果ATK 為CPA，敵手對解密預言機的訪問會被移除）.

2.2 簽 名

簽名方案[20]由3 個多項式時間算法組成，分別為S IG.KeyGen,S IG.S ign,S IG.Ver.其中，S IG.KeyGen是隨機密鑰生成算法，它以一個安全參數作為輸入，然后輸出一個公私鑰對（pk, sk）.SIG.S ig是簽名算法，它接收消息m∈M和私鑰sk，然后輸出一個簽名σ ←S IG.S ign(sk,m).S IG.Ver是確定性驗證算法，它接收公鑰pk、消息m和簽名 σ，簽名有效輸出1；反之輸出0.

EUF-CMA 安全是指選擇消息攻擊下的不可偽造性，是指任何概率多項式時間的敵手 A攻擊一個簽名方案SIG=(S IG.KeyGen,S IG.S ign,S IG.Ver)的優勢是可忽略的.

簽名預言機的工作原理為：

S ign(sk,m,Q)：

1）σ =Sign(sk,m)；

2）setQ=Q∪m；

3） r eturn σ.

2.3 非交互式零知識證明

設關系R是對（x, y）上的NP 關系，表示為LR={y|?xs.t.(x,y)∈R}.關系R的一個非交互式零知識（noninteraction zero-knowledge, NIZK）[21]由3 個算法組成，分別為Setup, P , V.其中，Setup是參數設置算法，它以一個安全參數作為輸入，輸出一個公共參考串（common reference string），記為CRS； P是證明算法，它以y∈LR的證明x作為輸入，輸出一個使得R（x,y）=1 的參數 π ←PCRS(x,y) ； V 是驗證算法，它以y和π作為輸出，驗證結果正確輸出1，反之輸出0.

零知識證明要求具備3 個安全特性：

1）完 備 性.對 于 任 意 的 (x,y)∈R，如 果CRS←S etup(λ)， π ←PCRS(x,y) ， 那么 V(y,π)=1.

2）可靠性.對于任何概率多項式時間的敵手A而言，

3）零知識性.存在一個有效的模擬器S=(S1,S2)，對于任何概率多項式時間的敵手A，使得其中，試驗ExptA(λ)和ExptSA(λ)的定義為：

其中 S′CRS(x,y,AUX)=S2CRS(y,AUX).

3 基于Intel SGX 的公鑰認證可搜索加密

3.1 PAEKS-SGX 模型

根據1.1 節的分析，我們修改了原始PAEKS 模型[1]的陷門生成算法，將其輸入中的發送方公鑰pkS修改為接收方公鑰pkR，使之更符合云存儲的實際應用場景.如圖1 所示，一個公鑰認證可搜索加密方案由6 部分組成.

1）PAEKS.S etup(λ).輸入安全參數 λ，輸出全局公開參數pp.

2）PAEKS.KeyGenR(pp).輸入公開參數pp，輸出接收者的公私鑰對 (pkR,skR）.

3）PAEKS.KeyGenS(pp).輸入 公 開 參 數pp，輸 出發送者的公私鑰對 (pkS,skS）.

4）PAEKS.PAEKS(pkR,skS,w).輸 入 接 收 者 公 鑰pkR、 發送者私鑰skS和關鍵詞w，輸出關鍵詞w的密文CT.

5）PAEKS.Trapdoor(skR,pkR,w′).輸 入 接 收 者 私鑰skR、 接收者公鑰pkR和 關鍵詞w′，輸出w′的陷門Tw′.

6）PAEKS.Test(pkR,pkS,CT,Tw′).輸入接收者公鑰pkR、 發 送 者 公 鑰pkS、 關 鍵 詞 密 文CT←PAEKS.PAEKS(pkR,skS,w)和 陷 門Tw′←PAEKS.Trapdoor(skR,pkR,w′)， 如果w=w′，輸出1，否則輸出0.

在本文中，我們借鑒了文獻[9]中提出的PAEKS方案的安全性定義，并對之做了一定的修改：

首先，文獻[10]指出文獻[9]中的密文不可區分性（ciphertext indistinguishability，CI-security）定義存在瑕疵：不允許敵手獲得挑戰關鍵詞的密文，在生成密文時使用了發送者私鑰的情形下，這導致滿足密文不可區分性的PAEKS 方案并不一定滿足多密文不可區分性.因此，我們修改了文獻[9]中的密文不可區分性定義，在生成挑戰關鍵詞密文后，允許敵手繼續詢問挑戰關鍵詞的密文，從而使該定義可以涵蓋多密文不可區分性.密文不可區分性定義了選擇關鍵詞攻擊，滿足CI-security 可以保證敵手無法從關鍵詞密文中獲得任何關鍵詞相關信息.

其次，針對陷門的安全性，我們認為，因為在文獻[9]的陷門隱私性（trapdoor privacy，TP-security）定義的詢問階段2 中限制了敵手無法對挑戰關鍵詞進行陷門和關鍵詞密文詢問，所以文獻[9]中的陷門隱私性定義無法完全涵蓋所有陷門隱私泄露情況，比如如果關鍵詞的陷門生成算法是確定性的，那么敵手就可以根據2 次搜索的陷門是否相同來判斷是否搜索的是同一關鍵詞.因此，我們將該定義改名為陷門不可區分性（trapdoor indistinguishability，TI-security），但保持正式定義不變.陷門不可區分性定義中隱含著允許敵手嘗試自己構造關鍵詞密文，因此如果方案同時滿足密文不可區分性和陷門不可區分性，則方案可以抵抗關鍵詞猜測攻擊.進一步地，為了涵蓋敵手通過比較2 個陷門而獲得的隱私信息，我們增加了一個新的安全性定義，即搜索模式隱私性（search pattern privacy，SP-privacy）.搜索模式隱私性可以確保敵手無法僅通過陷門來判斷搜索的是否是同一關鍵詞，從而避免向外部敵手泄露部分隱私.

CI-security 旨在防止外部攻擊者在不知道關鍵詞陷門的情況下獲取加密文件中所包含的關鍵詞信息.CI-security 由敵手 A 和挑戰者 C參與的游戲定義為5 個步驟：

1）系統建立.輸入安全參數 λ，挑戰者 C執行PAEKS.S etup(λ)生成公共參數pp，然后執行

并將生成的 (pp,pkR,pkS) 發 送給敵手 A.

2）詢問階段1.A 可以進行2 種詢問：

①關鍵詞密文詢問.A將想要查詢的關鍵詞w發送給 C ， C 執行算法CT←PAEKS.PAEKS(pkR,skS,w)，并將CT發回 A.

②陷門詢問.A將想要查詢的關鍵詞w發送給 C，C執行算法Tw←PAEKS.Trapdoor(skR,pkR,w) ，并將Tw發回 A.

3）挑戰階段.A發送2 個未在詢問階段1 查詢過的 關 鍵 詞w0，w1給 C ， C 隨 機 選 擇b∈{0,1}，執 行 算 法C*←PAEKS.PAEKS(pkR,skS,wb) ， 并 將 生 成 的C*作 為挑戰密文發回 A.

4）詢問階段2.在這一階段， A 可以繼續發送與詢問階段1 相同的詢問，但是在詢問陷門時所使用的關鍵詞w不能為w0或w1.

5）猜測.敵手 A 猜測 C 之前加密的是w0還 是w1，若猜對，則視為攻擊成功.

敵手 A在上述游戲中的優勢可以定義為函數:

定義1.如果對任何多項式時間敵手 A，存在一個可忽略的優勢 σ ，使得(λ)≤σ，那么PAEKS方案具備密文不可區分安全性.

TI-security 保證了內外部攻擊者在拿到一個不知道關鍵詞的陷門時，無法獲取該關鍵詞陷門中所包含的關鍵詞信息.TI-security 由敵手 A 和挑戰者 C參與的游戲定為5 個步驟：

1）系統建立.輸入安全參數 λ，挑戰者 C執行PAEKS.S etup(λ)生成公共參數pp，然后執行

并將生成的 (pp,pkR,pkS)發 送給敵手 A.

2）詢問階段1.A 可以進行2 種詢問：

①關鍵詞密文詢問.A將想要查詢的關鍵詞w發送給 C ， C 執行算法CT←PAEKS.PAEKS(pkR,skS,w)，并將CT發回 A.

②陷門詢問.A將想要查詢的關鍵詞w發送給 C，C執行算法Tw←PAEKS.Trapdoor(skR,pkR,w) ，并將Tw發回 A.

3）挑戰階段.A發送2 個未在詢問階段1 查詢過的 關 鍵 詞w0，w1給 C ， C 隨 機 選 擇b∈{0,1}，執 行 算 法T*←PAEKS.Trapdoor(skR,pkR,wb) ，并 將 生 成 的T*作為挑戰陷門發回 A.

4）詢問階段2.在這一階段， A 可以繼續發送與詢問階段1 相同的詢問，前提是所詢問的關鍵詞w不能為w0或w1.

5）猜 測.敵手 A 猜 測T*是w0還 是w1的陷 門，若猜對，則視為攻擊成功.

敵手 A在上述游戲中的優勢可以定義為函數：

定義2.如果對任何多項式時間的敵手 A，存在一個可忽略的優勢，使得(λ)≤σ，那么PAEKS方案具備陷門不可區分安全性.

SP-privacy 保證了外部攻擊者在僅拿到2 個陷門的情況下，無法判斷2 個陷門是否對應著同一個關鍵詞.SP-privacy 由敵手 A 和挑戰者 C參與的游戲定義為5 個步驟：

1）系 統 建 立.輸 入 安 全參數 λ ，挑 戰 者 C執行PAEKS.S etup(λ)生成公共參數pp，然后執行

并將生成的 (pp,pkR,pkS)發 送給敵手 A.

2）詢問階段1.A 可以進行2 種詢問：

①關鍵詞密文詢問.A將想要查詢的關鍵詞w發送給 C ， C 執行算法CT←PAEKS.PAEKS(pkR,skS,w)，并將CT發回 A.

②陷門詢問.A將想要查詢的關鍵詞w發送給 C，C執行算法Tw←PAEKS.Trapdoor(skR,pkR,w) ，并將Tw發回 A.

3）挑戰階段.A發送2 個未在詢問階段1 階段查詢過的關鍵詞w0，w1給 C ， C 隨機選擇b∈{0,1}，執行算法T*←PAEKS.Trapdoor(skR,pkR,wb) ， 并將 生成的T*作為挑戰陷門發回 A.

4）詢問階段2.在這一階段， A 可以繼續發送與詢問階段1 相同的詢問，在關鍵詞密文詢問中，要求所詢問的關鍵詞w不能為w0或w1；而在陷門詢問中則沒有限制.

5）猜 測.敵 手 A 猜測T*是w0還 是w1的陷門，若 猜對，則視為攻擊成功.

敵手 A在上述游戲中的優勢可以定義為函數：

定義3.如果對任何多項式時間的敵手 A，存在一個可忽略的優勢，使得(λ)≤σ，那么PAEKS方案具備搜索模式隱私性.

值得注意的是，在這3 個安全性定義中，均允許敵手訪問Test預言，該預言接收關鍵詞密文和陷門作為輸入，輸出匹配結果.

3.2 PAEKS-SGX 方案構造

由于SGX 為程序提供了一個可靠的執行環境執行敏感操作，一個自然的構造思路就是將私鑰加載到可信的執行環境enclave 中，利用私鑰來解密公鑰加密的密文.這樣，如果關鍵詞密文和陷門都是由接收方公鑰加密的密文（各自包含發送方和接收方用私鑰對關鍵詞所做的簽名），那么就可以從密文中分別解密得到關鍵詞明文進行比對.PAEKS 方案不僅設計思路比較直接和簡單，而且由于可以使用私鑰，所以很多擴展功能就比較容易實現，如第5 節將介紹的面向多用戶場景的擴展.但是，利用這個思路構造PAEKS 方案的一個關鍵問題是：如果在關鍵詞密文和陷門生成時只使用公鑰加密1 次，那么在進行安全性證明時，如果想要利用PAEKS 方案的敵手A來構造一個公鑰加密方案的敵手 B ， 那么 B作 為 A的挑戰者，在不知道所挑戰的公鑰方案私鑰的前提下，該如何為 A生成陷門（這里的陷門隱含匹配算法所使用的enclave 程序）.而使用類似Naor-Yung 的INDCCA 公鑰加密方案“雙加密”構造范式[3]，則可以在安全性證明時解決這個問題.

假設PKE=(KeyGen,Enc,Dec)是一個IND-CPA 安全公鑰密碼方案， ( P,V)是一個自適應安全非交互零知識證明系統，S IG=(KeyGen,S ign,Ver)是一個EUFCMA 安全的簽名方案.在本文方案中，假設關鍵詞長度相同①若長度不同，可采用哈希函數將關鍵詞映射為長度相同..PAEKS-SGX 方案（Setup,KeyGenR,KeyGenS,PAEKS,Trapdoor,Test）構造為：

1）PAEKS.S etup(λ).選擇公鑰加密方案PKE，數字簽名方案SIG和非交互零知識證明系統 (P,V)構造如算法1 所示的enclave 搜索程序E(Csearch)，在服務器上建立enclave 執行環境，其中的接收方私鑰為skR.sk1在搜索時由接收方與enclave 認證后上傳到enclave 中.

2）PAEKS.KeyGenR(pp).執行

設置接收者公私鑰對為

3）PAEKS.KeyGenS(pp).執行

(pk,sk)←S IG.KeyGen(λ)，設置發送者公私鑰對為

4）PAEKS.PAEKS(pkR,skS,w).設pkR=(pk1,pk2,pk3,r←{0,1}poly(λ))是接收方的公鑰.假設w是文件中的一個關鍵詞，首先執行sigw←S IG.S ign(skS,w)，然后計算PAEKS 密文CT=(C1,C2,Π)，其中

r1,r2是PKE.Enc算法使用的隨機性.

5）PAEKS.Trapdoor(skR,pkR,w′).設skR=(sk1,sk3)是接收方的私鑰.搜索某個關鍵詞w′時，計算搜索陷門Tw′=(,Π)，其中

r3,r4是PKE.Enc算法使用的隨機性，sigw′←S IG.S ign(sk3,w′)是 接收方利用私鑰sk3對w′的簽名.

6）PAEKS.Test(pkR,pkS,CT,Tw′).服務器將pkR,pkS,CT,Tw′傳 入enclave，執 行enclave 搜 索 程 序E(Csearch)，獲取匹配結果.

算法1.enclave 搜索程序E(Csearch).

輸入：接收方的公鑰pkR=(pk1,pk2,pk3,r)，發送方的公鑰pkS=(pk,rS) ，接收方的私鑰skR.sk1，關鍵詞密文CT，搜索陷門Tw′；

輸出：匹配時為1，不匹配時為0.

①ifV(pkS.rS,(CT.C1,CT.C2),CT.Π)==0

② r eturn 0；

③endi f

④ifV(pkR.r,(Tw′.Tw1′,Tw′.Tw2′),Tw′.Π)==0

⑤ r eturn 0；

⑥end if

⑦w1||sigw1←PKE.Dec(skR.sk1,CT.C1)；

⑧ifSIG.Ver(pkS.pk,sigw1,w1)==false

⑨ return 0；

⑩else

?w2||sigw2←PKE.Dec(skR.sk1,Tw′.)；

?ifSIG.Ver(pkR.pk3,sigw2,w2)==false

? return 0；

?else

? ifw1==w2

? r eturn 1；

?else

? return 0；

?end if

?end if

?end if

3.3 安全性證明

定理1.PAEKS-SGX 方案具備密文不可區分安全性.

證明.我們通過如下一系列不可區分的游戲來證明.

Game0是PAEKS-SGX 的密文不可區分安全性CI游戲.

Game1除了挑戰者生成的enclave 搜索程序之外，其他和Game0完全相同.在這個游戲中，挑戰者生成enclave 搜 索 程 序E(C′search)而 不 是E(Csearch)，如 算 法2所示.在E(C′search)中，用接收方在生成公私鑰對時未使用的私鑰sk2代 替sk1， 解密CT.C2和Tw′.Tw2′.

Game2與Game1相比，除了 (P,V)替換成其模擬器（記作 Π′），其他和Game1完全相同.

不難看出，E(C′search)和E(Csearch)具有相同的功能.由于Intel SGX 的安全機制，僅從輸入輸出來看，E(Csearch)和E(C′search)是 不 可 區 分 的.因 此，Game0和Game1是無法區分的.

Game1和Game2也是無法區分的.因為如果存在一個敵手 A可以區分Game1和Game2，那么相當于存在一個NIZK 的敵手 A′可以區分真實證明和模擬證明，這顯然是不成立的.

下面證明PAEKS-SGX 的敵手在Game2中的優勢是可以忽略的.

假設 A是Game2的一個敵手，它可以構造一個IND-CPA 安全 的PKE 方案的敵手 B ， B在IND-CPA安全游戲中與它的挑戰者 C交互的同時，作為Game2的挑戰者與 A交互.具體構造過程有5 個步驟：

1）系統建立.構造如算法2 所示的enclave 搜索程序E(C′search)，在服務器上建立enclave執行環境.挑戰者C執行 (pk1,sk1)←PKE.KeyGen(λ)，生成的公鑰pk1發送給敵手 B，私鑰sk1由 C自行保管；敵手B執行(pk2,sk2)←PKE.KeyGen(λ)，(pk3,sk3)←S IG.KeyGen(λ)和r←Sim1(λ)，私鑰B自行保管，接收者公鑰設為(pk1,pk2,pk3,r)，B生 成發送者公私鑰對(pkS,skS)，將公鑰(pk1,pk2,pk3,r,pkS)和構造的enclave搜索程序E(C′search)發 送給敵手 A.

2）詢問階段1.A 可以向 B請求2 個詢問.

①關鍵詞密文詢問.A將想要查詢的關鍵詞w發送給 B ， B執 行CT←PAEKS.PAEKS(pkR,skS,w)，并將CT發回 A.

②陷門詢問.A將想要查詢的關鍵詞w發送給 B，B 執 行Tw←PAEKS.Trapdoor(skR,pkR,w)， 并 將Tw發回 A.注意這里還允許 A詢問Test操作的返回結果.

3）挑戰階段.首先 A發送2 個關鍵詞w0，w1給 B，B使 用 私 鑰skS對w0，w1簽 名 得 到sigw0,sigw1，并 將(w0||||sigw0,w1||||sigw1) 作為挑戰明文轉發給C.在 B 與C的交互中， B 作為敵手接收來自 C的挑戰密文C←PKE.Enc(pk1,w||sigw;r0)； 然 后 計 算C2←PKE.Enc(pk2,w0||sigw0;r1) ，Π′←S im2(C1,C2)； 最后以 A 挑戰者的身份 計 算CT=(C1,C2,Π′)，將CT作為PAEKS 的挑戰密文發送給 A.

4）詢問階段2.在這一階段， A 可以繼續執行如詢問階段1 一樣的詢問，但是在詢問陷門時所使用的關鍵詞w不能為w0或w1.

5）猜測.敵手 B輸出敵手 A的輸出內容.

不難看出，如果 C 選擇 β=0（ 概率為 1/2），則此時B 為 A提供了一個完美的模擬；否則，通過非交互零知識證明系統的零知識性和可靠性， A在區分PAEKS 密文方面的優勢可忽略.因此， B作為PKE 方案的IND-CPA 敵手，其優勢相當于Game2中敵手A優勢的 1 /2.又因為所基于的PKE 方案是IND-CPA 安全的，即 B的優勢可忽略，所以敵手 A在Game2中的優勢也是可以忽略的.由于Game2和Game0不可區分，因此密文不可區分性游戲Game0中敵手的優勢可以忽略不計.證畢.

算法2.enclave 搜索程序E(C′search).

輸入：接收方的公鑰pkR=(pk1,pk2,pk3,r)，發送方的公鑰pkS=(pk,rS) ，私鑰sk2， 關鍵詞密文CT，搜索陷門Tw′；

輸出：匹配時為1，不匹配時為0.

①ifV(pkS.rS,(CT.C1,CT.C2),CT.Π)==0

② r eturn 0；

③endif

④ifV(pkR.r,(Tw′.Tw1′,Tw′.Tw2′),Tw′.Π)==0

⑤ r eturn 0；

⑥end if

⑦w1||sigw1←PKE.Dec(sk2,CT.C2)；

⑧ifSIG.Ver(pkS.pk,sigw1,w1)==false

⑨ r eturn 0；

⑩else

?w2||sigw2←PKE.Dec(sk2,Tw′.Tw2′)；

?ifSIG.Ver(pkR.pk3,sigw2,w2)==false

? r eturn 0；

?else

? ifw1==w2

? r eturn 1；

?else

? r eturn 0；

?end if

?end if

?end if

定理2.PAEKS-SGX 具有陷門不可區分性.

證明.可以看出陷門的生成過程實際上就是Naor-Yung 的IND-CCA 公鑰加密構造范式[3]中加密明文w′||sigw′的過程，而陷門不可區分性的定義與INDCCA 安全性的定義是類似的.所以在敵手無法自己構造關鍵詞密文情況下，可以利用Naor-Yung 范式[3]的證明思路證明我們方案的陷門不可區分性.具體證明過程不再詳述.

接下來證明，若敵手嘗試構造挑戰關鍵詞的密文并能通過挑戰陷門Tw’的測試，那么可以構造一個具有EUF-CMA 安全性的簽名方案SIG 的敵手，從而打破簽名方案SIG 的EUF-CMA 安全性.由于簽名方案的敵手打破EUF-CMA 安全性的優勢是可以忽略不計的，所以PAEKS-SGX 中敵手無法自己構造關鍵詞密文.所以綜合可知PAEKS-SGX 具有陷門不可區分性.證畢.

下面我們介紹EUF-CMA 安全簽名方案敵手的具體構造過程.

假設 A是陷門不可區分性游戲的敵手，嘗試構造挑戰關鍵詞的密文， B是我們想要構造的EUFCMA 安全簽名方案的一個敵手，它在EUF-CMA 安全游戲中與它的挑戰者 C交互的同時，作為挑戰者與A交互.在EUF-CMA 安全性游戲中執行算法(sk,pk)←S IG.KeyGen(λ)，生成的私鑰sk自行保存，公鑰pk發送給它的敵手 B.然后 B執行

私鑰自行保存，將pkR=(pk1,pk2,pk3,r)作為接收方的公鑰發送給它的敵手 A.同樣， B還 要將pkS=pk作為發送方公鑰發送給敵手 A.當敵手 A 向 B進行關鍵詞密文詢問時， B向它的挑戰者 C詢問對該關鍵詞的簽名，然后生成關鍵詞密文；當敵手 A 向 B進行陷門詢問時，由于 B自己生成接收者的公私鑰對，所以直接利用接收者私鑰生成陷門.最終，對于挑戰陷門，如果敵手 A 通過構造關鍵詞密文CT=(C1,C2,Π)，其中

并通過Test成功判斷陷門中的關鍵詞，我們可知其中的簽名sigw必然可以用發送方公鑰進行正確的驗證，即敵手 A成功地對挑戰關鍵詞構造了在發送者私鑰下的簽名sigw，即可打破簽名方案的EUF-CMA安全性.

定理3.PAEKS-SGX 具有搜索模式隱私性.

證明.首先，由于SGX 的安全特性，enclave 中的搜索程序是安全可靠的.其次，同定理2 的證明，可以看到關鍵詞w′的陷門實際上就是Naor-Yung 的IND-CCA 公鑰加密構造范式中加密明文w′||sigw′后得到的密文[3].如果敵手僅通過關鍵詞陷門就能判斷陷門中是否是同一關鍵詞，那么實際上相當于在利用Naor-Yung 范式構造的IND-CCA 方案中可以通過挑戰密文區分挑戰明文，也就打破了Naor-Yung 范式的IND-CCA 安 全 性.因 此，PAEKS-SGX 具 有 搜 索 模式隱私性.證畢.

3.4 密鑰管理

由對PAEKS-SGX 的描述可以看到，我們構造的enclave 搜索程序的正確運行需要文件接收方的私鑰，因此如何對該私鑰進行安全有效地管理，是需要考慮的一個重要問題.PAEKS-SGX 采用Intel SGX 遠程認證技術和Intel SGX 密封技術，給出了一個行之有效的解決方案.該方案中，接收方可以在初始時將其私鑰skR.sk1用私鑰傳遞過程發送到enclave 搜索程序中，然后enclave 可將該私鑰利用密封技術加密保存在硬盤中對應存儲位置.當后續再需要搜索時，enclave 可以從硬盤中將密封的接收方私鑰讀入enclave 并解封得到skR.sk1.

1）私鑰傳遞.通過Intel SGX 遠程認證技術，用戶可以和云服務器上的enclave 通過Diffie-Hellman 密鑰交換協議建立一個安全的信道，文件接收方可以通過此信道將私鑰發送到云服務器的enclave 搜索程序中.

2）私鑰保存.對于enclave 來說，其本身是沒有狀態的，當云服務器關機、重啟或應用程序退出時，enclave 就會被銷毀，此后，其中的所有內容都會丟失，因此安全地將其中的數據如私鑰等保存到enclave 外的非可信內存中是必要的.通過Intel SGX 密封技術，我們可以實現這個目的.在接收到文件接收方發送的私鑰之后，enclave 搜索程序可以使用MRENCLAVE或 MRSIGNER 將其加密，然后保存到enclave 之外的地方，比如硬盤中.

3）私鑰加載.在enclave 搜索程序中，可以調用ecall 接口從硬盤中讀取密封的私鑰，然后在enclave中進行解密.為了降低ecall 引起的CPU 模式切換開銷，我們將最近使用的私鑰保存到私鑰緩沖區，每次調用ecall 接口讀取私鑰之前，先檢查所需的私鑰是否在緩沖區，然后再選擇是否去硬盤中讀取.同時為了節省enclave 的內存使用，使用LRU（least recently used）策略來定期刷新私鑰緩沖區.

3.5 PAEKS-SGX 方案實施架構

PAEKS-SGX 方案具體實施時的整體架構如圖2所示，該框架共有2 個行為主體，云服務器和用戶，其中，云服務器由云存儲、云應用和enclave 搜索程序3 部分組成.

Fig.2 The architecture of PAEKS-SGX圖2 PAEKS-SGX 架構

在云存儲中，我們只關注PAEKS-SGX 密文和密封的密鑰.在云應用中，我們簡單地將其劃分為主程序和文件加載器2 部分，其中主程序負責和enclave搜索交互，包括enclave 的創建、運行、中斷、銷毀等，文件加載器負責從云存儲中讀取文件.在enclave 搜索程序中，為了更直觀地表示，我們將其抽象為匹配器和密鑰管理器2 部分，其中匹配器執行公鑰可搜索加密的驗證階段，密鑰管理器負責將云應用發送的密鑰解封.用戶enclave 程序中，我們只表示了SGX 遠程驗證執行器，將其用于與云服務器上的enclave 搜索程序進行遠程驗證和建立安全信道來傳遞私鑰.

一般情況下，公鑰可搜索加密的驗證階段可由圖2 中的過程①～⑥來表示：首先用戶向云服務器發送搜索陷門，云應用從云存儲中讀取關鍵詞密文、用戶公鑰和密封的密鑰，并將它們發送給enclave.然后在enclave 中，密鑰管理器解封密鑰，匹配器執行公鑰可搜索加密的驗證算法，并將結果返回給云應用.最后，云應用銷毀enclave 搜索程序，并將搜索結果發送給用戶.

圖2 還表示了用戶enclave 程序和云服務器enclave 搜索程序之間的遠程認證過程.用戶可以通過遠程認證對運行在云服務器上的enclave 搜索程序的初始化、結構、代碼完整性等進行驗證，并可以將通過遠程認證建立安全信道來傳遞用戶私鑰.事實上，遠程認證需要使用云服務器上的一個身份公認的特殊enclave，稱為引用（quoting）enclave，由它創建用于平臺認證的EPID（enhanced privacy identification）.當enclave 搜索程序收到用戶enclave 的遠程認證請求時，首先需要執行EREPORT 指令，將身份和附加信息組合生成REPORT 結構，并使用引用enclave 的報告密鑰（REPORT KEY）生成一個MAC 并交由引用enclave 驗證身份.驗證通過后，引用enclave 會將其封裝成引用結構體QUOTE，并使用EPID 密匙進行簽名.最后將QUOTE 及其簽名一并發送給用戶enclave.用戶enclave 便可以驗證enclave 搜索程序的身份是否合法.為了突出本文方案的整體架構，遠程認證的細節在圖2 中我們并沒有展開闡述.

4 實驗結果與分析

本節將PAEKS-SGX 方案部署到真實環境中進行測試，并和其他方案進行對比，根據在關鍵詞密文生 成（PEKS/PAEKS）、陷 門 生 成（Trapdoor）、匹 配（Test）等方面的具體表現對PAEKS-SGX 進一步分析.

4.1 實驗環境及部署

測試環境配置為：支持Intel SGX 的主機，Windows 10，Intel?CoreTMi7-8700 CPU（6 核，3.20 GHz，12 MB 高速緩存），內存16.0 GB（15.8 GB 可用），SGX SDK 2.14，Intel SGX Driver 2.15.

PAEKS-SGX 的具體實施過程為：

1）部署enclave 中的代碼，主要包括算法1 的實現代碼（匹配器的核心代碼），以及遠程認證、密鑰封裝和讀入封裝密鑰并解封的代碼（密鑰管理器的核心代碼）.

2）接收方執行SGX 遠程認證建立安全信道，并將自己的私鑰通過安全信道發送給enclave，enclave將私鑰密封寫入相應文件（注意，該操作只需要執行1 次）.

3）當接收方對某個關鍵詞進行搜索時，過程有3 步：

①接收方在本地執行陷門生成算法，生成待搜索關鍵詞的搜索陷門發送給云服務器.

②云服務器首先調用密鑰管理器程序，將接收方的私鑰密封文件作為輸入，執行私鑰解封.需要說明的是，當云服務器收到某個用戶的1 次搜索請求時，會使用收到的搜索陷門對所有文件的關鍵詞密文進行匹配，即多次執行匹配器程序.因為匹配時使用的用戶私鑰是相同的，所以，對于1 次搜索請求，解封過程只需執行1 次，后續對所有關鍵詞密文的匹配則無需再次解封用戶私鑰.

③云服務器利用關鍵詞密文、搜索陷門、接收方公鑰以及文件對應的發送方公鑰作為輸入，調用enclave 里的匹配器程序，得到搜索結果.

4.2 實驗結果分析

PAEKS-SGX 實現中，本文的加密算法采用ElGamal公鑰加密算法，簽名算法采用ElGamal 簽名算法，零知識證明方案驗證ElGamal 加密的2 個密文是在不同公鑰下對同一明文的加密密文.PAEKS-SGX 和所有對比方案（Boneh 等人[1]的方案、Huang 等人[9]的方案和Qin 等人[10]的方案）均采用256 b 安全強度.由于對比方案均基于雙線性配對實現，因此本文基于PBC 庫對雙線性群上的基本元素操作進行測試，得出雙線性群上的基本操作時間，如表1 所示.

Table 1 Computation Time of Basic Element Operation表1 基本元素操作的計算時間

首先，我們分析用戶與SGX 進行遠程認證，enclave 密封用戶私鑰所需的時間.測試結果顯示，該過程的平均用時為3.3 s.雖然時間達到了秒級，但由于在整個系統生命周期，對于一個用戶來說，該過程只需執行1 次，所以我們認為這個時間消耗是可以接受的.

接下來我們從關鍵詞密文生成（PEKS/PAEKS）、陷門生成（Trapdoor）、匹配（Test）這3 個階段對所有方案進行測試.需要指出的是，在PAEKS 中，當我們把關鍵詞長度設定為256 b 且使用ElGamal 加密和簽名算法時，w||sigw的長度是關鍵詞w長度的3 倍，對w||sigw進行ElGamal 加密時需要將其分為3 組，各組對應1 個零知識證明.這也意味著在匹配算法中要合計驗證6 次零知識證明，時間消耗比較大.而且此時實際的關鍵詞密文和陷門長度也會擴大3 倍，即6組ElGamal 加密的密文和3 組零知識證明.因此我們對方案做了改進，在關鍵詞密文和陷門生成算法中，除了生成w||sigw的 密文外，還要計算Hash（w||sigw）的密文，其中Hash（·）是一個輸出長度為256 b 的哈希函數.我們不再計算針對w||sigw的密文的零知識證明，而是計算針對Hash（w||sigw）的密文的零知識證明.在enclave 里的匹配算法中，首先驗證該零知識證明，在驗證通過后解密得到w||sigw和Hash（w||sigw），然后利用哈希計算w||sigw的 哈希值，并與Hash（w||sigw）進行比較，比較通過后再進行簽名驗證.通過這種改進，匹配算法中零知識證明驗證的次數變為2，關鍵詞密文和陷門變為4 組ElGamal 加密的密文加1 組零知識證明，實際長度大約變為原來的1/2.各方案每個階段的執行時間見圖3.如圖3 所示，在PEKS/PAEKS中，所有對比方案耗時均超過30 ms，而 PAEKS-SGX速度僅為1.15 ms；在Trapdoor 中，所有對比方案耗時均在12 ms 以上， PAEKS-SGX 僅耗時1.15 ms；在最受關注的Test 中， PAEKS-SGX 僅需2.00 ms 即可完成單次驗證，而對比方案最快也需要6.51 ms.可見，PAEKS-SGX 在每個階段都具有明顯的速度優勢，這和PAEKS-SGX 沒有使用雙線性群的元素操作有很大關系.

Fig.3 Comparison of time costs in different schemes圖3 不同方案耗時對比

在上面的測試中， PAEKS-SGX 的匹配算法并未包含enclave 讀取接收方的私鑰密封文件并解封的操作.下面我們考慮包含私鑰讀取和解封操作，并分析服務器收到1 次搜索請求后完成搜索過程所需的時間.設當前待搜索的文件總數為N，每個文件的關鍵詞個數為M，我們首先測試了SGX 執行私鑰解封（含讀入封裝文件的過程）的時間，其平均用時為4.5 ms.當采用順序匹配的策略時，每個文件的關鍵詞匹配次數均值為M/2.所以，對比方案對1 個關鍵詞陷門執行匹配的總時間均值為各自匹配算法的執行時間乘以MN/2，即，均不小于6.51×MN/2 ms.而PAEKSSGX 對1 個關鍵詞陷門進行匹配時，總的匹配時間均值=一次私鑰解封的時間+單個關鍵詞密文匹配時間×MN/2 = 4.5+2.00×MN/2 ms.當MN較大時，一次私鑰解封的時間可以忽略不計，總匹配時間均值可視作2.00×MN/2 ms，所以PAEKS-SGX 在總的匹配時間上依然有著很大的優勢.

更進一步地，我們根據關鍵詞的數量變化，測試了不同數量的關鍵詞時相應算法的執行時間，結果如圖4～6 所示.

Fig.4 Comparison of time cost of PEKS/PAEKS generation in different schemes圖4 不同方案生成PEKS/PAEKS 耗時對比

Fig.5 Comparison of time cost of Trapdoor generation in different schemes圖5 不同方案生成Trapdoor 耗時對比

Fig.6 Comparison of time cost of Test generation in different schemes圖6 不同方案生成Test 耗時對比

如圖4～6 所示，PAEKS-SGX 的優勢是十分明顯的：在PEKS/PAEKS 生成階段生成1 000 個關鍵詞的密文時，PAEKS-SGX 耗時控制在1 s 左右，而其他方案則需要30 s 以上；Trapdoor 生成階段，PAEKS-SGX同樣具有領先其他方案至少10 倍以上的速度優勢；而在Test 階段，匹配1 000 個（關鍵詞，陷門）對時，PAEKSSGX 相比起其他方案仍然具有明顯的速度優勢.

在方案的通信量分析方面，表2 給出了PAEKSSGX 和3 個對比方案的關鍵詞密文大小和搜索陷門的大小.結果顯示，PAEKS-SGX 的通信量比對比方案要大.但我們認為，無論是關鍵詞密文大小還是陷門的大小都在幾百字節的量級，對于網絡通信和具有大容量存儲的云服務器來說，均是可接受的.

Table 2 Communication Overhead Comparison表2 通信量比較

5 方案擴展

PAEKS-SGX 具有易擴展的優勢，一些新的功能只需在現有方案的基礎上稍加修改即可.下面我們介紹如何擴展方案支持多關鍵詞搜索、如何擴展方案到多用戶場景以及如何支持前向安全性.

5.1 多關鍵詞搜索

PAEKS-SGX 可以擴展為支持多關鍵詞搜索功能.在進行多關鍵詞搜索功能的擴展時，首先，不能要求預先對關鍵詞排序；其次，不能在搜索陷門中暴露搜索的關鍵詞個數，即滿足搜索模式隱私性，且搜索陷門大小與待搜索的關鍵詞個數無關.

1）基本思路.在生成關鍵詞密文的時候，用所有關鍵詞計算1 個布隆過濾器BFw，然后為這個布隆過濾器生成關鍵詞密文.生成搜索陷門的時候，同樣使用待搜索的多個關鍵詞計算1 個布隆過濾器BF.對BF生成陷門，將enclave 搜索程序E(Csearch)的部分代碼稍作修改，解密之后，將比對關鍵詞的過程改為布隆過濾器的按位與操作，即BFr=BFw&BF， 若BFr==BF，則輸出1，完成對1 個文件的匹配過程.詳見算法3.

算法3.enclave 多關鍵詞搜索程序E(Csearchmul-kw).

輸入：接收方的公鑰pkR=(pk1,pk2,pk3,r)，發送方的公鑰pkS=(pk,rS) ，接收方的私鑰skR.sk1，關鍵詞密文CT，搜索陷門Tw′；

輸出：無.

① ifV(pkS.rS,(CT.C1,CT.C2),CT.Π)==0

② r eturn 0；

③end if

④ ifV(pkR.r,(Tw′.Tw1′,Tw′.Tw2′),Tw′.Π)==0

⑤ r eturn 0；

⑥end if

⑦BFw||sigBFw←PKE.Dec(skR.sk1,CT.C1)；

⑧ ifS IG.Ver(pkS.pk,sigBFw,BFw)==false

⑨ return 0；

⑩else

?BF||sigBF←PKE.Dec(skR.sk1,Tw′.Tw1′)；

? ifS IG.Ver(pkR.pk3,sigBF,BF)==false

? r eturn 0；

?else

? ifBFw&BF==BF

? r eturn 1；

?else

? r eturn 0；

?end if

?end if

?end if

2） PAEKS-SGX 的安全性.與單關鍵詞搜索的方案相比，多關鍵詞搜索的方案僅僅是將關鍵詞替換為布隆過濾器，然后對布隆過濾器生成關鍵詞密文、搜索陷門.因此不會影響方案的安全性.

需要指出的是，PAEKS-SGX 使用布隆過濾器存在假陽性率，且布隆過濾器的密文所需的存儲空間比單關鍵詞密文要大.例如，當系統內有1 000 個關鍵詞，假陽性率為10-6時，采用16 個不同的哈希函數，則對應的關鍵詞密文大約需要3 KB 的存儲空間.雖然這個存儲空間比單關鍵詞密文的存儲空間（如32 B）要大得多，但當1 個文件包含l個關鍵詞時，單關鍵詞搜索方案中的關鍵詞密文需要32lB 存儲空間，當l=100 時，所需存儲空間與多關鍵詞方案基本相同.因此，我們認為這個存儲空間的消耗是可以接受的.

5.2 多用戶場景

在傳統的公鑰可搜索加密場景中，文件發送方將數據分享給文件接收方后，只有文件接收方擁有合法的搜索能力，但有些情況下這也會帶來不便.

想象下面這個場景：文件接收方想在不下載文件的前提下，把從文件發送方收到的數據中的一部分分享給第2 個文件接收方，一方面要分享文件密文，另一方面還要分享關鍵詞密文，從而讓第2 個文件接收方有搜索能力.通常的云數據共享過程中，發送方會用一個對稱密鑰key對文件進行分組加密，然后將key用接收方公鑰加密發送給接收方.當接收方想將數據共享給另一個用戶時，只需將密鑰key用該用戶的公鑰加密發送給他即可.但是如何同時將文件搜索能力也分享給該用戶，是需要解決的問題.第1 個文件接收方不能把用于生成陷門的私鑰發給第2 個文件接收方，而重新生成的第2 個文件接收方可以搜索的關鍵詞密文則需要下載文件、抽取關鍵詞，會增加交互次數和通信負載.

上述場景中解決問題的關鍵在于關鍵詞密文的重加密，可以采用代理重加密的方式由云服務器將關鍵詞密文轉換為第2 個接收方可以搜索的密文.而在PAEKS-SGX 中，利用enclave 可以很方便地實現重加密過程.

如圖7 所示，上述場景共有4 個行為主體，分別是文件發送方、第1 個文件接收方、第2 個文件接收方和enclave 重加密程序，其中enclave 重加密程序的功能是將由第1 個文件接收方公鑰加密的關鍵詞密文轉換成由第2 個文件接收方公鑰加密的密文.第1個文件接收方將部分數據的關鍵詞搜索能力分享給第2 個文件接收方的具體操作是一個簡單的“解密再加密”的過程，即原始關鍵詞密文以及密封的第1個文件接收方私鑰由外部的非可信程序發送給enclave 重加密程序，在enclave 重加密程序中用第1個文件接收方的私鑰解密關鍵詞密文，再用第2 個文件接收方的公鑰加密得到新的關鍵詞密文.

Fig.7 Share of PAEKS-SGX ciphertext圖7 PEKS-SGX 密文共享

這樣，云服務器就擁有了第2 個文件接收方公鑰加密的關鍵詞密文，第2 個文件接收方也就擁有了合法的關鍵詞搜索能力.整個過程的安全性由enclave程序本身的安全特性所保證，核心操作也是在云端完成，無需多余的交互和通信負載.相比之前那些利用代理重加密的PEKS 方案，PAEKS-SGX 的這種擴展能夠在無需指定驗證人的情況下抵抗關鍵詞猜測攻擊，且滿足搜索模式隱私性，即陷門生成算法是隨機的.

5.3 前向安全性

前向安全性最早是在動態對稱可搜索加密方案（dynamic symmetric searchable encryption, DSSE）的構造中提出的，旨在確保用之前的搜索陷門無法搜索到新增加的文件.因為文件注入攻擊[22]這種攻擊方式的存在，如果DSSE 方案不具備前向安全性，敵手可以恢復所有文件所包含的關鍵詞，所以很多研究者都在研究如何構造支持前向安全性的DSSE 方案.而實際上，文件注入攻擊更容易施加在傳統公鑰可搜索加密的場景，因為文件注入時只需要用接收者的公鑰即可，這其實相當于一種關鍵詞猜測攻擊.但是，一個PEKS 方案可以抗關鍵詞猜測攻擊并不意味著一定具有前向安全性，因為即使敵手不能主動進行文件注入攻擊（如在公鑰認證可搜索加密方案中），敵手依然可以根據接收者之前發送的陷門以及匹配結果判斷后續的文件是否跟前面的文件具有相同的關鍵詞，進而當關鍵詞空間較小的時候可以通過搜索頻率來推測關鍵詞信息[23].

由此分析可知，前向安全性依然需要在抗關鍵詞猜測攻擊的PEKS 方案中被考慮，即我們的公鑰認證可搜索加密方案也需要考慮前向安全性.PAEKSSGX 的實現機制使得我們可以很方便地將其修改為具有前向安全性，只需要在關鍵詞密文和陷門生成時均加入時間戳信息，在匹配的時候對解密出的時間戳作比較，如果陷門時間戳早于關鍵詞密文時間戳，則enclave 中直接返回0 即可.

6 結束語

針對PEKS 方案的抵抗關鍵詞猜測攻擊以及PEKS 方案的搜索能力共享（多用戶）等問題，本文首次提出了一個在正式公鑰認證可搜索加密安全性模型下可證明安全的基于SGX 的PAEKS 方案，方案可抵抗關鍵詞猜測攻擊，具有搜索模式隱私性和易擴展性，能夠很方便地擴展到多用戶情形，支持較為復雜的搜索功能以及增強的安全性.實驗結果表明，相比于傳統的PEKS 方案以及傳統的PAEKS 方案，本文提出的PAEKS-SGX 具有較高的效率優勢.另外PAEKS-SGX 具有一定的通用性，可以基于任何可信執行環境、任意IND-CPA 安全的公鑰加密算法及相應的非交互零知識證明方法，在具體實施時根據實際的硬件支持情況選擇高效的對應算法來實現整個方案.

作者貢獻聲明：劉永志負責完成實驗和數據分析，并撰寫論文初稿；秦桂云負責方法調研，并參與部分論文撰寫；劉蓬濤參與方案的實驗設計和論文修改；胡程瑜提出方案的概念、設計方法和證明思路，并修改論文；郭山清提出指導意見并參與論文修改.