云存储具有低成本、可扩展、部署快、容量大等优势，越来越多的企业和组织倾向于把数据存放在云端，这使云存储成为未来数据存储的发展方向. 然而，为了保护数据隐私，数据发送到云服务器存储之前，通常需要进行加密处理. 为了解决在密文数据上的搜索问题，可搜索加密（searchable encryption, SE）技术应运而生. 作为可搜索加密的一个分支，公钥可搜索加密（public key encryption with keyword search, PEKS）体制^[1]主要用于解决对称可搜索加密（symmetric searchable encryption, SSE）中复杂的密钥管理问题，以满足接收方对存储在云服务器中的不同发送方的数据进行关键词搜索的需求.

PEKS方案的框架如图1所示，在这个场景中，有云服务器、文件发送方和文件接收方3个行为主体. 一个完整的搜索过程为：文件发送方使用文件接收方的公钥生成关键词的PEKS密文，并将PEKS密文连同文件密文一起发送给云服务器；文件接收方通过自己的私钥生成对某个关键词的搜索陷门，将其发送给云服务器；由云服务器执行匹配算法进行搜索，最后将搜索结果返回给文件接收方；根据搜索结果，文件接收方可以选择性地下载文件密文，并在本地进行解密以获取原文件.

图  1  PEKS系统框架

Figure  1.  PEKS system framework

下载: 全尺寸图片 幻灯片

虽然已有大量的研究工作在一定程度上解决了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）在真实环境中进行了完整的实验，并和其他方案进行了全方面的对比. 实验结果表明，PAEKS-SGX是可行且有效的，同时在效率方面表现出色.

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 re-encryption 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}\in \mathcal{M}$和公钥pk，并选择随机性，然后计算出密文c并输出. ${PKE}{. }{Dec}$是确定性解密算法，它接收密文c和私钥sk，解密成功是指输出消息m；解密失败，则输出错误符号“$\perp$”.

IND-ATK（ATK为CPA或 CCA）安全是指选择明文攻击下的不可区分性和选择密文攻击下的不可区分性，是公钥加密体制下的2个安全定义. 对于一个公钥加密方案PKE的敌手$\mathcal{A}=（{\mathcal{A}}_{1},{\mathcal{A}}_{2}）$，其优势${{Adv}}_{{PKE},\mathcal{A}}^{\text{IND-ATK}}\left({ \lambda }\right)$是可忽略的（如果ATK为CPA，敌手对解密预言机的访问会被移除）.

2.2   签　名

签名方案^[20]由3个多项式时间算法组成，分别为${SIG}{. }{KeyGen}{,}{SIG}{. }{Sign}{,}{SIG}{. }{Ver}$. 其中，${SIG}{. }{KeyGen}$是随机密钥生成算法，它以一个安全参数作为输入，然后输出一个公私钥对（pk, sk）. ${SIG}{. }{Sig}$是签名算法，它接收消息${m}\in \mathcal{M}$和私钥sk，然后输出一个签名$\sigma\leftarrow{SIG}{. }{Sign}{(}{sk,m}{)}$. ${SIG}{. }{Ver}$是确定性验证算法，它接收公钥pk、消息m和签名$\sigma$，签名有效输出1；反之输出0.

EUF-CMA安全是指选择消息攻击下的不可伪造性，是指任何概率多项式时间的敌手$\mathcal{A}$攻击一个签名方案${SIG=(SIG}{. }{KeyGen, SIG}{. }Sign, SIG{. }Ver)$的优势${{Adv}}_{{SIG},\mathcal{A}}^{\text{EUF-CMA}}\left({ \lambda }\right)$是可忽略的.

签名预言机的工作原理为：

${Sign}{(}{sk}{,}{m}{,}{Q}{)}$：

1） $\sigma ={Sign}{(}{sk}{,}{m}{)}$；

2） ${set}\mathcal{Q}=\mathcal{Q}\bigcup {m}$；

3） $\text{return}\;\sigma$.

2.3   非交互式零知识证明

设关系R是对（x, y）上的NP关系，表示为${L}_{R}= \{{y|}{\exists}{x}\;{{\rm{s.t.}}}{(}{x, y}{)}{\in}{R}\}$. 关系R的一个非交互式零知识（non-interaction zero-knowledge, NIZK）^[21]由3个算法组成，分别为Setup,$\mathcal{P}$,$\mathcal{V}$. 其中，Setup是参数设置算法，它以一个安全参数作为输入，输出一个公共参考串（common reference string），记为CRS；$\mathcal{P}$是证明算法，它以${y}\in {L}_{{R}}$的证明x作为输入，输出一个使得R（x, y）=1的参数$\pi \leftarrow {\mathcal{P}}_{{CRS}}{(}{x}{,}{y}{)}$；$\mathcal{V}$是验证算法，它以y和$\pi$作为输出，验证结果正确输出1，反之输出0.

零知识证明要求具备3个安全特性：

1）完备性. 对于任意的${(}{x,y}{)}\in{R}$，如果${CRS} \leftarrow$${Setup}({ \lambda })$，$\pi \leftarrow {\mathcal{P}}_{{CRS}}{(}{x}{,}{y}{)}$，那么$\mathcal{V}\left({y}{,}{\pi}\right){=1}$.

2）可靠性. 对于任何概率多项式时间的敌手$\mathcal{A}$而言，

3）零知识性. 存在一个有效的模拟器$\mathcal{S}{=}{(\mathcal{S}}_{1}, {\mathcal{S}}_{2})$，对于任何概率多项式时间的敌手$\mathcal{A}$，使得${|}{Pr}\left[{{Expt}}_{\mathcal{A}}\left({ \lambda }\right){=1}\right]{-}{Pr}\left[{{Expt}}_{\mathcal{A}}^{\mathcal{S}}\left({ \lambda }\right){=1}\right]{| \leq}{negl}{(}{ \lambda }{)}$. 其中，试验${{Expt}}_{\mathcal{A}}\left({ \lambda }\right)$和${{Expt}}_{\mathcal{A}}^{\mathcal{S}}\left({ \lambda }\right)$的定义为：

${{Expt}}_{\mathcal{A}}\left({ \lambda }\right)$：

${CRS}{\leftarrow}{Setup}{(}{ \lambda }{)}$；

${{\rm{return}}}\;{\mathcal{A}}^{{\mathcal{P}}_{{CRS}}\left(· ,· \right)}{(}{CRS}{)}$；

${{Expt}}_{\mathcal{A}}^{\mathcal{S}}\left({ \lambda }\right)$：

${(}{CRS}{,}{AUX}{)\leftarrow}{\mathcal{S}}_{1}\left(\lambda \right)$；

