摘要

含等值测试的基于ID的加密（IBEET）允许测试人员比较不同公钥加密的密文，以检查它们是否包含相同的消息。本文首先将组机制引入到IBEET中，提出了一种新的原语，即具有相等检验的基于组ID的加密（G-IBEET）。采用组机制：（1）组管理员可以授权测试员对组内用户的密文进行比较，但不能将组内用户的密文与组外用户的密文进行比较。这种组粒度授权可以使IBEET适应组场景；（2）对于组粒度授权，只需发放给测试人员一个活板门，命名为组活板门，可以大大降低传统IBEET方案中活板门的计算、传输和存储成本；（3）G-IBEET能够抵御授权测试人员发起的内部攻击，这是IBEET中的一个开放性问题。我们给出了G-IBEET的定义，并提出了一个具体的构造和一个有效的测试算法。然后在随机预言模型下对其进行了安全性分析。

引言

在云计算时代，如何对加密数据进行搜索已经得到了广泛的研究。Public key encryption with equal test (PKEET)，由yang等人[1]引入，是一种多用户环境下的可搜索加密，允许测试者比较在不同公钥下加密的密文，检查它们是否包含相同的消息。为了简化PKEET的证书管理，Ma[2]提出了基于身份的等价测试加密（ID-based encryption with equal test，IBEET），将基于身份的密码系统集成到PKEET中。由于具有相等测试功能，IBEET有许多有趣的应用程序，例如，个人健康记录系统和加密电子邮件分区。本文首先将组机制引入到IBEET中，提出了一种新的原语，即具有相等检验的基于组id的加密（G-IBEET）。通过分组机制：
  1. 组管理员可以授权测试员对组内用户的密文进行比较，但不能将组内用户的密文与非组内用户的密文进行比较。这种组粒度授权可以使IBEET适应组场景；
  2. 对于组粒度授权，只需发放给测试人员一个陷门，即组陷门，可以大大降低传统IBEET方案中活板门的计算、传输和存储成本；
  3. G-IBEET能够抵御授权测试人员发起的内部攻击，这是IBEET的开放性问题。
我们给出了G-IBEET的定义，并提出了一个具体的构造和一个有效的测试算法。然后在随机预言模型下对其进行了安全性分析。

相关工作

PKEET及其授权。可搜索加密分为两组：秘钥可搜索加密[3]和公钥可搜索加密[4]。在本文中，我们只关注公钥可搜索加密。
Boneh等人[4]提出了第一种可搜索的公钥加密，名为公钥加密与关键字搜索(PEKS)。在PEKS中，Alice使用Bob的公钥对关键字进行加密。然后Bob使用他的私钥计算关键字的活板门，并通过活板门搜索加密的数据。但是当给出两个密文时，这个原语不能直接检查它们是否包含相同的信息。因此，Yang等[1]引入了PKEET，这是一种多用户环境下的可搜索公钥加密方法。该原语允许测试人员直接比较在不同公钥下加密的密文，以检查它们是否包含相同的消息，而无需解密。但是原始的PKEET方案[1]只能在选择密文攻击(OW-CCA)安全下对任何实体实现单向攻击，这对于某些应用来说可能太弱了。因此，PKEET引入了授权机制。为了引入PKEET中的授权机制，我们首先将三种类型的授权描述如下。
  • 用户粒度授权，用户授权测试人员将用户的(全部)密文与任意用户的(全部)密文进行比较。
  • 密文粒度授权，允许用户授权测试人员将用户的特定密文与任何用户的(所有)密文进行比较。
  • 针对用户的密文粒度授权，用户授权测试人员将用户的特定密文与特定用户的特定密文进行比较。
Tang首先在PKEET中引入了细粒度授权[5]和用户粒度授权[6]，用户粒度授权后来被许多PKEET方案广泛使用[5-17]。因此，Tang的方案[5,6]的安全性提高到对已授权的对手的OW-CCA安全性，以及对未授权的对手在选择密文攻击(IND-CCA)下的不可区分安全性。在Tang的工作之后，Huang等[7]将用户粒度授权和密文粒度授权引入PKEET, Ma等[18]将用户粒度授权、密文粒度授权和用户对应的密文粒度授权引入PKEET。他们的方案的安全性也提高到针对已授权的对手的OW-CCA安全性和针对未授权的对手的IND-CCA安全性。事实上，这三种类型的授权不仅提高了安全性，而且为PKEET提供了授权的灵活性。但是，他们不能使PKEET适应组场景，这将在后面详细讨论。

