指定密文可搜索加密

指定密文可搜索加密

刘子源 a,曾以凡 a,∗,左瑞麟 a,间本昌宏 b
a国立政治大学计算机科学系，台北市11605，台湾
b金泽大学科学与工程研究所，日本金泽市角马町 920-1192

相关服务：日本云服务器租用

摘要

由 Boneh 等人（2004年）提出的带关键词的公钥加密（PEKS），允许用户在不泄露数据隐私的情况下搜索加密的关键词。尽管该领域已开展了大量研究，但仅有少数研究关注可能泄露用户敏感信息的内部关键字猜测攻击（IKGA）。特别是，当恶意内部人员（e.g., 服务器）接收到用户用于搜索密文的陷门后，可使用该用户的公钥随机加密可能的关键词，然后测试该陷门是否对应于所选关键词。本文提出一种称为指定密文可搜索加密（ DCSE）的新概念，该机制具备与 PEKS 方案相同的功能，并能抵御 IKGA。在 DCSE 中，每个陷门都被指定给特定的可搜索密文，因此恶意内部人员无法实施 IKGA。我们进一步提出了一种通用 DCSE 构造，该构造采用基于身份的加密和密钥封装机制。我们提供了形式化证明，以表明该通用构造满足安全性要求。此外，我们还提供了一种基于格的实例化方案，其安全性基于 NTRU 和环上带误差学习假设，因此所提出的方案被认为能够抵抗量子计算攻击。

1. 引言

随着5G和物联网（IoT）的发展，云存储的重要性日益增加。然而，由于云服务提供商难以被完全信任，为了避免数据泄露或滥用，数据所有者需要确保敏感数据的隐私性。一种直接的方法是在将数据上传到云服务器之前对其进行加密。然而，加密数据失去了处理灵活性，无法用于有用的操作，例如排序或搜索。特别是，搜索功能对云存储至关重要。
如果一个数据拥有者希望在大量加密数据集中搜索某些特定文件，则必须下载并解密所有数据才能进行搜索，这既不实际又耗费资源。为了解决这个问题，宋等人[1]提出了首个可搜索加密（SE），允许使用相应的陷门对密文进行搜索。然而，由于他们的构造基于对称密钥原语，只有特定密钥的拥有者才能生成任何相应的密文和陷门。因此，与对称密码系统一样，当其部署在公共云环境中时，他们的工作面临密钥分发问题。

1.1. 基于关键词搜索的公钥加密

为了克服对称可搜索加密的问题，并允许多个数据所有者为单个数据接收者轻松生成不同的密文，Boneh 等人[2]提出了首个基于关键词搜索的公钥加密（PEKS）。该方案不同于宋等人[1],的工作，它是构建在公钥密码系统之上的。PEKS方案包含三个实体：数据拥有者（爱丽丝）、数据接收者（鲍勃）和云服务器。考虑以下场景：爱丽丝希望存储一些文件，这些文件可由鲍勃访问和搜索，且不会向云服务器泄露任何信息。因此，除了使用鲍勃的公钥 pk加密文件外，她还使用一种 PEKS算法对文件的相关关键词进行加密，以实现对密文的搜索，例如， Enc pk(文件)‖PEKS(pk,‘‘pkc’’)‖ ⋯‖PEKS(pk,‘‘ crypto’’)‖；然后她将加密文件连同加密的关键词一起上传至云服务器。如果鲍勃希望请求云服务器搜索包含关键词“crypto”的任何加密文件，他首先使用自己的私钥生成针对“crypto”的陷门，然后将该陷门发送给云服务器。云服务器利用此陷门可以测试所有加密关键词的值，确定哪个值是由关键词“crypto”生成的，并将相应的加密文件返回给鲍勃。

与对称可搜索加密相比，PEKS更适合云服务、物联网和电子邮件系统等应用场景。在二十一世纪的前二十年中，许多适用于不同场景并提供显著功能的PEKS方案被提出。

1.2. 动机

尽管已提出了大量PEKS方案，但其安全防护措施仍不充分。例如，大多数已提出的方案假设内部人员（e.g.，云服务器、邮件服务器或物联网网关）是可信的，因此未考虑来自内部人员的潜在攻击。Byun等人 [3]首次指出，这可能在PEKS中引发问题。事实上，由于常用关键词数量较少，内部人员可以从陷门中猜测某些关键词并获取一些有用信息；这种攻击被称为内部人员关键词猜测攻击（IKGA）。更具体地说，在收到来自授权数据接收者的陷门后，恶意内部人员可以使用该数据接收者的公钥对可能的关键词进行加密，然后测试该陷门是否对应于所选的关键词。正如Byun等人所述，恶意内部人员成功获取关键词的概率约为 1∕218。此外，在关键词空间较小的某些应用中（e.g.，电子邮件应用），攻击成功的概率会更高。由于数据发送方选择的关键词通常与加密文件相关，若恶意内部人员能够通过IKGA获得这些关键词，则可提前猜测加密内容。因此，一旦与密文相关的关键词被猜出，就可认为密文的机密性已被破坏。

另一方面，Shor[4,5]证明了存在能够破解数论中某些困难假设（即离散对数假设和整数分解假设）的量子算法，因此量子计算机对现代密码学可能带来的威胁是可预见的。Arute 等人 [6]最近提出了一台 53量子比特的量子计算机。学者们认为量子计算将在二十一世纪走向成熟。尽管已有许多关于抗量子PEKS [7–10]的研究被提出以抵御量子计算攻击，但只有毛等人 [9]的方案是IKGA安全的。该方案的安全性基于带误差学习假设，该假设已被证明与求解最坏情况下的格问题一样困难[11]。然而，由于尺寸限制，该方案实用性不足；其公钥和私钥大小可达数百兆字节。

实际上，Abdalla 等人 [12] 证明了 IND‐ANON‐ID‐CPA 安全的基于身份的加密（IBE）方案可以构造出一个安全的PEKS方案。然而，如何在此基础上支持IKGA安全性仍不清楚。本文考虑以下问题：
我们能否利用IND-ANON-ID-CPA安全的身份基加密方案作为构建模块，实例化一种抗量子且支持搜索功能以及抗IKGA的密码学原语？

1.3. 我们的结果

为了回答我们的问题，我们首先引入一种新的密码学原语，称为 “指定密文可搜索加密”（DCSE），以提供与PEKS方案相同的功能，并具备抵御IKGA的额外安全性。

1.3.1. 指定密文可搜索加密

