x

【同态加密】通过同态加密实现可搜索的加密：综合分析

Chinese, Simplified
SEO Title
Leveraging Searchable Encryption through Homomorphic Encryption: A Comprehensive Analysis

PORTIC—Porto Research, Technology and Innovation Center, Polytechnic Institute of Porto (IPP), 4200-374 Porto, Portugal

Author to whom correspondence should be addressed.

Mathematics 2023, 11(13), 2948; https://doi.org/10.3390/math11132948

Received: 10 June 2023 / Revised: 25 June 2023 / Accepted: 27 June 2023 / Published: 1 July 2023

(This article belongs to the Section Mathematics and Computer Science)

 

Browse Figures

 Versions Notes

 

摘要

云基础设施的广泛采用彻底改变了数据存储和访问。然而，它也引发了对敏感数据隐私的担忧。为了解决这些问题，加密技术已被广泛使用。然而，传统的加密方案限制了加密数据的有效搜索和检索。为了应对这一挑战，出现了创新的方法，例如在可搜索加密（SE）方案中使用同态加密（HE）。本文全面分析了基于HE的隐私保护技术的进展，重点介绍了它们在SE中的应用。这项工作的主要贡献包括识别和分类现有的利用HE的SE方案，全面分析了SE中使用的HE类型，研究HE如何塑造搜索过程结构并实现额外功能，并为基于HE的SE的未来研究确定有希望的方向。研究结果表明，HE在SE方案中的使用越来越多，尤其是部分同态加密。这类HE方案的流行，尤其是Paillier的密码系统，可以归因于其简单性、已证明的安全性以及在开源库中的广泛可用性。该分析还强调了使用HE的基于索引的SE方案的普遍性，对排名搜索和多关键字查询的支持，以及在可验证性以及授权和撤销用户的能力等功能方面进一步探索的必要性。未来的研究方向包括探索与HE一起使用其他加密方案，解决模糊关键字搜索等功能中的遗漏，以及利用全同态加密方案的最新进展。

Keywords: 

searchable encryption; homomorphic encryption; secure search; data privacy; keyword search

MSC:94A60; 68P25

1.简介

云基础设施的快速增长和广泛采用彻底改变了我们存储和访问信息的方式。从Dropbox和Google Drive等个人数据备份和文件共享服务，到企业级数据管理和可扩展的基础设施解决方案，云存储对我们的日常生活产生了深远影响，尤其是在医疗[1，2]和教育[3，4]等领域。根据Netwrix发表的一份报告[5]，80%的组织将敏感数据存储在云中。它提供的优势包括高数据可用性、从任何地方方便访问、降低基础设施成本、无限存储空间和成本效益[6]。然而，随着云的采用，托管给云服务器的敏感信息面临潜在的漏洞，如未经授权的访问、数据泄露和内部威胁，安全问题也随之加剧。Netwrix的报告[5]还发现，55%的医疗保健组织在去年经历了涉及第三方实体的数据泄露，这是所有行业中第二高的百分比，仅次于金融部门，金融部门58%的公司经历了类似的泄露。这两个部门严重依赖能够访问其敏感数据的第三方实体，这对网络犯罪分子极具吸引力。此外，他们的研究结果表明，攻击变得更加复杂，更难发现。

为了解决这些问题，确保用户敏感数据的隐私变得至关重要。实现隐私的最常见方式是通过加密，即数据在存储到云中之前进行加密，从而提供端到端的数据隐私。然而，在高效搜索和检索以加密形式存储的数据时，传统的加密方案带来了挑战，限制了加密存储解决方案的可用性。天真的方法，例如下载所有密文、解密它们和搜索明文，是不切实际的。因此，为了应对这些挑战，出现了安全搜索、私人信息检索（PIR）和可搜索加密（SE）等创新概念。安全搜索解决了执行搜索操作的需要，同时保持数据的隐私和机密性[7]。PIR与安全搜索密切相关，使用户能够从数据库中检索特定数据，而无需透露他们正在访问的项目[8]。另一方面，SE是一种加密技术，允许对加密数据进行安全高效的搜索操作[9]。需要注意的是，“安全搜索”和“可搜索加密”这两个术语有时可以互换使用，模糊了这两个概念之间的区别。在实践中，这些术语之间的界限可能是不稳定的，不同的研究人员和从业者使用它们来指代相关的技术和机制。此外，PIR通常被认为是安全搜索或SE方法中的一个组件，因为它可以从数据库中检索私人数据。在这项工作中，我们主要使用“可搜索加密”一词，而“安全搜索”则在我们觉得需要区分的时候使用。

SE可以使用几种不同的加密技术以及这些技术的组合来实现。两种最流行的SE方案是可搜索对称加密（SSE）和带关键字搜索的公钥加密（PEKS），正如名称所示，它们分别依赖于安全对称加密方案或安全非对称加密方案。通常使用的其他技术是基于属性的加密（ABE），以便对SE方案执行细粒度访问控制，以及保序加密（OPE），以便有效地允许对搜索结果进行排序。然而，在SE领域中有一种值得注意的方法，那就是利用同态加密（HE），这是一种允许直接对加密数据执行计算的加密技术[10]。这一特性使其非常适合于隐私保护技术，在保持机密性的同时，可以直接对加密数据进行搜索操作。研究人员越来越关注这种方法，因为它为安全搜索提供了一个有吸引力的框架，而不需要昂贵的设置程序[11]。

已经提出了许多利用同态特性提供隐私保护技术的方法，特别是在SE的背景下。然而，缺乏专门的研究来分析这一领域的进展。另一方面，至关重要的是，科学界要全面了解最先进的技术，并为该学科的进一步探索确定有希望的方向。

在这项工作中，我们旨在对高等教育在SE中的应用进行深入分析。

1.1.相关工作

自2020年Song等人[12]发表第一篇关于SE的工作以来，已经就这一主题提出了几篇调查和评论论文，这突出了在大多数数据存储在第三方云服务中的世界中，安全数据管理的重要性日益增加。

Bösch等人[13]提出了第一项关于SE的调查。在他们的工作中，对每种方案支持的作者和读者数量进行了全面的讨论。作者考虑了四种不同的情况：单作者/单读者、多作者/单阅读器、单作者/多读者和多作者/多阅读器。根据它们的查询表达能力对这些方案进行了组织，并进行了分析，比较了效率和安全性。王等人[14]和韩等人[15]发表了两项关于SE的新的系统调查。前者考虑到现有SE方案在对称和非对称密钥环境中的应用，对其进行了更广泛的展望，而后者根据三个方面对系统进行了分类：安全要求、搜索功能和部署模型。此外，正如作者所说，后者还引入了一种新的部署模型，该模型在Bösch等人的工作中没有涉及，称为服务器-用户模型，其中云服务器是数据的所有者，同时充当数据所有者和存储服务器。

在后来的几年里，发表了其他关于SE方法的综述[16，17，18，19]。

最近，在2022年，Andola等人[20]发表了一篇全面的综述论文，重点分析了这些技术的特点和局限性，基于它们对各种类型攻击的性能和鲁棒性。这项工作的关键方面之一是深入分析每种技术以及决定其效率的密码基础。同年，Noorallahzade等人[21]发表了基于一组全面指标的SE方案的完整分类，包括搜索类型、索引类型、结果类型、安全模型、实现类型、用户的多样性、加密原语和所使用的技术。对每个类别的可用方案进行了比较和评估。Sharma[9]为非安全专家提供了一份关于SE的全面指南。这项工作的主要目标是帮助全科医生根据他们的具体需求选择最合适的SE方案，方法是进行一项调查，根据五个关键特征详细介绍现有方案：关键结构、搜索结构、搜索功能、对读者/作者的支持和读者能力。讨论了对称和非对称SE方案。它还提供了一个比较分析，可以帮助非安全专家就其加密需求做出明智的决定。

多年来，已经出版了其他作品，调查了SE在不同背景下的应用。例如，张等人[22]讨论了SE在医疗保健系统中的应用，而Bader和Michala[23]则重点讨论了其在工业物联网（IoT）中的应用。其他工作也分析了区块链等新技术如何被用于增强SE机制的潜力[24，25]。然而，没有研究将HE用于安全搜索机制。尽管如此，HE在SE方案中具有很高的价值，因为它具有独特的功能，例如允许直接对加密数据执行计算，以及实现隐私保护搜索操作。使用HE，用户可以对他们的查询进行加密，并根据加密的数据对其进行评估，从而确保查询和数据的机密性。因此，利用HE的最新进展可以增强SE方案，使其更适合现实世界的应用。在这种情况下，我们的主要目标是调查将HE纳入其设计的SE技术，同时对HE的使用方式及其带来的好处进行全面分析，并确定该领域应探索的潜在研究方向。

1.2主要贡献

我们工作的主要贡献是：

  1. 利用HE识别和分类现有SE。我们的分析涵盖了这些系统的几个方面，包括使用的加密技术、搜索过程的结构（基于顺序扫描或索引）以及提供的搜索功能（如处理多个关键字、正则表达式、通配符、短语、范围、出现次数和模糊关键字的能力）。此外，我们还研究了其他功能，如授权和访问撤销、SE的静态和动态方法以及正确性验证。
  2. 为了对SE方案中使用的最常见的HE类型进行广泛的分析，我们的分析重点是识别所使用的方案是否属于部分同态加密、部分同态加密或全同态加密的类别。此外，我们尽可能明确地识别HE方案。
  3. 在前面提到的分类的基础上，研究如何使用HE来实现SE中的不同属性和特性。具体来说，我们研究了HE如何塑造搜索过程结构，增强搜索能力，并在SE中启用其他功能。
  4. 为基于高等教育的SE计划的未来研发确定有希望的方向，旨在为SE提供更灵活、更先进的解决方案。

1.3研究方法

为了对高等教育在SE中的应用进行全面分析，采用了一种系统的方法。这种方法包括搜索几个学术数据库，包括ACM数字图书馆、IEEE Xplore、Elsevier ScienceDirect、Scopus和Web of Science。

为了在前面提到的数据库中进行搜索，在彻底审查了该领域的主要文献后，确定了一个关键词列表。在列出的数据库中搜索在标题、摘要或一组关键词中至少包含一个与SE相关的关键词和一个与HE相关的关键词的作品。与SE相关的关键词包括“可搜索”、“安全搜索”和“关键词搜索”。与HE相关的关键词包括“同态”。

因此，使用的主要研究查询是：

（可搜索或“安全搜索”或“关键字搜索”）AND同态。

搜索于2023年2月进行，表1显示了在每个搜索数据库中获得的研究出版物的数量。可以看出，总共返回了645个结果。

表1.在每个学术数据库中获得的搜索结果数量。

Table

在进行搜索后，我们能够识别出重复的结果，然后将其消除。这一过程总共产生了290篇不同的研究论文。为了选择与我们研究相关的出版物，有必要进行另一个筛选过程。因此，制定并适用了一套纳入和排除标准。表2中列出了这些标准。

Table 2. Inclusion and exclusion criteria.

Table

最后，在应用纳入和排除标准后，在290篇论文中，共有23篇论文被确定符合纳入和排除准则。因此，这23篇论文被选为我们分析的论文。

1.4.组织机构