IBEET。为了简化PKEET的证书管理，Ma[2]引入了IBEET，并提出了一个具体的IBEET结构。Wu等人改进了该结构的效率。Li等人[20]在Ma的工作[18]的基础上，将三种类型的授权引入IBEET，为IBEET提供灵活的授权。Wu et al.[13]和Wu et al.[21]分别引入了不同的对抗内部人攻击的对策（见下文）。

抵抗内部攻击。通常，在安全模型中，我们考虑的消息空间是超级策略的。然而，在一些实际应用中，加密的消息是关键字。因此，消息空间是多项式的（例如，一个普通的字典）。在这种情况下，内部攻击（IA）不可避免，类似于PEKS[4]中的内部关键字猜测攻击。IA最早由Tang[6]描述。粗略地说，由于授权测试者有能力访问用户的密文，并且可以使用自己的公钥对任何消息进行加密，因此可以通过穷尽地猜测消息来恢复隐藏在该密文中的消息。更详细地说，给定一个用户的密文C，授权测试者的目标是猜测隐藏在密文C中的信息。（1）从消息空间M中选择一个猜测信息M'，用他的公钥对M'加密生成密文C'，（2）然后对比C和C'，检查C和C'是否包含相同的信息。如果是，则恢复M成功；否则重复（1）和（2）。由于实际消息空间M通常是多项式，授权测试者可以在多项式时间内找到等于M的M'。因此，它的目标可以实现。
事实上，IA不仅存在于PKEET中，也存在于IBEET中。为了在PKEET中抵抗IA, Tang [17]， Ma等人[22]和Ling等人[23]采用了双服务器设置。在这个设置下，他们不能独立地检查两个密文是否包含相同的消息(因为他们需要一起工作)，即使他们可以使用用户的公钥加密任何猜测消息。因此，只要他们没有勾结，他们都不能成功启动IA。Wu et al.[13]和Wu et al.[21]分别对IBEET中IA的抗性提出了不同的对策。Wu等人使用双服务器设置[13]。他们的想法与上述类似。Wu等人。[21]使用了认证加密。更详细地说，一些用户组织一个小组，并通过安全协议共享一个公共的秘密令牌。它们都使用秘密令牌加密它们的消息。在不知道秘密令牌的情况下，被授权的测试人员无法为这些用户生成合法的密文，从而导致无法获得正确的测试结果。因此，IA的启动不会失败。

本工作与其初步版本[24]的主要区别。这项工作是初步版本[24]的扩展，已在ACISP 2019年发布。我们从以下几个方面对[24]工作进行了实质性的修改和改进。
  1. 修改了1型对手的安全目标。具体而言，将弱不可区分性修正为单一性。
  2. 我们加强了1型对手的能力。具体来说，攻击者可以在任何时候自适应地选择两个身份作为挑战目标。我们将在随机oracle中展示这种安全性。
  3. 我们加强了2型对手的能力。具体来说，攻击者可以在任何时候自适应地选择两个身份作为挑战目标。我们将在随机oracle中展示这种安全性。
  4. 我们修改了初版[24]的构造，减少了根系统参数的数量。更具体地说，初版[24]中提出的hash函数不再需要了。
  5. 我们通过修改初步版本[24]来增强演示和可读性。

动机和策略

为了便于描述，我们首先介绍G-IBEET密码系统。如图1所示，有一个由系统用户信任的私钥生成器(PKG)，它为系统用户生成私钥，还有一个由组用户信任的组管理员（GA），它为组用户生成组担保，并向测试人员发出组活动门。组织机制要求（1）遗传算法允许用户（例如用户我）加入集团通过发行他保证描述一组,这是机密信息对应于他的身份IDi，和（2）遗传算法允许通过发行测试人员一组陷门gtd,它可以使比较暗文集团用户但不能比较与任何用户的密文的暗文不在，和（3）每组用户需要他的团队作为输入时加密消息的一部分。
支持组粒度授权。我们认为这三种类型的授权不能使PKEET/IBEET适应组场景。对于用户粒度授权，使用我们图2中的示例，让Ui、Uj和Uk是支持用户粒度授权的PKEET/IBEET密码系统中的用户，以及在一个组中定义的Ui和Uj组用户。有一天，组用户Ui, Uj希望测试人员可以对他们的密文进行比较，但是他们的密文不能与任何不在组内的用户的密文进行比较（例如Uk的密文）。不幸的是，他们的目的无法实现。更详细地说，要授权测试人员这样做，他们应该分别向测试人员颁发他们的陷门tdi和tdj。然而，当得到tdi、tdj时，测试人员可以做比预期更多的事情。假设测试人员已经获得了英国的授权。使用tdi、tdj和tdk，测试者不仅可以用tdi和tdj比较Ui和Uj的密文，还可以用tdi（或tdj）和tdk比较Ui（或Uj）和Uk的密文。因此，用户粒度授权并不合适。密文粒度授权也存在同样的问题。虽然针对用户的密文粒度授权可以授权测试人员对Ui的特定密文和Uj的特定密文进行比较，但是当需要多次比较密文时，需要发出大量的陷门。为了适应IBEET的分组场景，我们通过分组机制在IBEET中引入了分组粒度授权，允许测试人员对组用户的密文进行比较，但不允许测试人员将组用户的密文与非组用户的密文进行比较。如图3所示，在组粒度授权下，测试者无法将Ui/Uj的密文与Uk的密文进行比较。


