WBSE的突出优点

  1. WBSE提供了一种新的方法来解决一个具有挑战性的问题，即如何通过NP语言上的见证关系来抵抗公钥可搜索加密中的关键字猜测攻击。
  2. 我们利用光滑投影哈希函数(SHIT)提出了一种基于见证的可搜索加密的一般构造，并证明了它具有WB- IND-CCA密文安全性、WB-IND-TD陷门安全性和EUFT- CIA陷门不可伪造性。
  3. 由于基于判定性迪菲-赫尔曼(DDH)假设的SPHF的有效实例化，我们获得了有效的WBSE方案，而没有任何配对操作。

摘要

我们提出了一种新的密码原语，称为基于见证的可搜索加密(WBSE)，即如果w和x满足见证关系，则(m，w)的加密可以通过(m′，x)的陷门来测试关键字m′是否等于m。

该原语的好处是解决了公钥可搜索加密中具有挑战性的关键字猜测攻击问题。

我们使用光滑投影散列函数(SPHF)作为构造块，以一般的方式构造了一个WBSE方案，并证明了它的WB-IND-CCA密文安全性、WB-IND-TD陷门安全性和EUFT-CIA陷门不可伪造性。由于来自判定性迪菲-赫尔曼(DDH)假设的有效SPHF实例化，我们获得了没有任何配对操作的有效WBSE实例。

引言

自从Boneh等人在2004年提出第一个带有关键字搜索的公钥加密(PEKS)以来，这种密码原语已经得到了广泛的研究。

特别是在云计算时代，其对加密数据进行隐私保护查询变得非常有吸引力。PEKS的功能是允许服务器使用接收方的密钥生成的关键字m的陷门（trapdoor）Tm来验证给定的密文c是否为任意关键字m的加密。PEKS安全保证，如果c不是m的加密，那么活动门Tm不应该泄露关于底层关键字m的任何信息。

关于可搜索加密的一个主要安全问题是对insider的关键字猜测攻击。在传统的PEKS框架中，在接收到陷门之后，内部人员（例如，服务器）可以如下猜测关键字。

  1. 对手捕获一个有效的陷门Tm，并想从Tm中找出关键字。
  2. 对手计算猜测的关键字m′的PEKS密文C。
  3. 对手检查Test(C，Tm) = 1。如果等式成立，对关键字m′的猜测是成功的。否则，转到步骤2。

本质上，由于服务器有责任执行PEKS功能，因此它总是可以发起这种攻击。许多研究认为，在传统的PEKS框架中，很难抵抗针对内部人的关键字猜测攻击。我们想解决这个具有挑战性的问题，这是我们工作的动力。

相关工作

Byun等人指出Boneh等人的方案容易受到攻击，其漏洞在于简单地结合关键字和密钥生成活板门。也就是说，任何攻击者都可以在某种特殊的结构（如双线性配对）下将该组合与公钥关联起来，从而发起攻击。受到这项工作的启发，Yau等人对其他方案发起了同样的攻击。

Jeong等人表明，一致性意味着公钥加密与关键字搜索攻击的不安全性。Baek等人提出了一种可搜索的加密方法，该加密方法具有安全的自由通道，可以抵御外部攻击者，而不是内部人员（例如服务器）本身。Park等人提出了可搜索加密来支持结合搜索关键字。Hwang等人还提供了包含公共密钥设置中的每个关键字的文档搜索，这具有高效的计算和通信开销。Rhee等人提供了一个可搜索的公钥加密方案，该方案有一个指定的测试器，只有指定的服务器（测试器）可以对特定关键字的密文执行测试。Fang等人构造了针对外部攻击者的安全可搜索加密，没有随机oracle。Chen等人提出了一种带关键字搜索的双服务器公钥加密方法，只要两个服务器不串通，就可以抵御攻击。据我们所知，在单服务器设置下，如何抵御对局内人的关键字猜测攻击仍然是一个具有挑战性的问题。