针对传统PEKS方案的攻击之所以成功，是因为内部人员可以自适应地为任意关键词生成密文。因此，在DCSE中，我们的策略是防止内部人员自行生成有效的密文，使其无法通过从授权数据接收者处获得的陷门进行有效测试。考虑这样一个场景：爱丽丝希望加密一些文件并上传到云服务器，并希望这些加密文件能够在云端被搜索。此外，她希望避免任何IKGA。爱丽丝首先对关键词 w1,…,wn执行 DCSE(pk,wi)，以生成密文 ci和该密文的标签 vi，其中标签隐藏了一些私有信息， pk是鲍勃的公钥，而 DCSE将在后文讨论。类似于 PEKS算法， DCSE的输出可以使用由数据接收者生成的陷门进行搜索。然而，为了抵抗IKGA，DCSE还为密文额外生成一个标签，只有指定的数据接收者（即鲍勃）才能从该标签中提取可与密文关联的私有信息。除了将 Encpk(文件)||c1|| ⋯||cn发送给云服务器外，爱丽丝还将标签(v1,…, vn)公开发送给鲍勃。鲍勃首先使用他的私钥从标签 vi中提取私有信息，然后利用该信息生成对应于该标签的密文的陷门 ti。换句话说，我们可以认为陷门已被指定给某一密文。随后，鲍勃将(vi, ti)提交给云服务器进行搜索。云服务器利用该陷门返回匹配的加密文件给鲍勃。由于云服务器无法随机选择一个关键词来生成与此陷门匹配的密文，因此该设计不再提供任何方法来识别数据接收者正在搜索的关键词。此外，与PEKS 不同的是，云服务器在所提出的方案中无需测试每一个密文，而是可以通过将标签 vi作为索引值快速找到所有匹配的密文。

对于DCSE，我们定义了两种安全模型：选择关键词攻击下的不可区分性（IND‐CKA）和内部人员关键词猜测攻击下的不可区分性（ IND‐IKGA）。特别地，IND‐CKA安全性和IND‐IKGA安全性确保了即使对手能够查询多项式时间陷门预言机，也无法从密文和陷门中获取任何关于关键词的信息。由于恶意内部人员的能力强于恶意外部人员，我们仅考虑IND‐IKGA安全性。

1.3.2. 通用构造及其安全性

我们提出了一种用于DCSE的通用构造，该构造包含一个伪随机生成器 F(⋅)、一个IND‐ANON‐ID‐CPA安全的IBE方案 = (KeyGen,Extract,Enc,Dec)以及一个IND‐CCA2安全的KEM方案 =(KeyGen,Encaps,Decaps)。其基本思想如下：为了向授权数据接收者加密关键词 w ，数据拥有者首先使用KEM和数据接收者的公钥生成一个随机密钥 k及其对应的封装 e ，即(k, e) ← .Encaps(pk)。然后，数据拥有者将伪随机生成器 f ← F(k ∥ w)的输出定义为一个身份，并用它来加密另一个随机消息 r，即 ct ← .Enc(pk, f, r)。在此，我们可以将封装 e视为密文 ct的一个标签。只有授权数据接收者才能使用其私钥对 e进行解封装以获得私有信息密钥 k。该数据接收者随后为“身份” f ← F(k ∥w)生成陷门 t。通过这种方式，陷门实际上关联到与某一密文相关的标签。因此，恶意内部人员无法随意生成密文来测试陷门。

此外，我们提供了严格的证明，以表明该通用构造满足IND‐CKA和 IND‐IKGA安全性标准。我们证明安全要求的主要思路是采用游戏序列方法，逐步修改我们的原始协议，使得在最终游戏中挑战消息不包含关键词的任何信息。因此，对手赢得游戏的策略只能是猜测，即对手无法通过攻击我们的构造获得任何优势。

1.3.3. 基于格的实例化

我们提供了一种利用两种高效且安全的基于格的构造的实例化：基于NTRU的IBE [13]和基于NTRU的KEM [14]。这些构造的安全性基于环上LWE和NTRU假设，从而使我们的实例化具备抗量子性。我们还在现代笔记本电脑上对其实例化的性能进行了实验评估。每次加密、陷门生成、测试算法分别仅需约1、0.3、0.01（毫秒）。与其他最先进的方案相比，我们的方案不仅更高效且更实用，还提供了更强的安全性。

1.4. 论文结构

本文的其余部分组织如下。在第2节中，我们描述了PEKS的相关工作。在第3节中，我们介绍了一些符号和预备知识。在第4节中，我们介绍了三个密码学基础模块：伪随机生成器、KEM方案和IBE方案。在第5节中，我们引入了一个新概念——“指定密文可搜索加密”，并定义了其系统模型和安全要求。在第6节中，我们从IBE方案和KEM方案出发形式化了DCSE，并提供了其安全证明。在第7节中，提出了一个高效的基于格的DCSE。最后，在第8节中，我们给出结论。

2. 相关工作

Byun 等人[3]首次提出了 IND‐IKGA，并指出 Boneh 等人 的工作[2]无法抵御此类攻击。能够抵抗 IKGA 的方案可分为以下三类。

2.1. 双服务器PEKS

一些研究首先利用另一个服务器来执行测试算法，即分散内部人员的权力，使得当两个内部人员不共谋时，方案能够抵御IKGA。因此，陈等人[15–17]提出了“双服务器”公钥可搜索加密，如果两个服务器彼此之间不共谋，则可抵御IKGA。然而，Tso等人[18]最近指出陈等人工作[15–17]的安全模型缺乏健全性和强度。因此，他们进一步提出了一种通用构造的双服务器PEKS，能够实现更强更健全的安全性。此外，毛等人[9]借鉴指定测试者的思想，提出了首个基于格的可搜索加密，能够防御IKGA。

2.2. 带关键字搜索的公钥认证加密

通过添加一个测试服务器或指定一个附加服务器，恶意内部人员无法获得测试所需的私有信息（i.e.,陷门），因此可以有效避免IKGA。然而，在实际环境中，增加另一个服务器可能会带来额外的通信开销。此外，目前学者尚不清楚如何确保指定的服务器是可信的，且不会与恶意内部人员串通。因此，一些研究开始探讨如何对密文进行认证，使得陷门仅对认证密文有效。

方等人[19,20]提出了首个使用一次性签名的公钥可搜索加密方案，并证明了其在无随机预言模型下的安全性。黄和李[21]引入了一种称为“带关键字搜索的公钥认证加密（PAEKS）”的新概念，以抵御 IKGA。在他们的方案中，数据发送者不仅加密关键词，还对关键词进行认证，而数据接收者生成的陷门仅对由数据发送者认证过的密文有效。因此，恶意服务器无法自适应地生成密文来进行IKGA。然而，诺鲁齐 和埃斯拉米[22]指出，黄和李的方案甚至对外部关键词猜测攻击都不安全。

基于对密文进行认证的思想，张等人[10]提出了一种前向安全的基于格的关键字搜索方案以抵御IKGA。然而，刘等人[23]最近指出该工作中的安全性模型并未涵盖IKGA，因此该方案并不安全。此外，帕克尼亚特等人[24]提出了首个无证书的PAEKS方案。另外，秦等人 [25]和李等人[26]进一步考虑了数据接收者查询模式信息泄露的问题。换句话说，他们确保只有服务器能够执行测试算法，以防止对手判断两个密文是否包含相同关键词。

2.3. 基于见证的可搜索加密