${{\rm{return}}}\;{\mathcal{A}}^{{{\mathcal{S}}{{{'}}}}_{{CRS}}\left(·,· ,{AUX}\right)}{(}{CRS}{)}$.

其中${{\mathcal{S}}{'}}_{{CRS}}\left({x}{,}{y}{,}{AUX}\right){=}{{\mathcal{S}}_{2}}_{CRS}{(}{y}{,}{AUX}{)}$.

3.   基于Intel SGX的公钥认证可搜索加密

3.1   PAEKS-SGX模型

根据1.1节的分析，我们修改了原始PAEKS模型^[1]的陷门生成算法，将其输入中的发送方公钥${pk}_{\mathrm{S}}$修改为接收方公钥${pk}_{\mathrm{R}}$，使之更符合云存储的实际应用场景. 如图1所示，一个公钥认证可搜索加密方案由6部分组成.

${1}{）}{PAEKS}{. }{Setup}{(}{ \lambda }{)}$. 输入安全参数$\lambda$，输出全局公开参数pp.

${{2}{）}{PAEKS}{. }{KeyGen}}_{{{\rm{R}}}}\left({pp}\right){. }$ 输入公开参数pp，输出接收者的公私钥对$({{pk}}_{{{\rm{R}}}}{,}{{sk}}_{{{\rm{R}}}}$）.

${3}）{{PAEKS}{. }{KeyGen}}_{\mathrm{S}}\left({pp}\right){. }$输入公开参数pp，输出发送者的公私钥对$({{pk}}_{{{\rm{S}}}}{,}{{sk}}_{{{\rm{S}}}}$）.

${4}{）}{PAEKS}{. }{PAEKS}{(}{{pk}}_{{{\rm{R}}}}{,}{{sk}}_{{{\rm{S}}}}{,}{w}{)}$. 输入接收者公钥${{pk}}_{{{\rm{R}}}}$、发送者私钥${{sk}}_{{{\rm{S}}}}$和关键词w，输出关键词w的密文${CT}$.

${5}{）}{PAEKS}{. }{Trapdoor}{(}{{sk}}_{{{\rm{R}}}}{,}{{pk}}_{{{\rm{R}}}}{,}{w}{')}$. 输入接收者私钥${{sk}}_{{{\rm{R}}}}$、接收者公钥${{pk}}_{{{\rm{R}}}}$和关键词${w}{'}$，输出${w}{'}$的陷门${{T}}_{{w}{'}}$.

${6}{）}{PAEKS}{. }{Test}{(}{{pk}}_{{{\rm{R}}}}{,}{{pk}}_{{{\rm{S}}}}{,}{CT}{,}{{T}}_{{w}{'}}{)}$. 输入接收者公钥${{pk}}_{{{\rm{R}}}}$、发送者公钥${{pk}}_{{{\rm{S}}}}$、关键词密文${CT}{\leftarrow}{PAEKS}{. }$${PAEKS}{(}{{pk}}_{{{\rm{R}}}}{,}{{sk}}_{{{\rm{S}}}}{,}{w}{)}$和陷门${}{{T}}_{{w}{'}}{\leftarrow}{PAEKS}{. }{Trapdoor}$ $({{sk}}_{{{\rm{R}}}}{,} {{pk}}_{{{\rm{R}}}}{,}{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由敌手$\mathcal{A}$和挑战者$\mathcal{C}$参与的游戏定义为5个步骤：

1）系统建立. 输入安全参数$\lambda$，挑战者$\mathcal{C}$执行${PAEKS}{. }{Setup}{(}{ \lambda }{)}$生成公共参数pp，然后执行

并将生成的${(}{pp}{,}{{pk}}_{{{\rm{R}}}}{,}{{pk}}_{{{\rm{S}}}}{)}$发送给敌手$\mathcal{A}$.

2）询问阶段1. $\mathcal{A}$可以进行2种询问：

①关键词密文询问. $\mathcal{A}$将想要查询的关键词w发送给$\mathcal{C}$，$\mathcal{C}$执行算法${CT}{\leftarrow}{PAEKS}{. }{PAEKS}{(}{{pk}}_{{{\rm{R}}}}{,}{{sk}}_{{{\rm{S}}}}{,}{w}{)}$，并将$CT$发回$\mathcal{A}$.

②陷门询问. $\mathcal{A}$将想要查询的关键词w发送给$\mathcal{C}$，$\mathcal{C}$执行算法${{T}}_{{w}}{\leftarrow}{PAEKS}{. }{Trapdoor}{(}{{sk}}_{{{\rm{R}}}}{,}{{pk}}_{{{\rm{R}}}}{,}{w}{)}$，并将${{T}}_{{w}}$发回$\mathcal{A}$.

3）挑战阶段.$\mathcal{A}$发送2个未在询问阶段1查询过的关键词${{w}}_{{0}}{，}{{w}}_{{1}}$给$\mathcal{C}$，$\mathcal{C}$随机选择${b}{\in}\{{0,1}\}$，执行算法${{C}}^{{*}}{\leftarrow}{PAEKS}{. }{PAEKS}{(}{{pk}}_{{{\rm{R}}}}{,}{{sk}}_{{{\rm{S}}}}{,}{{w}}_{{{\rm{b}}}}{)}$，并将生成的${{C}}^{{*}}$作为挑战密文发回$\mathcal{A}$.

4）询问阶段2. 在这一阶段，$\mathcal{A}$可以继续发送与询问阶段1相同的询问，但是在询问陷门时所使用的关键词w不能为${{w}}_{{0}}$或${{w}}_{{1}}$.

5）猜测. 敌手$\mathcal{A}$猜测$\mathcal{C}$之前加密的是${{w}}_{{0}}$还是${{w}}_{{1}}$，若猜对，则视为攻击成功.

敌手$\mathcal{A}$在上述游戏中的优势可以定义为函数:

定义1. 如果对任何多项式时间敌手$\mathcal{A}$，存在一个可忽略的优势$\sigma$，使得${{Adv}}_{{{\rm{PAEKS}}}}^{{{\rm{CI}}}}\left({ \lambda }\right){\le}{\sigma}$，那么PAEKS方案具备密文不可区分安全性.

TI-security保证了内外部攻击者在拿到一个不知道关键词的陷门时，无法获取该关键词陷门中所包含的关键词信息. TI-security由敌手$\mathcal{A}$和挑战者$\mathcal{C}$参与的游戏定为5个步骤：

1）系统建立. 输入安全参数$\lambda$，挑战者$\mathcal{C}$执行${PAEKS}{. }{Setup}{(}{ \lambda }{)}$生成公共参数pp，然后执行

并将生成的$\text{(}{pp}\text{,}{{pk}}_{\text{R}}\text{,}{{pk}}_{\text{S}}\text{)}$发送给敌手$\mathcal{A}$.

2）询问阶段1. $\mathcal{A}$可以进行2种询问：

①关键词密文询问. $\mathcal{A}$将想要查询的关键词w发送给$\mathcal{C}$，$\mathcal{C}$执行算法${CT}{\leftarrow}{PAEKS}{. }{PAEKS}{(}{{pk}}_{{{\rm{R}}}}{,}{{sk}}_{{{\rm{S}}}}{,}{w}{)}$，并将${CT}$发回$\mathcal{A}$.

②陷门询问. $\mathcal{A}$将想要查询的关键词w发送给$\mathcal{C}$，$\mathcal{C}$执行算法${{T}}_{{w}}{\leftarrow}{PAEKS}{. }{Trapdoor}{(}{{sk}}_{{{\rm{R}}}}{,}{{pk}}_{{{\rm{R}}}}{,}{w}{)}$，并将${{T}}_{{w}}$发回$\mathcal{A}$.

3）挑战阶段. $\mathcal{A}$发送2个未在询问阶段1查询过的关键词${{w}}_{{0}}{，}{{w}}_{{1}}$给$\mathcal{C}$，$\mathcal{C}$随机选择${b}{\in}\{{0,1}\}$，执行算法${{T}}^{{*}}{\leftarrow}{PAEKS}{. }{Trapdoor}{(}{{sk}}_{{{\rm{R}}}}{,}{{pk}}_{{{\rm{R}}}}{,}{{w}}_{{b}}{)}$，并将生成的${{T}}^{{*}}$作为挑战陷门发回$\mathcal{A}$.

4）询问阶段2. 在这一阶段，$\mathcal{A}$可以继续发送与询问阶段1相同的询问，前提是所询问的关键词w不能为${{w}}_{{0}}$或${{w}}_{{1}}$.

5）猜测. 敌手$\mathcal{A}$猜测${{T}}^{{*}}$是${{w}}_{{0}}$还是${{w}}_{{1}}$的陷门，若猜对，则视为攻击成功.

敌手$\mathcal{A}$在上述游戏中的优势可以定义为函数：

定义2. 如果对任何多项式时间的敌手$\mathcal{A}$，存在一个可忽略的优势${σ}$，使得${{Adv}}_{{{\rm{PAEKS}}}}^{{{\rm{TI}}}}\left({ \lambda }\right)\le\sigma$，那么PAEKS方案具备陷门不可区分安全性.

SP-privacy 保证了外部攻击者在仅拿到2个陷门的情况下，无法判断2个陷门是否对应着同一个关键词. SP-privacy由敌手$\mathcal{A}$和挑战者$\mathcal{C}$参与的游戏定义为5个步骤：

1）系统建立. 输入安全参数$\lambda$，挑战者$\mathcal{C}$执行${PAEKS.Setup}{(}{ \lambda }{)}$生成公共参数pp，然后执行

并将生成的${(}{pp}{,}{{pk}}_{{{\rm{R}}}}{,}{{pk}}_{{{\rm{S}}}}{)}$发送给敌手$\mathcal{A}$.

2）询问阶段1.$\mathcal{A}$可以进行2种询问：

①关键词密文询问. $\mathcal{A}$将想要查询的关键词w发送给$\mathcal{C}$，$\mathcal{C}$执行算法${CT}{\leftarrow}{PAEKS}{. }{PAEKS}{(}{{pk}}_{{{\rm{R}}}}{,}{{sk}}_{{{\rm{S}}}}{,}{w}{)}$，并将${CT}$发回$\mathcal{A}$.

②陷门询问. $\mathcal{A}$将想要查询的关键词w发送给$\mathcal{C}$，$\mathcal{C}$执行算法${{T}}_{{w}}{\leftarrow}{PAEKS}{. }{Trapdoor}{(}{{sk}}_{{{\rm{R}}}}{,}{{pk}}_{{{\rm{R}}}}{,}{w}{)}$，并将${{T}}_{{w}}$发回$\mathcal{A}$.

3）挑战阶段.$\mathcal{A}$发送2个未在询问阶段1阶段查询过的关键词${{w}}_{{0}}{，}{{w}}_{{1}}$给$\mathcal{C}$，$\mathcal{C}$随机选择${b}{\in}\{{0,1}\}$，执行算法${{T}}^{{*}}{\leftarrow}{PAEKS}{. }{Trapdoor}{(}{{sk}}_{{{\rm{R}}}}{,}{{pk}}_{{{\rm{R}}}}{,}{{w}}_{{b}}{)}$，并将生成的${{T}}^{{*}}$作为挑战陷门发回$\mathcal{A}$.

4）询问阶段2. 在这一阶段，$\mathcal{A}$可以继续发送与询问阶段1相同的询问，在关键词密文询问中，要求所询问的关键词w不能为${{w}}_{{0}}$或${{w}}_{{1}}$；而在陷门询问中则没有限制.

5）猜测. 敌手$\mathcal{A}$猜测${{T}}^{{*}}$是${{w}}_{{0}}$还是${{w}}_{{1}}$的陷门，若猜对，则视为攻击成功.

敌手$\mathcal{A}$在上述游戏中的优势可以定义为函数：

定义3. 如果对任何多项式时间的敌手$\mathcal{A}$，存在一个可忽略的优势${σ}$，使得${{Adv}}_{{{\rm{PAEKS}}}}^{{{\rm{SPP}}}}\left({ \lambda }\right)\le\sigma$，那么PAEKS方案具备搜索模式隐私性.

值得注意的是，在这3个安全性定义中，均允许敌手访问Test预言，该预言接收关键词密文和陷门作为输入，输出匹配结果.

3.2   PAEKS-SGX方案构造

由于SGX为程序提供了一个可靠的执行环境执行敏感操作，一个自然的构造思路就是将私钥加载到可信的执行环境enclave中，利用私钥来解密公钥加密的密文. 这样，如果关键词密文和陷门都是由接收方公钥加密的密文（各自包含发送方和接收方用私钥对关键词所做的签名），那么就可以从密文中分别解密得到关键词明文进行比对. PAEKS方案不仅设计思路比较直接和简单，而且由于可以使用私钥，所以很多扩展功能就比较容易实现，如第5节将介绍的面向多用户场景的扩展. 但是，利用这个思路构造PAEKS方案的一个关键问题是：如果在关键词密文和陷门生成时只使用公钥加密1次，那么在进行安全性证明时，如果想要利用PAEKS方案的敌手$\mathcal{A}$来构造一个公钥加密方案的敌手$\mathcal{B}$，那么$\mathcal{B}$作为$\mathcal{A}$的挑战者，在不知道所挑战的公钥方案私钥的前提下，该如何为$\mathcal{A}$生成陷门（这里的陷门隐含匹配算法所使用的enclave程序）. 而使用类似Naor-Yung的IND-CCA公钥加密方案“双加密”构造范式^[3]，则可以在安全性证明时解决这个问题.

假设${PKE}{=(}{KeyGen}{,}{Enc}{,}{Dec}{)}$是一个IND-CPA安全公钥密码方案，$\left(\mathcal{P},\mathcal{V}\right)$是一个自适应安全非交互零知识证明系统，${SIG}{=(}{KeyGen}{,}{Sign}{,}{Ver}{)}$是一个EUF-CMA安全的签名方案. 在本文方案中，假设关键词长度相同 ¹. PAEKS-SGX方案（Setup,${{KeyGen}}_{\mathrm{R}}$, ${{KeyGen}}_{\mathrm{S}}$, PAEKS, Trapdoor, Test）构造为：

1）${PAEKS}{. }{Setup}{(}{ \lambda }{)}$. 选择公钥加密方案PKE，数字签名方案SIG和非交互零知识证明系统$\left(\mathcal{P},\mathcal{V}\right)$构造如算法1所示的enclave搜索程序${{E}{(}{C}}_{{{\rm{search}}}}{)}$，在服务器上建立enclave执行环境，其中的接收方私钥为${{sk}}_{{{\rm{R}}}}{. }{{sk}}_{{1}}$在搜索时由接收方与enclave认证后上传到enclave中.

${2}）{{PAEKS}{. }{KeyGen}}_{\mathrm{R}}\left(pp\right)$. 执行

设置接收者公私钥对为

3）${{PAEKS}{. }\;\;{KeyGen}}_{\mathrm{S}}\left(pp\right)$. 执行

$\left({pk}{,}\;{sk}\right)\leftarrow$${SIG}{. } {KeyGen}{(}{ \lambda }{)}$，设置发送者公私钥对为

4）${PAEKS}{. }{PAEKS}{(}{{pk}}_{{{\rm{R}}}}{,}{{sk}}_{{{\rm{S}}}}{,}{w}{)}$. 设${{pk}}_{{{\rm{R}}}}{=}({{pk}}_{{1}}{,}{{pk}}_{{2}}{,} {{pk}}_{{3}}{,}$${r}\leftarrow{\left\{{0,1}\right\}}^{{poly}\left({ \lambda }\right)})$是接收方的公钥. 假设w是文件中的一个关键词，首先执行${{sig}}_{{w}}\leftarrow {SIG}{. }{Sign}{(}{{sk}}_{{{\rm{S}}}}{,}{w}{)}$，然后计算PAEKS密文${CT}{=(}{{C}}_{{1}}{,}{{C}}_{{2}}{,}{\varPi}{)}$，其中

${{r}}_{{1}}{,}{{r}}_{{2}}$是PKE.Enc算法使用的随机性.

5）${PAEKS}{. }{Trapdoor}{(}{{sk}}_{{{\rm{R}}}}{,}{{pk}}_{{{\rm{R}}}}{,}{w}{')}$. 设${{sk}}_{{{\rm{R}}}}{=(}{{sk}}_{{1}}{,}{{sk}}_{{3}}{)}$是接收方的私钥. 搜索某个关键词${w}{'}$时，计算搜索陷门${{T}}_{{w}{'}}{=}\left({{T}}_{{w}{'}}^{{1}}{,}{{T}}_{{w}{'}}^{{2}}{,}{\varPi}\right)$，其中

${{r}}_{{3}}{,}{{r}}_{{4}}$是PKE.Enc算法使用的随机性，${{sig}}_{{w}{'}}\leftarrow{SIG}{. }$${Sign}{(}{{sk}}_{{3}}{,} {w}{')}$是接收方利用私钥${{sk}}_{{3}}$对${w}{'}$的签名.

6）${PAEKS}{. }{Test}{(}{{pk}}_{{{\rm{R}}}}{,}{{pk}}_{{{\rm{S}}}}{,}{CT}{,}{{T}}_{{w}{'}}{)}$. 服务器将${{pk}}_{{{\rm{R}}}}{,}{{pk}}_{{{\rm{S}}}}{,} {CT}{,}{{T}}_{{w}{'}}$传入enclave，执行enclave搜索程序${{E}{(}{C}}_{{{\rm{search}}}}{)}$，获取匹配结果.

算法1. enclave搜索程序${{E}{(}{C}}_{{{\rm{search}}}}{)}$ .

输入：接收方的公钥${{pk}}_{{{\rm{R}}}}{=}\left({{pk}}_{{1}}{,}{{pk}}_{{2}}{,}{{pk}}_{{3}}{,}{r}\right)$，发送方的公钥${{pk}}_{{{\rm{S}}}}{=}\left({pk}{,}{{r}}_{{{\rm{S}}}}\right)$，接收方的私钥${{sk}}_{{R}}{. }{{sk}}_{{1}}$，关键词密文${CT}$，搜索陷门${{T}}_{{w}{'}}$；

输出：匹配时为1，不匹配时为0.

① if $\mathcal{V}\left({{pk}}_{\text{S}}\text{. }{{r}}_{\text{S}}\text{,}\left({CT}\text{. }{{C}}_{\text{1}}\text{,}{CT}\text{. }{{C}}_{\text{2}}\right)\text{,}{CT}\text{. }\varPi \right)\text{==0}$

②　 $\text{return 0}$；

③ $\text{end if}$

④ if $\mathcal{V}\left({{pk}}_{{{\rm{R}}}}{. }{r}{,}\left({{T}}_{{w}{'}}{. }{{T}}_{{w}{'}}^{{1}}{,}{{T}}_{{w}{'}}{. }{{T}}_{{w}{'}}^{{2}}\right){,}{{T}}_{{w}{'}}{. }\varPi\right){==0}$

⑤　 $\text{return 0}$；

⑥ $\text{end if}$

⑦ ${{w}}_{{1}}\left|\right|{{sig}}_{{{w}}_{{1}}}{\leftarrow}{PKE.Dec}\left({{sk}}_{{{\rm{R}}}}{. }{{sk}}_{{1}}{,}{CT}{. }{{C}}_{{1}}\right)$；

⑧ if ${SIG.Ver}\left({{pk}}_{{{\rm{S}}}}{. }{pk}{,}{{sig}}_{{{w}}_{{1}}}{,}{{w}}_{{1}}\right){=={\rm{false}}}$

⑨ 　$\text{return 0}$；

⑩ $\text{else}$

⑪　 ${{w}}_{{2}}\left|\right|{{sig}}_{{{w}}_{{2}}}{\leftarrow}{PKE}{. }{Dec}\left({{sk}}_{{R}}{. }{{sk}}_{{1}}{,}{{T}}_{{w}{'}}{. }{{T}}_{{w}{'}}^{{1}}\right)$；

⑫ 　if ${}{SIG}{. }{Ver}\left({{pk}}_{{{\rm{R}}}}{. }{{pk}}_{{3}}{,}{{sig}}_{{{w}}_{{2}}}{,}{{w}}_{{2}}\right){=={\rm{false}}}$

⑬ 　　$\text{return 0}$；

⑭　 $\text{else}$

⑮ 　　if ${}{{w}}_{{1}}{==}{{w}}_{{2}}{}$

⑯　　　 $\text{return\;1}$；

⑰ 　　$\text{else}$

⑱ 　　　$\text{return 0}$；

⑲　　 $\text{end if}$

⑳　 $\text{end if}$

㉑ $\text{end if}$

3.3   安全性证明

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

证明. 我们通过如下一系列不可区分的游戏来证明.

Game₀是PAEKS-SGX的密文不可区分安全性CI游戏.

Game₁除了挑战者生成的enclave搜索程序之外，其他和Game₀完全相同. 在这个游戏中，挑战者生成enclave搜索程序${{E}{(}{C'}}_{{{\rm{search}}}}{)}$而不是${{E}{(}{C}}_{{{\rm{search}}}}{)}$，如算法2所示. 在${{E}{(}{C'}}_{{{\rm{search}}}}{)}$中，用接收方在生成公私钥对时未使用的私钥${{sk}}_{{2}}$代替${{sk}}_{{1}}$，解密${CT}{. }{{C}}_{{2}}$和${{T}}_{{w}{'}}{. }{{T}}_{{w}{'}}^{{2}}$.

Game₂与Game₁相比，除了$\left(\mathcal{P},\mathcal{V}\right)$替换成其模拟器（记作${\varPi'}$），其他和Game₁完全相同.

不难看出，${{E}{(}{C'}}_{{{\rm{search}}}}{)}$和${{E}{(}{C}}_{{{\rm{search}}}}{)}$具有相同的功能. 由于Intel SGX的安全机制，仅从输入输出来看，${{E}{(}{C}}_{{{\rm{search}}}}{)}$和${{E}{(}{C'}}_{{{\rm{search}}}}{)}$是不可区分的. 因此，Game₀和Game₁是无法区分的.

Game₁和Game₂也是无法区分的. 因为如果存在一个敌手$\mathcal{A}$可以区分Game₁和Game₂，那么相当于存在一个NIZK的敌手${\mathcal{A}}{{{'}}}$可以区分真实证明和模拟证明，这显然是不成立的.

下面证明PAEKS-SGX的敌手在Game₂中的优势是可以忽略的.

假设$\mathcal{A}$是Game₂的一个敌手，它可以构造一个IND-CPA安全的PKE方案的敌手$\mathcal{B}$，$\mathcal{B}$在IND-CPA安全游戏中与它的挑战者$\mathcal{C}$交互的同时，作为Game₂的挑战者与$\mathcal{A}$交互. 具体构造过程有5个步骤：

1）系统建立. 构造如算法2所示的enclave搜索程序${{E}{(}{C'}}_{{{\rm{search}}}}{)}$，在服务器上建立enclave执行环境. 挑战者$\mathcal{C}$执行$\left({{pk}}_{{1}}{,}{{sk}}_{{1}}\right)\leftarrow {PKE}{. }{KeyGen}{(}{ \lambda }{)}$，生成的公钥${pk}_{1}$发送给敌手$\mathcal{B}$，私钥${sk}_{1}$由$\mathcal{C}$自行保管；敌手$\mathcal{B}$执行$\left({{pk}}_{{2}}{,}{{sk}}_{{2}}\right) \leftarrow {PKE}{. }{KeyGen}{(}{ \lambda }{)}$，$\left({{pk}}_{{3}}{,} {{sk}}_{{3}} \right)\leftarrow {SIG}{. }{KeyGen}{(}{ \lambda }{)}$和${r}\leftarrow {{Sim}}_{{1}}{(}{ \lambda }{)}$，私钥$\mathcal{B}$自行保管，接收者公钥设为$\left({{pk}}_{{1}}{,}{{pk}}_{{2}}{,}{{pk}}_{{3}}{,}{r}\right)$，$\mathcal{B}$生成发送者公私钥对${(}{{pk}}_{{S}}{,}{{sk}}_{{S}}{)}$，将公钥$\left({{pk}}_{{1}}{,}{{pk}}_{{2}}{,}{{pk}}_{{3}}{,}{r}{,}{{pk}}_{{S}}\right)$和构造的enclave搜索程序${{E}{(}{C'}}_{{search}}{)}$发送给敌手$\mathcal{A}$.

2）询问阶段1.$\mathcal{A}$可以向$\mathcal{B}$请求2个询问.

①关键词密文询问. $\mathcal{A}$将想要查询的关键词w发送给$\mathcal{B}$，$\mathcal{B}$执行${CT}\leftarrow {PAEKS}{. }{PAEKS}{(}{{pk}}_{{{\rm{R}}}}{,}{{sk}}_{{{\rm{S}}}}{,}{w}{)}$，并将${CT}$发回$\mathcal{A}$.

②陷门询问. $\mathcal{A}$将想要查询的关键词w发送给$\mathcal{B}$，$\mathcal{B}$执行${{T}}_{{w}}\leftarrow {PAEKS}{. }{Trapdoor}{(}{{sk}}_{{{\rm{R}}}}{,}{{pk}}_{{{\rm{R}}}}{,}{w}{)}$，并将${{T}}_{{w}}$发回$\mathcal{A}$. 注意这里还允许$\mathcal{A}$询问Test操作的返回结果.

3）挑战阶段. 首先$\mathcal{A}$发送2个关键词${{w}}_{{0}}{，}{{w}}_{{1}}$给$\mathcal{B}$，$\mathcal{B}$使用私钥${{sk}}_{{{\rm{S}}}}$对${{w}}_{{0}}{，}{{w}}_{{1}}$签名得到${{sig}}_{{{w}}_{{0}}},{{sig}}_{{{w}}_{{1}}}$，并将${(}{{w}}_{{0}}\left|\left|{{sig}}_{{{w}}_{{0}}}{,}{{w}}_{{1}}\right|\right|{{sig}}_{{{w}}_{{1}}}{)}$作为挑战明文转发给$\mathcal{C}$. 在$\mathcal{B}$与$\mathcal{C}$的交互中，$\mathcal{B}$作为敌手接收来自$\mathcal{C}$的挑战密文${C}\leftarrow {PKE}{. }{Enc}{(}{{pk}}_{{1}}{,}{{w}}_{{β}}\left|\right|{{sig}}_{{{w}}_{{β}}}{;}{{r}}_{{0}}{)}$；然后计算${{C}}_{{2}}\leftarrow {PKE}{. }$ ${Enc}{(}{{pk}}_{{2}}{,}{{w}}_{{0}}\left|\right|{{sig}}_{{{w}}_{{0}}}{;}{{r}}_{{1}}{)}$，${\varPi'}\leftarrow {{Sim}}_{{2}}{(}{{C}}_{{1}}{,}{{C}}_{{2}}{)}$；最后以$\mathcal{A}$挑战者的身份计算${CT}{=(}{{C}}_{{1}}{,}{{C}}_{{2}}{,}{\varPi'}{)}$，将CT作为PAEKS的挑战密文发送给$\mathcal{A}$.

4）询问阶段2. 在这一阶段，$\mathcal{A}$可以继续执行如询问阶段1一样的询问，但是在询问陷门时所使用的关键词w不能为${{w}}_{{0}}$或${{w}}_{{1}}$.

5）猜测. 敌手$\mathcal{B}$输出敌手$\mathcal{A}$的输出内容.

不难看出，如果$\mathcal{C}$选择$\beta{=0}$（概率为$1/2$），则此时$\mathcal{B}$为$\mathcal{A}$提供了一个完美的模拟；否则，通过非交互零知识证明系统的零知识性和可靠性，$\mathcal{A}$在区分PAEKS密文方面的优势可忽略. 因此，$\mathcal{B}$作为PKE方案的IND-CPA敌手，其优势相当于Game₂中敌手$\mathcal{A}$优势的$1/2$. 又因为所基于的PKE方案是IND-CPA安全的，即$\mathcal{B}$的优势可忽略，所以敌手$\mathcal{A}$在Game₂中的优势也是可以忽略的. 由于Game₂和Game₀不可区分，因此密文不可区分性游戏Game₀中敌手的优势可以忽略不计. 证毕.

算法2. enclave搜索程序${{E}{(}{C'}}_{{{\rm{search}}}}{)}$.

输入：接收方的公钥${{pk}}_{{{\rm{R}}}}{=}\left({{pk}}_{{1}}{,}{{pk}}_{{2}}{,}{{pk}}_{{3}}{,}{r}\right)$，发送方的公钥${{pk}}_{{{\rm{S}}}}{=}\left({pk}{,}{{r}}_{{{\rm{S}}}}\right)$，私钥${{sk}}_{{2}}$，关键词密文${CT}$，搜索陷门${{T}}_{{w}{'}}$；

输出：匹配时为1，不匹配时为0.

① if $\mathcal{V}\left({{pk}}_{{{\rm{S}}}}{. }{{r}}_{{{\rm{S}}}}{,}\left({CT}{. }{{C}}_{{1}}{,}{CT}{. }{{C}}_{{2}}\right){,}{CT}{. }{\varPi}\right){==0}$

②　 $\text{return 0}$；

③ $\text{end if}$

④if ${}\mathcal{V}\left({{pk}}_{{{\rm{R}}}}{. }{r}{,}\left({{T}}_{{w}{'}}{. }{{T}}_{{w}{'}}^{{1}}{,}{{T}}_{{w}{'}}{. }{{T}}_{{w}{'}}^{{2}}\right){,}{{T}}_{{w}{'}}{. }{\varPi}\right){==0}$

⑤　 $\text{return 0}$；

⑥ $\text{end if}$

⑦ ${{w}}_{{1}}\left|\right|{{sig}}_{{{w}}_{{1}}}\leftarrow {PKE}{. }{Dec}\left({{sk}}_{{2}}{,}{CT}{. }{{C}}_{{2}}\right)$；

⑧ if ${}{SIG}{. }{Ver}\left({{pk}}_{{{\rm{S}}}}{. }{pk}{,}{{sig}}_{{{w}}_{{1}}}{,}{{w}}_{{1}}\right){=={\rm{false}}}$

⑨　 $\text{return 0}$；

⑩ $\text{else}$

⑪　 ${{w}}_{{2}}\left|\right|{{sig}}_{{{w}}_{{2}}}\leftarrow {PKE}{. }{Dec}\left({{sk}}_{{2}}{,}{{T}}_{{w}{'}}{. }{{T}}_{{w}{'}}^{{2}}\right)$；

⑫　 if ${}{SIG}{. }{Ver}\left({{pk}}_{{{\rm{R}}}}{. }{{pk}}_{{3}}{,}{{sig}}_{{{w}}_{{2}}}{,}{{w}}_{{2}}\right){==false}$

⑬　　 $\text{return 0}$；

⑭ 　$\text{else}$

⑮　　 if ${}{{w}}_{{1}}{==}{{w}}_{{2}}$

⑯　　　 $\text{return 1}$；

⑰　　 $\text{else}$

⑱　　　 $\text{return 0}$；

⑲　　 $\text{end if}$

⑳　 $\text{end if}$

㉑ $\text{end if}$

定理2. PAEKS-SGX具有陷门不可区分性.

证明. 可以看出陷门的生成过程实际上就是Naor-Yung的IND-CCA公钥加密构造范式^[3]中加密明文${w}{'||}{{sig}}_{{w}{'}}$的过程，而陷门不可区分性的定义与IND-CCA安全性的定义是类似的. 所以在敌手无法自己构造关键词密文情况下，可以利用Naor-Yung范式^[3]的证明思路证明我们方案的陷门不可区分性. 具体证明过程不再详述.

接下来证明，若敌手尝试构造挑战关键词的密文并能通过挑战陷门${T}_{{w}\text{'}}$的测试，那么可以构造一个具有EUF-CMA安全性的签名方案SIG的敌手，从而打破签名方案SIG的EUF-CMA安全性. 由于签名方案的敌手打破EUF-CMA安全性的优势是可以忽略不计的，所以PAEKS-SGX中敌手无法自己构造关键词密文. 所以综合可知PAEKS-SGX具有陷门不可区分性. 证毕.

下面我们介绍EUF-CMA安全签名方案敌手的具体构造过程.

假设$\mathcal{A}$是陷门不可区分性游戏的敌手，尝试构造挑战关键词的密文，$\mathcal{B}$是我们想要构造的EUF-CMA安全签名方案的一个敌手，它在EUF-CMA安全游戏中与它的挑战者$\mathcal{C}$交互的同时，作为挑战者与$\mathcal{A}$交互. 在EUF-CMA安全性游戏中执行算法${(}{sk}{,}{pk}{)\leftarrow}{SIG}{. }{KeyGen}{(}{ \lambda }{)}$，生成的私钥sk自行保存，公钥pk发送给它的敌手$\mathcal{B}$. 然后$\mathcal{B}$执行

私钥自行保存，将${{pk}}_{{{\rm{R}}}}{=}\left({{pk}}_{{1}}{,}{{pk}}_{{2}}{,}{{pk}}_{{3}}{,}{r}\right)$作为接收方的公钥发送给它的敌手$\mathcal{A}$. 同样，$\mathcal{B}$还要将${{pk}}_{{{\rm{S}}}}{=}{pk}$作为发送方公钥发送给敌手$\mathcal{A}$. 当敌手$\mathcal{A}$向$\mathcal{B}$进行关键词密文询问时，$\mathcal{B}$向它的挑战者$\mathcal{C}$询问对该关键词的签名，然后生成关键词密文；当敌手$\mathcal{A}$向$\mathcal{B}$进行陷门询问时，由于$\mathcal{B}$自己生成接收者的公私钥对，所以直接利用接收者私钥生成陷门. 最终，对于挑战陷门，如果敌手$\mathcal{A}$通过构造关键词密文${CT}{=(}{{C}}_{{1}}{,}{{C}}_{{2}}{,}{\varPi}{)}$，其中

并通过Test成功判断陷门中的关键词，我们可知其中的签名${{sig}}_{{w}}$必然可以用发送方公钥进行正确的验证，即敌手$\mathcal{A}$成功地对挑战关键词构造了在发送者私钥下的签名${{sig}}_{{w}}$，即可打破签名方案的EUF-CMA安全性.

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

证明. 首先，由于SGX的安全特性，enclave中的搜索程序是安全可靠的. 其次，同定理2的证明，可以看到关键词${w}{'}$的陷门实际上就是Naor-Yung的IND-CCA公钥加密构造范式中加密明文${w}{'||}{{sig}}_{{w}{'}}$后得到的密文^[3]. 如果敌手仅通过关键词陷门就能判断陷门中是否是同一关键词，那么实际上相当于在利用Naor-Yung范式构造的IND-CCA方案中可以通过挑战密文区分挑战明文，也就打破了Naor-Yung范式的IND-CCA安全性. 因此，PAEKS-SGX具有搜索模式隐私性. 证毕.

3.4   密钥管理

由对PAEKS-SGX的描述可以看到，我们构造的enclave搜索程序的正确运行需要文件接收方的私钥，因此如何对该私钥进行安全有效地管理，是需要考虑的一个重要问题. PAEKS-SGX采用Intel SGX远程认证技术和Intel SGX密封技术，给出了一个行之有效的解决方案. 该方案中，接收方可以在初始时将其私钥${{sk}}_{\text{R}}.{{sk}}_{\text{1}}$用私钥传递过程发送到enclave搜索程序中，然后enclave可将该私钥利用密封技术加密保存在硬盘中对应存储位置. 当后续再需要搜索时，enclave可以从硬盘中将密封的接收方私钥读入enclave并解封得到${{sk}}_{\text{R}}.{{sk}}_{\text{1}}$.

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部分组成.

图  2  PAEKS-SGX架构

Figure  2.  The architecture of 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^®Core^TM i7-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所示.

表  1  基本元素操作的计算时间

Table  1.  Computation Time of Basic Element Operation

操作	计算时间/ms
对运算	6.5083
模幂运算	12.8706
哈希运算	0.0032

下载: 导出CSV 

| 显示表格

首先，我们分析用户与SGX进行远程认证，enclave密封用户私钥所需的时间. 测试结果显示，该过程的平均用时为3.3 s. 虽然时间达到了秒级，但由于在整个系统生命周期，对于一个用户来说，该过程只需执行1次，所以我们认为这个时间消耗是可以接受的.

接下来我们从关键词密文生成（PEKS/PAEKS）、陷门生成（Trapdoor）、匹配（Test）这3个阶段对所有方案进行测试. 需要指出的是，在PAEKS中，当我们把关键词长度设定为256 b且使用ElGamal加密和签名算法时，${w}{||}{{sig}}_{{w}}$的长度是关键词w长度的3倍，对${w}{||}{{sig}}_{{w}}$进行ElGamal加密时需要将其分为3组，各组对应1个零知识证明. 这也意味着在匹配算法中要合计验证6次零知识证明，时间消耗比较大. 而且此时实际的关键词密文和陷门长度也会扩大3倍，即6组ElGamal加密的密文和3组零知识证明. 因此我们对方案做了改进，在关键词密文和陷门生成算法中，除了生成${w}{||}{{sig}}_{{w}}$的密文外，还要计算Hash（${w}{||}{{sig}}_{{w}}$）的密文，其中Hash（·）是一个输出长度为256 b的哈希函数. 我们不再计算针对${w}{||}{{sig}}_{{w}}$的密文的零知识证明，而是计算针对Hash（${w}{||}{{sig}}_{{w}}$）的密文的零知识证明. 在enclave里的匹配算法中，首先验证该零知识证明，在验证通过后解密得到${w}{||}{{sig}}_{{w}}$和Hash（${w}{||}{{sig}}_{{w}}$），然后利用哈希计算${w}{||}{{sig}}_{{w}}$的哈希值，并与Hash（${w}{||}{{sig}}_{{w}}$）进行比较，比较通过后再进行签名验证. 通过这种改进，匹配算法中零知识证明验证的次数变为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没有使用双线性群的元素操作有很大关系.

图  3  不同方案耗时对比

Figure  3.  Comparison of time costs in different schemes

下载: 全尺寸图片 幻灯片

在上面的测试中， PAEKS-SGX的匹配算法并未包含enclave读取接收方的私钥密封文件并解封的操作. 下面我们考虑包含私钥读取和解封操作，并分析服务器收到1次搜索请求后完成搜索过程所需的时间. 设当前待搜索的文件总数为N，每个文件的关键词个数为M，我们首先测试了SGX执行私钥解封（含读入封装文件的过程）的时间，其平均用时为4.5 ms. 当采用顺序匹配的策略时，每个文件的关键词匹配次数均值为M/2. 所以，对比方案对1个关键词陷门执行匹配的总时间均值为各自匹配算法的执行时间乘以MN/2，即，均不小于6.51×MN/2 ms. 而PAEKS-SGX对1个关键词陷门进行匹配时，总的匹配时间均值=一次私钥解封的时间+单个关键词密文匹配时间×MN/2 = 4.5+2.00×MN/2 ms. 当MN较大时，一次私钥解封的时间可以忽略不计，总匹配时间均值可视作2.00×MN/2 ms，所以PAEKS-SGX在总的匹配时间上依然有着很大的优势.

更进一步地，我们根据关键词的数量变化，测试了不同数量的关键词时相应算法的执行时间，结果如图4~6所示.

图  4  不同方案生成PEKS/PAEKS耗时对比

Figure  4.  Comparison of time cost of PEKS/PAEKS generation in different schemes

下载: 全尺寸图片 幻灯片

图  5  不同方案生成Trapdoor耗时对比

Figure  5.  Comparison of time cost of Trapdoor generation in different schemes

下载: 全尺寸图片 幻灯片

图  6  不同方案生成Test耗时对比

Figure  6.  Comparison of time cost of Test generation in different schemes

下载: 全尺寸图片 幻灯片

如图4~6所示，PAEKS-SGX的优势是十分明显的：在PEKS/PAEKS生成阶段生成1000个关键词的密文时，PAEKS-SGX耗时控制在1 s左右，而其他方案则需要30 s以上；Trapdoor生成阶段，PAEKS-SGX同样具有领先其他方案至少10倍以上的速度优势；而在Test阶段，匹配1000个（关键词，陷门）对时，PAEKS-SGX相比起其他方案仍然具有明显的速度优势.

在方案的通信量分析方面，表2给出了PAEKS-SGX和3个对比方案的关键词密文大小和搜索陷门的大小. 结果显示，PAEKS-SGX的通信量比对比方案要大. 但我们认为，无论是关键词密文大小还是陷门的大小都在几百字节的量级，对于网络通信和具有大容量存储的云服务器来说，均是可接受的.

表  2  通信量比较

Table  2.  Communication Overhead Comparison

方案	PEKS/PAEKS大小/B	Trapdoor大小/B
文献[1]	160	128
文献[9]	256	128
文献[10]	160	128
PAEKS-SGX	416	416

下载: 导出CSV 

| 显示表格

5.   方案扩展

PAEKS-SGX具有易扩展的优势，一些新的功能只需在现有方案的基础上稍加修改即可. 下面我们介绍如何扩展方案支持多关键词搜索、如何扩展方案到多用户场景以及如何支持前向安全性.

5.1   多关键词搜索

PAEKS-SGX可以扩展为支持多关键词搜索功能. 在进行多关键词搜索功能的扩展时，首先，不能要求预先对关键词排序；其次，不能在搜索陷门中暴露搜索的关键词个数，即满足搜索模式隐私性，且搜索陷门大小与待搜索的关键词个数无关.

1）基本思路. 在生成关键词密文的时候，用所有关键词计算1个布隆过滤器BFw，然后为这个布隆过滤器生成关键词密文. 生成搜索陷门的时候，同样使用待搜索的多个关键词计算1个布隆过滤器BF. 对BF生成陷门，将enclave搜索程序${{E}\text{(}{C}}_{\text{search}}\text{)}$的部分代码稍作修改，解密之后，将比对关键词的过程改为布隆过滤器的按位与操作，即BFr=BFw&BF，若BFr==BF，则输出1，完成对1个文件的匹配过程. 详见算法3.

算法3. enclave多关键词搜索程序${{E}\text{(}{C}}_{{\text{search}}_{\text{mul-kw}}}\text{)}$.

输入：接收方的公钥${{pk}}_{{{\rm{R}}}}{=}\left({{pk}}_{{1}}{,}{{pk}}_{{2}}{,}{{pk}}_{{3}}{,}{r}\right)$，发送方的公钥${{pk}}_{{{\rm{S}}}}{=}\left({pk}{,}{{r}}_{{{\rm{S}}}}\right)$，接收方的私钥${{sk}}_{{{\rm{R}}}}{. }{{sk}}_{{1}}$，关键词密文${CT}$，搜索陷门${{T}}_{{w}{'}}$；

输出：无.

① if ${}\mathcal{V}\left({{pk}}_{{{\rm{S}}}}{. }{{r}}_{{{\rm{S}}}}{,}\left({CT}{. }{{C}}_{{1}}{,}{CT}{. }{{C}}_{{2}}\right){,}{CT}{. }{\varPi}\right){==0}$

②　 $\text{return 0}$；

③ $\text{end if}$

④ if ${}\mathcal{V}\left({{pk}}_{{{\rm{R}}}}{. }{r}{,}\left({{T}}_{{w}{'}}{. }{{T}}_{{w}{'}}^{{1}}{,}{{T}}_{{w}{'}}{. }{{T}}_{{w}{'}}^{{2}}\right){,}{{T}}_{{w}{'}}{. }{\varPi}\right){==0}$

⑤　 $\text{return 0}$；

⑥ $\text{end if}$

⑦ ${BFw}{||}{{sig}}_{{BFw}}{\leftarrow }{PKE}{. }{Dec}\left({{sk}}_{{{\rm{R}}}}{. }{{sk}}_{{1}}{,}{CT}{. }{{C}}_{{1}}\right)$；

⑧ if ${}{SIG}{. }{Ver}\left({{pk}}_{{{\rm{S}}}}{. }{pk}{,}{{sig}}_{{BFw}}{,}{BFw}\right){=={\rm{false}}}$

⑨ 　$\text{return 0}$；

⑩ $\text{else}$

⑪ 　${BF}{||}{{sig}}_{{BF}}{\leftarrow }{PKE}{. }{Dec}\left({{sk}}_{{{\rm{R}}}}{. }{{sk}}_{{1}}{,}{{T}}_{{w}{'}}{. }{{T}}_{{w}{'}}^{{1}}\right)$；

⑫　 if ${}{SIG}{. }{Ver}\left({{pk}}_{{{\rm{R}}}}{. }{{pk}}_{{3}}{,}{{sig}}_{{BF}}{,}{BF}\right){=={\rm{false}}}$

⑬ 　　$\text{return 0}$；

⑭ 　 $\text{else}$

⑮　　 if ${}{BFw}{\&}{BF}{==}{BF}$

⑯ 　　　$\text{return 1}$；

⑰　　 $\text{else}$

⑱ 　　　$\text{return 0}$；

⑲　　 $\text{end if}$

⑳　 $\text{end if}$

㉑ $\text{end if}$

2） PAEKS-SGX的安全性. 与单关键词搜索的方案相比，多关键词搜索的方案仅仅是将关键词替换为布隆过滤器，然后对布隆过滤器生成关键词密文、搜索陷门. 因此不会影响方案的安全性.

需要指出的是，PAEKS-SGX使用布隆过滤器存在假阳性率，且布隆过滤器的密文所需的存储空间比单关键词密文要大. 例如，当系统内有1000个关键词，假阳性率为10⁻⁶时，采用16个不同的哈希函数，则对应的关键词密文大约需要3 KB的存储空间. 虽然这个存储空间比单关键词密文的存储空间（如32 B）要大得多，但当1个文件包含l个关键词时，单关键词搜索方案中的关键词密文需要32l B存储空间，当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个文件接收方的公钥加密得到新的关键词密文.

图  7  PEKS-SGX密文共享

Figure  7.  Share of PAEKS-SGX ciphertext

下载: 全尺寸图片 幻灯片

这样，云服务器就拥有了第2个文件接收方公钥加密的关键词密文，第2个文件接收方也就拥有了合法的关键词搜索能力. 整个过程的安全性由enclave程序本身的安全特性所保证，核心操作也是在云端完成，无需多余的交互和通信负载. 相比之前那些利用代理重加密的PEKS方案，PAEKS-SGX的这种扩展能够在无需指定验证人的情况下抵抗关键词猜测攻击，且满足搜索模式隐私性，即陷门生成算法是随机的.

5.3   前向安全性

前向安全性最早是在动态对称可搜索加密方案（dynamic symmetric searchable encryption, DSSE）的构造中提出的，旨在确保用之前的搜索陷门无法搜索到新增加的文件. 因为文件注入攻击^[22]这种攻击方式的存在，如果DSSE方案不具备前向安全性，敌手可以恢复所有文件所包含的关键词，所以很多研究者都在研究如何构造支持前向安全性的DSSE方案. 而实际上，文件注入攻击更容易施加在传统公钥可搜索加密的场景，因为文件注入时只需要用接收者的公钥即可，这其实相当于一种关键词猜测攻击. 但是，一个PEKS方案可以抗关键词猜测攻击并不意味着一定具有前向安全性，因为即使敌手不能主动进行文件注入攻击（如在公钥认证可搜索加密方案中），敌手依然可以根据接收者之前发送的陷门以及匹配结果判断后续的文件是否跟前面的文件具有相同的关键词，进而当关键词空间较小的时候可以通过搜索频率来推测关键词信息^[23].

由此分析可知，前向安全性依然需要在抗关键词猜测攻击的PEKS方案中被考虑，即我们的公钥认证可搜索加密方案也需要考虑前向安全性. PAEKS-SGX的实现机制使得我们可以很方便地将其修改为具有前向安全性，只需要在关键词密文和陷门生成时均加入时间戳信息，在匹配的时候对解密出的时间戳作比较，如果陷门时间戳早于关键词密文时间戳，则enclave中直接返回0即可.

6.   结束语

针对PEKS方案的抵抗关键词猜测攻击以及PEKS方案的搜索能力共享（多用户）等问题，本文首次提出了一个在正式公钥认证可搜索加密安全性模型下可证明安全的基于SGX的PAEKS方案，方案可抵抗关键词猜测攻击，具有搜索模式隐私性和易扩展性，能够很方便地扩展到多用户情形，支持较为复杂的搜索功能以及增强的安全性. 实验结果表明，相比于传统的PEKS方案以及传统的PAEKS方案，本文提出的PAEKS-SGX具有较高的效率优势. 另外PAEKS-SGX具有一定的通用性，可以基于任何可信执行环境、任意IND-CPA安全的公钥加密算法及相应的非交互零知识证明方法，在具体实施时根据实际的硬件支持情况选择高效的对应算法来实现整个方案.

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