选择密文攻击是PEKS的另一个安全问题。在真实的攻击环境中，恶意接收方会得到wb∈{w0,w1}的修改后的挑战密文C '与自身生成的陷门（trapdoor）Twb之间的关系。在文献中，很多PEKS图式在这种攻击下是不安全的。Rhee等人通过额外向对手提供（C，T）上的测试oracle提出了一种增强的PEKS。不幸的是，具有这种增强的安全性的方案仍然可能遭受选定的密文攻击。在接收方R'的帮助下，A可以在不知道关键字wb的情况下修改挑战密文C*= (A*，B*)，在接收方R0的公钥pkR'下创建一个新的有效密文C'，同时计算活动门tw。因此，定义了一个弱安全模型，即对手可以查询任何密文，而不包含挑战密文的元素。

技术方法

现在我们解释基于证人的可搜索加密如何抵御公钥设置中的关键字猜测攻击。我们的想法是设计一个条件关键字搜索，以区分用于应用程序的正常过程和用于关键字猜测攻击的离线过程。幸运的是，我们观察到一个可能的区别在于创建活板门和密文的顺序：

  1. 一般情况下，当关键字被加密存储到远程后，数据所有者会计算出关键字对应的陷门（trapdoor），并将其发送给服务器进行密文搜索。

  2. 在脱机关键字猜测攻击中，给定一个陷门（trapdoor），攻击者生成关键字的密文，从而通过运行测试过程发起攻击。

关键字搜索的这一特点使我们想起NP语言上的证人关系R（w, x）：给定证人w，很容易计算证人关系R对应的实例x。然而，给定一个实例x，很难找到它对应的见证w。因此，基于证人关系R（w, x）的条件关键字搜索可能实现如下：

  1. 在一个普通的过程中，给定一个密文c，通过将目标关键字和测试密文c中的实例x作为输入来生成一个陷门（trapdoor）。
  2. 在关键词猜测攻击中,给定一个陷门t来自一个特定的关键字和x的一个实例，是不可能产生一个相应的密文目标关键词，因为很难找到从x由于证人关系R w，因此成功地抵御攻击。

我们的贡献

我们介绍了一种新的基于原始见证的可搜索加密方法，并论证了其优点如下：

  1. 基于证人的可搜索加密（WBSE）为解决公钥可搜索加密中如何抵御关键字猜测攻击这一具有挑战性的问题提供了一种新颖的方法。本质上，它使用NP语言上的证人关系，以确保在给定活动门的情况下，不可能为目标关键字m生成有效的密文。
  2. 我们提出了一个通用的WBSE结构，使用平滑投影哈希函数（SPHF）作为构建模块，并证明了它的WB-IND-CCA密文安全性、WB-IND-TD陷门（trapdoor）安全性和EUFT-CIA活动门不可伪造性。
  3. 利用DDH假设下SPHF的有效实例化，我们得到了一个不需要任何配对操作的高效WBSE方案。

论文组织

在第2节中，我们将介绍几个标准定义和工具。在第3节中，我们定义了基于证人的可搜索加密（WBSE）及其安全性。在第4节中，我们提供了一个基于光滑投影哈希函数的通用构造，并在第3节中提出的安全模型中证明了它。在第5节中，我们描述了一个基于DDH假设的WBSE的有效实例，并提供了效率比较的实验评价。最后，我们在第6节中总结了这一工作。

预备知识

平滑投影哈希函数

定义1：一个平滑的投射哈希函数(SPHF)在一个集合Y上的NP语言L∈X上，其中L是硬分区的子集，由六种算法(加上WordGen算法)定义:

  • SPHFSetup（k）：它生成全局参数参数。
  • HashKG（L，param）：生成一个哈希键hk。
  • ProjKG（hk，（L，param），W）：它从哈希键hk派生出投影键hp，可能与单词W有关。
  • WordGen（（L，param），w）：它用见证人w∈WT生成一个单词w∈L。
  • Hash（hk，（L，param），W）：输出任意单词W∈X上的哈希键hk的哈希值hv∈Y。
  • ProjHash（hp，（L，param），W，w）：它输出单词W∈L的投影键hp和见证人W∈WT的哈希值hv0∈Y，其中WT表示见证人空间。

集合Y通常是一个群，其中定义了一个算子：对于任意y1∈Y和y2∈Y，y1·y2∈Y。特别地，y·y−1=1，它是y的单位元。