马等人[27]提出了一种称为“基于证明的可搜索加密”的密码学原语，其中仅当密文与陷门具有证明关系时，陷门才有效。陈等人[28]进一步提出了改进方案，以降低陷门大小的复杂性。

3. 预备知识

3.1. 符号说明

为简便和易读起见，我们在全文中使用以下符号。设 λ为自然安全参数。我们采用标准符号 O和 o来分类函数的增长。记号 negl(n)表示任意函数 f在 n中是可忽略的，其中 f(n)= o(n −c)对每个固定的常数 c 成立。记号 poly(n)表示存在某个常数 c，使得 f(n)= O(nc)成立。用 N（分别地， Z和 R）表示正整数集（分别地，整数集和实数集）。此外，对于素数 q， Zq表示一个阶为 q的有限域（或伽罗瓦域）。对于2的幂 n，有 = Z[x]∕(x n+ 1)和q= Zq[x]∕(x n+1)。PPT是概率多项式时间的缩写。对于两个字符串 a、b， a和 b的连接记为 a ∥ b。矩阵用粗体大写字母表示（例如， X）。对于向量 x和矩阵 X， x和 X的欧几里得范数分别记为 ‖x‖和 ‖X‖。对于有限集合 Q， a ← Q表示 a从Q中按均匀分布随机选取。对于两个向量 a、b，a和 b的内积记为 ⟨a, b⟩。

3.2. 格

我们的实例化形式化基于NTRU格。在本节中，我们首先简要介绍格理论，然后回顾一些格困难假设。

一个 m‐维格 Λ是 Rm的一个加法离散子群。基本上，格是一组线性无关向量的所有整数组合的集合，这些线性无关向量称为格的基。格的形式化定义如下。

定义 1 （格）． 设 B=[b1 | ⋯|bn] ∈ Rm×n 是一个 m × n 矩阵，其中 b 1 ,…, b n ∈ Rm 是 n 组线性无关向量。由 B 生成的 m维格 Λ 是如下集合，
Λ(B)= Λ(b1 ,…, b n)={ ∑ i=1 n b i a i |ai ∈ Z}.
此外，当 n= m时，我们称一个格为满秩。

3.2.1. 困难性假设

雷格夫[11]提出了一种新的格难题假设，称为带误差学习（ LWE）；他证明了若干最坏情况格问题可以归约到LWE问题。此外，他还提出了首个基于LWE假设难度的公钥密码系统。

定义 2 （LWE假设）。 给定 n，m ∈ N、 q为一个素数，以及定义在 Zq 上的概率分布 χ。假设存在一个 oracle ns，它输出 m 个形如 (a, ⟨a, s⟩+ e) 的样本，其中每个样本的 a ∈ Znq 和 e ∈ χ 都是随机独立选取的，而 s在所有样本中保持不变。搜索‐LWE假设即为寻找该 s。此外，令 r 为一个输出样本 (a, b)←(Znq × Znq) 的 oracle 均匀地随机选择。判定‐LWE假设是指猜测你正在与 ns还是 r交互。

在雷格夫的开创性工作之后，许多基于LWE的密码系统被提出[29– 33]。然而，由于密钥大小过大和效率低下，这些密码系统遇到了实际问题。为了解决这一问题，2009年，柳巴舍夫斯基等[34]从[35],引入了一种新的LWE假设代数变体，并称之为环LWE。环‐LWE假设是专门针对有限域上的多项式环的LWE假设，其可以表述为“搜索”版本和 “决策”版本，定义如下。

定义 3 （环-LWE假设）。 给定 n，m ∈ N，设 q 为一个素数， χ 为定义在 q 上的概率分布。假设有预言机 s 输出 m 个形如 (a, ⟨a, s⟩+e) 的样本，其中 a ∈ q，且每个样本中的 e ∈ χ 均独立均匀随机选取，而 s ← q 在所有样本中保持不变。搜索‐环‐LWE假设是指找出 s。此外，设 r 为一个预言机，它随机均匀地输出样本 (a, b) ←(q × q)。判定‐环‐LWE假设是指猜测用户正在与 s 还是 r 交互。

另一个格难题假设是NTRU假设，定义在[36]中。

定义 4 （NTRU假设）。 设 χ是定义在 q上的概率分布。NTRU假设是指区分以下两种分布：第一种分布的样本为多项式 ℎ= g∕f，其中 f, g ← χ且 f可逆；第二种分布则在 q上均匀随机选取一个多项式 ℎ。

3.3. 基于关键词搜索的公钥加密

在本节中，我们介绍由Boneh 等人提出的PEKS的系统模型[2]。
一个PEKS方案由一组四元组概率多项式时间算法 =(KeyGen, P EKS, T rapdoor, T est)组成，描述如下：

• KeyGen(1 λ )： 以安全参数 λ作为输入，该算法输出一个主私钥 msk和一个主公钥mpk。
• PEKS(mpk,w)： 以主公钥 mpk和一个关键词w作为输入，该算法生成关键词 w的可搜索密文 c。
• Trapdoor(msk,w)： 以主私钥 msk和一个关键词 w作为输入，该算法生成一个陷门 t。
• Test(mpk, c, t)： 以主公钥 mpk、一个可搜索密文 c= PEKS(mpk,w) 和一个陷门 t= Trapdoor( msk,w′ )作为输入，如果 w= w′成立则该算法输出1，否则输出0。

定义5 (PEKS的正确性). 设 λ为一个安全参数。我们称一个PEKS方案是正确的，如果：
Pr[ Test( mpk, P EKS( mpk,w), T radpoor( msk,w))= 1]= 1 −negl(λ)，
其中 ( msk, mpk ) ← KeyGen ( 1 λ )。

4. 密码学基本构件

在本节中，我们回顾了在通用构造中用作构建模块的三个关键密码学原语：伪随机生成器、身份基加密和密钥封装机制。

4.1. 伪随机生成器

在我们的通用构造中，我们使用伪随机生成器来生成“伪随机”序列。非正式地说，如果不存在任何多项式时间的区分器能够区分一个字符串 s ← 与一个随机且均匀选择的字符串 s，则称分布 是伪随机的。我们回顾[37]定义3.15中伪随机生成器的定义。

定义 6 （伪随机生成器）。 设 F ∶{0, 1}n →{0, 1}n ′是一个确定性多项式时间算法，其中 n′= poly(n)且 n′> n。我们称 F是一个伪随机生成器，如果它满足以下两个条件：
扩展性：对于每个 n，都有 n′> n；
伪随机性：对于所有概率多项式时间区分器 ，
AdvPSE F,(n)=|Pr[(r)= 1] −Pr[(F(s))= 1]| ≤ negl(n),
其中 r从{0, 1}n ′中随机且均匀地选取，种子 s从{0, 1}n中随机且均匀地选取，概率取决于 使用的随机数以及 r和 s的选择。

4.2. 基于身份的加密（IBE）