降低陷门的计算、传输和存储成本。假设有n个用户想授权测试人员对他们的密文进行比较。显然，使用用户粒度授权时，陷门的计算、传输和存储成本都低于使用密文粒度授权或针对用户的密文粒度授权。因此，我们只对用户粒度授权和组粒度授权之间的成本进行比较。对于用户粒度，这些用户应分别向测试人员发出n个陷门。也就是说，有n个陷门需要计算、传输和存储。对于组粒度授权，如果这些用户定义在一个组中，组管理员应该只颁发一个陷门（即组陷门）给测试人员。也就是说，只有一个组陷门需要计算、传输和存储。显然，在传统的IBEET方案中，群陷门的使用可以大大降低陷门的计算、传输和存储成本。
抵制IA。根据相关研究[13,17,21-23]，抵抗IA的对策可以分为两种，即（1）使用双服务器设置和（2）使用认证加密。我们选择后者来对抗IA。我们的组机制要求每个组保持其组授权，并在加密消息时将其组授权作为输入的一部分。在不知道组用户权限的情况下，被授权的测试人员将无法成功发起攻击。

比较

在表1中，我们将G-IBEET方案与相关的IBEET方案[2,19-21]在组粒度授权、组活动门、抗IA、Test算法的安全性和计算代价等方面进行了比较。注意，我们只分析单服务器设置下的IBEET方案。
由表1可知，只有G-IBEET支持组粒度授权和组trapdoor。对于抵抗IA, G-IBEET方案和wu等人的[21]方案可以抵抗。在安全性方面，G-IBEET方案和Li等人的[20]方案对1型对手可以实现OW-ID-CCA安全，对2型对手可以实现IND-ID-CCA安全，其安全性比2型对手更强[2,19,21]。注意，Wu等人的方案[21]没有授权机制。
计算成本的测试算法，测试算法的计算成本为用户粒度授权在Ma的计划[2]是4p，这为用户粒度授权在吴et al的计划[19]是2p+2Exp，为用户粒度授权在李et al的[20]年代方案4p（注意，我们忽略其他类型的授权），吴et al[21]的方案2p和，集团在G-IBEET粒度授权方案2p。再次注意，wu等人的方案[21]没有授权机制。显然，Wu等人的方案[21]和G-IBEET方案具有更高效的测试算法。但是wu等人的方案[21]由于缺乏授权机制，其安全性低于G-IBEET方案。
综上所述，G-IBEET方案具有组粒度授权、组活板门和抗IA三种特性。与[2,19,20]相比具有更高效的Test算法，与[2,19,21]相比具有更强的安全性。
我们强调G-IBEET方案使用了类型3配对(即非对称配对)，但据我们所知，现有的IBEET方案[2,13,19 - 21]都使用了类型1配对(即对称配对)。根据[25]，使用非对称对的优点包括更紧凑的组元素表示，更广泛的椭圆曲线实现[26]的选择，甚至可能还有额外的安全属性[27]。此外，与type 1配对相比，type 3配对对于高安全性参数[27]提供了良好的性能和灵活性。因此，在IBEET方案中最好使用type 3配对。

我们的贡献

本文的贡献如下：

  • 我们首先将群机制引入到IBEET中，提出了一个新的原语——G-IBEET。采用组机制：
（1）组管理员可以授权测试员对组内用户的密文进行比较，但不能将组内用户的密文与非组内用户的密文进行比较。这种组粒度授权可以使IBEET适应组场景；
（2）组粒度授权时，只需发放给测试人员一个活板门，命名为组活板门，可大大降低传统IBEET方案中活板门的计算、传输和存储成本；
（3）G-IBEET能够抵御授权测试人员发起的内部攻击，这是IBEET中的一个开放性问题。
  • 我们给出了G-IBEET的定义，并提出了一个具体的构造和一个有效的测试算法。
  • 在随机预言模型下对其进行了安全性分析。