《带有关键字搜索的公钥加密》文章阅读

摘要

我们研究使用公钥系统加密的数据的搜索问题。考虑用户Bob向用户Alice发送用Alice的公钥加密的电子邮件。电子邮件网关想要测试电子邮件是否包含关键字“紧急”，以便它可以相应地路由电子邮件。另一方面，Alice不希望给网关解密她所有消息的能力。我们定义并构建了一种机制，使Alice能够向网关提供密钥，使网关能够测试单词“urgent”是否是电子邮件中的关键字，而无需了解关于该电子邮件的任何其他信息。我们将这种机制称为带有关键字搜索的公钥加密。作为另一个例子，考虑一个邮件服务器，它存储了由他人为Alice公开加密的各种消息。使用我们的机制，Alice可以向邮件服务器发送一个密钥，该密钥将使服务器能够识别包含某些特定关键字的所有邮件，但不了解其他内容。我们用关键字搜索定义了公钥加密的概念，并给出了几种构造。

介绍

假设用户Alice希望在多种设备上阅读她的电子邮件：笔记本电脑、台式机、寻呼机等。Alice的邮件网关应该根据电子邮件中的关键字将电子邮件路由到合适的设备。例如，当Bob发送带有关键字“紧急”的电子邮件时，该邮件被路由到Alice的寻呼机。当Bob发送带有关键字“午餐”的电子邮件时，该邮件被路由到Alice的桌面以便稍后阅读。人们期望每封电子邮件包含少量的关键词。例如，主题行中的所有单词以及发件人的电子邮件地址可以用作关键词。移动人员项目提供这种电子邮件处理功能。
现在，假设Bob使用Alice的公钥向Alice发送加密的电子邮件。电子邮件的内容和关键字都是加密的。在这种情况下，邮件网关看不到关键字，因此无法做出路由决定。因此，移动人员项目无法在不侵犯用户隐私的情况下处理安全电子邮件。我们的目标是使Alice能够给网关测试“紧急”是否是电子邮件中的关键字的能力，但是网关不应该了解关于电子邮件的任何其他信息。更一般地说，Alice应该能够指定邮件网关可以搜索的几个关键字，但不了解关于传入邮件的任何其他信息。我们在第节中给出了精确的定义。

为此，Bob使用标准的公钥系统加密他的电子邮件。然后，他将每个关键字的关键字搜索(PEKS)公钥加密附加到生成的密文上。为了发送带有关键字 $W_{1},...,W_{m}$ 的消息M，Bob发送：

$E_{A_{pub}}(M)||PEKS(A_{pub},W_{1})||…||PEKS(A_{pub},W_{m})$

