摘要

等值测试公钥加密（Public Key Encryption with Equal Test, PKEET）是一种允许测试人员使用一个或多个用户Ui发出的活动门对使用Ui的公钥加密的密文进行等值测试的密码系统。由于该特性具有很多实际应用，包括对加密数据的搜索，目前已经提出了几种PKEET方案。然而，据我们所知，所有现有的提议只有在数论问题和随机预言启发式的困难下才被证明是安全的。
在本文中，我们证明了该原语不仅可以从已建立良好的其他原语中获得，而且甚至不需要依赖随机预言启发式。更准确地说，我们对PKEET的一般构造采用了一个基于身份的两级分层加密方案，该方案对选定的明文攻击具有选择性的安全性，一个强不可伪造的一次性签名方案和一个加密哈希函数。与之前的所有工作相比，我们对PKEET的通用方法有几个优点；它直接引导了第一个标准模型构建，也直接暗示了第一个基于晶格的构建。最后，我们将展示如何将我们的方法扩展到基于身份的设置。
关键词：公钥加密与等值测试，基于身份加密与等值测试，标准模型

引言

等值测试公钥加密(PKEET)是由Yang等人[23]首先提出的，它是一种公钥加密(PKE)方案，允许使用不同的公钥以及相同的公钥对加密的数据进行等值测试。在PKEET方案中，每个用户发送一个陷门给测试者进行等值测试，测试者就可以检查发送该陷门的用户的密文是否相等。此属性可用于各种实际应用，例如对加密数据进行关键字搜索、对加密数据进行高效的加密数据管理的加密数据分区、个人健康记录系统等。
作为一个与PKEET非常相似的原语，我们可能还记得Boneh等人[6]提出的使用关键字搜索的公钥加密(PKEKS)。在PKEKS方案中，每个用户使用他/她的私钥向测试者发出一个关键字的令牌，从此测试者能够在用户的密文中的消息和发出的令牌中的关键字之间执行一个等值测试。因此，它可以用来检查同一个用户的密文是否相等。但是，PKEET在PKEKS之外最重要的特性是支持不同用户之间对密文的等值测试。
让我们考虑更具体的PKEET应用场景，来阐述PKEET相对于PKEKS的优势。在电子邮件服务中，假设每个用户将他/她的电子邮件加密存储到服务器。为了对加密邮件进行有效的关键字搜索，在存储的邮件中添加加密的关键字。服务器需要监控存储的邮件，以维护系统的安全性。为此，服务器可能需要测试加密关键字之间的平等性。如果系统利用PKEKS实现此功能，服务器可以通过使用由密文所有者颁发的关键字令牌对加密的关键字执行等值测试。但是，服务器需要为每个用户和每个关键字使用不同的令牌，因此当它有一个要监视的新关键字时，它应该与每个用户交互。相反，如果系统利用PKEET，服务器可以自己生成关键字的密文，并进行等值测试。
为了支持上述场景所需的加密数据的等值测试，可以考虑使用其他类型的加密方案，例如确定性加密和全同态加密等。然而，他们也面临着PKEKS所面临的障碍。我们将在1.2节中更多地讨论PKEET与其他原语（包括PKEKS）的关系。另一方面，除了上述场景之外，PKEET还可以用作设计高级密码构造的构建块，例如，具有可控链接性[19]的群签名。
由于其广泛的适用性，自Yang等人提出第一个PKEET实现以来，各种后续结构[20,22,17,16,11,15,14,12]被提出以提高性能或支持高级功能。我们注意到，然而，所有现有的建议被证明是安全的，只有在特定的数字理论问题和随机oracle启发式的困难下。有很多文献讨论了随机预言模型的局限性（例如，[8,10,13]），因此，在不依赖随机预言启发式的理论和实践角度下，实现每个原语（在我们的例子中为PKEET）是非常可取的。

我们的贡献