身份基加密（IBE）是公钥加密的一个基本原语，其中用户的公钥是可以识别该用户的信息（例如电子邮件地址、姓名和社保号码）。这一概念最早由Shamir于1984年提出。然而，第一个实际构造是由 Cocks基于二次剩余问题实现的。随后，Boneh和Franklin利用对技术提出了一种更实用且安全的身份基加密方案。

一个基于身份的加密方案是由概率多项式时间算法  = (Setup,Extract,Enc,Dec) 组成的四元组，描述如下：

• Setup(1 λ )： 以安全参数 λ 作为输入，该算法输出主私钥 msk 和主公钥 mpk。
• Extract(msk, id)： 以主私钥 msk 和身份 id 作为输入，该算法输出对应于该身份的私钥 skid。
• Enc(mpk, id,m)： 以主公钥 mpk、身份 id 和消息 m 作为输入，该算法输出由 id 加密的密文 ct。
• Dec(skid , ct)： 以私钥 sk id 和可搜索密文 ct 作为输入，该算法输出一个解密后的消息 m′。

定义 7 （身份基加密的正确性）。 我们称一个基于身份的加密方案  是正确的，如果
Pr[Dec(sk id ,Enc(mpk, id,m))= m]= 1 −negl(λ)
其中 (mpk, msk)← Setup(1 λ ) 和 sk id ← Extract(msk, id)。

此外，一个基于身份的加密方案必须满足在任意自适应选择身份和选择明文攻击下的不可区分性（IND‐ID‐CPA），该安全性通过挑战者  与对手  之间的如下游戏来定义。

游戏 IND‐ID‐CPA:
- 设置。 在此阶段， 运行 Setup(1 λ )算法以生成主公钥 mpk和主私钥 msk。然后， 将 msk保密，并将 mpk发送给 。
- 阶段1。 对任意身份 id上的 Extract预言机进行多项式有界数量的查询，并且 向  返回一个私钥skid。
- 挑战. 在此阶段， 向 发送两条挑战消息 m0,m1以及一个挑战身份 id∗，其中 id∗之前未被查询过 Extract预言机。在收到消息和身份后， 随机选择一个随机比特 b ←{0, 1}，并生成挑战密文 ct∗ ← Enc(mpk, id∗,mb)。最后， 将ct∗返回给 。
- 阶段2。 可以继续请求与阶段1中相同的 Extract预言机。唯一的限制是 不能对挑战身份 id∗发起 Extract查询。
- 猜测。 输出其猜测 b′。如果 b′= b，则称该对手赢得游戏。  的优势如下：
AdvIND-ID-CPA , (λ)= |||| Pr[b′= b] − 1 2 |||| .

定义8 （IND-ID-CPA安全的IBE）． 我们称一个基于身份的加密方案  是 IND‐ID‐CPA 安全的，如果没有任何 PPT 攻击者  能以超过 negl(λ) 的优势在上述游戏中获胜。

此外，我们说一个基于身份的加密方案  是匿名的，如果它满足以下更强的安全性概念：

游戏IND‐ANON‐ID‐CPA:
- 设置。 在此阶段， 运行 Setup(1λ)算法以生成主公钥 mpk和主私钥 msk。然后 将 msk保密，并将 mpk发送给 。
- 阶段1。 向 Extract预言机对任意身份 id进行多项式有界数量的查询，且 返回一个私钥skid给 。
- 挑战. 在此阶段， 向 发送一个挑战消息 m以及两个挑战身份 id0, id1，其中 id0和 id1均未被查询过 Extract预言机。在接收到消息和身份后， 选择一个随机比特 b←{0, 1}，并生成挑战密文 ct∗← Enc(mpk, idb,m)。最后， 将 ct∗返回给 。
- 阶段2 可以继续请求 Extract预言机，与阶段1相同。唯一的限制是 不能对挑战身份 id0和 id1发起 Extract查询。
- 猜测。 输出其猜测 b′。
如果 b′= b，则称对手赢得游戏。 的优势定义如下：
AdvIND-ANON-ID-CPA , (λ)= | | | | Pr[b ′= b] − 1 2 | | | | .

定义9 （IND-ANON-ID-CPA安全的IBE）. 我们称一个基于身份的加密方案  是 IND‐ANON‐ID‐CPA 安全的，如果没有任何 PPT 攻击者  能以超过 negl(λ) 的优势在前述游戏中获胜。

4.3. 密钥封装机制 (KEM)

密钥封装机制（KEM）最早由Cramer和Shoup [42],提出，是公钥加密的一种变体。KEM并不加密消息，而是使用公钥对一个随机值进行“封装”（encaps），并输出一个封装结果。通过相应的私钥，任何人都可以对该封装结果进行“解封装”（decaps），以获得相同的随机值。

一个KEM方案是三个概率多项式时间算法的三元组， = (KeyGen,Encaps,Decaps)，描述如下。

• KeyGen(1 λ )： 以安全参数 λ作为输入，该算法输出一个公钥 pk和一个私钥 sk。
• Encaps( pk )： 以公钥 pk 作为输入，该算法输出一个密钥 k 和一个封装 e。
• Decaps(sk, e)： 以私钥 sk 和一个封装 e 作为输入，该算法输出对应的密钥 k，或一个无效符号 ⊥。

定义10 (KEM的正确性). 我们说一个密钥封装机制方案  是正确的，如果
Pr[Decaps(sk, e)= k ∶(k, e)← Encaps(pk)]= 1 −negl(λ),
where(pk, sk)← KeyGen(1λ).

自适应选择密文攻击下的不可区分性（IND‐CCA2）安全性通过以下挑战者 与对手 之间的游戏来定义。

游戏IND‐CCA2:
- 密钥生成。 在此阶段， 运行 KeyGen(1λ)算法以生成公钥/私钥密钥对(pk, sk)。然后， 将 pk发送给。
- 阶段1。 对 Decaps预言机在任意封装 e上进行多项式有界数量的查询； 向 k返回一个密钥 ⊥或无效符号 。
- 挑战。 在此阶段， 选择一个随机比特 b ←{0, 1}。然后，  生成(e∗, k∗ 0)← Encaps(pk)，并从密钥空间 中随机选择 k∗ 1。最后， 将挑战密文(e∗, k∗ b)返回给 。
- 阶段2。 可以继续像阶段1一样向 Decaps预言机发出查询。唯一的限制是 不能对 e∗发起 Decaps查询。
- 猜测。 输出其猜测 b′。
我们说如果 b′= b，则对手赢得游戏。 的优势定义为
AdvIND-CCA2 ,(λ)= | | | | Pr[b ′= b] − 1 2 | | | | .

定义 11 （KEM的IND-CCA2）。 我们称一个密钥封装机制方案 是 IND‐CCA2安全的，如果不存在PPT攻击者 能够在前述游戏中以超过 negl(λ)的优势获胜。

5. 指定密文可搜索加密（DCSE）

在本节中，我们形式化了DCSE方案的系统模型及其安全性模型。

5.1. 系统模型