其中 $A_{pub}$ 是Alice的公钥。这种形式的加密的要点是Alice可以给网关一个特定的陷门 $T_{W}$ ，使网关能够测试与消息相关联的关键字之一是否等于Alice选择的单词 $W$ 。给定 $PEKS(A_{pub},W')$ 和 $T_{W}$ ，网关可以测试是否满足 $W=W'$ 。如果 $W≠W'$ 网关不了解更多关于 $W'$ 的信息。注意Alice和Bob在整个过程中没有交流。Bob根据Alice的公钥为 $W'$ 生成可搜索加密。
在某些情况下，将电子邮件网关视为IMAP或POP电子邮件服务器是有启发性的。服务器存储**电子邮件，每封电子邮件包含少量关键字。和以前一样，所有这些电子邮件都是由不同的人用Alice的公钥加密发送给Alice的。我们希望Alice 能够提出以下形式的查询：服务器上的任何消息包含关键字“urgent”吗？Alice将通过给服务器一个陷门 $T_{W}$ 来做到这一点，从而使服务器能够检索包含关键字W的电子邮件。
相关工作。一个相关的问题涉及数据库数据的隐私。有两种不同的场景：公共数据库和私有数据库，每种场景的解决方案都是不同的。
私有数据库：在这种设置中，用户希望将其私有数据上传到远程数据库，并希望对远程数据库管理员保持数据私有。之后，用户必须能够从远程数据库中检索包含特定关键字的所有记录。奥斯特洛夫斯基在20**90年代初提出了解决这个问题的方法26]还有奥斯特洛夫斯基和戈德里奇[17]以及最近由宋在阿尔。[28]. 宋之解。至少28]需要用户和数据库之间很少的通信(与安全参数成比例),并且只需要一**互。对于每个查询，数据库执行线性大小的工作。的解决方案26,17]需要在用户和之间进行多对数循环(以数据库的大小为单位)数据库，但是允许数据库在每个查询中只进行多元对数运算。在某些情况下，另一个可能有吸引力的隐私要求是对数据库管理员隐藏有关访问模式的任何信息，即，如果某个项目被检索了不止一次，则某个项目根本没有被检索，等等。费一定工夫的事[26,17]以相同的多对数成本也实现了这一特性5针对数据库-用户交互和实际数据库工作的每个查询。我们强调[26,17]以及[10,28,16]仅适用于拥有其数据并希望将其上传到他们不信任的第三方数据库的用户的私钥设置。
公共数据库这里，数据库数据是公共的(例如股票报价)，但是用户并不知道它，并且希望检索某个数据项或搜索某个数据项，而不向数据库管理员透露它是哪个项。简单的解决方案是用户可以下载整个数据库。公共信息检索(PIR)协议允许用户以比下载整个数据库小得多的通信量从公共数据库中检索数据。PIR首先被证明仅在存在相同数据库的**拷贝并且没有一个拷贝能够相互对话的情况下才是可能的[5].Kushilevitz和Ostrovsky证明PIR对于单一数据库是可能的[22](使用同态加密方案[19]).通信的复杂性[22] 解(即用户和数据库之间传输的比特数)是O(nє，其中n是数据库的大小，ϵ > 0。这被卡钦、米卡里和斯塔德勒简化为多对数开销[4].正如在中指出的[2[2]，PIR的模型可以扩展到n取一的不经意传输和公共数据上的关键字搜索，并且在文献中受到了很多额外的关注(例如，参见[22,8,20,9,23,25,27].我们强调，在所有这些设置中，数据库是公共的，用户试图检索或找到某些项目，而不向数据库管理员透露它正在搜索什么。在单个公共数据库的设置中，可以表明数据库必须总是执行至少与数据库大小成线性关系的工作。
我们的问题不符合上面提到的两个模型中的任何一个。与私钥设置不同，邮件服务器收集的数据来自第三方，用户不能以任**便的方式“组织”这些数据。与公开可用的数据库不同，数据不是公开的，因此PIR解决方案不适用。
我们指出，在实际应用中，由于公钥加密的计算成本，我们的构造适用于搜索少量的关键字，而不是整个文件。最近，沃特斯等人[30]展示了可以使用带有关键字搜索的公钥加密来构建加密且可搜索的审计日志。中介绍了搜索加密数据的其他方法[16,12]。

带搜索的公钥加密的定义

本文中，我们使用可忽略函数来指代一个函数 $f:R\rightarrow \left[ 0,1 \right]$ ，其中 $f(s)<1/g(s)$ ，对于任意多项式 $g$ 和足够大的 $s$ 。

我们首先精确定义什么是安全的带有关键字搜索的公钥加密(PEKS)方案。这里的“公钥”指的是不同的人使用Alice的公钥创建密文的事实。假设用户Bob将要向Alice发送带有关键字 $W_{1},...,W_{k}$ 的加密电子邮件（例如，主题行和发件人地址中的单词可以用作关键字，所以k相对较小）。Bob发送了以下消息：

$\left[ E_{A_{pub}}(msg),PEKS(A_{pub},W_{1}),…,PEKS(A_{pub},W_{k}) \right]$

其中 $A_{pub}$ 是Alice的公钥，msg是电子邮件正文，PEKS是一种算法，其特性将在下面讨论。PEKS值不会显示有关邮件的任何信息，但可以搜索特定的关键字。对于本文的其余部分，我们使用一个邮件服务器作为我们的示例应用程序，它存储所有传入的电子邮件。
我们的目标是使Alice能够向邮件服务器发送一个短的秘密密钥 $T_{W}$ ，这将使服务器能够定位所有包含关键字 $W$ 的消息，但不了解其他任何信息。爱丽丝用她的私人钥匙制造了这个陷门 $T_{W}$ 。服务器只是将相关的电子邮件发回给Alice。我们称这样的系统为带有关键字搜索的非交互式公钥加密，或者简称为“可搜索公钥加密”。
定义1。具有关键字搜索的非交互式公钥加密（我们有时将其缩写为“可搜索加密”）方案由以下多项式时间随机化算法组成：
1. $KeyGen(s)$ ：获取一个安全参数s，并生成一个公钥/私钥对 $A_{pub}$ ， $A_{priv}$ 。
2. $PEKS(Apub,W)$ ：对于一个公钥 $A_{pub}$ 和一个字 $W$ ，生成 $W$ 的可搜索加密。
3. $Trapdoor(A_{priv},W)$ ：给定Alice的私钥和一个字 $W$ 产生一个陷阱门 $T_{W}$ 。
4. $Test(A_{pub} ,S, T_{W})$ ：给定Alice 的公钥，一个可搜索的加密 $S=PEKS(A_{pub},W')$ ，一个陷门 $T_{W}=Trapdoor(A_{priv},W)$ ，如果 $W=W'$ 则输出“yes”，否则输出“no”。
Alice运行KeyGen算法来生成她的公钥/私钥对。她使用陷门为她希望邮件服务器或邮件网关搜索的任何关键字 $W$ 生成陷门 $T_{W}$ 。邮件服务器使用给定的陷门作为Test()算法的输入，以确定给定的电子邮件是否包含Alice指定的关键字W之一。
接下来，我们在语义安全的意义上定义了PEKS 的安全性。我们需要确保 $PEKS(A_{pub},W)$ 不会泄露任何关于W的信息，除非 $T_{W}$ 可用。我们定义了针对主动攻击者的安全性，主动攻击者能够为他选择的任何W获得活板门 $T_{W}$ 。即使在这样的攻击下攻击者应该不能区分关键字 $W_{0}$ 的加密和他没有获得陷门的关键字 $W_{1}$ 的加密。在形式上，我们使用挑战者和攻击者之间的以下游戏来定义针对主动攻击者的安全性（安全参数s作为输入提供给双方）。
PEKS安全游戏：
1. 挑战者运行 $KeyGen(s)$ 算法生成 $A_{pub}$ 和 $A_{priv}$ 。它给了攻击者 $A_{pub}$ 。
2. 攻击者可以自适应地向挑战者询问他所选择的任意关键字 $W\in \{0,1\}^{∗}$ 。
3.在某些时候，攻击者A向挑战者发送两个单词 $W_{0}$ ， $W_{1}$ ，它希望在这两个单词上受到挑战。唯一的限制是攻击者之前没有要求 $T_{W_{0}}$ 或 $T_{W_{1}}$ 的陷门。挑战者随机选取一个 $b\in \{0,1\}$ ，给攻击者 $C=PEKS(A_{pub},W_{b})$ 。我们将C称为PEKS挑战。
4. 攻击者可以继续向陷阱门TW请求任意关键字W，只要 $W≠W_{0},W_{1}$ 。
5. 最终，攻击者A输出 $b'\in \{0,1\}$ ，如果 $b=b'$ ，则获胜。
换句话说，如果攻击者能正确地猜出他得到的是 $W_{0}$ 还是 $W_{1}$ 的PEKS，他就赢了。我们定义A突破PEKS的优势为
$Adv_{A}(s)=|Pr[b=b']-\frac{1}{2}|$

定义2。如果对于任何多项式时间的攻击者a，我们有 $Adv_{A}(s)$ 是一个可以忽略的函数，我们说PEKS对于自适应选择关键字攻击是语义安全的。

选择密文安全性。我们注意到，每当公钥加密系统 $E_{A_{pub}}$ 在语义上安全时，定义2确保了式（1）中给出的构造在语义上是安全的。然而，就像这样，构造不是选择密文安全的。事实上，选中的密文攻击者可以通过重新排序方程（1）中的关键字并提交得到的密文进行解密来打破语义安全性。一种标准的技术可以使用[7]的方法使这种构造选择密文安全。我们把这个问题推迟到论文的完整版。

PEKS暗示基于身份的加密

基于关键字搜索的公钥加密与基于身份的加密（Identity Based encryption, IBE）有关。构建一个安全的PEKS似乎比构建一个IBE更困难。事实上，下面的引理表明PEKS意味着基于身份的加密。相反的说法可能是错误的。在[2]中定义了IBE的安全概念，特别是选定的密文安全IBE（IND-ID-CCA）。

引理1：一种非交互式可搜索加密方案(PEKS)对自适应选择关键字攻击具有语义安全性，从而产生了一种选择密文安全的IBE系统(IND-ID-CCA)。

证明示意图：给定 $PEKS (KeyGen,PEKS,Trapdoor,Test)$ ， IBE系统如下：

1. 安装：运行PEKS KeyGen算法生成 $A_{pub}/A_{priv}$ 。IBE系统参数为 $A_{pub}$ 。万能钥匙是 $A_{priv}$ 。

2. 密钥产生：与公钥 $X\in \{0,1\}^{*}$ 相关联的IBE私钥是： $dX=[Trapdoor(A_{priv}, X||0), Trapdoor(A_{priv}, X||1)]$ 。

3. 加密：使用公钥 $X\in \{0,1\}^{*}$ 作为： $CT=PEKS(A_{pub},X||b)$ 。
4. 解密：解密 $CT=PEKS(A_{pub},X||b)$ 使用私钥 $d_{X}=(d_{0},d_{1})$ ，如果 $Test(A_{pub}, CT, d_{0})=“yes”$ 则输出‘0’，如果 $Test(A_{pub}, CT, d_{1}) =“yes”$ 则输出‘1’。

假设PEKS在语义上是安全的，可以证明产生的系统是ind-id-cca，以抵御自适应选择的消息攻击。

这表明，构建非交互式公钥可搜索加密至少与构建IBE系统一样困难。人们可能试图通过定义来证明相反的情况（即IBE隐含PEKS）：

$PEKS(A_{pub},W) = E_{W}[0^{k}]$ 。

即，使用IBE公钥 $W\in \{0,1\}^{∗}$ 加密一串k个0。Test算法尝试解密 $E_{W}[0]$ ，并检查生成的明文是否为 $0^{k}$ 。不幸的是，这并不一定会给出一个安全的可搜索加密方案。问题是密文CT可能会暴露用于创建CT的公钥（W）。通常，加密方案不需要隐藏用于创建给定密文的公钥。但这个属性对于（2）中给出的PEKS构造是必不可少的。我们注意到，Bellare等人以前研究过公钥隐私。

通常，构造一个可搜索的公钥加密似乎比构造一个IBE方案更难。尽管如此，我们的第一个PEKS构建是基于最近的IBE系统的构建。我们能够通过利用这个系统的额外特性来证明安全性。

构建

我们给出了公钥可搜索加密的两种构造：

（1）一种基于Diffie-Hellman假设（假设随机预言）的有效系统和

（2）一种基于一般陷门置换（不假设随机预言）的有限系统，但效率较低。

使用双线性映射的构造

我们的第一个构造是基于一个计算Diffie-Hellman问题的变体。博纳和富兰克林[2]最近使用椭圆曲线上的双线性映射建立了一个有效的IBE系统。理论上，他们使用了两个素数阶为p的群 $G_{1}$ ， $G_{2}$ 和他们之间的双线性映射 $e:G1\times G1 \rightarrow G2$ 。该映**足以下属性:
1. 可计算性：给定 $g,h\in G_{1}$ ，有多项式时间算法计算 $e(g,h)\in G_{2}$ 。

2. 双线性：对于任意整数 $x, y\in [1,p]$ ，我们有 $e(g^{x}, g^{y}) = e(g, g)^{xy}$

3. 非退化：如果g是 $G_{1}$ 的生成器，那么 $e(g,g)$ 是 $G_{2}$ 的生成器。

$G_{1}$ 、 $G_{2}$ 的大小由安全参数决定。我们利用这种双线性映射构造了一个非交互的可搜索加密方案。

构造基于[2]。我们需要hash函数 $H_{1}:\{0,1\}^{∗} \rightarrow G_{1}$ 和 $H_{2}:G_{2}\rightarrow \{0,1\}^{log p}$ 。我们的PEKS工作原理如下：

KeyGen：输入安全参数决定组 $G_{1}$ 和 $G_{2}$ 的大小p。该算法随机选取 $α\in Z^{*}_{p}$ 和一个 $G_{1}$ 生成器g。它输出 $A_{pub}=[g,h=g^{α}]$ 和 $A_{priv}=α$ 。

$PEKS(A_{pub},W)$ ：首先计算随机 $r\in Z^{*}_{p}$ 的 $t=e(H_{1}(W),h^{r})$ 。输出 $PEKS(A_{pub},W) = [g^{r}, H_{2}(t)]$ 。

$Trapdoor(A_{priv},W)$ ：输出 $T_{W}=H_{1}(W)^{α}\in G_{1}$ 。

$Test(A_{pub},S,T_{W})$ ：设 $S=[A,B]$ 。测试 $H_{2}(e(T_{W},A))=B$ 是否成立。如果是，输出“yes”；如果不是，输出“no”。

证明了该系统是一种非交互式可搜索的加密方案，在随机预言机模型中对选择的关键字攻击具有语义安全。安全性的证明依赖于双线性Diffie-Hellman问题（BDH）的难度。

双线性Diffie-Hellman问题（BDH）：修复 $G_{1}$ 的生成器g。BDH问题如下：给定 $g,g^{a},g^{b}, g^{c}\in G_{1}$ 为输入，计算 $e(g,g)^{abc}\in G_{2}$ 。我们说，如果所有多项式时间算法在求解BDH时都具有微不足道的优势，那么BDH是不可解决的。

我们注意到Boneh-Franklin IBE系统依赖于同样棘手的安全性假设。我们的PEKS的安全性用下面的定理证明。证明是建立在随机oracle模型上的。事实上，构建一个安全的IBE（也就是PEKS），而不使用随机预言机模型，目前是一个开放的问题。

定理1。假设BDH难以处理，上述非交互式可搜索加密方案（PEKS）在语义上是安全的，可以抵御随机预言机模型中所选择的关键字攻击。

证明：假设A是一种攻击算法，该算法在破解PEKS时优势为 $\epsilon$ 。假设A最多对 $H_{2}$ 进行 $q_{H_{2}}$ 哈希函数查询，最多对 $q_{T}$ 陷门查询（我们假设 $q_{H}$ 和 $q_{H_{2}}$ 为正）。我们构造了一个算法B，以至少 $\epsilon'=\epsilon/(eq_{T}q_{H_{2}})$ 的概率解决BDH问题，其中e是自然对数的底。算法B的运行时间与算法A大致相同。因此，如果BDH假设在 $G_{1}$ 中成立，那么 $\epsilon'$ 是一个可以忽略的函数，因此在安全参数中 $\epsilon$ 必须是一个可以忽略的函数。

设g是G1的生成函数。算法B给定 $g$ ， $u_{1}=g^{α}$ ， $u_{2}=g^{β}$ ， $u_{3}=g^{γ}\in G_{1}$ 。其目标是输出 $v=e(g, g)^{αβγ}\in G_{2}$ 。算法B模拟挑战者，与伪造者A进行如下交互：

KeyGen：算法B首先给A一个公钥 $A_{pub}=[g,u_{1}]$ 。

$H_{1},H_{2}-queries$ ：算法A在任何时候都可以查询到随机的预言机语句 $H_{1}$ 或 $H_{2}$ 。

为了响应H1查询，算法B维护了一个元组列表 $<W_{j},h_{j},a_{j},c_{j}>$ ，称为 $H_{1}-list$ 。列表最初为空。当A在 $W_{i}\in \{0,1\}^{∗}$ 处查询随机预言机 $H_{1}$ 时，算法B的响应如下:

1. 如果查询 $W_{i}$ 已经出现在元组 $<W_{i},h_{i},a_{i},c_{i}>$ 的 $H_{1}-list$ 中，那么算法B响应 $H_{1}(W_{i}) = h_{i}\in G_{1}$ 。

2. 否则，B生成一个随机硬币 $c_{i}\in \{0,1\}$ ，使 $Pr[c_{i}=0]=1/(q_{T}+1)$ 。

3. 算法B随机选取 $a_{i}\in Z_{p}$ 。如果 $c_{i}=0$ ，B计算 $h_{i}\leftarrow u_{2}\cdot g^{a_{i}}\in G_{1}$ 。如果 $c_{i}=1$ ，B计算 $h_{i}\leftarrow g^{a_{i}}\in G_{1}$ 。

4. 算法B将元组 $<W_{i},h_{i},a_{i},c_{i}>$ 添加到 $H_{1}-list$ 中，并通过设置 $H_{1}(W_{i})=h_{i}$ 来响应A。请注意， $h_{i}$ 在 $G_{1}$ 中是统一的，并且根据需要独立于A的当前视图。

类似地，在任何时候A都可以向 $H_{2}$ 发出一个查询。算法B通过为每个新的t选择一个新的随机值 $V\in \{0,1\}^{log p}$ ，并设置 $H_{2}(t)=V$ 来响应对 $H_{2}(t)$ 的查询。另外，B通过将 $(t,V)$ 对添加到 $H_{2}$ 列表来跟踪所有的 $H_{2}$ 查询。 $H_{2}$ 列表最初是空的。

陷门的查询。当A对单词 $W_{i}$ 算法对应的陷门发出查询时，B的响应如下：

1. 算法B运行上述算法响应 $H_{1}$ 查询，得到 $h_{i}\in G_{1}$ ，使 $H_{1}(W_{i})=h_{i}$ 。让 $<W_{i}, h_{i}, a_{i}, c_{i}>$ 是 $H_{1}-list$ 中对应的元组。如果 $c_{i}=0$ ，则B报告失败并终止。

2. 否则，我们知道 $c_{i}=1$ ，因此 $h_{i}=g^{a_{i}}\in G_{1}$ 。定义 $T_{i}=u^{a_{i}}_1$ 。观察到 $T_{i}=H(W_{i})^{α}$ ，因此 $T_{i}$ 是公钥 $A_{pub}=[g, u_{1}]$ 下关键字 $W_{i}$ 的正确活动门。算法B将 $T_{i}$ 赋给算法A。

挑战。最终，算法A生成一对关键字 $W_{0}$ 和 $W_{1}$ ，希望对其提出质疑。算法B生成挑战PEKS如下：

1. 算法B运行上述算法响应 $H_{1}$ 查询，得到 $h_{i}\in G_{1}$ ，使 $H_{1}(W_{i})=h_{i}$ 。让 $<W_{i},h_{i},a_{i},c_{i}>$ 是 $H_{1}-list$ 中对应的元组。如果 $c_{i}=0$ ，则B报告失败并终止。

2. 否则，我们知道 $c_{i}=1$ ，因此 $h_{i}=g^{a_{i}}\in G_{1}$ 。定义 $T_{i}=u^{a_{i}}_{1}$ 。注意到 $T_{i}=H(W_{i})^{α}$ ，因此 $T_{i}$ 是公钥 $A_{pub}=[g,u_{1}]$ 下关键字Wi的正确活动门。算法B将 $T_{i}$ 赋给算法A。

挑战。最终，算法A生成一对关键字 $W_{0}$ 和 $W_{1}$ ，希望对其提出质疑。算法B生成挑战PEKS如下：

1. 算法B运行上述算法两次响应 $h_{1}-queries$ ，得到一个 $h_{0},h_{1}\in G_{1}$ ，使 $H_{1}(W_{0}) = h_{0}$ ， $H_{1}(W_{1})=h_{1}$ 。对于 $i=0,1$ ，让 $<W_{i},h_{i},a_{i},c_{i}>$ 是 $H_{1}-list$ 上对应的元组。如果 $c_{0}=1$ ， $c_{1}=1$ ，则B报告失败并终止。

2. 我们知道 $c_{0}$ 和 $c_{1}$ 中至少有一个等于0。算法B随机选取一个 $B\in \{0,1\}$ ，使 $c_{b}=0$ （如果只有一个 $c_{b}$ 等于0，则不需要随机性，因为只有一个选项）。

3. 算法B对一个随机 $J\in \{0,1\}^{log p}$ 响应挑战PEKS $C=[u_{3},J]$ 。

注意，这个挑战隐式定义了 $H_{2}(e(H_{1}(W_{b})， u^{γ}_{1}))=J$ 。换句话说， $J = H_{2}(e(H_{1}(W_{b}), u^{γ}_{1})) = H_{2}(e(u_{2}g^{a_{b}}, g^{α_{γ}})) = H_{2}(e(g,g)^{αγ(β+a_{b})})$

根据这个定义，C是 $W_{b}$ 需要的有效PEKS。

更多的陷门的查询。A可以继续对关键字 $W_{i}$ 发出陷门查询，其中唯一的限制是 $W_{i}=W_{0},W_{1}$ 。算法B像以前一样响应这些查询。

输出。最终，A输出其猜测 $b'\in \{0,1\}$ ，表示挑战C是 $PEKS(A_{pub},W_{0})$ 还是 $PEKS(A_{pub},W_{1})$ 的结果。此时，算法B从 $H_{2}-list$ 中选择一个随机对 $(t, V)$ ，并输出 $t/e(u_{1}, u_{3})^{a_{b}}$ 作为对 $e(g, g)^{αβ_{γ}}$ 的猜测，其中 $a_{b}$ 是挑战步骤中使用的值。这样做的原因是，正如我们将展示的，A必须发出了对 $H_{2}(e(H_{1}(W_{0}),u^{γ}_{1}))$ 或 $H_{2}(e(H_{1}(W_{1}),u^{γ}_{1}))$ 的查询。因此 $H_{2}-list$ 以1/2的概率包含一对，其左手边是 $t=e(H_{1}(W_{b}),u^{γ}_{1})=e(g, g)^{αγ(β+a_{b})}$ 。如果B从 $H2-list$ 中选择这对 $(t,V)$ ，那么 $t/e(u_{1},u_{3})^{a_{b}}=e(g,g)^{αβγ}$ 。

这就完成了算法B的描述，还需要证明B正确输出 $e(g, g)^{αβγ}$ 的概率至少为 $\epsilon'$ 。为此，我们首先分析B在模拟过程中不中止的概率。我们定义了两个事件：

$\varepsilon_{1}$ ：B不会因为A的任何陷门查询而中止。

$\varepsilon_{2}$ ：B在挑战阶段不会中止。

首先，我们认为在[6]中事件 $\varepsilon_{1}$ 和 $\varepsilon_{2}$ 都有足够大的概率发生。

断言1：算法B不因a的陷门查询而中止的概率至少为 $1/e$ 。因此， $Pr[\varepsilon_{1}]≥1/e$ 。

证明：在不失一般性的前提下，我们假设A不会两次请求相同关键字的活板门。一个陷门查询导致B中止的概率是 $1/(q_{T}+1)$ 。为了看到这一点，让 $W_{i}$ 是a的第i个陷门查询，并让 $<W_{i},h_{i},a_{i},c_{i}>$ 是 $H_{1}-list$ 上对应的元组。在执行查询之前，位ci是独立于A的视图的——可以给A的唯一依赖 $c_{i}$ 的值是 $H(W_{i})$ ，但是无论 $c_{i}=0$ 还是 $c_{i}=1$ ， $H(W_{i})$ 上的分布是相同的。因此，该查询导致B中止的概率最多为 $1/(q_{T}+1)$ 。由于A最多进行 $q_{T}$ 陷门查询，那么B在所有活动门查询中不中止的概率至少为 $(1−1/(q_{T}+1))q_{T}≥1/e$ 。

断言2：算法B在挑战阶段不中止的概率至少为 $1/q_{T}$ 。因此， $Pr[\varepsilon_{2}]≥1/q_{T}$ 。

证明。如果A能够产生 $W_{0}$ ， $W_{1}$ ，算法B将在挑战阶段中止， $c_{0}=c_{1}=1$ ，其中对于 $i = 0,1$ ，元组 $<W_{i}, h_{i}, a_{i}, c_{i}>$ 是与 $W_{i}$ 对应的 $H_{1}-list$ 元组。由于A没有为 $W_{0}$ 查询陷门，我们有 $c_{0}$ ， $c_{1}$ 都是独立于A的当前视图。因此，由于 $Pr[c_{i}=0]=1/(q_{T}+1)$ 对于 $i = 0,1$ ，和两个值是相互独立的，我们得到 $Pr[c_{0}=c_{1}=1]=(1−1/(q_{T}+1))^{2}≤1−1/q_{T}$ 。因此，B不中止的概率至少为 $1/q_{T}$ 。

注意，由于A永远不能对挑战关键字 $W_{0}$ 发出陷门查询，所以 $W_{0}$ 两个事件E1和E2是独立的。因此，

注意，由于A永远不能对挑战关键字 $W_{0}$ ， $W_{1}$ 发出陷门查询，两个事件 $\varepsilon_{1}$ 和 $\varepsilon_{2}$ 是独立的。因此， $Pr[\varepsilon_{1}∧\varepsilon_{2}]≥1/(eq_{T})$ 。

要完成定理1的证明，还需要证明B输出给定BDH实例的解的概率至少为 $\epsilon/q_{H_{2}}$ 。为了做到这一点，我们展示了在模拟过程中，A发出对 $H_{2}(e(H_{1}(W_{b}),u^{γ}_{1}))$ 的查询，其概率至少为 $\epsilon$ 。

断言3：假设在一个真实的攻击博弈中，给出了A的公钥 $[g,u_{1}]$ ， A要求对 $W_{0}$ 和 $W_{1}$ 进行挑战。对此，给A一个挑战 $C=[g^{r},J]$ 。然后，在真正的攻击游戏中，A对 $H_{2}(e(H_{1}(W_{0}),u^{r}_{1}))$ 或 $H_{2}(e(H_{1}(W_{1}), u^{r}_{1}))$ 发出 $H_{2}$ 查询，概率至少为 $2\epsilon$ 。

证明。设 $\varepsilon_{3}$ 为在实际攻击中A没有对 $H_{2}(e(H_{1}(W_{0}),u^{r}_{1}))$ 和 $H_{2}(e(H_{1}(W_{1}),u^{r}_{1}))$ 中的任何一个发出查询的事件。那么，当 $\varepsilon_{3}$ 发生时，我们知道表示C是 $W_{0}$ 还是 $W_{1}$ 的PEKS的位 $b\in \{0,1\}$ 与A的视图无关。因此，A的输出 $b'$ 将满足 $b = b'$ ，概率最多为 $\frac{1}{2}$ 。由A的定义可知，在真实攻击中 $|Pr[b=b']−1/2|≥\epsilon$ 。这两个事实表明， $Pr[\neg\varepsilon_{3}]≥2\epsilon$ 。为此，我们首先推导出 $Pr[b=b']$ 的简单上下界： $Pr[b=b']$

$=Pr[b=b'|\varepsilon_{3}]Pr[\varepsilon_{3}]+Pr[b=b'|\neg\varepsilon_{3}]Pr[\neg\varepsilon_{3}]$

$\leq Pr[b=b'|\varepsilon_{3}]Pr[\varepsilon_{3}]+Pr[\neg \varepsilon_{3}]$

$=\frac{1}{2}Pr[\varepsilon_{3}]+Pr[\neg \varepsilon_{3}]$

$=\frac{1}{2}+\frac{1}{2}Pr[\neg\varepsilon_{3}]$

$Pr[b=b']\geq Pr[b=b'|\varepsilon_{3}]Pr[\varepsilon_{3}]=\frac{1}{2}Pr[\varepsilon_{3}]=\frac{1}{2}-\frac{1}{2}Pr[\neg\varepsilon_{3}]$

即 $\epsilon \leq |Pr[b=b']−1/2|≤\frac{1}{2}Pr[\neg\varepsilon_{3}]$ 。因此，在实际攻击中，按要求 $Pr[\neg\varepsilon_{3}]\geq 2\epsilon$ 。

现在，假设B不中止，我们知道B完美地模拟了一个真实的攻击游戏，直到a发出 $H_{2}(e(H_{1}(W_{0}),u^{γ}_{1}))$ 或 $H_{2}(e(H_{1}(W_{1}),u^{γ}_{1}))$ 的查询。因此，根据权利要求3，在模拟结束时，A将发出对 $H_{2}(e(H_{1}(W_{0}),u^{γ}_{1}))$ 或 $H_{2}(e(H_{1}(W_{1}),u^{γ}_{1}))$ 的查询，概率至少为 $2\epsilon$ 。由此可见，A对 $H_{2}(e(H_{1}(W_{b}),u^{γ}_{1}))$ 发出了查询概率至少 $2\epsilon$ 。因此，值 $e(H_{1}(W_{b}),u^{γ}_{1})=e(g^{β+a_{b}}, g)^{αγ}$ 将出现在 $H_{2}-list$ 中某些对的左边。算法B将以至少 $1/q_{H_{2}}$ 的概率选择正确的对，因此，假设B在模拟过程中没有中止，它将以至少 $\epsilon/q_{H_{2}}$ 的概率产生正确的答案。由于B不以至少 $1/(eq_{T})$ 的概率终止，我们看到B的成功概率至少为所需的 $\epsilon/(eq_{T}q_{H_{2}})$ 。

使用任何陷门排列的有限构造

我们的第二个PEKS构造基于一般的陷门排列，假设用户希望搜索的关键字的总数受安全参数中的某个多项式函数的限制。（作为我们构建的第一步，我们将做一个更强的假设，即字典中单词的总数 $Σ\subset\{0,1\}^{∗}$ 也受多项式函数的限制，我们稍后将展示如何消除这个额外的假设。）我们还需要一系列语义安全的加密，对于给定的密文，很难计算出该密文与哪个公钥相关联。这个概念由Bellare等人[1]形式化。我们说具有此属性的公钥系统是源无法区分的。更准确地说，加密方案(G,E,D)的源不可区分性是使用挑战者和攻击者A之间的以下博弈来定义的（这里G是密钥生成算法，E/D是加密/解密算法）。安全参数s给定给两个参与者。

来源不可区分安全游戏：

1. 挑战者运行算法G(s)两次，生成两个公私钥对 $(**_{0}, Priv_{0})$ 和 $(**_{1}, Priv_{1})$ 。

2. 挑战者选择一个随机的 $M\in \{0,1\}^{s}$ 和一个随机的 $b\in \{0,1\}$ ，计算一个加密 $C=**_{b}(M)$ 。挑战者给攻击者(M,C)。

3. 攻击者输出 $b'$ ，如果 $b=b'$ 则获胜。

换句话说，如果攻击者正确地猜出他得到的是 $**_{0}$ 下的M加密还是 $**_{1}$ 下的M加密，他就赢了。我们将A的获胜优势定义为：

$AdvSI_{A}(s)=|Pr[b=b']−\frac{1}{2}|$

定义3。如果对于任何多项式时间攻击者A，我们有 $AdvSI_{A}(s)$ 是一个可以忽略的函数，我们就说一个公钥加密方案是源不可区分的。

我们注意到Bellare等人[1]通过允许对手选择挑战消息m，定义了一个比上面更强的源不可区分的概念。对于我们的目的，给对手一个随机消息的加密就足够了。

很容易检查从任何陷门排列族中都可以获得源不可分辨性，其中对于给定的安全参数，该排列族中的所有排列都在同一域上定义。这样一个家族可以由[1]中描述的任何活板门排列家族构成。然后对比特b进行加密，我们随机选取一个x，输出 $[f(x),GL(x) \oplus b]$ ，其**L为Goldreich-Levin硬核比特[19]。因此，我们得到以下引理：

引理2：对于任意的陷门排列族，我们可以构造一个语义安全的源无区别加密方案。

我们注意到源不可区分性与语义安全性是正交的。我们可以构建一个源不可区分的语义安全系统（通过在每个密文中嵌入公钥）。相反，可以构建一个在语义上不安全的源不可区分的系统（通过在每个密文中嵌入明文）。

一个简单的陷门排列的PEKS。当关键字族Σ具有多项式大小（在安全参数中）时，很容易从任何源不可区分的公钥系统(G,E,D)构造可搜索的加密。设s为该方案的安全参数。

KeyGen：对于每个 $W\in Σ$ 运行G(s)来生成一个新的源无区别加密方案的公钥/私钥对 $**_{W}/Priv_{W}$ 。PEKS公钥为 $A_{pub}=\{**_{W}|W\in Σ\}$ 。私钥为 $A_{priv}=\{Priv_{W}| W\in Σ\}$ 。

$PEKS(A_{pub},W)$ ：随机选取 $M\in \{0,1\}^{s}$ ，输出 $PEKS(A_{pub},W)=(M, E[**_{W},M])$ ，即使用公钥 $**_{W}$ 对M进行加密。

$Trapdoor(A_{priv},W)$ ：单词W的陷门就是 $T_{W} = Priv_{W}$ 。

$Test(A_{pub},S,T_{W})$ ：测试解密 $D[T_{W},S]=0^{s}$ 。如果是输出'yes'，否则输出'no'。

注意，字典的大小必须是多项式大小，这样公钥和私钥的大小才能是多项式大小。

这种构造给出了一个语义安全的PEKS，如下面的简单定理所述。语义安全的PEKS的定义与定义2相同，只是不允许对手进行所选的关键字查询。

定理2。假设底层公钥加密方案(G,E,D)是源不可区分的，上述PEKS方案在语义上是安全的。

证明草图：设 $Σ=\{W_{1},…,W_{k}\}$ 为关键字字典。假设我们有一个PEKS攻击者A，其中 $Adv_{A}(s)>\epsilon(s)$ 。我们构建了一个攻击者B，它破坏(G,E,D)的源不可区分性，其中 $AdvSI_{B}(s)>\epsilon(s)/k^{2}$ 。

这个缩减是立即的：给B两个公钥 $**_{0}$ ， $**_{1}$ 和一对 $(M,C)$ ，其中M在 $\{0,1\}^{s}$ 中是随机的， $b\in \{0,1\}$ 的 $C=**_{b}(M)$ 。算法B使用G(s)生成k-2个额外的公钥/私钥。它将 $A_{pub}$ 创建为所有k个公钥的列表，其中 $**_{0}$ 和 $**_{1}$ 嵌入在列表中的一个随机位置。设 $W_{i}$ ， $W_{j}$ 为与公钥 $**_{0}$ ， $**_{1}$ 相关的单词。B将 $A_{pub}$ 发送给A，A回复两个词 $W_{k},W_{l}\in Σ$ ， A希望在这两个词上受到质疑。如果 $\{i, j\}\ne\{k,l\}$ 算法B报告失败，终止。否则，B向A发送挑战(M,C)，然后A用 $a b'\in \{0,1\}$ 回应。算法B输出 $b'$ 作为对源不可分辨性挑战的响应。我们得到 $b=b'$ ，如果算法B没有中止并且A的响应是正确的。这发生的概率至少是 $\frac{1}{2}+\epsilon/k^{2}$ 。因此，需要满足 $AdvSI_{B}(s)>\epsilon(s)/k^{2}$ 。

我们注意到，这个PEKS可以被视为派生自具有有限数量身份的IBE系统。对于每个身份，都有一个预先指定的公钥。Dodis等人[13]的研究中暗示了这种IBE系统。他们建议使用无覆盖集系统来减少公钥的大小。下面我们应用相同的思想来减少上面PEKS中公钥的大小。

减少公钥大小。上述方案的缺点是公钥长度随字典总大小线性增长。如果我们有一个用户将释放到电子邮件网关的关键字t陷门总数的上限（尽管我们不需要先验地知道这些关键字），我们可以使用无覆盖族[15]做得更好，并且可以允许关键字字典呈指数级大小。因为通常情况下，用户只允许第三方（如电子邮件服务器）搜索有限数量的关键字，因此假定发布的陷门数量的上限是合理的。我们首先回顾一下无保险家庭的定义。

定义4。非覆盖的族。设d, t, k为正整数，设G为大小为d的ground集合，设 $F=\{S_{1},...,S_{k}\}$ 是G的子集的一个族，我们说子集 $S_{j}$ 不包括 $S_{i}$ ，如果它成立 $S_{i} ⊄ S_{j}$ 。如果F中的每个子集都不被F中的t个子集的并集覆盖，我们就说G上的F族是t覆盖自由的。此外，如果子集族中的所有子集的大小都是q一致的，我们就说一个子集族是q一致的。

我们将从[14]使用以下事实。

引理3。存在一个确定性算法，对于任意固定的t, k，在大小为d的地面集上构造一个q均匀t覆盖自由族F，对于 $q=⌈d/4t⌉$ 且 $d≤16t^{2}(1+log(k/2)/log3)$ 。

PEKS。以前面的PEKS构造为起点，我们可以通过允许用户为不同的关键字重用单个公钥来显著减小公共文件 $A_{pub}$ 的大小。我们将从免覆盖系列中选择的公钥子集关联到每个关键字。设k为字典的大小 $Σ=\{W_{1},...,W_{k}\}$ ，设t为用户Alice发布到邮件网关的关键字陷门数量的上限。设d，q满足引理3的界。PEKS(d, t, k, q)构造如下：

KeyGen：当 $i=1,...,d$ 时运行算法G(s)为源不可区分加密方案生成新的公钥/私钥对 $**_{i}/Priv_{i}$ 。PEKS公钥为 $A_{pub}=\{**_{1},...,**_{d}\}$ 。私钥为： $A_{priv}=\{Priv_{1},...,Priv_{d}\}$ 。我们将使用一个q一致的t覆盖自由的 $\{**_{1},...,**_{d}\}$ 子集族 $F=\{S_{1},...,S_{k}\}$ 。因此，每个 $S_{i}$ 都是公钥的一个子集。

$PEKS(A_{pub},W_{i})$ ：设 $S_{i}\in F$ 为单词 $W_{i}\in Σ$ 的子集。令 $S_{i}=\{**^{(1)},...,**^{(q)}\}$ 。取随机信息 $M_{1},...,M_{q}\in \{0,1\}^{s}$ ，令M = M1⊕···⊕Mq。输出元组：

$PEKS(A_{pub},W_{i})=(M, E[**^(1),M_{1}],...,E[**^{(q)},M_{q}])$

$Trapdoor(A_{priv},W_{i})$ ：设 $S_{i}\in F$ 是单词 $W_{i}\in Σ$ 的子集。单词 $W_{i}$ 的活动门只是一组私有密钥，对应于 $S_{i}$ 集合中的公共密钥。

$Test(A_{pub},R,T_{W})$ ：令 $T_{W}=\{Priv^{(1)},...,Priv^{(q)}\}$ ，令 $R=(M,C_{1},…,C_{q})$ 做一个PEKS。当 $i=1,...,q$ 使用私钥 $Priv^{(i)}$ 对每个 $C_{i}$ 进行解密，得到 $M_{i}$ 。如果 $M=M_{1}\oplus ...\oplus M_{q}$ ，则输出'yes'，否则输出'no'。

公钥文件 $A_{pub}$ 的大小现在小了很多：是字典大小的对数。缺点是Alice只能向电子邮件网关释放t个关键字。一旦陷门被打开，隐私就不再有保障了。另外，请注意PEKS的大小现在更大了（字典大小为对数，t为线性）。定理2的以下推论表明，得到的PEKS是安全的。

推论1：让d，t，k，q满足引理3的界。假设基础公钥加密方案(G,E,D)的源不可区分且在语义上是安全的，并且对手不进行超过t次的陷门查询，上述 $PEKS(d,t,k,q)$ 方案在选择的关键字攻击下是语义安全的。

证明草图：设 $Σ=\{W_{1},...,W_{k}\}$ 为关键字字典。假设我们有一个PEKS攻击者a，其中 $Adv_{A}(s)>\epsilon(s)$ 。我们构建一个攻击者B，破坏(G,E,D)的源不可区分性。

算法B给定两个公钥 $**_{0}$ ， $**_{1}$ 和一对 $(M,C)$ ，其中M在 $\{0,1\}^{s}$ 内是随机的，对于 $b\in \{0,1\}$ ， $C=**_{b}(M)$ 。它的目标是通过与a交互输出对b的猜测。算法B使用G(s)生成d−2个额外的公钥/私钥。它将 $A_{pub}$ 创建为所有d公钥的列表，其中 $**_{0}$ 和 $**_{1}$ 嵌入在列表中的一个随机位置。设 $W_{i}$ ， $W_{j}$ 为与公钥 $**_{0}$ ， $**_{1}$ 相关的单词。

算法B给定两个公钥 $**_{0}$ ， $**_{1}$ 和一对 $(M,C)$ ，其中M在 $\{0,1\}^{s}$ 内是随机的，对于 $B\in \{0,1\}$ ， $C=**_{b}(M)$ 。它的目标是通过与a交互输出对b的猜测。算法b使用 $G(s)$ 生成d-2个额外的公钥/私钥。它将 $A_{pub}$ 创建为所有d公钥的列表，其中 $**_{0}$ 和 $**_{1}$ 嵌入在列表中的一个随机位置。设 $W_{i}$ ， $W_{j}$ 为与公钥 $**_{0}$ ， $**_{1}$ 相关的单词。

B向A发送 $A_{pub}$ ，算法A发出多达t个陷门查询。B对 $W\in Σ$ 的活板门查询的响应如下：设 $S\in F$ 是单词W对应的子集，如果 $**_{0}\in S$ 或 $**_{1}\in S$ 算法B报告失败并中止。否则，B给A一个私钥集合 $\{Priv_{i}|i\in S\}$ 。

在某一时刻，算法A输出两个单词 $W'_{0},W'_{1}\in Σ$ ，它希望在这两个单词上被挑战。设 $S'_{0}, S'_{1}\in F$ 分别为 $W'_{0},W'_{1}$ 对应的子集。设E为 $**_{0}\in S'_{0}$ 和 $**_{1}\in S'_{1}$ 的事件。如果事件 $\varepsilon$ 没有发生，则B报告失败并终止。

我们现在知道 $**_{0}\in S'_{0}$ 和 $**_{1}\in S'_{1}$ 。对于 $j=0,1$ 令 $S'_{j}=\{**^{(1)}_{j},…,**^{(q)}_{j}\}$ 。我们对一些随机的 $1≤c≤q$ 进行排列，使 $**_{0}=**^{(c)}_{0}$ 和 $**_{1}=**^{(c)}_{1}$ 。接下来，B选取随机的 $M_{1},...,M_{c−1},M_{c+1},…,M_{q}\in \{0,1\}^{s}$ ，集合 $M_{c}=M$ 令 $M'=M1\oplus ··· \oplus M_{q}$ 。算法B定义了以下混合元组：

$R=(M',E[**_{0}^{(1)},M_{1}],...,E[**_{0}^{(c-1)},M_{c-1}],C,E[**_{1}^{(c+1)},M_{c+1}],...,E[**_{1}^{(q)},M_{q}])$

它将R作为PEKS对算法A的挑战。算法A最终以某个 $b'\in \{0,1\}$ 作出响应，表示R是 $PEKS(A_{pub},W'_{0})$ 还是 $PEKS(A_{pub},W'_{1})$ 。算法B输出 $b'$ 作为其对B的猜测。可以使用一个标准的混合参数表明，如果B不中止，那么 $|Pr[b=b']−\frac{1}{2}|>\epsilon/q^{2}$ 。B不因活动门查询的结果而终止的概率至少为 $1−(tq/d)$ 。B不因选择单词 $W'_{0}$ ， $W'_{1}$ 而中止的概率至少是 $(q/d)^{2}$ 。因此，B不中止的概率至少为 $1/poly(t,q,d)$ ，重复运行B直到不中止，表明在A的运行时间中，我们可以在打破 $(G,E,D)$ 在期望多项式时间内的源不可区分性方面获得 $\epsilon/q^{2}$ 的优势。

使用雅可比符号构造

考虑到基于身份的加密和PEKS之间的关系，由于Cocks[3]，从IBE系统构建PEKS是很**的。Cocks的IBE系统的安全性是基于对 $N=pq$ 模的二次残基与非残基的区分困难，其中 $p=q=3(mod4)$ 。

不幸的是，Galbraith[11]表明[3]中所描述的Cocks系统不是Bellare等人[1]意义上的公钥私有。因此，Cocks系统似乎不能直接用于构建PEKS。它提供了一个很好的例子，构造PEKS是一个比构造IBE更难的问题。

结论

我们定义了关键字搜索公钥加密（PEKS）的概念，给出了两种构造。构建PEKS与基于身份的加密（IBE）有关，尽管PEKS似乎更难构建。我们展示了PEKS意味着基于身份的加密，但反过来是目前一个开放的问题。我们对PEKS的建设是基于最近的IBE建设。我们能够通过利用这些方案的额外特性来证明安全性。

致谢

我们感谢Glenn Durfee建议在3.1节的构造中使用 $H_{2}$ 。我们感谢叶夫根尼·多迪斯（Yevgeniy Dodis）、大卫·莫尔纳（David Molnar）和史蒂文·加尔布雷思（Steven Galbraith）对这项工作的有益评论。