在本文中，我们的主要贡献是提出了一个PKEET方案。与所有以前的PKEET结构相比，所提议的结构有几个优点。首先，我们的构造不依赖于随机预言启发式。第二，我们的结构不依赖于底层的数学结构，因为我们不需要任何数字理论的假设来保证拟议结构的安全性。更准确地说，我们采用了一个2级分层基于身份的加密（HIBE）方案，该方案对选择明文攻击、强不可伪造的一次性签名方案和密码哈希函数具有选择性的安全性。最后，我们的结构可以很容易地扩展到基于身份的设置，因为它已经使用HIBE作为构建模块。因此，我们也得到了标准模型中第一个具有相等检验(IBEET)的基于身份的加密。
作为我们的通用构造的直接应用，我们可以获得在各种类型的假设下被证明是安全的PKEET构造，例如基于配对的、基于晶格的和基于rsa的。特别是，例如，我们可以通过利用强不可伪造的基于格的签名方案(如[18])和2级基于格的HIBE方案(如[2,3])从格中获得一个PKEET结构，该方案满足选择性身份选择明文攻击(IND-sID-CPA)下的不可区分性。据我们所知，它是第一个基本假设完全基于格的PKEET方案。
Lee等人最近的一项研究[12]与我们的目标相似。我们清楚地注意到Lee等人的方法在本质上使用了计算Diffe-Hellman (CDH)假设的意义上不是完全通用的。此外，Lee等人仅在随机oracle模型中证明了他们的方案的安全性。
我们的一般结构概述。让我们解释一下通用PKEET构造的高层次直观感受。我们从一个微不足道的不安全构造开始，然后修改它。假设每个用户都有一个2级HIBE方案。为了生成消息M的密文，我们设计了一个加密算法，该算法执行以下步骤。它首先从集合中选择一个随机字符串str作为第二级标识，并生成两个密文和。
其中mpk是HIBE的主公钥，H是哈希函数，表示i=1,2时第i级身份为IDi的身份。这个过程输出(str,C0,C1)作为消息m的密文。解密算法很简单；它首先生成与str相关的密钥，使用生成的密钥对C0和C1进行解密，如果H(Dec(C0))=Dec(C1)则输出Dec(C0)。
一旦陷门算法向测试者发出身份1的密钥，测试者就可以自己生成身份[1.str]的密钥。利用这一点，他可以通过解密密文的C1部分，然后比较H(M)值来进行等值测试。另一方面，使用HIBE主秘钥作为密钥的用户，可以生成身份[0.str]的密钥，并使用该秘钥解密C0，获得正确的消息。然而，上述构造并不满足抗自适应选择密文攻击(CCA2)的安全性。虽然C0和C1之间使用str链接，并且在解密算法执行过程中有一个进程检查C0和C1之间的链接，但这不足以防止选定的密文攻击。事实上，对手可以通过请求查询安全博弈中解密预言的修改密文来获得C0中的消息。为了防止这种选定的密文攻击，在随机预言模型中几乎所有以前的PKEET结构（包括半通用的[12]）都嵌入了一个CDH问题的实例。
为了以通用的方式实现CCA2的安全性，我们借鉴了Canetti、Halevi和Katz (CHK)转换的思想，在标准模型中使用强不可伪造的一次性签名方案，从一个IND-sID-CPA安全基于身份加密（IBE）方案中获得了一个可抵抗CCA2的PKE方案。我们首先为每个用户分配一个签名方案。通过调整他们的技术，我们修改了我们的加密算法，首先生成一对签名密钥和一个密钥(sks,vks)，并使用验证密钥vks作为第二级身份，而不是使用随机字符串str。生成两个密文后，和，它使用一个签名密钥sks在密文C0和C1上生成签名σ。此后，它输出作为密文。
非正式地，我们可以认为对手必须成功地对挑战密文中的验证密钥伪造一个签名，以便从对通过修改挑战密文获得的密文的解密预言查询中获得正确的响应。我们证明，如果利用的HIBE方案是IND-sID-CPA安全的，并且利用的签名方案在标准模型中是强不可伪造的，我们的构造在自适应选择密文攻击(OW-CCA2)下对具有活动门进行等值测试的i型对手是单向的，而在自适应选择密文攻击(IND-CCA2)下对不具有活动门的ii型对手是不可区分的。因此，我们获得了标准模型中的第一个PKEET构造。
最后，我们讨论了将我们的构建扩展到基于身份的设置，用3级HIBE方案取代2级HIBE方案。在我们的修改中，所采用的3级HIBE方案的第一级被保留为一个身份，而它的第二级和第三级分别扮演着与我们的PKEET结构的第一级和第二级相同的角色。得到的结果也是标准模型中第一个IBEET构建。