我们扩展了Boneh等人工作的系统模型[2]。在DCSE中，陷门不仅与关键词相关联，还与密文相关联。更具体地说，每个密文都有一个相应的标签，数据接收者使用该标签和关键词共同生成用于搜索的陷门。
设 λ为安全参数， 为关键词空间， 为密文空间， 为标签空间。DCSE方案是由四个概率多项式时间算法组成的四元组 =(KeyGen, DCSE, Trapdoor, Test)，其描述如下。

• KeyGen(1 λ )： 输入安全参数 λ，该算法输出一个公钥 pk和一个私钥 sk。
• DCSE(pk,w)： 输入公钥 pk和关键词 w ∈，该算法输出一个可搜索密文 c ∈ 和该密文的标签 v ∈ 。
• Trapdoor( sk,w′, v′ )： 输入一个私钥 sk、一个关键词 w′ ∈ 和一个密文的标签 v ′ ∈  ，该算法输出一个陷门 t。
• Test(c, t)： 以可搜索密文 c 和陷门 t 作为输入，该算法在 t 和 c 共享相同关键词且 t 确实由对应于 c 的标签生成时输出 1；否则输出 0。

定义12 (DCSE的正确性). 设 λ为安全参数，为关键词空间， (pk, sk) ← KeyGen(1λ)，且(c, v)是由DCSE(pk,w)生成的一对可搜索密文及其对应的标签，其中 w ∈ 。我们称一个DCSE方案是正确的，如果：
Pr[Test(c, T rapdoor(sk,w, v))= 1]= 1 −negl(λ).

5.2. 安全模型

我们要求提出的DCSE方案满足以下两个安全要求：选择关键词攻击下的不可区分性（IND‐CKA）和内部人员关键词猜测攻击下的不可区分性（IND‐IKGA），这两个安全性通过对手 与挑战者 执行的以下两个游戏进行建模。需要注意的是，由于恶意内部人员的能力强于恶意外部人员，因此我们在此仅考虑IND‐IKGA。

5.2.1. 选择关键词攻击下的不可区分性

IND‐CKA 安全性确保对手无法从密文及其对应的标签中获取任何关于关键词的信息。

游戏 IND‐CKA:
- 密钥生成。 在此阶段， 运行 KeyGen(1λ)算法以生成用户的公钥 pk和私钥 sk。然后， 将pk发送给 。
- 阶段1。 向 Trapdoor预言机发起多项式有界数量的查询。当 对(w, v)发起此类查询时，使用私钥 sk通过 Trapdoor算法生成陷门 t并返回给  。
- 挑战 发送两个挑战关键词 w0,w1 ∈，其中w0,w1在阶段1中未被查询过。 选择一个随机比特 b ←{0, 1}，从 DCSE(pk,wb) 生成挑战密文 c∗和相应的挑战标签 v∗，并返回(c ∗, v∗ )给 。
- 阶段2。 可以继续向 T rapdoor预言机查询，与阶段1相同。唯一的限制是
不能对 w0或 w1发起 T rapdoor查询。
- 猜测。 输出其猜测 b′。
如果 b′= b成立，则称对手赢得游戏。 赢得此游戏的优势定义为
AdvIND-CKA ,(λ)= | | | | Pr[b ′= b] − 1 2 | | | | .

定义13 (DCSE的IND-CKA)。 我们称一个DCSE方案 是IND‐CKA安全的，如果不存在PPT攻击者 能够在前述游戏中以超过 negl(λ)的优势赢得游戏。

5.2.2. 内部人员关键词猜测攻击下的不可区分性

IND‐IKGA安全性确保了对手无法从陷门中获得关于关键词的任何信息。
IND‐IKGA游戏：
- 密钥生成. 在此阶段， 运行 KeyGen(1 λ )算法以生成用户的公钥 pk和私钥 sk。然后， 将pk发送给 。
- 阶段1。 向 T rapdoor预言机发起多项式有界数量的查询。当  对(w, v)提出此类查询时， 使用私钥 sk通过 Trapdoor算法生成陷门 t并返回给 。
- 挑战 发送两个挑战关键词 w0,w1 ∈，其中w0,w1在阶段1中未被查询过。 首先从 中随机选择一个标签 v∗。然后，它选择一个随机比特 b←{0, 1}并生成挑战陷门 t∗ ← Trapdoor(sk,wb, v∗)。最后， 将 t∗返回给 。
- 阶段2. 可以继续查询 T rapdoor预言机，与阶段1相同。唯一的限制是 不能对 w0或 w1发起 T rapdoor查询。
- 猜测. 输出其猜测 b′。
我们说攻击者赢得游戏，如果 b′= b。 赢得此游戏的优势定义为
AdvIND-IKGA ,(λ)= |||| Pr[b′= b] − 1 2 |||| .

定义14 (DCSE的IND-IKGA). 我们说一个DCSE方案 是IND‐IKGA安全的，如果不存在PPT攻击者 能够以前述游戏中超过 negl(λ)的优势赢得该游戏。

6. DCSE的高效通用构造

在本节中，我们首先提出一种从IND‐ANON‐ID‐CPA安全的IBE方案和IND‐CCA2安全的KEM方案构造DCSE的通用构造方法。然后，我们给出严格的证明，以表明该构造满足第5节中定义的正确性和安全性要求。

6.1. 通用构造

为了构造一个DCSE方案 ，我们首先设置以下参数。令 =(Setup,Extract,Enc,Dec)为一个IND‐ANON‐ID‐CPA安全的基于身份的加密方案，且 =(KeyGen,Encap,Decaps)为一个 IND‐CCA2安全的KEM。设和 分别为 的关键词空间和密文空间，令 为 的密钥空间。令 F ∶ → 是一个具有适当定义域和值域 的伪随机生成器。其中，定义域 包含任意关键词 w ∈ 与任意密钥 k ∈ 的拼接结果，即 ={w ∥ k ∣ w ∈ ∧k ∈ }。此外，令值域 包含算法 .Extract所使用的适当长度的随机性。另外，令 H是一个定义在{0, 1} ∗×{0, 1} ∗→{0, 1} ∗上的抗碰撞哈希函数。然后，我们从算法1到算法4给出DCSE的通用构造。

算法 1 KeyGen(1 λ )
输入: 安全参数 λ
输出: 用户的密钥对 (pk, sk)
1: (pk1, sk1)← .KeyGen(1 λ )
2: (pk2, sk2)← .Setup(1 λ )
3: 设置公钥 pk=(pk1, pk2)，私钥 sk=(sk1, sk2)
4：输出一个密钥对 (pk, sk)

在此构造中，数据接收者的公钥和私钥由 .KeyGen(1 λ )和 .KeyGen(1 λ )生成。为了为关键词 w生成可搜索密文 c，数据拥有者首先使用密钥封装机制（KEM），利用数据接收者的公钥 (e, k)← .Encaps(pk)随机生成一个密钥 k及其对应的封装 e。然后，他运行 f ← (w ∥ k)获得一个伪随机数，该数可被视为一个 “身份”。接着，他选择一个随机值 r，并使用身份 f对其进行加密，即 ct ← .Enc(pk, f, r)，并计算一个哈希值 ℎ= H(ct, r)。最后，他输出一个可搜索密文 c=( ct, ℎ)和一个标签 v= e。这里我们注意到，如果数据拥有者希望为同一数据接收者加密不同的关键词，他可以重复使用相同的密钥 k，而无需重新运行封装算法，从而降低计算开销。