本文件组织如下：第2节介绍了SE方案中涉及的主要参与者和过程，以及如何在搜索结构、搜索功能、用户多样性和其他功能方面对其进行表征。理解本节中提出的关键概念对于理解后续关于使用HE的SE方案的讨论至关重要。第3节重点介绍高等教育，介绍其定义、现有的主要类型和方法。HE在这项工作中发挥着至关重要的作用，理解基本的相关概念和属性对于理解其对增强安全搜索机制的影响至关重要。在第4节中，对所选作品进行了全面分析，对每一部研究作品进行了描述和分类。第5节涵盖了对研究趋势的讨论，这对于了解该领域的最新进展和新兴方向很重要。它为正在进行的研究工作、潜在的挑战和未来的机遇提供了宝贵的见解。最后，在第6节中，我们总结了关键发现，强调了主要贡献，并对研究的意义提供了见解。这一部分对于得出结论、总结研究意义和启发进一步研究具有重要意义。

2.可搜索加密

术语SE指的是一种加密技术，它可以在不首先解密的情况下搜索加密数据。在使用云服务存储大量敏感数据的情况下，SE特别有用和重要。在这种情况下，隐私保护技术对于搜索和检索存储的敏感数据是必要的。因此，我们在这项工作中的重点是基于云的SE系统。

SE技术可以根据底层加密过程大致分为两种主要类型：对称和非对称。与传统的对称加密方案类似，对称SE技术使用相同的密钥进行加密和解密。另一方面，非对称SE方案使用两个密钥——一个用于加密，另一个用于解密。

图1描述了一个通用的基于云的SE系统的高级架构，该系统通常由以下三个主要实体组成：

Mathematics 11 02948 g001 550

Figure 1. A conceptual overview of a cloud-based SE system.

  • 数据所有者（DO）负责数据加密及其外包给云服务器的实体是数据所有者，在相关文献中也称为“客户端”[9]。通常，数据由对其拥有合法控制权和所有权的DO生成。然而，在某些情况下，另一个实体，即数据提供商，可能负责生成数据。使用索引来帮助搜索过程的SE方法，也称为基于索引的SE方案，通常要求数据提供商（无论是否是数据所有者）加密索引并与云共享。
  • 数据用户（DU）想要搜索DO保存的加密数据的实体被称为数据用户。理想情况下，它只能在DO已经给予许可的情况下进行搜索。因此，DU负责向云服务器发送搜索请求，云服务器处理该请求，然后检索结果。值得注意的是，在某些系统中，DO也可以充当DU。
  • 云服务器（CS）云服务器是负责安全存储加密数据并向授权DU提供SE服务的实体。它在接收DO的加密文档后执行三项主要任务：存储数据、搜索数据和保持搜索数据结构的最新状态。CS执行搜索的方式取决于所使用的SE方案。对于基于索引的SE，CS通过将搜索请求与加密索引进行比较来进行搜索，然后将结果发送给授权的DU。然而，对于不基于索引的SE方案，搜索加密数据的过程通常需要扫描整个文档，这将在本节稍后讨论。

SE系统的体系结构通常包括四个涉及先前描述的实体的过程。根据SE方案的具体设计和要求，每个步骤中使用的具体算法可能有所不同。

考虑到各种因素，例如是否存在基于索引的搜索机制，以及它是对称的还是非对称的SE方案，对每个过程的以下描述已经尽可能广泛。

  • Setup（）算法根据输入的安全参数生成各种系统参数（P）和所需密钥（K）(𝜆)。非对称SE必须生成公钥和私钥，而对称SE只需要一个密钥。通常，系统所有者运行此算法。
  • Encryption（）加密算法使用上一个进程K中生成的密钥对数据进行加密，并输出一条消息𝑀′通过使用加密算法E对原始数据M进行加密而获得。如果SE方案是基于索引的，则关键字W的输入集合也将使用（一个或多个）输入密钥K来加密，那么它可以用于生成加密关键字的索引I。DO然后应用该算法将加密的索引I与加密的消息相关联𝑀′以便创建可搜索的密文(𝑆𝐶)。然后可以将SC上传到CS。如果SE方法是基于扫描的（意味着服务器将直接扫描加密的数据），则可以跳过前面的步骤，并且消息𝑀′可以直接存储在CS上而不生成SC。
  • TokenGen（）搜索查询的创建由授权用户使用此算法完成，也称为Trapdoor。它需要一个输入加密密钥K和一个输入查询𝑄=𝑘1.𝑘2，…，𝑘𝑚并生成搜索令牌𝑇𝑄算法的具体实现取决于SE方案是基于索引还是基于扫描。对于基于索引的方案，该算法使用加密密钥K加密查询Q中的每个关键字，并生成索引𝐼=𝑤′1.𝑤′2，…，𝑤′𝑚的加密关键字。搜索令牌𝑇𝑄然后由I构造。对于基于扫描的方案，该算法生成扫描令牌𝑇𝑆.使用所选择的搜索查询Q和扫描令牌𝑇𝑆，搜索令牌𝑇𝑄然后创建。一旦构建，搜索令牌𝑇𝑄被发送到服务器，服务器使用它来搜索加密数据库中的相关数据。DU可能是唯一可以执行查询的人，具体取决于场景。
  • Search（）CS使用搜索算法在加密数据中搜索与搜索查询匹配的数据。在基于索引的方案中，搜索算法应用搜索令牌𝑇𝑄到可搜索的密文𝑆𝐶以标识与查询匹配的加密关键字集和相应索引。然后，它将相应的加密数据检索到DU。在基于扫描的方案中，搜索算法应用搜索令牌𝑇𝑄和扫描令牌𝑇𝑠以识别具有与搜索查询的关键字匹配的关键字的可搜索数据段的集合。一旦发现任何匹配，服务器就向DU发送搜索结果。

2.1.SE方案的特征

SE方案可以通过各种方式进行分类，文献中对SE方案有几种分类。例如，Han等人[15]根据三个方面对SE系统进行了分类：安全需求、搜索功能和部署模型。Noorallahzade等人[21]通过考虑其他方面，如搜索类型、索引类型、结果类型、安全模型、实现类型、用户多样性和加密原语，提出了更全面的分类。Sharma[9]基于五个关键特征详细介绍了现有的SE方案：关键结构、搜索结构、搜索功能、对读者/作者的支持以及读者能力。

在我们的工作中，我们将考虑SE方案的分类，包括四类：搜索结构、用户多样性、搜索功能和其他功能。通过使用这种分类，我们分析每个方案并确定它属于哪个类别，使我们能够对使用HE的SE方案中最常见的特征进行适当的分析。

我们将使用的分类如图2所示，每个类别在以下章节中都有详细描述，以供澄清。

Mathematics 11 02948 g002 550

Figure 2. Key characteristics of a cloud-based SE scheme.

2.1.1.搜索结构

SE方案的一个重要方面是用于对加密数据执行搜索的搜索结构，因为它可能会显著影响方案的效率。历史上，由于Song等人[12]，第一种方案使用了所谓的顺序扫描搜索结构。此搜索操作包括按顺序扫描数据库中的所有加密文档，以找到与搜索查询匹配的文档。尽管顺序扫描类别中的其他工作已经发表，例如Boneh等人的工作。[26]关于关键字搜索的公共加密，但使用这种方法的著名研究工作并不多[18]。这是由于这些技术效率非常低，不太适合大型数据库或频繁的搜索查询，因为搜索操作可能变得非常耗时且计算成本高昂。此外，这种搜索方法容易将敏感信息暴露给服务器，这损害了数据的隐私和安全性[20]。基于顺序扫描的SE方案的一个潜在优势是，它们可以提供一种简单直接的方式来搜索加密数据，而不需要复杂的索引或搜索结构。

SE中通常用于提高搜索性能的另一种类型的搜索结构是基于索引的搜索结构。在这种方法中，一种称为索引的特殊数据结构与加密文档相关联。这种新的数据结构可以将搜索查询与索引中的条目进行比较，而不是搜索数据库中每个文档的内容。此外，使用索引可以处理各种格式的文件，包括多媒体文件以及压缩和加密文件[19]。然而，使用这种方法，加密的数据和加密的索引必须由DO发送到CS。这两组信息可以使用相同的加密方案进行加密，也可以使用SE方案对索引进行加密，使用另一种可靠的加密方案对敏感数据进行加密。关键字索引主要有三种类型：简单索引、反向索引和树索引。

简单索引。在采用这种策略的系统中，每个文档在被加密并上传到CS之前都会被赋予一个索引。索引由被认为与该文档相关的单词组成。这种索引适用于需要将少量文档上传到CS[9]的应用程序。

反向指数。反向指数这个术语来源于反向构建指数的过程。这是因为，索引不是将每个文档与一组关键字相关联，而是通过将每个关键字与它出现的文档集相耦合来创建的。这种方法显著减少了搜索所需的时间，使其成为最适合将大量文档上传到CS[9]的应用程序的搜索结构。

树索引。树索引也是优化搜索过程的一种非常有效的方法。尽管有各种方法可以构建树索引，但基本思想是通过将一组关键字划分为更小的集合来创建一个包含可搜索关键字的树状结构。当DU搜索特定关键字时，CS将搜索索引树，从根开始，遍历每个相关节点，直到找到匹配。

与顺序扫描方法相比，基于索引的方案效率很高，每个文件的比较次数从𝑂(𝑛)�(�)至𝑂（1）�（1） 。然而，一个缺点是，可以在查询中使用的关键字仅限于在索引生成过程中提取的关键字[19]。

2.1.2.用户的多样性

SE方案允许DO安全地外包数据存储，允许DU根据特定的搜索标准检索数据。基于所涉及的用户的多样性，如果DO扮演DU的角色，我们将这些方案进一步分类为单用户，如果DU与DO不同，则将这些方案分类为多用户。

2.1.3.搜索功能

顾名思义，SE方案的搜索功能决定了可以执行的查询类型、过滤和排序选项以及帮助数据用户完善搜索的其他工具。在这项工作中，根据类似于Sharma[9]的分类，我们区分了与关键字数量直接相关的搜索功能和其他功能。与关键字数量没有直接联系的一组功能被称为“杂项”（图2）。

关于关键字的数量，SE方案可以被分类为单个关键字或多个关键字。在前者中，DU被允许在每个查询中仅包括一个搜索项。因此，如果他/她想使用这种类型的方案搜索多个术语，那么他/她需要执行多个查询，每个搜索术语一个[19]。另一方面，在多关键字SE方案中，允许用户在每个查询中使用多于一个搜索项来执行搜索。然而，值得一提的是，仅仅因为支持多个关键词，并不一定意味着用户可以使用无限数量的关键词进行搜索。一些方案可能被限制为特定数量的关键字。

此外，在多关键字SE方案中，查询可以表示为搜索项的简单列表、连接查询（使用AND关系）或析取查询（使用or关系）。多关键字SE可以属于连接关键字或析取关键字类别，这取决于查询的表达方式。

现有的SE方案除了包含多少关键字之外，还可以根据各种功能将其分组。在这项工作中，我们考虑了以下内容：通配符和正则表达式、模糊关键字搜索、短语搜索、范围搜索、出现搜索和排序搜索。

正则表达式和通配符

当DU知道他们想要在文档中搜索的关键字的特定模式时，允许基于正则表达式或通配符的搜索查询的SE方案非常有用。在这两种情况下，查询都可以使用特殊字符来描述关键字模式。

如果SE方案允许通配符查询，则DU可以用称为通配符的符号替换搜索查询中的单个字符。通常使用两种类型的通配符：“？”和“*”，后者被称为多字符通配符，表示任意数量的字符，而前者仅表示一个字符[27]。如果使用基于正则表达式的SE方案，则可以使用特殊字符和运算符的组合来描述搜索查询中比通配符所允许的更复杂的模式。尽管正则表达式提供了更大的灵活性，但在搜索变化较小的关键字时，基于通配符的SE方案是一种更简单的选择。

模糊关键字搜索

