可证明安全的基于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 安全的公钥加密算法及相应的非交互零知识证明方法，在具体实施时根据实际的硬件支持情况选择高效的对应算法来实现整个方案.

作者贡献声明：刘永志负责完成实验和数据分析，并撰写论文初稿；秦桂云负责方法调研，并参与部分论文撰写；刘蓬涛参与方案的实验设计和论文修改；胡程瑜提出方案的概念、设计方法和证明思路，并修改论文；郭山清提出指导意见并参与论文修改.