算法 2 DCSE(pk,w)
输入： 数据接收者的公钥 pk=(pk1, pk2) 和一个关键词 w ∈
输出: 一个可搜索密文 c 和该密文的标签 v
1: (e, k)← .Encaps(pk1)
2: 随机选择 r←{0, 1}∗
3: f ← F(w‖k)
4: ct ← .Enc(pk2, f, r)
5: 计算 ℎ= H(ct, r)
6: 输出一个密文 c=(ct, ℎ)和标签 v= e

为了生成用于搜索通过关键词 w加密的可搜索密文的陷门，数据接收者首先获取标签中隐藏的密钥k ← .Decaps(sk1, v)，并计算“身份” f ← F(w ∥ k)。然后，他为身份 f生成陷门 t， t ← .Extract(sk, f)，并将其发送到服务器。

算法 3 T rapdoor(sk,w, v)
输入： 用户的私钥 sk=(sk1, sk2)，一个关键词 w ∈ ，及其对应的标签 v= e
输出： 关键词 w和标签 v的陷门 t
1: k← .Decaps(sk1, v)
2: if k= ⊥ then
3: 将陷门 t设为无效符号 ⊥
4: else
5: f ← F(w‖k)
6: 设置陷门 t← .Extract(sk2, f)
7: endif
8: 输出一个陷门 t

接收到陷门后，由于密文实际上是通过某个身份加密的，服务器首先解密该密文以获得明文 r ← .Dec(t, ct)。然后可以检查是否 H(ct, r)= ℎ。如果匹配，则输出 1；否则输出 0。在现实场景中，数据接收者不仅可以发送陷门，还可以发送她或他使用的附加标签。服务器随后可以将该标签作为索引，快速查找可能需要测试的任何可搜索密文。

算法 4 T est(c, t)
输入: 一个可搜索密文 c=(ct, ℎ)，以及一个陷门 t
输出： 如果 t匹配 c则为1，否则为0
1: 如果 t= ⊥ 那么
2: 输出 0
3： 否则
4: r← .Dec(t, ct)
5: 如果 H(ct, r)= ℎ 则输出 1，否则输出 0
6: 结束如果

6.2 正确性与安全性证明

定理 1。 根据定义 12，所提出的构造是正确的。
定理 1 的证明定理 1。 设 (c=(ct, ℎ), v) ← DCSE(pk,w)为一个有效的可搜索密文及其对应的标签，且令 t ← Trapdoor(sk,w, v)为一个有效的陷门，其中 (pk, sk) ← KeyGen(1 λ )。由于 t实际上是基于身份的加密方案中身份 F(w ∥ k)的私钥，而 ct是使用身份 F(w ∥k)对随机值 r进行加密所得到的密文。根据基于身份的加密方案的正确性（定义 7），可以以极大概率获得 r ←.Dec(t, ct )。因此，H ( ct, r) = ℎ；于是我们有 T est ( c, t ) = 1。 □

接下来，我们证明所提出的通用构造是IND‐CKA安全的和 IND‐IKGA安全的。总体而言，我们的策略是使用一系列游戏：逐步修改挑战阶段的结构，使得在最终的游戏中的挑战不包含任何关键词。因此，攻击者在IND‐CKA和IND‐IKGA游戏中获胜的优势不会高于纯粹的猜测。

定理2。 如果底层的密钥封装机制方案 是IND-CCA2安全的，且基于身份的加密方案 是IND-ANON-ID-CPA安全的，则所提出的方案 是IND-CKA安全的。
证明 定理2。 我们通过定义如下的一系列游戏来证明 定理2。
- Game0： 这是原始的IND‐CKA游戏，如第 5.2.1 节所示。
- Game1： 我们现在对前述游戏进行轻微修改。不再从 .Encaps(pk1) 获取 k，而是从 .Encaps(pk1) 的输出范围内随机选择 k′。
- Game2： 现在我们将 Game1 转换为 Game2。在此游戏中，令 f= F(w ∥ k′)；我们将值 ct ← .Enc(f, r) 替换为 ct ← .Enc(f′, r)，其中 f′ 从  中随机选取，  是 F 的输出范围。
设 Advi表示对手在 Gamei中获胜的优势。我们有以下引理。

引理 1。 对于所有概率多项式时间算法 01，若底层的密钥封装机制方案  是 IND-CCA2 安全的，则 |Adv0 −Adv1| 是可忽略的。
引理 1 的证明。 假设存在一个对手 01使得|Adv0 −Adv1|是不可忽略的，则存在另一个挑战者 01能够在底层的密钥封装机制方案 的 IND‐CCA2 游戏中以不可忽略的优势获胜。
- 密钥生成。 01首先调用  的 IND‐CCA2 游戏以获得 pk1。接着， 01 计算 (pk2, sk2) ← .Setup(1 λ )。最后， 01 设置公钥 pk=(pk1, pk2)， 并将 pk 发送给 01。
- 阶段1。 在此阶段， 01可以对(pk,w, v)进行多项式次数的 Trapdoor查询， 01按如下方式响应。 01首先在 v上调用 .Decaps预言机。该预言机返回一个无效符号 ⊥或一个有效密钥 k。如果预言机返回 ⊥，则 01也向 01返回 ⊥。否则， 01计算 f ← F(w ∥ k)和 t← .Extract(sk2, f)。最后，将 t返回给 01。
- 挑战. 01发送两个挑战关键词 w0,w1 ∈，其中w0,w1在阶段1中未被查询过。收到这些挑战关键词后， 01选择一个随机比特 b ←{0, 1}，并执行以下步骤：
– 调用 IND‐CCA2 游戏的挑战阶段以获取挑战密文 (e ∗, k∗ )。– 选取 r∗←{0, 1} ∗。– 计算 f ∗← F(wb ∥k ∗ )。– 计算 ct∗← .Enc(f ∗, r∗)。– 计算 ℎ∗= H(ct∗, r∗)。– 设置 v∗= e∗。
然后， 01将(c ∗=(ct∗, ℎ∗ ), v ∗ )返回给 01。
- 阶段2。 01可以继续进行 T rapdoor查询，与阶段1相同。唯一的限制是  01不能对 w 0或 w 1进行 Trapdoor查询。
- 猜测。 01 输出其猜测 b′。然后 01 输出 b′。
注意，如果 k∗ 是一个有效密钥，则 01 向 01 提供 Game0 的视图；如果 k∗ 是一个随机元素，则 01 向 01 提供 Game 1 的视图。如果 |Adv0 −Adv1 | 是不可忽略的，则 01 对底层密钥封装机制方案的 IND‐CCA2 游戏也必须具有不可忽略的优势。因此，
|Adv0 −Adv1 | ≤ AdvIND-CCA2 , 01 ( λ ) . □