相关的工作

含等值测试的PKE/IBE。Yang等[23]首先引入了PKEET的概念，它允许任何人在不同的公钥以及相同的公钥下检查两个密文是否包含相同的消息。在他们的工作之后，Tang[22]提出了一种变体，称为全或无PKEET，它只允许两个用户授权的测试人员对这些用户的所有密文进行等值测试。随后，人们提出了各种PKEET结构[20,21,17,16,11,14,12]来提高性能或支持高级功能。
在基于身份的设置中，Ma[15]提出了一个IBEET的系统模型，它是Tang的全或无PKEET模型的基于身份的版本，并给出了IBEET的实例。后来，Lee等人[12]表明他们的PKEET半通用结构可以扩展到基于身份的设置，导出的结果比Ma的方案具有更好的安全性。
另一方面，现有的所有PKEET/IBEET方案都是在随机预言模型中构建的。此外，所有之前的提议都依赖于具体的数论假设。
带关键字搜索的PKE/IBE。带关键字搜索的PKE (PKEKS)是一种PKE方案，它支持对嵌入在标签中的关键字和密文[6]中的消息执行等值测试。它与PKEET非常相似，都能够在加密数据上检查是否相等。然而，这两种方案的主要区别在于，PKEKS只允许对与发布标记相关的一个混合公钥下的密文进行测试，而PKEET则允许对不同公钥下的密文以及相同公钥下的密文进行等值测试。
Abdalla等人[1]考虑将PKEKS扩展到基于身份的设置，这与IBEET具有类似的特性。与PKEKS和PKEET之间的关系类似，IBE的关键字搜索(IBEKS)也允许对与发布标签相关的固定身份下的密文进行等值测试，而IBEET允许对不同身份下的密文以及相同身份下的密文进行等值测试。
确定性加密。确定性加密的概念是由Bellare等人首创的。对于测试人员来说，虽然PKEET是一种概率加密，但在支持对密文进行相等测试的意义上，PKEET具有与确定性加密非常相似的特性。因此，PKEET可以应用于确定性加密的许多应用中。另一方面，在其他没有陷门的人看来，PKEET的工作原理与传统的PKE方案一样，因此预计PKEET比确定性加密具有更好的安全性。此外，与PKEKS一样，确定性加密只支持同一用户的密文之间的等值测试。
从(H)IBE到其他原语的转换。在我们的构建中，我们借鉴了CHK转换策略，利用强不可伪造的一次性签名，从一个IND-sID-CPA安全的IBE方案中获得了一个CCA2安全的PKE方案。我们注意到使用IBE方案获得PKEKS方案有一个通用的转换。在[1]中，Abdalla等人提供了一个匿名IBE方案到安全PKEKS方案的转换。此外，就像我们一样，他们也通过将基础的IBE方案替换为HIBE方案，将转换扩展到基于身份的设置。然而，它的设计原则与我们的完全不同：例如，当我们的构造使用底层签名方案的验证密钥作为身份并使用它加密消息时，它们的转换生成一个随机消息并使用PKEKS中的关键字作为身份加密。

论文的组织

第2节介绍了在我们的构造中使用的几个组件的基本定义。在第3节中，我们介绍了PKEET的语法和安全模型。第4节提供了我们的PKEET方案，第5节分析了它的安全性。我们在第6节讨论我们的结构的扩展，并在第7节进行总结。关于IBEET的正式定义和我们的IBEET构造的细节在附录中给出。