典型的SE方案，即使允许基于通配符或正则表达式的搜索查询，也只能搜索密文中关键字的精确匹配。它排除了搜索词格式中的任何拼写错误或不一致。但是，通过在SE方案中包括模糊关键字搜索功能，可以克服这一限制。有了这一功能，即使DU在搜索过程中拼错了单词，该方案也能够搜索与正确拼写单词相关的结果[19]。

短语搜索

通常，DU更喜欢查找特定的短语，而不仅仅是查找单个关键字。尽管这可以使用允许联合搜索查询的SE方案来实现，但这需要DU执行几个额外的步骤。首先，他们需要将短语转换为连接查询并执行搜索。然后，在从CS获得相应的文档后，他们必须对其进行解密和筛选，以找到包含他们要查找的短语的文档[28]。因此，在处理大型数据库时，这种方法可能效率非常低。另一方面，具有短语搜索功能的SE方案使数据用户能够直接搜索短语[9]。

范围搜索

允许范围查询的SE方案使DU能够在特定的值范围内搜索加密数据，这意味着它们可以根据间隔而不仅仅是精确匹配来执行搜索。例如，数据用户可能希望搜索2020年至2022年间创建的数据库中的所有文档，或者搜索所有者年龄超过30岁的文档。事实上，最后提到的例子属于范围查询的一个特定子类别，称为比较查询[29]。这种搜索查询对于避免多个单一关键字搜索非常有用。

事件搜索

具有此属性的SE方案允许数据用户向云服务器发出包括搜索项和值的查询。此值指定所选关键字必须出现在文档中才能在搜索结果中检索到的最小次数。这一功能非常有助于衡量我们的关键词在数据库中每个文档中的重要性[19]。

排名搜索

此功能的主要目的是通过仅检索与查询匹配的相关文档来增强数据用户的搜索体验。为了实现这一点，信息检索研究界采用了各种评分函数[19]。最常用的评分函数被称为TF-IDF，其中TF代表术语频率，表示该关键字在文档中的重要性，IDF代表倒置的文档频率，表示关键字在数据库中所有文档中的意义[18]。

2.1.4.其他功能

SE方案可能具有其他功能，并且对某些场景很重要。例如，关于访问控制功能，授权和撤销DU的能力至关重要。

授权和吊销用户

顾名思义，SE方案中的这一功能意味着DO可以授予新用户搜索功能，也可以撤销该功能。具有此功能的SE方案并不多，而且现有的方案效率低下且不切实际。这是因为启用此功能需要牺牲安全性[20]。

静态或动态

用于实际应用程序的SE方案中的另一个重要功能是允许动态更新的能力。当在创建加密数据库后没有添加、删除或更新文档时，SE方案被认为是静态的。因此，在数据加密之前，整个数据集必须可用。相比之下，如果用户可以添加、删除或修改文档，而不会危及加密数据的安全性或系统搜索和检索文档的能力，那么SE系统就是动态的。动态SE方案更灵活，更适合实际应用。然而，与动态SE方案相比，静态SE方案通常更有效，实现起来更简单，这使其成为数据相对稳定、不需要频繁更新的简单场景的更好选择。需要注意的是，在动态和基于索引的SE方案中，当对文档集合进行更改时，必须有效地更新索引，并且必须在不添加任何泄漏的情况下进行更新[19]。

可验证性

在大多数应用中，SE系统中的CS被认为是半可信的，这意味着它可能会向DU检索不完整或不正确的结果[19]。因此，对于SE方案来说，允许DU验证CS已经检索到的搜索结果是重要的。这样的SE方案被指定为可验证的SE方案。正如预期的那样，与不允许可验证性的SE方案相比，这种方案在所有站点（DO、DU和CS）上都会遭受更高的计算开销[9]。结果验证可能包括正确性（如果检索到的结果与查询相对应）、完整性（如果返回了所有相关文档）和新鲜度（如果将文档的最新版本检索到DU）[19]。

代表

此功能允许授权用户将搜索功能委托给另一用户。该功能主要出现在非对称SE方案中，也称为带有关键字搜索的公钥加密。这些SE方案包括代理重新加密，也就是说，它们有一个半可信的第三方服务器（代理服务器），将用DO的公钥创建的密文转换为受委托用户可以解密的密文[9]。尽管这不是一种非常常见的SE类型，但已经有几项工作解决了这一特点[21]。

3.同态加密

HE方案背后的主要思想是允许在加密数据上执行计算，而无需首先对其进行解密。这个概念是由Rivest等人[30]引入的，最初被称为“隐私同态”。因此，HE方案是加密函数是同态的任何加密方案。形式上讲，设M表示明文的集合，C表示密文的集合。Let⊙𝑀和⊙𝐶分别是M和C中的运算。如果对于任何加密密钥k加密函数E满足以下性质，

∀𝑚1,𝑚2∈𝑀,𝐸(𝑚1⊙𝑀𝑚2)←𝐸(𝑚1)⊙𝐶𝐸(𝑚2),