引理2。 对于所有概率多项式时间算法， 12,|Adv1 −Adv2|是可忽略的，如果底层的身份基加密方案 是IND-ANON-ID-CPA安全的。
引理2的证明。 假设存在一个对手 12使得|Adv1 −Adv2|是不可忽略的， 则存在另一个挑战者12能够以不可忽略的优势赢得底层基于身份的加密方案 的IND‐ANON‐ID‐CPA游戏。 12构造一个与对手 12 交互的混合游戏如下：
- 密钥生成。 12首先调用 的IND‐ANON‐ID‐CPA游戏 以获得 pk2；然后， 12 计算 (pk1, sk1)← .KeyGen(1λ)。 最后， 12设置公钥 pk=(pk1, pk2)，并将 pk发送给 12.
- 阶段1。 在此阶段， 12能够对(pk,w, v)进行多项式次数的 Trapdoor查询， 12按如下方式响应。12首先获得 k← .Decaps(v, sk1)。如果 k是无效符号 ⊥，则 12将 ⊥返回 给 12。否则， 12调用 .Extract预言机作用于 F(k ∥ w)以获 得一个陷门 t。最后， 12将 t发送给12。
- 挑战. 12发送两个挑战关键词 w0,w1，其中w0,w1在阶段1中 未被查询过。 12选择一个随机比特 b←{0, 1}，并执行以下步骤：
– 计算(e∗, k∗)← .Encaps(pk1)。– 从.Encaps(pk1)的 输出范围内随机选择 k′∗ 。– 随机选择 f′ ← 。– 选取 r∗←{0, 1}∗。– 使用 F(wb ∥ k′∗, r∗)和(f′, r∗)调用 IND‐ANON‐ID‐CPA游戏的挑战阶段以获得挑战密文 ct∗。– 计算 ℎ∗= H(ct∗, r∗)。– 设置 v∗= e∗。
然后， 12将(c ∗=(ct∗, ℎ∗ ), v ∗ )返回给 12。
- 阶段2 12可以继续进行 Trapdoor查询，类似于阶段1。唯一的限 制是 12不能对 w0或 w1进行 T rapdoor查询。
- 猜测。 12输出其猜测 b′。然后， 12输出 b′。
如果 ct ∗ 是由 (F(wb ∥ k′∗), r ∗ ) 生成的，则 12 向 Game1 提供 12 的视图；如果 ct ∗ 是由 (f ′, r∗) 生成的，则 12 向 Game2 提供 12 的视图。如果 |Adv1 −Adv2| 是不可忽略的，则 12 在底层基于身份的加密方案的 IND‐ANON‐ID‐CPA 安全性游戏中也必须具有不可忽略的优势。因此，
|Adv1 −Adv2| ≤ Adv IND-ANON-ID-CPA ,12 (λ). □

引理3. Adv2= 0.
证明 引理3。 引理3的证明是直观的。由于可搜索密文 c∗与关键词 w0, w1无关，因此该密文不会泄露任何关于关键词的信息。对手 2只能通过猜测来返回 b′。因此，
Adv2= 0. □

根据游戏 IND‐CKA 的定义， Adv0= AdvIND-CKA  ，(λ)。结合 引理 1、2 和 3，我们得到
AdvIND-CKA , (λ) ≤ Adv IND-CCA2 , 01 (λ)+ Adv IND-ANON-ID-CPA , 12 (λ).
因此，如果底层的密钥封装机制和基于身份的加密方案是安全的，那么攻击者优势接近于0。这完成了定理2的证明。 □

定理3. 如果底层的密钥封装机制方案 是IND-CCA2安全的，且伪随机生成器 F满足伪随机性，则所提出的方案是IND-IKGA安全的。
证明定理3. 我们通过如下定义的游戏序列来证明 定理3。
- Game0： 这是原始的IND‐IKGA游戏，如第5.2.2节所示。
- Game1： 此游戏与 Game0完全相同，只是 k是从 .Encaps(pk1)的 输出范围内随机选取的，而不是由 .Encaps(pk1)计算得出。
- Game2： 此游戏与 Game1相同，只是 f是从 中随机选取的，而不是从 F(wb ∥k)计算得出。
设 Advi表示对手在 Gamei中的攻击者优势。我们有以下引理。

引理 4。 对于所有概率多项式时间算法， 01，|Adv0 −Adv1|是可忽略的，如果底层的密钥封装机制方案 是IND-CCA2安全的。
引理 4 的证明。 假设存在一个对手 01使得|Adv0 −Adv1|是不可忽略的，则存在另一个挑战者 01能够以不可忽略的优势赢得底层密钥封装机制方案 的 IND‐CCA2 游戏。
- 密钥生成。 01首先调用 的IND‐CCA2游戏以获得pk1。接着， 01计算(pk2, sk2) ← .Setup(1λ)。最后， 01设置公钥 pk=(pk1, pk2)，并将 pk发送给 01。
- 阶段1。 在此阶段， 01可以对(pk,w, v)进行多项式次Trapdoor查询， 01按如下方式响应：01首先调用 v上的 .Decaps预言机。该预言机返回一个无效符号 ⊥或一个有效密钥 k。如果预言机返回 ⊥，则 01也向 ⊥回复 01。否则， 01计算 f= F(w ∥ k)和t← .Extract(sk2, f)。最后，将 t返回给 01。
- 挑战 01发送两个挑战关键词 w0,w1 ∈，其中w0,w1在阶段1中 未被查询过。 01选择一个随机比特 b←{0, 1}，并执行以下步骤：
– 调用 IND‐CCA2 游戏的挑战阶段以获取挑战 (e ∗, k∗ )。– 计算 f ∗← F(wb ∥k ∗ )。– 计算 t∗← .Extract(sk2, f)。
然后， 01将 t∗返回给 01。
- 阶段2。 01可以继续进行 T rapdoor查询，与阶段1相同。唯一的 限制是 01不能对 w0或 w1进行 T rapdoor查询。
- 猜测。 01输出其猜测 b′。然后， 01输出 b′。
如果 k∗ 是一个有效密钥，则 01 向 01 提供 Game0 的视图；如果 k∗ 是一个随机元素，则 01 向 01 提供 Game1 的视图。如果 |Adv0 −Adv1| 是不可忽略的，则 01 在 IND‐CCA2 游戏中也必须具有不可忽略的优势。因此，
|Adv0 −Adv1| ≤ Adv IND-CCA2 , 01 (λ). □

引理5。 对于所有概率多项式时间算法， 12,|Adv1 −Adv2 |是可忽略的，如果 F是一个安全的伪随机生成器。
引理5的证明。 我们通过描述一个PPT归约算法 12来证明该引理，该算法参与一个伪随机生成器安全性游戏。给定一个挑战字符串 T ∈  和一个伪随机生成器的描述 F，  12 构造一个混合游戏，并与一个对手  12 进行如下交互。
- 密钥生成。  12 选择公共参数，如第6.1节所述，但不同之处在于，不是从伪随机生成器族中选择一个合适的伪随机生成器，而是  12 将 F设为公共参数。然后，  12 生成密钥对( pk, sk) ←KeyGen(1 λ )，并将 pk发送给  12 。注意，  12 完全掌控私钥 sk。

表1 基于安全属性与相关方案的比较。
| 方案 | 抗量子性 | IKGA安全性 |
| :— | :— | :— |
| [2] | ✗ | ✗ |
| [7] | ✓ | ✗ |
| [8] | ✓ | ✗ |
| [10] | ✓ | ✗ |
| [9] | ✓ | ✓ |
| Ours | ✓ | ✓ |

表2 基于密钥大小、陷门大小和密文大小（字节）与相关方案的比较。注意 |ID| 指的是用户身份的长度。
| 方案 | PK | SK | 陷门 | 密文 |
| :— | :— | :— | :— | :— |
| [2] | 0.38 | 0.19 | 0.38 | 0.57 |
| [7] | 27.2 | 35 | 27 | 52 |
| [8] | |ID| | 560 128 | 113 | 113 |
| [10] | 3657.05 | 139 325.1 | 142.86 | 14.28 |
| [9] | 3657.42 | 139 325.1 | 71.42 | 57.14 |
| Ours | 31.88 | 59.98 | 38.98 | 23 |

表3 不同操作的耗时（每秒操作次数），包括密钥生成（KeyGen）、加密（[2,7]中的 PEKS和我们的方案中的DCSE）、提取（Extract）和测试（Test）。
| 方案 | 密钥生成 | 加密 | 提取 | Test |
| :— | :— | :— | :— | :— |
| [2] | 84.88 | 186.48 | 17.41 | 100 908.17 |
| [7] | 0.10 | 349.28 | 67.42 | 174.64 |
| Ours | 26.56 | 3224.35 | 739.06 | 63 451.77 |

• 阶段1。 在此阶段， 12可以使用(pk,w, v)进行多项式次 Trapdoor查询。由于知晓 sk， 12只需运行 T rapdoor算法即可回答这些查询。
• 挑战. 12发送两个挑战关键词 w0,w1 ∈，其中w0,w1在阶段1中未被查询过。 12选择一个随机比特 b←{0, 1}，并执行以下步骤：
  – Set f ∗= T.
  – Compute t∗← .Extract(sk2, f ∗ ).
  然后， 12将 t∗返回给 12。
  注意，如果 T 是由 F 生成的，则 12 向 Game1 提供 12 的视图；如果 T 是从  中随机选取的随机字符串，则 12 向 Game2 提供 12 的视图。如果 |Adv1 −Adv2| 是不可忽略的，则 12 在伪随机生成器安全性游戏中也必须具有不可忽略的优势。因此，
  |Adv1 −Adv2| ≤ Adv PSE F,12 (λ). □

引理6. Adv2= 0.
引理6的证明引理6。 引理6 的证明是直观的。由于陷门 t∗与关键词无关， w0和 w1，因此陷门不会泄露任何关于关键词的信息。对手2只能通过猜测返回 b′。因此，
Adv2 = 0. □

根据IND‐IKGA游戏的定义， Adv 0 = AdvIND-IKGA  ，(λ)。结合 引理4、5和6，我们得到
AdvIND-IKGA , (λ) ≤ AdvIND-CCA2 , 01 (λ)+ Adv PSE F, 12 (λ).
因此，如果底层的KEM和伪随机生成器是安全的，则对手的优势与0几乎不可区分。这完成了定理3的证明。 □

7. 高效实例化与比较

在本节中，我们首先提出了一种基于NTRU格的DCSE实例化。然后，我们将该实例化的各个方面与其他最先进的方案进行比较。

7.1. 高效实例化

我们的实例化利用了Ducas等人提出的身份基加密[13]和Hülsing等人提出的密钥封装机制[14]（以下分别称为DLP‐IBE和HRSS‐KEM）。
DLP‐IBE 是首个具有实用参数的基于格的身份基加密方案。其安全性基于 NTRU 和环‐LWE 假设。此外， Behnia 等人 [7] 还证明了 DLP‐IBE 是 IND‐ANON‐ID‐CPA 安全的。DLP‐IBE 的首个实现由 Ducas 1 提供，基于 NTL 库 [43] 用 C++ 编写。尽管该实现效率很高，但它仅仅是一个概念验证，未进行任何优化。为了提高效率， McCarthy 等人 [44] 提出了一种 DLP‐IBE 的实用化实现，使用 ANSI C 编写，并采用了数论变换（NTT）优化技术。
HRSS‐KEM 是美国国家标准与技术研究院后量子项目第二轮中的候选密码学KEM。2在该研究中，Hülsing 等人首先提出了一种参数优化的OW‐CPA安全的基于NTRU的加密方案；然后，他们在量子可访问随机预言模型下将该方案转换为IND‐CCA2安全的基于NTRU的KEM。
对于具体的实例化，我们使用SHA256作为安全哈希函数，并使用对称加密AES‐256作为伪随机生成器。我们采用开源项目软件实现DLP‐IBE3和 HRSS‐KEM4，在配备10G内存的Intel Core i7‐8700 3.2‐GHz CPU上测试了我们的DCSE方案的可行性。对于DLP‐IBE，我们选择参数n= 1024, q ≈ 227以达到192位安全级别；对于HRSS‐KEM，我们选择参数 n= 701, p= 3, q= 8192以达到128位安全级别。

7.2. 比较

为了将所提出的方案与其它最先进的方案进行比较，我们设置参数如下：对于[2],中的基于配对的PEKS方案，我们选择160位群阶和2048位群元素 , T；对于[7],中的基于NTRU的PEKS方案，我们选择n= 1024, q= 227 以实现192位安全级别；对于[8–10],中的基于LWE的PEKS方案，我们采用与[8],相同的安全部署参数，即 n= 256、维度 m= 9753以及素数 q= 4093。此外，我们设置不同关键词的数量为 k= 1，异常关键词为 k′= 1，适用于[9],，安全级别为 l= 10，适用于[10]。
表1 基于安全属性比较了我们的方案与其他方案。只有毛等人的工作 [9]是抗量子的且IKGA安全的。然而，如 表2所示，该方案过大的密钥大小使其不具实用性。我们还注意到，毛等人的方案需要另一个服务器来执行测试算法，从而增加了计算开销。此外，与毛的方案相比， [9],我们的公钥和私钥大小缩小了1/115倍。
在表3中，我们进一步从效率角度将我们的实例化方案与另外两个实用的PEKS方案[2,7]进行比较。具体而言，我们采用PBC库5以及由6作者提出的开源[7]方法来分别实现[2]和[7],。与[2],相比，尽管我们的实例化方案分别慢了0.31倍和0.62倍密钥生成和测试算法相比，我们的实例化分别比加密和提取算法快17