其中← 意思是“可以直接从”[31]获得。即在（1）中，𝐸(𝑚1⊙𝑀𝑚2）

可以直接从𝐸(𝑚1） ⊙𝐶𝐸(𝑚2）

而不必执行任何解密。

根据系统允许的操作类型和数量，HE方案可以分为三类：部分同态加密（PHE）、部分同态加密和全同态加密（FHE）。

3.1.部分同态加密

Rivest等人的工作发表后，密码学研究人员开始寻找允许直接对加密数据执行多个操作的HE方案。尽管如此，在接下来的二十年里，大多数尝试都产生了只允许一种操作类型的方案，即PHE方案。在这些方案中，同态性质仅通过一个运算（如加法或乘法）来满足，而不对该运算的执行次数施加任何限制。

众所周知的RSA公钥密码系统[32]是一种PHE方案，它只支持通常的乘积运算，并且是确定性的，这意味着当一个人使用相同的密钥加密相同的明文时，总是会得到相同的密文。

几年后的1982年，Goldwasser和Micali[33]发表了第一个概率PHE方案，这激发了随后几十年发表的大多数PHE方案的灵感，如Benaloh[34]，这是Goldwasser等人方案的推广，Naccache和Stern[35]，这是Benaloh方案的改进。

Elgamal[36]介绍了一种PHE，它也只允许通常的乘积，Paillier[37]发表了一种只允许通常和的PHE。后一种方案是使用HE的SE方案中最常用的方案，如第5节所示。

3.2.某种同态加密

2005年，Boneh等人[38]发表了第一个能够执行两种运算的HE方案：加法和乘法。然而，尽管加法可以无限次执行，但它只允许一次乘法。这是一种被称为SWHE的HE方案，因为同态性质被满足的次数有限，而不是一次运算。

在引入最初的高等教育计划后不久，就出现了一些关于SWHE计划的建议。尽管由于其局限性，它们不如PHE计划具有吸引力，但对PHE的广泛研究导致了更完整的计划的开发，这些计划是实现FHE计划的垫脚石。事实上，许多研究人员认为Boneh等人[38]提出的方案是FHE方案发展的重要组成部分。

3.3.全同态加密

在这种类型的HE方案中，同态性质适用于不同的运算，并且它们可以执行任意次数。

这一类别被许多人认为是密码学的“圣杯”，因为它允许在加密数据上自由执行计算。2009年，Gentry发布了第一个FHE方案[39]。在他的工作中，Gentry还提出了一种从不完全同态但具有一定同态评估能力的FHE方案构造一般FHE方案的方法[40]。从那时起，HE引发了相当大的兴趣，导致了基于Gentry思想的新型FHE方案的提出。其中最显著的是FV[41]、BGV[42]、CKKS[43]和TFHE[44]。

HE方案中常见的安全问题是0加密的累积。如果恶意参与者能够收集大量0的加密，则可能会危及该方案的安全性。为了解决这个漏洞，许多方案都采用了一种被称为“添加噪声”的技术来伪装零加密。

然而，随着计算次数的增加，这些方案中的噪声往往会增加，可能导致不正确的解密。为了解决这个问题，Gentry引入了自举的概念。然而，这种方法需要大量的计算成本，而Gentry方案复杂的数学基础使其在现实应用中不实用。

根据Acar等人[10]，自Gentry于2009年开展工作以来，FHE方案主要有四类：

理想格——在这一类中，本质上存在着对Gentry方案的优化。这一类别的例子包括Scholl和Smart的作品[45]以及Gentry和Haveli的作品[46]。

整数——第一个基于整数的FHE出现在2010年[47]。这些方案背后的主要动机在于其概念的简单性。然而，由于缺乏实用性，它们成为研究人员最不喜欢的类别。

（Rings）Learning With Error，（R）LWE-Brakerski和Vaikuntanathan[48]是第一个提出这类方案的人。这些方案基于LWE问题，这是实时解决的最具挑战性的问题之一，即使对于后量子算法也是如此。LWE有一个称为RLWE的代数变体，在实际应用中更有用；

𝑁𝑡ℎ��ℎ次截断多项式环单元-这些方案允许在使用各种密钥加密的数据之间进行计算。López-Alt等人[49]是第一个提出这种HE方案的人。

由于其在密码应用方面的巨大潜力，已经提出了HE方案来解决几个领域的广泛问题，包括大数据和云计算、安全图像处理、医疗应用、电子投票系统、私人信息检索和生物特征验证，如Challa[50]和Alloghani[51]所述。

4.利用HE的SE方案的分析

在本节中，我们回顾和分析了第1节中所述的筛选过程中产生的23项研究工作。我们只考虑了清楚如何使用HE的拟议方案。该分析的目的是研究它们的功能，考虑图2中所示的特征，并确定这些特征中的哪些利用了HE和所使用的HE类型。表3列出了选定的作品，并概述了它们的功能。它还确定了使用HE实现的特性。该表是一个完整的资源，用于识别和访问本研究中分析的作品，确保透明度并促进未来的参考。

Table 3. Categorization of selected SE schemes that utilize HE.

Table

我们的分析分为以下几类：搜索结构、搜索功能和其他功能。我们没有专门讨论“用户的多样性”这一类别，因为每当我们分析所选作品时，都会提到这一功能。需要注意的是，提供密码结构的详细解释超出了本工作的范围，可以在参考作品中找到。

4.1.搜索结构

SE方案的搜索结构可以包括对整个数据库的顺序扫描，也可以包括基于索引的方法，其中创建索引以促进搜索过程，如第2节所述。在本分析中，我们将重点关注基于顺序扫描的SE方案，因为所有其他方案都是基于索引的，它们将在下一节中讨论。此外，重要的是要记住，安全搜索的概念与SE的概念相似，因此，这两种方法都将包含在本分析中。请注意，安全搜索方法通常包括验证数据库中的所有文档，以找到与查询匹配的文档，这类似于顺序扫描过程。

Akavia等人的工作[7]是第一篇介绍对FHE加密数据进行安全搜索的方法的论文。作者声称，这是通过使用一个多项式来实现的，该多项式的次数相对于数据数组中的条目数量是对数的（而不是线性的）。

他们的安全搜索协议的核心是计算第一个查询匹配的草图，这是使用他们称之为SPiRiT的方法完成的。此方法返回与加密数据数组中的查找值匹配的第一条信息。任何标准的语义安全FHE都可以用于他们提出的方案，前提是明文模参数是素数p，在这种情况下同态运算是加法和乘法模p。他们声称只有一轮通信，并且通信开销只会随着输入和输出大小的增加而增加。

2020年，Wen等人[66]提出了一种用于安全搜索方案的搜索方法，该方法适用于单个用户设置，名为LEAF。这种方法使用了三种新方法：定位、提取和重建。定位技术用于将原始数据库数组划分为长度相等的较小间隔，并识别包含匹配项的第一个数组。返回包含匹配项的加密间隔索引。然后使用提取来找到包含第一个匹配项目的区间，以便在该区间上进行后续搜索操作，并使用重建来组合来自这两种技术的信息，以便在不需要解密任何内容的情况下正确定位我们想要的数据。值得一提的是，这些作者声称安全搜索大致由两个步骤组成，即匹配和搜索。在匹配步骤中，服务器将客户端的加密搜索查询与所有加密数据库项进行比较，返回第二个0和1的加密数组，1表示数据库中与查询匹配的项。搜索步骤将所有1的索引和相应的项目返回给客户端。因此，他们的工作集中在搜索步骤上。FHE在该方案中用于加密敏感数据和搜索查询。事实上，该方案的主要目标之一是通过减少必要的计算次数，即乘法次数，优化FHE在安全搜索中的使用。此外，作者还提出了该方案的一个变体，名为LEAF+，它使用了懒惰自举。从好的方面来说，自举步骤可以控制算法的计算深度，并且数据库越大，优化效果就越大。另一方面，当数据库的大小很小时，这种变体将是无效的，因为它带来了许多额外的乘法运算和计算深度。

Choi等人在2021年[11]提出了一种安全搜索方法，该方法使用标准CPA安全（分级）FHE，用于一次性使用，还对加密数据库进行顺序扫描以执行搜索。事实上，在他们的方法中，安全搜索的计算任务分为两个步骤，称为匹配和获取，这两个步骤对应于Wen等人方法的数学和搜索阶段。在匹配步骤中，云服务器使用底层FHE方案的同态属性将加密的搜索查询与数据库中的所有加密记录进行比较，以找到与该查询相对应的记录。然后，在获取步骤中，同样使用同态属性，从数据库中检索那些对应的记录，并使DU可用，然后DU可以对它们进行解密。关于提取过程，作者提出了两种新的检索算法，即COIE方案（基于幂和或bloom滤波器）和CODE方案（基于bloom滤波器集），并将这些算法的性能与LEAF+[66]和PIR等其他众所周知的检索算法进行了比较。

2022年，Iqbal等人[53]提出了一种机制，用于安全地搜索在医疗环境中外包给CS的加密音频数据，该机制还执行顺序扫描。他们的方法包括使用BGV FHE方案对数据文件进行加密，然后将数据文件发送到云服务器进行存储。当请求搜索时，CS使用同态运算对存储的加密文件执行顺序扫描，以找到包含搜索关键字的文档。然后，使用BGV方案对检索到的文档进行解密。在Iqbal等人进行的实验中，使用了开源编程库HElib 2.1.0版本。该库允许将BGV与自举一起使用，并应用增强功能，如Smart–Vercauteren的密文打包技术和Gentry–Halevi–Smart的优化技术[73]。

在Malik等人[52]于2023年发表的最新工作中，提出了一种使用PHE的单关键字SE方案，该方案使用Paillier密码系统[37]来保护外包给云服务器的机场数据。该方案使用HE来执行搜索操作，并通过使用陷门隐藏搜索模式来提供高级别的安全性。提出了两种方法，一种利用了Paillier密码系统的确定性性质，称为“有效SKSE”，另一种利用其概率性性质，命名为“安全SKSE”。前者适用于将轻量级方法置于安全之上的场景。相比之下，后者更适合于安全性优先于性能的场景。这两种方法都使用顺序扫描搜索结构，并且是为单个用户场景设计的，其中机场充当加密数据的DO和DU。

在该方案中，原始数据文件被加密两次。第一次加密是使用高级加密标准（AES）[74]进行的，之后将加密的文件上传到CS。第二次加密使用Paillier密码系统对原始文件进行加密，得到的加密数据也被上传到CS。这些是将用于执行顺序扫描的加密文件。作为该扫描的输出，系统检索加密结果，该加密结果在DU使用Paillier方案解密后，允许恢复包含搜索关键字的文件的标识符。然后使用AES来解密这些文件并恢复原始数据。

4.2.搜索功能

在本节中，我们将分析所选的涉及搜索功能的作品。我们根据以下特征对本节进行了划分：正则表达式和通配符、连词搜索、范围搜索、短语搜索和排序搜索。我们没有提供单独的章节专门讨论允许多关键字搜索或析取搜索的能力，因为所有拥有这些功能的作品也拥有其他搜索功能，并在其相应的章节中进行分析。此外，在表3中可以很容易地识别出具有特定特征的纸张。

4.2.1正则表达式和通配符

允许通配符查询的SE方案是多余的，在我们的研究中只发现了两个。杨等人于2020年提出了第一个方案[65]。在这项工作中，他们提出了一种新的基于索引的SE方案，该方案专为多用户环境设计。所提出的方案允许通配符查询以及用户授权和撤销。此外，用户可以对搜索关键字进行“与”或“或”查询，还可以获得相关性得分最高的前k个文档。

该方案使用了一种简单的索引方法。更具体地说，文档索引包含三条信息：文档ID、其对应的关键字以及用于保护文档的对称加密方案中使用的密钥。该索引在外包给云服务器之前，使用PHE方案（即Paillier的密码系统）进行加密。另一方面，文档本身使用任何安全对称加密方案进行加密。

The authors cover a wide range of different algorithms to look for a match within the search protocols, regarding different types of wildcard queries. These algorithms can be split into three categories: zero wildcards (1 algorithm), one wildcard (3 algorithms), and two wildcards (4 algorithms). More specifically, for one wildcard we have the following possibilities for a query: *+𝑌1*+�1, 𝑌1+*�1+* and 𝑌1+*+𝑌2�1+*+�2, (𝑌1,𝑌2�1,�2 are strings of any size). When two wildcards are present in the query, we have the following possibilities: *+𝑌1+**+�1+*, 𝑌1+*+𝑌2+*�1+*+�2+*, *+𝑌1+*+𝑌2*+�1+*+�2 and 𝑌1+*+𝑌2+*+𝑌3�1+*+�2+*+�3 (𝑌1,𝑌2,𝑌3�1,�2,�3 are strings of any size). These algorithms take advantage of the homomorphic properties of the Paillier’s cryptosystem to encrypt the keywords in a way that comparisons are possible to identify matches. Finally, with respect to the authorization and revocation functionality, PHE is not utilized. Despite this, the system allows a DO to grant research privileges to other users for a specified period of time and to automatically revoke these privileges once the authorization period expires.

In 2021, Yin et al. [58], suggested a new SE scheme which uses FHE and allow some types of wildcard queries. The scheme was designed to achieve compound substring query on multiple attributes. A substring query, as the name suggests, is a query that allows to search for a contiguous sequence of characters within a string. For example, the substring query “cat” would return all the results which contain the substring cat, e.g., caterpillar, cats, concatenate, ducat. The proposed scheme can, in fact, support two types of substring patterns: *+𝑠+**+�+* and 𝑠1+*+𝑠2�1+*+�2, where s, 𝑠1�1, and 𝑠2�2 represent queried substrings and * represents any string of any length. This is achieved by constructing a tree index structure using a modified version of the well-known position heap technique.

在该方案中，使用对称密钥加密方案对敏感数据进行加密，该方案在所选明文攻击（如AES）下不可区分，并且使用FHE方案（如BGV）和伪随机函数对树索引进行加密。FHE方案用于加密树中每个节点的ID，伪随机函数用于加密沿着从根到该节点的路径的所有边缘标签的级联。

基于FHE方案的性质，作者还设计了一种算法来计算不同搜索关键字的搜索结果的交集，从而实现对多个属性的复合子串查询。在这种情况下，复合公式由查询的子字符串的合取表达式和析取表达式组成，因此，该方案允许第2节中定义的合取和析取查询。

我们没有发现任何文献提出能够使用正则表达式并利用HE的SE方案。

4.2.2.联合搜索

执行联合搜索的能力非常有吸引力，在选定的作品中，有六部作品允许此功能。然而，这些论文中只有4篇使用HE来促进连词搜索。这些论文中的大多数都具有其他搜索功能，并在相应的章节中进行了分析。有趣的是，只有一个作品提供了联合搜索，而没有其他搜索功能。这项工作归功于Wang等人，他们在2022年[56]提出了一种基于索引的SE方案，用于多用户设置，该方案支持联合关键字搜索，并使用特殊的PHE方案来隐藏搜索模式。他们的工作特别利用了辅助服务器和加性同态加密方案PBC[75]，以有效地实现联合关键字搜索特性，同时确保DU只能学习所需的搜索结果。事实上，引入辅助服务器是为了允许系统通过采用作者所称的双陷门解密机制来实现所需的属性，该机制在该方案中可用。

为了实现联合关键字搜索特性，作者使用多集的多项式表示，并使用BCP密码系统对多项式进行加密以保持其机密性。然后由云服务器和辅助服务器使用加法和乘法同态性质来联合执行搜索。

这项工作没有详细说明在将文档上传到数据库之前，使用什么样的加密方案来加密文档。

4.2.3.短语搜索

在SE方案中，使用HE来实现短语搜索并不常见。事实上，在23个分析的SE方案中，只有2个能够执行短语搜索，并使用HE来实现该功能。第一个由Shen等人于2019年提出，命名为P3[70]。该方案适用于多用户设置，支持多关键字搜索，特别是短语搜索和联合关键字搜索。该方案的主要思想是建立一个反向索引，该索引不仅包含每个关键字出现的文档标识符，还包含每个关键字在这些文档中的位置。

为了保护位置信息，该方案使用Boneh等人[38]的PHE方案对其进行加密，其同态特性允许服务器分析两个加密的关键字是否相邻。此外，这使得DU能够从与云服务器的单个交互中获得精确的搜索结果。请注意，短语搜索是一种特定类型的连接查询，其中查询的关键字的位置很重要。

文档标识符和关键字分别使用其他技术来保护，特别是伪随机排列原语和安全kNN技术。

随后，在2022年，Hou等人[61]提出了一种SE方案，该方案也使用了Boneh等人的PHE方案。以保护关键字的位置并启用短语搜索。然而，他们提出了一种不同的索引结构，称之为虚拟二叉树。这个索引树只是一个用于存储关键字和相关信息的逻辑结构。它的元素存储在哈希表中（如果它们是叶节点），或者映射到bloom过滤器。同胚性质的使用类似于Shen等人的工作。[70]，允许该方案检查关键字是否相邻。此外，他们的方法允许动态更新，这与以前的方案相比是一个优势。

4.2.4范围搜索

执行范围搜索的能力是在使用HE的SE方案中不常见的另一个功能。在我们的研究中，由于郭等人[69]，只发现了一项工作。这项工作发表于2019年，它提出了一种用于物联网环境下多用户设置的概率阈值范围搜索方案。该方案解决了在多维不确定数据上执行范围搜索的问题，同时通过返回在感兴趣范围内的概率高于给定阈值的所有加密数据来允许误报。

该方案的概念是，DO从物联网设备中获得不确定的数据，这些设备被建模为多维对象。因此，每个物联网对象都由一个不确定区域及其概率密度函数表示。从这样一个对象收集的一段数据称为实例，包括三个组成部分：对象的标识、实例的坐标及其概率。

他们的方法利用了KD树，这是一种用于索引分布在d维空间中的d维点数据的数据结构。KD树中的每个节点都由一个实例及其相应的范围组成，这些范围是根据实例的坐标计算的。节点使用保序加密（OPE）方案加密，而实例概率使用Paillier密码系统加密

值得注意的是，该方案依赖于两个云服务器。具体来说，第一云服务器负责：存储加密的数据和加密的KD树，执行KD树搜索，并将结果发送给第二服务器。然后，第二服务器有权基于搜索查询中提供的阈值来过滤结果，并将获得的加密文档发送到DU。

当第一个云服务器接收到查询时，它通过比较实例坐标的值，并使用Paillier密码系统的同态加法来计算每个IoT对象相对于搜索的上下出现概率，从而在KD树上进行搜索，因此结果落在查询的范围内。然后，将结果发送到第二服务器进行过滤，最后，将过滤后的结果发送到DU。

4.2.5.排名搜索

执行排序搜索的能力是使用HE的SE中最常观察到的特征，在23个分析的作品中有10个具有这种特性。此外，所有这些工作都利用HE来实现这一功能。

2018年，Elizabeth等人[71]提出了一种允许动态更新的多用户排名前k的SE（TSED）方案。该方案基于反向索引，该索引使用每个关键字的二进制向量来指示每个文件是否包含该关键字（类似于Wu等人提出的Z索引[72]）。

在该方案中，使用诸如AES之类的安全对称加密方案对敏感数据进行加密。然后使用两个PHE方案来加密反转索引的两个分量。具体而言，Paillier的密码系统用于加密每个关键字，而Goldwasser–Micali（GM）[33]用于加密每个二进制索引向量。

TSED方案允许使用TF-IDF规则进行排名前k的搜索。该过程由安全协处理器完成，该安全协处理器负责使用加密的分数索引来计算查询关键字的分数，用于基于结果与查询的相关性来对结果进行排名，并且用于将前k个文档标识符返回给CS，CS随后在DU中检索相应的文档。

Elizabeth等人也在2020年提出了该方案的一个变体[63]，该方案被指定为具有动态更新（VSED）的加密云数据上的可验证前k位SE。该方案除了具有类似于VSED方案的动态和排序搜索能力外，还具有可验证性。

在VSED方案中，构造了类似的加密反向索引，但现在作者使用了秘密正交向量和Paillier密码系统[37]。使用PHE方案以及预先计算的排名分数对执行搜索时使用的索引和陷门进行加密，并且与TSDE中所做的类似，使用安全协处理器来基于TF-IDF规则查找排名前k的搜索。

Paillier密码系统也用于更新过程，更新过程使用两种不同的算法：一种是添加新关键字，另一种是删除现有关键字。为了验证CS接收到的查询结果，该方案使用了名为HMAC[76]的众所周知的消息认证机制。关于敏感数据，该系统允许使用安全对称加密方案（如AES）对其进行加密，如TSED。

2019年，Boucenna等人[68]提出了一种SE方案，称为基于安全反向索引的SE（SIIS），用于多用户设置，支持使用HE进行排名搜索。事实上，该方案还允许通过使用CP-ABE来加密数据收集来进行用户访问权限管理。正如该方案的名称所示，它涉及反向指数的构建。更具体地说，使用了两个独立的反向索引。一种是用于存储使用双分数加权公式[77]计算的相似性分数。通过使用伪文档技术[78]来允许关键字隐私，创建了第二个反向索引来管理用户的访问权限并降低误报数量。第二个索引中的条目是用户的ID，用于标识他们可以访问的文档集合。然后使用FHE方案BGV对两个索引进行加密，该方案的同态性质用于执行搜索。

2020年，张等人[62]提出了一种针对混合云计算中加密数据的安全排名搜索方案，适用于单个用户环境。“混合云计算”一词指的是公共和私有云的使用，后者主要用于执行昂贵的计算，否则必须在客户端执行。在该方案中，私有云具有加密和解密数据的能力，并且大多数通信轮次在私有云和公共云之间进行。

在该提案中，作者使用Ocapi BM25排名模型[79]，并使用未指定的FHE方案在私有云上分别加密TF和IDF。然后，这些信息被用来构建一个反向索引，这是在公共云中完成的。

关于敏感数据的加密，可以使用任何安全的对称加密方案来执行，例如AES。最后，所提出的方案还依赖于私有云用来下载加密文档的检索技术，尽管作者没有具体说明。

同年，李等人[64]提出了一种双服务器排序的动态SE方案（TS-RDSE），用于单用户设置，支持多关键字搜索。该方案使用两个云服务器进行搜索和排序，其中一个服务器负责存储加密数据，另一个服务器用于存储密钥。该方案在反向索引的加密中使用正交向量和两个PHE方案，即Paillier和GM，反向索引包含用于执行排序搜索的TF-IDF分数。更具体地说，该索引分为搜索索引和权重索引，搜索索引使用Paillier和GM进行加密，权重索引仅使用Pailliier。

由于索引的加密基于两种PHE方案，因此用于添加或删除文档的TS-RDSE协议也利用同态性质来有效地更新索引。

关于敏感数据的加密，可以使用任何安全的对称加密方案对其进行加密。

2020年，杨等人[67]提出了一种基于索引的SE方案，用于支持多个数据所有者的多用户设置。该方案还支持多关键字查询、排名前k的结果和用户授权/撤销。

作者使用PHE方案，更具体地说是具有阈值解密的Paillier密码系统（PCTD）来加密索引，该索引由关键字及其权重、文档ID和文档密钥组成（例如，关键字的权重可以使用TF-IDF规则计算）。在给定某个查询的情况下，作者提出了一种新的算法来计算与该查询相关的分数，称为跨域安全多关键字搜索协议（MKS）。

文件本身的加密通过任何安全对称加密方案来执行。

2021年，Tosun等人[60]提出了一种多用户SE方案，称为完全安全文档相似性（FSDS），该方案将安全K近邻（SK-NN）与SWHE相结合，SK-NN是一种对欧几里得空间中的数据集进行操作并使用欧几里得距离测量相似性的安全算法。在该方案中，敏感数据和搜索查询表示为TF-IDF向量，这些向量用SK-NN的变体加密，作者将其命名为mSk-NN。使用TF-IDF表示从文档中生成的可搜索索引首先用mSK NN加密，然后用名为FV[41]的SWHE方案加密。该方案的总体概念是使用余弦相似性比较度量来计算给定查询的k个最近邻居。作者声称，与只使用SWHE对查询进行加密的方法相比，使用mSK NN和SWHE的组合会产生更高效、更安全的系统。这是因为所需的计算量被最小化了。

刘等人在2022年[54]提出了一种基于索引的多关键字SE方案，该方案使用FHE来支持排名搜索，即检索与搜索查询最相关的前k个文档。文档本身使用对称加密方案（未指定）进行加密，而FHE方案用于加密索引和搜索查询。所使用的FHE是由同一作者开发的，并被命名为全同态保序加密（FHOPE）[80]。在加密数据上，这种加密方法提供了同态加法、同态乘法和阶数比较。因此，它被用于计算加密数据的相关性得分，并支持搜索操作。DO负责提取关键字，FHOPE对可搜索索引进行加密，并将其上传到该系统中的CS。CS在代表DU完成搜索操作和排名得分操作之后，将前k个最相关的文档返回给DU。

同年，Andola等人[57]提出了一个多用户SE系统，该系统支持多关键字搜索，并使用HE属性构建和搜索索引。该方案还允许使用TF-IDF实现的排序搜索。作者使用基于椭圆曲线的ElGamal[81]对索引进行加密，敏感数据的加密可以使用任何安全的对称加密算法进行。

4.3. Other Functionalities

In this section, we analyze the selected works that offer other functionalities, although they are not common. Specifically, we did not find any papers that use HE to provide the ability to “Authorize or Revoke” access, nor did we find any works addressing the “Delegate” functionality. As for the remaining functionalities, we have identified six approaches that are “Dynamic” and just one which uses HE to provide the “Verifiability” characteristic.

4.3.1. Dynamic

Even though dynamic SE schemes are more likely to be employed in real-world applications, not many works have been proposed to address this problem. In our research, we identified only five published studies that exploit the HE properties to develop dynamic SE schemes. There are, however, other schemes, which are dynamic, but they do not utilize the HE properties to achieve this functionality, as can be seen in Table 3.

Before 2021, three dynamic SE schemes that use HE to provide index updates were proposed, namely the TSED scheme proposed by Elizabeth et al. [71], a variant of this scheme, named VSED [63], and the TS-RDSE scheme proposed by Li et al. [64]. These schemes are designed for a single-user setting.

Prakash et al. proposed, in 2021 [59], a dynamic and index-based SE scheme, named PINDEX, which is intended for a multi-user setting. Their approach suggests a dynamic index construction method that is multi-linked, and which uses the PHE scheme proposed by Paillier, to encrypt the index, along with secret orthogonal vectors as building blocks. In this scheme, a DO can add and delete keywords or documents without having to reconstruct the encrypted index stored in the CS and the homomorphic properties are used on both the search and update processes.

Furthermore, the proposed scheme achieves forward privacy because of the probabilistic nature of the Paillier cryptosystem and the usage of secret orthogonal vectors. Notice that, in a dynamic SE scheme, forward privacy is a critical requirement since it ensures that newly added data does not reveal any information about previously searched queries. This is especially important in a multi-client setting where different users search different queries, and new data should not reveal anything about previous searches.

Gan et al. [55], in 2022, proposed a new dynamic searchable symmetric encryption scheme for multi-user settings, which uses XOR homomorphic function to ensure forward privacy.

The authors introduced two novel data structures to achieve efficient multi-user search and forward privacy: private links and a public search tree. Each client has three options, namely to search their own private link, the public search tree, or both. The proposed scheme also employs a state-based approach to manage database updates. This involves maintaining a state variable that tracks the current state of the database and allows for efficient updates without requiring its complete re-encryption. The XOR-homomorphic function is used in both the update and search processes. The documents themselves are encrypted using a symmetric cryptosystem.

4.3.2. Verifiability

There is only one paper which uses HE to provide the verifiability characteristic. In fact, only one more paper was found in our research which has this property, but does not use HE to achieve it, namely the work of Elizabeth and Prakash [63]. The former paper is due to Wu et al. and it was published in 2018 [72]. Their work presented a verifiable public key encryption scheme with keyword search meant for multi-user settings.

In this scheme, a standard proxy re-encryption public key algorithm is used to encrypt sensitive data. The authors also suggest a novel index construction, named Z-index, which uses a binary vector for each keyword to indicate whether each file contains that keyword. The index is constructed using an inverted data structure and is encrypted using an FHE scheme, namely DGHV [47], and a homomorphic hash function. The main objective of this scheme is to avoid using query trapdoors and therefore improve search efficiency. The verifiability feature is achieved using the homomorphic hash function.

5. Research Trends and Discussion

The research on SE schemes enhanced by HE properties has significantly increased in recent years. This trend aligns with the broader adoption of HE in various domains. In this section, we aim to provide an overview of the current trends in this research area as well as highlight their significant implications on the design of the studied approaches. Specifically, we will discuss the types of HE schemes used in SE, the application of HE in search structures, in search functionalities, and in other types of functionalities. Finally, we will also discuss the ability to allow multi-users, even though achieving this functionality does not directly rely on HE.

5.1. Types of HE Schemes Used in SE

The use of HE in SE schemes has increased in recent years. In fact, 74% of the 23 selected works were published within the last three years. This is consistent with the overall trend observed in the increased application of HE in diverse areas.

Our analysis revealed that PHE is the most frequently type of HE used in SE, as shown in Figure 3. This is not surprising since PHE is the simplest type of HE among the three. On the other hand, FHE schemes have the most potential, but they are still inefficient. However, despite this, a considerable percentage of SE schemes utilize FHE due to its potential benefits (38% use FHE for 57% of systems using PHE).

Mathematics 11 02948 g003 550

Figure 3. Types of HE schemes used in SE.

Finally, we also observed that more than a half of the schemes that rely on a PHE scheme use either the Paillier cryptosystem [52,59,64,65,69], a combination of the Paillier cryptosystem with GM [63,71], or the Paillier cryptosystem with threshold decryption [67]. The reason that so many approaches choose to use the Paillier cryptosystem (or any other variations) is the simplicity and security of the scheme, as well as the number of existing implementations freely available.

The remaining articles using PHE, use several different schemes, such as XOR- homomorphic [55], BCP [56], EC El Gamal [57], Boneh [61] and Shen et al. [70].

SWHE schemes were barely present in the studied schemes. In fact, only one article uses a SWHE scheme, more specifically an implementation of the FV scheme [60]. On the other hand, FHE schemes are used in nine articles, where the BGV [7,53,58,68] and BFV [66] are utilized the most, leveraging the open-source software library HElib, which implements some HE schemes. Table 4 lists the selected works and identifies the HE schemes they use.

Table 4. HE schemes used in selected SE approaches.

Table

5.2. HE Usage in Search Structures

The utilization of HE in SE schemes has been well explored to provide more efficient search structures. This applies to both sequential scan-based approaches and index-based ones. In all the papers that have been studied, HE is used to design the search structure of the respective scheme. It is worth mentioning that index-based SE schemes are predominant (see Figure 4), which is expected since most current applications require efficient search processes on large encrypted databases.

Mathematics 11 02948 g004 550

Figure 4. Use of HE on the Search structure.

5.3. HE Usage in Search Functionalities

The usage of HE to improve or allow for search functionalities is very prevalent in the selected works. There is, however, a functionality which is not present in none of the works, namely the ability to perform a fuzzy keyword search. Figure 5 illustrates the number of works that support each search functionality, considering the functionalities that appeared at least once.

Mathematics 11 02948 g005 550

Figure 5. Uses of HE on search functionalities.

From our analysis, we observed that ranked search is the most prevailing search functionality, being present in 10 out of the 23 analyzed works. Moreover, in all of those works, this functionality is achieved using the homomorphic properties of the underlying HE scheme. The most commonly used protocol involves ranking documents according to TF-IDF, where the information needed to compute relevance scores is encrypted using HE. Therefore, relevance scores can be computed in the public cloud. One of these schemes, FASE [54], which allows for multi-keyword queries, firstly ranks documents by keyword matching degree, i.e., how many queried keywords are present in the documents, then the secondary criteria are the respective relevance scores. Among all studied schemes, there is only one that uses a technique other than TF-IDF to rank their search results, namely the double score weighting formula (firstly proposed by Boucenna et al. [77] and used in the work of Boucenna et al. [68]).

Another important observation, now regarding schemes that allow for top-k results, is that the majority of these schemes do not allow it in a direct and single round of communication, i.e., most schemes either rely on PIR [60,67], or they include another entity in the framework, such as a coprocessor [63,71], a collaborate server [64] or a private cloud [62], which have access to the private key and are responsible for ranking search results.

Regarding the multiplicity of keywords, we observed that the majority of the works supports multi-keyword queries. There are, however, some articles that support only single-keyword queries [7,52,53,55,62]. Moreover, the ones that support multi-keyword queries can be further split into two categories: multi-keyword for ranked search and multi-keyword meant for conjunctive or disjunctive queries.

Some of the articles allow only for conjunctive queries [56,61,70,72], where the latter two also allow for phrase search, which basically is a conjunctive query where the order of keywords matters. Disjunctive queries are allowed in two of the studied works, namely the one published by Yin et al. [58] and the one by Yang et al. [65]. These approaches also allow conjunctive queries. Additionally, they allow for wildcards in each of the queried keywords, where the latter has a protocol to return the top-k results when the query performed is disjunctive. Besides the above-mentioned work [65], some other schemes allow for multi-keyword queries specifically for ranked search [54,57,60,63,64,67,68]. From all these papers, only the VSED scheme [63] has a slightly different approach on the ranking protocol. More specifically, before ranking the documents, it performs a disjunctive keyword search, to guarantee that every returned document has at least one queried keyword.

5.4. HE Usage in Other Functionalities

HE has also been explored to provide functionalities such as dynamic updates and verifiability. However, during our study, we did not find any work that mentioned the ability to delegate the search. Moreover, only two works allow the revocation of users, and they do not use HE for this purpose.

Among the properties within this category, “Dynamic” is the most frequent, and is always achieved using the properties of HE. Implementing dynamic updates is challenging, especially on index-based schemes, since they required some sort of index updates. Nonetheless, schemes that utilize HE to encrypt the index offer the advantage of performing computations directly on ciphertexts, thereby facilitating efficient index updates.

From the studied articles that allow for dynamic updates, half of them rely on an inverted index [63,64,71]. Hou et al. [61] uses a VBTree, which works as a tree index where the search is performed over keywords, similar to an inverted index. The work of Prakash et al. [59] relies on a novel index type called the multi-linked index.

Regarding the ability to update, most of the approaches allow only for updates of keywords over files. However, Prakash et al. [59] and Li et al. [64] also allow for dynamic updates of files, besides allowing for regular updates over keywords.

The capability to authorize or revoke users is crucial for ensuring data privacy, yet it is not commonly addressed in the selected articles. Only two of them incorporate this property [65,67], and neither of them exploits HE schemes to achieve this functionality. Both articles follow a similar protocol, involving the generation of a search token with an expiration date. Additionally, they allow users to query multiple DOs simultaneously by requesting an authorization token from all DOs at the same time.

5.5. Multiplicity of Users

The multiplicity of users is another property that we have analyzed in the selected works. Even though this property is not directly achieved using HE, we observed that schemes meant for the multi-user setting are the most common, with a total of 63% allowing this functionality (Figure 6). Nonetheless, there are a couple of papers that show different scenarios where single-user SE schemes are suitable. Malik et al. [52], presented an application where the single entity is an airport, and Iqbal et al. [53] presented a use case where both the DO and DU are the same hospital.

Mathematics 11 02948 g006 550

Figure 6. Multiplicity of users.

Regarding the schemes that are meant for a multi-user setting, the majority rely on user authorization [54,57,60,65,67,68,70,72]. Note also that Yang et al. [67] proposed a multi-user SE scheme that allows DUs to perform search queries over multiple DOs’ data at the same time. From the remaining schemes, it is worth highlighting the work of Gan et al. [55], which achieves the multi-user functionality by allowing users to search through a private link, a public search tree, or both.

6. Conclusions and Future Work

In this work, we have provided a comprehensive analysis of the research trends on searchable encryption (SE) schemes that utilize homomorphic encryption (HE). This analysis serves as a valuable tool for researchers, enabling them to gain insights into this specific area of research and make well-informed decisions regarding future research directions.

We focused our study on the types of HE schemes used, their application to enhance search structures, to allow several functionalities such as ranked, conjunctive, disjunctive, range, and phrase search, as well as verifiability, dynamic updates, and the ability to add and revoke users. This analysis was conducted on a carefully selected set of 23 works, following a well-defined research methodology.

Our findings revealed that HE usage in SE schemes has increased in recent years, with 75% of the selected works published within the last three years. The most commonly used type of HE schemes in SE is PHE, which accounted for the majority of the analyzed schemes. The popularity of PHE schemes, particularly the widespread adoption of Paillier’s cryptosystem, can be attributed to its simplicity, proven security properties, and availability in several open-source libraries, making it easily accessible for researchers.

When considering the usage of HE in search structures, we found that building the index using HE is the most prevalent approach. This is not surprising, since SE schemes that rely on sequential scans are not suitable for large databases. Additionally, we analyzed the types of indexes used in these schemes and observed that normal indexes are the most common choice, followed by inverted indexes and tree indexes.

Regarding the usage of HE in search functionalities, we found that ranked search is the most prevalent functionality. Relevance scores are computed using homomorphic properties and are often based on TF-IDF ranking. Multi-keyword queries are widely supported, either for ranked search or for conjunctive/disjunctive queries. However, fuzzy keyword search functionality was not found in any of the analyzed works.

In future research, there is a need to explore and improve upon various functionalities when searching over encrypted data using HE schemes. Although dynamic updates consistently take advantage of homomorphic properties, other functionalities such as authorizing and revoking users, verifiability, and delegation of search capability require further development. Among the analyzed works, only one study [72] utilized a HE scheme to achieve verifiability, while none of the articles addressed the ability to authorize and revoke users. However, we found two works that, although not employing HE schemes directly, utilized a cryptographic primitive called homomorphic message authentication to facilitate verifiability, namely the work of Zhang et al. [62], and the work of Wan et al. [82]. Furthermore, Zhang et al.’s work utilized this primitive to enable the authorization and revocation of users’ access. Therefore, considering the potential benefits and the limited exploration in this area, it is worth further exploring and investigating the utilization of homomorphic message authentication and similar cryptographic primitives for achieving verifiability, and the ability to add and revoke users.

Although FHE schemes were present in nearly half of the studied articles, we believe that the percentage could be significantly higher given the recent advancements in FHE schemes. For example, the TFHE scheme, introduced in 2020 [44], is an FHE scheme worth exploring. Leveraging other encryption schemes alongside HE, such as attribute-based encryption used for user access control (e.g., it is used in the work of Boucenna et al. [68]), or OPE for facilitating ciphertext comparison (e.g., it is used in FASE [54]), could lead to the development of more sophisticated schemes.

In our study, we also concluded that the studied articles cover several important search functionalities. However, there were some notable omissions, particularly in the areas of fuzzy keyword search and occurrence queries. Fuzzy keyword search is one of the most desirable functionalities in real-life applications, making it crucial to explore HE schemes that can support this functionality. One approach, as suggested by Dong et al. [83], involves using Hamming distances. Additionally, occurrence queries were not addressed in any of the studied schemes, but we observed that most articles allowing ranked searches could easily accommodate occurrence queries since they already require information such as TF to rank documents.

Finally, it is important for future research to focus on reducing the reliance on retrieval protocols like PIR. The emphasis should be on developing SE schemes that operate effectively with a minimum number of communication rounds, aiming to minimize the overall overhead.

Overall, our work provides a comprehensive summary of the latest research trends in SE enhanced by HE. We emphasize critical components related to the HE schemes most frequently employed, possible search structures, and search functionalities. This contribution significantly advances the scientific understanding in this domain, enabling researchers to explore state-of-the-art methodologies, leverage existing knowledge, and explore new research directions.

Author Contributions

Conceptualization, I.A. and I.C.; Data curation, I.A. and I.C.; Formal analysis, I.C.; Investigation, I.A. and I.C.; Methodology, I.A.; Visualization, I.C.; Project administration, I.A.; Supervision, I.A.; Validation, I.A.; Writing—original draft, I.A and I.C.; Writing—review and editing, I.A. and I.C. All authors have read and agreed to the published version of the manuscript.

Funding

This work was partially supported by the Norte Portugal Regional Operational Programme (NORTE 2020), under the PORTUGAL 2020 Partnership Agreement, through the European Regional Development Fund (ERDF), within project “Cybers SeC IP” (NORTE-01-0145-FEDER-000044).

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

All the data are already provided in the manuscript, with quoted reference.

Conflicts of Interest

The authors declare no conflict of interest.

Abbreviations

The following abbreviations are used in this manuscript:
AES Advanced encryption standard
CP-ABE Ciphertext-policy attribute-based encryption
CPA Chosen plaintext attack
CS Cloud server
DO Data owner
DU Data user
FHE Fully homomorphic encryption
FHOPE Fully homomorphic order-preserving encryption
FSDS Fully secure document similarity
GM Goldwasser–Micali
HE Homomorphic encryption
IoT Internet of Things
OPE Order-preserving encryption
PCTD Paillier cryptosystem with threshold decryption
PHE Partially homomorphic encryption
PIR Private information retrieval
RE Regular expression
𝑆𝐶�� Searchable ciphertext
SE Searchable encryption
SIIS Secure inverted index-based searchable encryption
SK-NN Secure K nearest neighbor
SWHE Somewhat homomorphic encryption
TF-IDF Term frequency inverse document frequency

References

  1. Suguna, M.; Ramalakshmi, M.; Cynthia, J.; Prakash, D. A Survey on Cloud and Internet of Things Based Healthcare Diagnosis. In Proceedings of the 2018 4th International Conference on Computing Communication and Automation (ICCCA), Greater Noida, India, 14–15 December 2018; pp. 1–4. [Google Scholar]
  2. Moumtzoglou, A.; Kastania, A.N.; Ghosh, R.; Papapanagiotou, I.; Boloor, K. A Survey on Research Initiatives for Healthcare Clouds. In Cloud Computing Applications for Quality Health Care Delivery; IGI Global: Hershey, PA, USA, 2014; pp. 1–18. [Google Scholar]
  3. Agrawal, S. A Survey on Recent Applications of Cloud Computing in Education: COVID-19 Perspective. J. Phys. Conf. Ser. 2021, 1828, 012076. [Google Scholar] [CrossRef]
  4. González-Martínez, J.A.; BoteLorenzo, M.L.; Gómez Sánchez, E.; Cano Parra, R. Cloud computing and education: A state-of-the-art survey. Comput. Educ. 2015, 80, 132–151. [Google Scholar] [CrossRef]
  5. Netwrix. Cloud Data Security Report; Technical Report; Netwrix: Frisco, TX, USA, 2022. [Google Scholar]
  6. Yang, P.; Xiong, N.N.; Ren, J. Data Security and Privacy Protection for Cloud Storage: A Survey. IEEE Access 2020, 8, 131723–131740. [Google Scholar] [CrossRef]
  7. Akavia, A.; Feldman, D.; Shaul, H. Secure Search on Encrypted Data via Multi-Ring Sketch. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, Toronto, ON, Canada, 15–19 October 2018; ACM: New York, NY, USA, 2018; pp. 985–1001. [Google Scholar]
  8. Xu, W.; Wang, B.; Lu, R.; Qu, Q.; Chen, Y.; Hu, Y.; Maglaras, L. Efficient Private Information Retrieval Protocol with Homomorphically Computing Univariate Polynomials. Sec. Commun. Netw. 2021, 2021, 5553256. [Google Scholar] [CrossRef]
  9. Sharma, D. Searchable encryption: A survey. Inf. Secur. J. 2023, 32, 76–119. [Google Scholar] [CrossRef]
  10. Acar, A.; Aksu, H.; Uluagac, A.; Conti, M. A survey on homomorphic encryption schemes: Theory and implementation. Acm Comput. Surv. 2018, 51, 1–35. [Google Scholar] [CrossRef]
  11. Choi, S.G.; Dachman-Soled, D.; Gordon, S.D.; Liu, L.; Yerukhimovich, A. Compressed Oblivious Encoding for Homomorphically Encrypted Search. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, CCS’21, Virtual, Republic of Korea, 15–19 November 2021; ACM: New York, NY, USA, 2021; pp. 2277–2291. [Google Scholar]
  12. Song, D.X.; Wagner, D.; Perrig, A. Practical techniques for searches on encrypted data. In Proceedings of the Proceeding 2000 IEEE Symposium on Security and Privacy, S&P 2000, Berkeley, CA, USA, 14–17 May 2000; pp. 44–55. [Google Scholar]
  13. Bösch, C.; Hartel, P.; Jonker, W.; Peter, A. A Survey of Provably Secure Searchable Encryption. Acm. Comput. Surv. 2014, 47, 18:1–18:51. [Google Scholar] [CrossRef]
  14. Wang, Y.; Wang, J.; Chen, X. Secure searchable encryption: A survey. J. Commun. Inf. Netw. 2016, 1, 52–65. [Google Scholar] [CrossRef][Green Version]
  15. Han, F.; Qin, J.; Hu, J. Secure searches in the cloud: A survey. Future Gener. Comput. Syst. 2016, 62, 66–75. [Google Scholar] [CrossRef]
  16. Dowsley, R.; Michalas, A.; Nagel, M.; Paladi, N. A survey on design and implementation of protected searchable data in the cloud. Comput. Sci. Rev. 2017, 26, 17–30. [Google Scholar] [CrossRef][Green Version]
  17. Poh, G.S.; Chin, J.J.; Yau, W.C.; Choo, K.K.R.; Mohamad, M.S. Searchable Symmetric Encryption: Designs and Challenges. Acm Comput. Surv. 2017, 50, 40:1–40:37. [Google Scholar] [CrossRef]
  18. Pham, H.; Woodworth, J.; Amini Salehi, M. Survey on secure search over encrypted data on the cloud. Concurr. Comput. Pract. Exp. 2019, 31, e5284. [Google Scholar] [CrossRef][Green Version]
  19. Handa, R.; Krishna, C.R.; Aggarwal, N. Searchable encryption: A survey on privacy-preserving search schemes on encrypted outsourced data. Concurr. Comput. Pract. Exp. 2019, 31, e5201. [Google Scholar] [CrossRef]
  20. Andola, N.; Gahlot, R.; Yadav, V.; Venkatesan, S.; Verma, S. Searchable encryption on the cloud: A survey. J. Supercomput. 2022, 78, 9952–9984. [Google Scholar] [CrossRef]
  21. Noorallahzade, M.; Alimoradi, R.; Gholami, A. A Survey on Public Key Encryption with Keyword Search: Taxonomy and Methods. Int. J. Math. Math. Sci. 2022, 2022, 3223509. [Google Scholar] [CrossRef]
  22. Zhang, R.; Xue, R.; Liu, L. Searchable Encryption for Healthcare Clouds: A Survey. IEEE Trans. Serv. Comput. 2018, 11, 978–996. [Google Scholar] [CrossRef]
  23. Bader, J.; Michala, A. Searchable Encryption with Access Control in Industrial Internet of Things (IIoT). Wirel. Commun. Mob. Comput. 2021, 2021, 5555362. [Google Scholar] [CrossRef]
  24. How, H.B.; Heng, S.H. Blockchain-Enabled Searchable Encryption in Clouds: A Review. J. Inf. Secur. Appl. 2022, 67, 103183. [Google Scholar] [CrossRef]
  25. Pillai, B.; Lal, N. Blockchain-based Asymmetric Searchable Encryption: A Comprehensive Survey. Int. J. Eng. Trends Technol. 2022, 70, 355–365. [Google Scholar] [CrossRef]
  26. Boneh, D.; Kushilevitz, E.; Ostrovsky, R.; Skeith, W.E. Public Key Encryption That Allows PIR Queries. In Advances in Cryptology—CRYPTO 2007, Proceedings of the 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, 19–23 August 2007; Menezes, A., Ed.; Lecture Notes in Computer Science; Springer: Berlin/Heidelberg, Gremany, 2007; pp. 50–67. [Google Scholar]
  27. Liu, J.; Zhao, B.; Qin, J.; Zhang, X.; Ma, J. Multi-Keyword Ranked Searchable Encryption with the Wildcard Keyword for Data Sharing in Cloud Computing. Comput. J. 2023, 66, 184–196. [Google Scholar] [CrossRef]
  28. Zheng, J.; Zhang, J.; Zhang, X.; Li, H. Symmetric searchable encryption scheme that supports phrase search. Microsyst. Technol. 2021, 27, 1721–1727. [Google Scholar] [CrossRef]
  29. Boneh, D.; Waters, B. Conjunctive, Subset, and Range Queries on Encrypted Data. In Theory of Cryptography, Proceedings of the Fourth Theory of Cryptography Conference, Amsterdam, The Netherlands, 21–24 February 2007; Vadhan, S.P., Ed.; Lecture Notes in Computer Science; Springer: Berlin/Heidelberg, Gremany, 2007; pp. 535–554. [Google Scholar]
  30. Rivest, R.L.; Adleman, L.; Dertouzos, M.L. On Data Banks and Privacy Homomorphisms. Found. Secur. Comput. Acad. Press 1978, 4, 169–179. [Google Scholar]
  31. Silva, I. Fully Homomorphic Encryption and Its Application to Private Search. Master’s Thesis, University of Porto, Porto, Portugal, 2022. [Google Scholar]
  32. Rivest, R.L.; Shamir, A.; Adleman, L. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 1978, 21, 120–126. [Google Scholar] [CrossRef][Green Version]
  33. Goldwasser, S.; Micali, S. Probabilistic encryption & how to play mental poker keeping secret all partial information. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, STOC’82, New York, NY, USA, 5–7 May 1982; pp. 365–377. [Google Scholar]
  34. Benaloh, J. Dense probabilistic encryption. In Proceedings of the Workshop on Selected Areas of Cryptography; Clarkson University: Potsdam, NY, USA, 1994; pp. 120–128. [Google Scholar]
  35. Naccache, D.; Stern, J. A new public key cryptosystem based on higher residues. In Proceedings of the 5th ACM Conference on Computer and Communications Security, San Francisco, CA, USA, 2–5 November 1998; pp. 59–66. [Google Scholar]
  36. Elgamal, T. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 1985, 31, 469–472. [Google Scholar] [CrossRef]
  37. Paillier, P. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In Proceedings of the Advances in Cryptology—EUROCRYPT ’99, Santa Barbara, CA, USA, 15–19 August 1999; Stern, J., Ed.; Lecture Notes in Computer Science. Springer: Berlin/Heidelberg, Germany, 1999; pp. 223–238. [Google Scholar]
  38. Boneh, D.; Goh, E.J.; Nissim, K. Evaluating 2-DNF Formulas on Ciphertexts. In Proceedings of the Theory of Cryptography; Kilian, J., Ed.; Lecture Notes in Computer Science. Springer: Berlin/Heidelberg, Germany, 2005; pp. 325–341. [Google Scholar]
  39. Gentry, C. A Fully Homomorphic Encryption Scheme. Ph.D. Thesis, Stanford University, Stanford, CA, USA, 2009. [Google Scholar]
  40. Marcolla, C.; Sucasas, V.; Manzano, M.; Bassoli, R.; Fitzek, F.; Aaraj, N.; Marcolla, C. Survey on Fully Homomorphic Encryption, Theory, and Applications. Proc. IEEE 2022, 110, 1572–1609. [Google Scholar] [CrossRef]
  41. Fan, J.; Vercauteren, F. Somewhat Practical Fully Homomorphic Encryption. Paper 2012/144. Cryptol. Eprint Arch. 2012, 2012, 144. [Google Scholar]
  42. Brakerski, Z.; Gentry, C.; Vaikuntanathan, V. (Leveled) fully homomorphic encryption without bootstrapping. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS’12, New York, NY, USA, 8–10 January 2012; pp. 309–325. [Google Scholar]
  43. Cheon, J.H.; Kim, A.; Kim, M.; Song, Y. Homomorphic Encryption for Arithmetic of Approximate Numbers. In Proceedings of the Advances in Cryptology—ASIACRYPT 2017; Takagi, T., Peyrin, T., Eds.; Lecture Notes in Computer Science. Springer: Cham, Switzerland, 2017; pp. 409–437. [Google Scholar]
  44. Chillotti, I.; Gama, N.; Georgieva, M.; Izabachène, M. TFHE: Fast Fully Homomorphic Encryption Over the Torus. J. Cryptol. 2020, 33, 34–91. [Google Scholar] [CrossRef]
  45. Scholl, P.; Smart, N.P. Improved Key Generation for Gentry’s Fully Homomorphic Encryption Scheme. In Proceedings of the Cryptography and Coding; Chen, L., Ed.; Lecture Notes in Computer Science. Springer: Berlin/Heidelberg, Germany, 2011; pp. 10–22. [Google Scholar]
  46. Gentry, C.; Halevi, S. Implementing Gentry’s Fully-Homomorphic Encryption Scheme. In Proceedings of the Advances in Cryptology—EUROCRYPT 2011; Paterson, K.G., Ed.; Lecture Notes in Computer Science. Springer: Berlin/ Heidelberg, Germany, 2011; pp. 129–148. [Google Scholar]
  47. van Dijk, M.; Gentry, C.; Halevi, S.; Vaikuntanathan, V. Fully Homomorphic Encryption over the Integers. In Proceedings of the Advances in Cryptology—EUROCRYPT 2010; Gilbert, H., Ed.; Lecture Notes in Computer Science. Springer: Berlin/ Heidelberg, Germany, 2010; pp. 24–43. [Google Scholar]
  48. Brakerski, Z.; Vaikuntanathan, V. Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages. In Proceedings of the Advances in Cryptology—CRYPTO 2011; Rogaway, P., Ed.; Lecture Notes in Computer Science. Springer: Berlin/ Heidelberg, Germany, 2011; pp. 505–524. [Google Scholar]
  49. López-Alt, A.; Tromer, E.; Vaikuntanathan, V. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, New York, NY, USA, 19–22 May 2012; pp. 1219–1234. [Google Scholar]
  50. Challa, R. Homomorphic Encryption: Review and Applications. Lect. Notes Data Eng. Commun. Technol. 2020, 37, 273–281. [Google Scholar]
  51. Alloghani, M.; Alani, M.M.; Al-Jumeily, D.; Baker, T.; Mustafina, J.; Hussain, A.; Aljaaf, A.J. A systematic review on the status and progress of homomorphic encryption technologies. J. Inf. Secur. Appl. 2019, 48, 102362. [Google Scholar] [CrossRef]
  52. Malik, H.; Tahir, S.; Tahir, H.; Ihtasham, M.; Khan, F. A homomorphic approach for security and privacy preservation of Smart Airports. Future Gener. Comput. Syst. 2023, 141, 500–513. [Google Scholar] [CrossRef]
  53. Iqbal, Y.; Tahir, S.; Tahir, H.; Khan, F.; Saeed, S.; Almuhaideb, A.M.; Syed, A.M. A Novel Homomorphic Approach for Preserving Privacy of Patient Data in Telemedicine. Sensors 2022, 22, 4432. [Google Scholar] [CrossRef] [PubMed]
  54. Liu, G.; Yang, G.; Bai, S.; Wang, H.; Xiang, Y. FASE: A Fast and Accurate Privacy-Preserving Multi-Keyword Top-k Retrieval Scheme Over Encrypted Cloud Data. IEEE Trans. Serv. Comput. 2022, 15, 1855–1867. [Google Scholar] [CrossRef]
  55. Gan, Q.; Wang, X.; Huang, D.; Li, J.; Zhou, D.; Wang, C. Towards Multi-Client Forward Private Searchable Symmetric Encryption in Cloud Computing. IEEE Trans. Serv. Comput. 2022, 15, 3566–3576. [Google Scholar] [CrossRef]
  56. Wang, Y.; Sun, S.F.; Wang, J.; Liu, J.K.; Chen, X. Achieving Searchable Encryption Scheme With Search Pattern Hidden. IEEE Trans. Serv. Comput. 2022, 15, 1012–1025. [Google Scholar] [CrossRef]
  57. Andola, N.; Prakash, S.; Yadav, V.K.; Venkatesan, S.; Verma, S. A secure searchable encryption scheme for cloud using hash-based indexing. J. Comput. Syst. Sci. 2022, 126, 119–137. [Google Scholar] [CrossRef]
  58. Yin, F.; Lu, R.; Zheng, Y.; Tang, X.; Jiang, Q. Achieve Efficient and Privacy-Preserving Compound Substring Query over Cloud. Sec. Commun. Netw. 2021, 2021, 7941233. [Google Scholar] [CrossRef]
  59. Prakash, A.J.; Elizabeth, B.L. Pindex: Private multi-linked index for encrypted document retrieval. PLoS ONE 2021, 16, e0256223. [Google Scholar] [CrossRef]
  60. Tosun, T.; Savaş, E. FSDS: A practical and fully secure document similarity search over encrypted data with lightweight client. J. Inf. Secur. Appl. 2021, 59, 102830. [Google Scholar] [CrossRef]
  61. Hou, J.; Liu, Y.; Hao, R. Privacy-Preserving Phrase Search over Encrypted Data. In Proceedings of the 4th International Conference on Big Data Technologies, ICBDT’21, Beijing, China, 26–28 May 2022; Association for Computing Machinery: New York, NY, USA, 2022; pp. 154–159. [Google Scholar]
  62. Zhang, J.; Shen, S.; Huang, D. A Secure Ranked Search Model Over Encrypted Data in Hybrid Cloud Computing. In Cyber Security, Proceedings of the 17th China Annual Conference, CNCERT 2020, Beijing, China, 12 August 2020; Lu, W., Wen, Q., Zhang, Y., Lang, B., Wen, W., Yan, H., Li, C., Ding, L., Li, R., Zhou, Y., Eds.; Springer: Singapore, 2020; pp. 29–36. [Google Scholar]
  63. Elizabeth, B.; Prakash, A. Verifiable top-k searchable encryption for cloud data. Sadhana-Acad. Proc. Eng. Sci. 2020, 45, 9. [Google Scholar] [CrossRef]
  64. Li, Y.; Zhou, F.; Xu, Z.; Ge, Y. An Efficient Two-Server Ranked Dynamic Searchable Encryption Scheme. IEEE Access 2020, 8, 86328–86344. [Google Scholar] [CrossRef]
  65. Yang, Y.; Liu, X.; Deng, R.H.; Weng, J. Flexible Wildcard Searchable Encryption System. IEEE Trans. Serv. Comput. 2020, 13, 464–477. [Google Scholar] [CrossRef]
  66. Wen, R.; Yu, Y.; Xie, X.; Zhang, Y. LEAF: A Faster Secure Search Algorithm via Localization, Extraction, and Reconstruction. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, CCS’20, New York, NY, USA, 9–13 November 2020; pp. 1219–1232. [Google Scholar]
  67. Yang, Y.; Liu, X.; Deng, R.H. Multi-User Multi-Keyword Rank Search Over Encrypted Data in Arbitrary Language. IEEE Trans. Dependable Secur. Comput. 2020, 17, 320–334. [Google Scholar] [CrossRef]
  68. Boucenna, F.; Nouali, O.; Kechid, S.; Tahar Kechadi, M. Secure Inverted Index Based Search over Encrypted Cloud Data with User Access Rights Management. J. Comput. Sci. Technol. 2019, 34, 133–154. [Google Scholar] [CrossRef]
  69. Guo, C.; Zhuang, R.; Jie, Y.; Choo, K.K.; Tang, X. Secure range search over encrypted uncertain IoT outsourced data. IEEE Internet Things J. 2019, 6, 1520–1529. [Google Scholar] [CrossRef]
  70. Shen, M.; Ma, B.; Zhu, L.; Du, X.; Xu, K. Secure phrase search for intelligent processing of encrypted data in cloud-based iot. IEEE Internet Things J. 2019, 6, 1998–2008. [Google Scholar] [CrossRef][Green Version]
  71. Elizabeth, B.; Prakash, A.; Uthariaraj, V. TSED: Top-k ranked searchable encryption for secure cloud data storage. Adv. Intell. Syst. Comput. 2018, 645, 113–121. [Google Scholar]
  72. Wu, D.; Gan, Q.; Wang, X. Verifiable Public Key Encryption with Keyword Search Based on Homomorphic Encryption in Multi-User Setting. IEEE Access 2018, 6, 42445–42453. [Google Scholar] [CrossRef]
  73. Halevi, S.; Shoup, V. Algorithms in HElib. In Advances in Cryptology—CRYPTO 2014, Proceedings of the 34th Annual Cryptology Conference, Santa Barbara, CA, USA, 17–21 August 2014; Garay, J.A., Gennaro, R., Eds.; Lecture Notes in Computer Science; Springer: Berlin/Heidelberg, Germany, 2014; pp. 554–571. [Google Scholar]
  74. Dworkin, M.; Barker, E.; Nechvatal, J.; Foti, J.; Bassham, L.; Roback, E.; Dray, J. Advanced Encryption Standard (AES); Federal Inf. Process. Stds. (NIST FIPS), National Institute of Standards and Technology: Gaithersburg, MD, USA, 2001.
  75. Bresson, E.; Catalano, D.; Pointcheval, D. A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications. In Advances in Cryptology—ASIACRYPT 2003, Proceedings of the 9th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, 30 November–4 December 2003; Laih, C.S., Ed.; Lecture Notes in Computer Science; Springer: Berlin/Heidelberg, Germany, 2003; pp. 37–54. [Google Scholar]
  76. Krawczyk, D.H.; Bellare, M.; Canetti, R. HMAC: Keyed-Hashing for Message Authentication; RFC 2104; RFC Editor: 1997.
  77. Boucenna, F.; Nouali, O.; Kechid, S. Concept-based Semantic Search over Encrypted Cloud Data. In Proceedings of the 12th International Conference on Web Information Systems and Technologies, Rome, Italy, 23–25 April 2016; pp. 235–242. [Google Scholar]
  78. Cao, N.; Wang, C.; Li, M.; Ren, K.; Lou, W. Privacy-Preserving Multi-Keyword Ranked Search over Encrypted Cloud Data. IEEE Trans. Parallel Distrib. Syst. 2014, 25, 222–233. [Google Scholar] [CrossRef][Green Version]
  79. Whissell, J.S.; Clarke, C.L.A. Improving document clustering using Okapi BM25 feature weighting. Inf. Retr. 2011, 14, 466–487. [Google Scholar] [CrossRef]
  80. Liu, G.; Yang, G.; Wang, H.; Xiang, Y.; Dai, H. A Novel Secure Scheme for Supporting Complex SQL Queries over Encrypted Databases in Cloud Computing. Secur. Commun. Netw. 2018, 2018, e7383514. [Google Scholar] [CrossRef]
  81. Menezes, A.J.; Vanstone, S.A.; Oorschot, P.C.V. Handbook of Applied Cryptography, 1st ed.; CRC Press, Inc.: Boca Raton, FL, USA, 1996. [Google Scholar]
  82. Wan, Z.; Deng, R. VPSearch: Achieving Verifiability for Privacy-Preserving Multi-Keyword Search over Encrypted Cloud Data. IEEE Trans. Dependable Secur. Comput. 2018, 15, 1083–1095. [Google Scholar] [CrossRef]
  83. Dong, Q.; Guan, Z.; Wu, L.; Chen, Z. Fuzzy keyword search over encrypted data in the public key setting. In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Springer: Berlin/Heidelberg, Germany, 2013; Volume 7923 LNCS, pp. 729–740. [Google Scholar]

参考:

原文地址
https://www.mdpi.com/2227-7390/11/13/2948
本文地址
https://architect.pub/leveraging-searchable-encryption-through-homomorphic-encryption-comprehensive-analysis

Tags

Article

微信

知识星球

微信公众号

视频号

↑