[type=editor, auid=000,bioid=1, orcid=0000-0001-6102-6165]

[1]

1]organization=PORTIC - Porto Research, Technology and Innovation Center,
Polytechnic Institute of Porto (IPP), postcode=4200-374, Porto,
country=Portugal

[style=chinese]

[cor1]Corresponding author

# Homomorphic Encryption: An Analysis of its Applications in Searchable
Encryption

Ivone Amorim<EMAIL_ADDRESS>[  Ivan Costa

###### Abstract

The widespread adoption of cloud infrastructures has revolutionized data
storage and access. However, it has also raised concerns regarding the privacy
of sensitive data stored in the cloud. To address these concerns, encryption
techniques have been widely used. However, traditional encryption schemes
limit the efficient search and retrieval of encrypted data. To tackle this
challenge, innovative approaches have emerged, such as the utilization of
Homomorphic Encryption (HE) in Searchable Encryption (SE) schemes. This paper
provides a comprehensive analysis of the advancements in HE-based privacy-
preserving techniques, focusing on their application in SE. The main
contributions of this work include the identification and classification of
existing SE schemes that utilize HE, a comprehensive analysis of the types of
HE used in SE, an examination of how HE shapes the search process structure
and enables additional functionalities, and the identification of promising
directions for future research in HE-based SE. The findings reveal the
increasing usage of HE in SE schemes, particularly Partially Homomorphic
Encryption. The analysis also highlights the prevalence of index-based SE
schemes using HE, the support for ranked search and multi-keyword queries, and
the need for further exploration in functionalities such as verifiability and
the ability to authorize and revoke users. Future research directions include
exploring the usage of other encryption schemes alongside HE, addressing
omissions in functionalities like fuzzy keyword search, and leveraging recent
advancements in Fully Homomorphic Encryption schemes.

###### keywords:

Searchable Encryption Homomorphic Encryption Secure Search Data Privacy
Keyword Search

##  1 Introduction

The rapid growth and widespread adoption of cloud infrastructures have
revolutionized the way we store and access information. From personal data
backup and file-sharing services like Dropbox and Google Drive to enterprise-
level data management and scalable infrastructure solutions, cloud storage has
had a profound impact on our day-to-day lives, particularly in sectors such as
Healthcare (Suguna et al. 2018; Moumtzoglou et al. 2014) and Education
(Agrawal 2021; González-Martínez et al. 2015). According to a report published
by Netwrix (2022), 80% of organizations store sensitive data in the cloud. The
advantages it offers include high data availability, convenient access from
anywhere, reduced infrastructure costs, unlimited storage space, and cost-
effectiveness (Yang et al. 2020a). However, with cloud adoption come
heightened security concerns as sensitive information entrusted to cloud
servers faces potential vulnerabilities, such as unauthorized access, data
breaches, and insider threats. Netwrix’s report (2022) also concluded that 55%
of healthcare organizations had experienced a third-party data breach in the
last 12 months, which was the second highest percentage of all industry
sectors, beaten only by the financial sector where 58% of companies had
experienced a third-party data breach. Both of these industry sectors rely
heavily on third parties, and those third parties have access to sensitive
data, which is of high value to cybercriminals. Moreover, their results show
that attacks have become more sophisticated and harder to spot. To address
these issues, ensuring the privacy of users’ sensitive data becomes crucial.
The most common way to achieve privacy is through encryption, where data is
encrypted before being stored in the cloud, providing end-to-end data privacy.
However, traditional encryption schemes pose challenges when it comes to
efficiently searching and retrieving data stored in encrypted form, limiting
the usability of encrypted storage solutions. Naive approaches, such as
downloading all ciphertexts, decrypting them, and searching on plaintexts, are
impractical. Therefore, to tackle these challenges, innovative concepts such
as Secure Search, Private Information Retrieval (PIR), and Searchable
Encryption (SE) have emerged. Secure search addresses the need to perform
search operations while maintaining the privacy and confidentiality of the
data (Akavia et al. 2018). PIR, closely related to secure search, enables
users to retrieve specific data from a database without revealing which items
they are accessing (Xu et al. 2021). SE, on the other hand, is a cryptographic
technique that allows for secure and efficient search operations over
encrypted data (Sharma 2023). It is important to note that the terms “Secure
Search” and “Searchable Encryption” are sometimes used interchangeably,
blurring the distinction between the two concepts. In practice, the boundaries
between these terms can be fluid, with different researchers and practitioners
using them to refer to related techniques and mechanisms. Additionally, PIR is
often considered a component within secure search or SE approaches, as it
enables private data retrieval from a database. In this work, we mainly use
the term “Searchable Encryption” while “Secure Search” is used whenever we
feel a distinction is needed.

Within the realm of SE, one notable approach is the utilization of Homomorphic
Encryption (HE). HE is a special type of encryption that allows computation on
encrypted data without decryption (Acar et al. 2018). This property makes it
well-suited for privacy-preserving techniques, enabling search operations
directly on encrypted data while maintaining confidentiality. Researchers have
increasingly focused on this approach, as it offers an attractive framework
for secure search without requiring costly setup procedures (Choi et al.
2021). Numerous approaches have been proposed that leverage the homomorphic
properties to provide privacy-preserving techniques, particularly in the
context of Searchable Encryption. However, there is a lack of dedicated
studies analysing the advancements in this area. On the other hand, it is
crucial for the scientific community to gain a comprehensive understanding of
the current state-of-the-art and identify promising directions for further
exploration in this subject.

In this work, we aim to provide a comprehensive analysis of the advancements
in HE-based privacy-preserving techniques, specifically focusing on their
application in SE.

###  1.1 Related Work

Since the publication of the first work on SE, due to Song et al. (2000),
several surveys and review papers have been proposed on this topic, which
highlights the growing importance of secure data management in a world where
the majority of data is stored in third-party cloud services.

Bösch et al. (2014) presented the first survey on SE. In this work, a
comprehensive discussion is given with respect to the number of writers and
readers supported by each scheme. The authors consider four different cases
are considered: single-writer/single-reader, multi-writer/single-reader,
single-writer/multi-reader, and multi-writer/multi-reader. The schemes are
organized based on their query expressiveness, and a comparative analysis is
made in terms of efficiency and security. Wang et al. (2016) and Han et al.
(2016) published two new systematic surveys on SE. The former gives a broader
view of the existing SE schemes based on their usage in symmetric or
asymmetric key settings, while the latter categorizes the systems according to
three aspects: security requirements, search functionalities, and deployment
model. Moreover, as stated by the authors, the latter also introduces a new
deployment model which was not covered in the work of Bösch et al. (2014),
called the Server-User model, in which the cloud server is the owner of the
data and acts as both the data owner and storage server.

In later years, other works have been published that provided reviews on
existing and new SE methods (Dowsley et al. 2017, Poh et al. 2017, Pham et al.
2019, Handa et al. 2019).

More recently, Andola et al. (2022a) published a comprehensive review paper
that focuses on analysing the features and limitations of these techniques
based on their performance and robustness against various types of attacks.
One of the key aspects of this work is the in-depth analysis of each technique
and the cryptographic basis that determines their efficiency. Also in the same
year, Noorallahzade et al. (2022) published a complete classification of SE
schemes based on a comprehensive set of metrics, including search type, index
type, results type, security models, type of implementation, the multiplicity
of users, cryptographic primitives and technique used. For each category, the
available schemes were compared and evaluated. Sharma (2023) provided a
comprehensive guide on SE for non-security experts. The main goal of this work
was to help general practitioners select the most suitable SE scheme for their
specific needs by presenting a survey that details the existing schemes based
on five key characteristics: key structure, search structure, search
functionality, support for readers/writers and reader capability. Both
Symmetric and Asymmetric SE schemes are discussed. It also presents a
comparative analysis, which may assist non-security experts in making informed
decisions about their encryption needs.

Over the years, other works have been published that survey the application of
SE in different contexts. For example, Zhang et al. (2018) discussed the use
of SE in healthcare systems, while Bader and Michala (2021) focused on its
application in the industrial Internet of Things (IoT). Other works have also
analysed how new technologies such as Blockchain are being used to enhance the
potential of SE mechanisms (How and Heng 2022, Pillai and Lal 2022). However,
no study is devoted to the use of HE in secure search mechanisms. In this
context, our main objective is to survey SE techniques that incorporate HE
into their design, while also providing a comprehensive analysis of how HE is
used and what benefits it brings.

###  1.2 Main Contributions

The main contributions of our work are:

  1. 1.

To identify and classify existing SE utilizing HE. Our analysis covers several
aspects of these systems, including the encryption techniques used, the
structure of the search process (sequential scan or index-based), and the
search capabilities offered (such as the ability to handle multiple keywords,
regular expressions, wildcards, phrases, ranges, occurrences, and fuzzy
keywords). Additionally, we study other functionalities like authorization and
access revocation, static and dynamic approaches to SE, and correctness
verification.

  2. 2.

To conduct an extensive analysis of the most common types of HE used in SE
schemes, focusing our analysis on the identification of whether the schemes
employed fall under the categories of Partially Homomorphic Encryption,
Somewhat Homomorphic Encryption, or Fully Homomorphic Encryption. Furthermore,
we explicitly identify the HE schemes whenever possible.

  3. 3.

To examine how HE is used to achieve the different properties and
characteristics within SE, building upon the categorization mentioned earlier.
Specifically, we investigate how HE shapes the search process structure,
enhances search capabilities, and enables additional functionalities in SE.

  4. 4.

To identify promising directions for future research and development in HE-
based SE schemes, aiming to deliver more flexible and advanced solutions for
SE.

###  1.3 Research Methodology

To perform a comprehensive analysis of the application of HE in SE, a
systematic approach was adopted. This approach involved searching several
academic databases, including Elsevier ScienceDirect, Scopus, ACM Digital
Library, IEEE Xplore, and Web of Science.

To conduct the search in the previously mentioned databases, a list of
keywords was identified after thoroughly reviewing the main literature on this
area. The listed databases were searched for works that included at least one
keyword related to SE and one related to HE in their title, abstract, or set
of keywords. Keywords related to SE included “searchable”, “secure search” and
“keyword search”. Keywords related to HE included “homomorphic” and
“encrypted”.

After conducting an initial search, a screening process was performed to
select only publications that met the following criteria: they were written in
English, published in peer-reviewed journals or conferences after 2016, and
focused on secure search methods or SE schemes that leverage the properties of
HE in the search process.

The search was conducted in February 2023 and 290 distinct papers were
identified. Out of these, 23 were determined to meet the established inclusion
criteria.

###  1.4 Organization

This paper is organized as follows: Section 2 introduces the main actors and
processes involved in SE schemes, as well as how they can be characterized in
terms of Search Structure, Search Functionalities, Multiplicity of users, and
Other functionalities. The definition of HE schemes, the main existing types,
and approaches are presented in Section 3. The comprehensive analysis of the
selected works is presented in Section 4, while the discussion of the research
trends is covered in Section 5. Finally, in Section 6 section, we provide our
conclusions and suggest research directions.

##  2 Searchable Encryption

SE refers to a cryptographic technique that enables searching over encrypted
data without the need to decrypt it. There are two main categories of SE
techniques based on the underlying encryption process: symmetric and
asymmetric. Similarly to conventional symmetric encryption schemes, symmetric
SE techniques typically use the same key for encryption and decryption, while
in asymmetric SE schemes, a pair of keys is used - one for encryption and one
for decryption.

Figure 1 depicts a high-level architecture of a generic cloud-based SE system
which is usually composed of three main entities, as follows:

  * •

Data Owner (DO) The data owner (sometimes referred to as “client” in relevant
literature, Sharma 2023) is the entity responsible for encrypting the data and
outsourcing it to the cloud server. Generally, the DO is the producer of the
data and has legitimate control and ownership over it. However, in some
scenarios, another entity, known as the data provider, may be responsible for
generating the data. The SE methods that use indices to aid in the search
process, also known as index-based SE schemes, typically require the data
provider (whether it is the data owner or not) to encrypt the index and share
it with the cloud.

  * •

Data User (DU) A data user represents an entity that wishes to search over the
DO’s encrypted data. Ideally, it is able to perform the search only if
previously authorized by the DO. The DU is, therefore, responsible for sending
a search request to the cloud server which, after processing the request,
returns the results. It is worth noting that, in some systems, the DO can also
act as a DU.

  * •

Cloud Server (CS) The cloud server is the entity responsible for securely
storing the encrypted data and providing a SE service to authorized DUs. It
receives the encrypted documents uploaded by the DO and carries out three main
tasks: storing the data, searching the data, and maintaining the search data
structures updated. The way the CS performs the search depends on the SE
scheme being used. In the case of an index-based SE, the cloud server performs
the search by comparing the search request with the secure index, and it then
sends the results to the authorized DU. However, for SE schemes that are not
index-based, the process of searching the encrypted data usually requires
scanning the whole document, as will be discussed later in this chapter.

Figure 1: Conceptual overview of a cloud-based SE system.

The architecture of a SE system usually includes four processes involving the
previously described entities. The specific algorithms used in each step may
differ based on the specific design and requirements of the SE scheme.

The following description of each process has been made as broad as possible,
taking into account various factors such as whether an index-based search
mechanism is present or not, and whether it is a symmetric or asymmetric SE
scheme.

  1. 1.

Setup() Based on an input security parameter $\lambda$, the algorithm
generates various system parameters $P$ as well as the necessary keys $K$. In
asymmetric SE, a public and a private key are generated, while in symmetric
SE, only a single key is needed. This algorithm is usually executed by the
system owner.

  2. 2.

Encryption() An encryption algorithm encrypts the data using the key(s)
generated in the previous process K, and it outputs a message $M^{\prime}$
obtained by encrypting the original data $M$ using an encryption algorithm
$E$.

If the SE is index-based, this algorithm will also use the input key(s) $K$ to
encrypt an input set of keywords $W$, which may be used to generate an Index
$I$ of encrypted keywords. Then, the DO uses this algorithm to construct a
Searchable Ciphertext ($SC$) by associating the encrypted Index $I$ with the
encrypted message $M^{\prime}$. The SC can then be uploaded to the cloud
server.

If the SE method is scan-based (meaning that the server will scan the
encrypted data directly), the previous step can be skipped, and the message
$M^{\prime}$ can be stored directly on the cloud server without generating an
SC.

  3. 3.

TokenGen() This algorithm, sometimes also called Trapdoor, is used by
authorized users to generate search queries. It takes an input encryption key
$K$ and an input query $Q={k_{1},k_{2},...,k_{m}}$ and generates a search
token $T_{Q}$. The specific implementation of the algorithm depends on whether
the SE scheme is index-based or scan-based. For an index-based scheme, the
algorithm encrypts each keyword in the query $Q$ using the encryption key(s)
$K$ and generates an index
$I={w_{1}^{\prime},w_{2}^{\prime},...,w_{m}^{\prime}}$ of encrypted keywords.
The search token $T_{Q}$ is then constructed from $I$. For a scan-based
scheme, the algorithm generates a scan token $T_{S}$. The search token $T_{Q}$
is then constructed from the chosen search query $Q$ and the scan token
$T_{S}$. Once constructed, the search token $T_{Q}$ is sent to the server,
which uses it to search for relevant data in the encrypted database.

Depending on the scenario, the query may only be performed by the DU.

  4. 4.

Search() The search algorithm is used by the CS to search the encrypted data
for matches to a search query. In an index-based scheme, the search algorithm
applies the search token $T_{Q}$ onto the searchable ciphertext $SC$ to
identify the set of encrypted keywords, and corresponding indices, that match
the query. Then, it retrieves the corresponding encrypted data to the DU. In a
scan-based scheme, the search algorithm applies the search token $T_{Q}$ and
the scan token $T_{s}$ onto the encrypted data to identify the set of
searchable data segments having keywords matched with the keywords of the
search query. Once the matches are found, the server sends the search result
to the Data User.

###  2.1 Characterization of a SE scheme

SE schemes can be categorized in various ways, and there are several
categorizations of SE schemes in the literature. For example, Han et al.
(2016) categorized SE systems based on three aspects: security requirements,
search functionalities, and deployment model. Noorallahzade et al. (2022)
presented a more comprehensive categorization by considering additional
aspects such as search type, index type, results type, security models, type
of implementation, multiplicity of users, cryptographic primitives and
technique used. Sharma (2023) detailed existing SE schemes based on five key
characteristics: key structure, search structure, search functionality,
support for readers/writers, and reader capability.

In our work, we will consider a categorization of SE schemes that includes
four categories: Search Structure, Multiplicity of Users, Search
Functionalities, and Other Functionalities. By using this categorization, we
then analyse each scheme and identify which category it belongs to, allowing
us to make a proper analysis of the features that are most common in SE
schemes that use HE.

The categorization we will use is represented in Figure 2, and each category
is described in detail in the following sections for clarification.

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

####  2.1.1 Search Structure

An important aspect of a SE scheme is the search structure used to perform
searches over the encrypted data, since it may significantly impact the
scheme’s efficiency. Historically, the first scheme, due to Song et al.
(2000), used what is called a sequential scan search structure. This search
operation involves sequentially scanning through all the encrypted documents
in the database to find those that match the search query. Although other
works in the sequential scan category have been published, such as the one by
Boneh et al. (2007) on public encryption with keyword search, there are not
many prominent research works that follow this approach (Pham et al. 2019).
This is due to the fact that these techniques are very inefficient and are not
well-suited for large databases or frequent search queries, as the search
operation can become very time-consuming and computationally expensive.
Moreover, this search method is prone to exposing sensitive information to the
server, which compromises the privacy and security of the data (Andola et al.
2022a). A potential advantage of sequential scan-based SE schemes is that they
can provide a simple and straightforward way to search over encrypted data
without the need for complex indexing or search structures.

Another type of search structure commonly used in SE schemes to improve search
performance is the index-based search structure. In this approach, a special
data structure, called Index, is associated with the encrypted documents. This
new data structure makes possible to compare the search query with the entries
in the index, instead of searching the contents of all the documents in the
database. Also, using indexes provides support for working with files of
different formats, including compressed and encrypted files, as well as
multimedia files (Handa et al. 2019). Nevertheless, with this method, the DO
needs to send to the cloud server the encrypted data as well as the encrypted
index. These two sets of information can be encrypted with the same encryption
scheme, or we can use a SE scheme to encrypt the index and another reliable
encryption scheme to encrypt the sensitive data. There are mainly three types
of index of keywords: simple index, inverted index, and tree index.

  * •

Simple index In systems where this approach is used, it is created an index
for each document before encrypting and uploading it to the cloud server. The
index consists of keywords that are considered relevant to that document. This
kind of index is suitable for applications where a small number of documents
with a specific value for each keyword field are required to be uploaded to
the CS (Sharma 2023).

  * •

Inverted index The term inverted-index comes from the process of building the
index backwards. This is because, instead of associating each document with a
set of keywords, the index is created by coupling each keyword with the set of
documents where it appears. This approach significantly reduces the time
required for searching, making it the most suitable search structure for
applications that involve uploading a large number of documents to the cloud
server (Sharma 2023).

  * •

Tree index A tree index is also a very efficient method to optimize the search
process. While there are various approaches to building a tree index, the
basic idea is to create a tree-like structure containing the searchable
keywords, by dividing the set of keywords into smaller sets. When a DU
searches for a specific keyword, the CS will search the index-tree, starting
at the root and traversing every relevant node until a match is found.

Compared to sequential scan approaches, index-based schemes are highly
efficient, reducing the comparisons per file from $O(n)$ to $O(1)$. However, a
drawback is the fact that the keywords that can be used in the query are
limited to those that were extracted during index generation (Handa et al.
2019).

####  2.1.2 Multiplicity of Users

SE schemes allow DOs to securely outsource data storage and DUs to retrieve
data based on specific search criteria. Based on the multiplicity of users
involved, we further classify these schemes as single-user, if the DO assumes
the role of DU, and multi-user if the DU is different from the DO.

####  2.1.3 Search Functionalities

The search functionalities of a SE scheme, as the name suggests, determine the
kind of queries which can be performed, the filtering and sorting options and
other tools that help data users to refine their search. In this work, and
following a categorization similar to Sharma (2023), we distinguish between
search functionalities directly associated with the number of keywords and
others. The set of functionalities not directly linked with the number of
keywords is referred to as “Miscellaneous” (Figure 2).

Regarding the number of keywords, a SE scheme can be categorized either as
Single or Multi-Keyword. In a Single-Keyword SE scheme, the DU is allowed to
include just one search term in each query. Consequently, if he/she wants to
search for multiple terms using this type of scheme, then he/she needs to
perform multiple queries, one for each search term (Handa et al. 2019). In a
Multi-Keyword SE scheme, the user is allowed to perform a search with more
than one search term in each query. However, it is important to mention that
just because multiple keywords are supported, it does not necessarily imply
that users can perform searches with an unlimited number of keywords. Some
schemes may be restricted to a specific number of keywords. Furthermore, in a
multi-keyword SE scheme, a query can be represented as a simple list of search
terms, as a conjunctive query (using the AND relation), or as a disjunctive
query (using the OR relation). Depending on the representation of the query,
the multi-keyword SE can be categorized as a Conjunctive Keyword SE or
Disjunctive Keyword SE.

Besides the characterization regarding the number of keywords, the existing SE
schemes can also be categorized based on miscellaneous functionalities. In
this work, we consider the following: Regular Expressions and Wildcards, Fuzzy
keyword search, Phrase search, Range search, Occurrence search, and Ranked
search.

Regular expressions and wildcards

SE schemes that allow regular expression or wildcard based search queries are
very useful when the DUs know the specific patterns of the keywords that they
want to search for in the documents. In both cases, the query can be
constructed using special characters to describe the keyword(s) pattern.

If a SE scheme allows wildcard queries, then the DUs can replace a single
character in the search query with a symbol known as a wildcard. Generally,
two types of wildcards are used: “?” and “*”, the former representing a single
character and being called a single-character wildcard, while the latter can
represent any number of characters and is called a multi-character wildcard
(Liu et al. 2023). In case a regular expression-based SE scheme is used, a
combination of special characters and operators can be employed to describe
more complex patterns in search queries than those allowed by wildcards. While
regular expressions provide greater flexibility, wildcard-based SE schemes are
a simpler alternative when searching for keywords with minor variations.

Fuzzy keyword search

A typical SE scheme, even when it allows wildcard or regular expression-based
search queries, can only search for exact matches of keywords in ciphertexts.
It does not allow any typos or inconsistencies in the format of the searched
term(s). However, this limitation can be addressed by incorporating the Fuzzy
Keyword Search functionality into the SE scheme. With this feature, the scheme
is able to search for results related to the correct spell word even if the
data users have misspelled it during their search (Handa et al. 2019).

Phrase search

Often, DUs are interested to find specific phrases instead of just individual
keywords. Even though this can be achieved using SE schemes that allow for
conjunctive search queries, this requires the DUs to perform several
additional steps. First, they need to convert the phrase into a conjunctive
query and perform the search. Then, after obtaining the corresponding
documents from the CS, they have to decrypt and screen them to find the ones
that contain the phrase they are looking for (Zheng et al. 2021). As a
consequence, this approach can be very inefficient when dealing with large
databases. SE schemes with Phrase Search functionality, on the other hand,
enable data users to directly search for phrases (Sharma 2023).

Range search
SE schemes allowing range queries enable DUs to search for encrypted data
within a specific range of values, meaning that they can perform searches
based on an interval rather than just on exact matches. For instance, a data
user may want to search for all documents in a database that were created
between 2020 and 2022 or search for documents whose owners have more than 30
years old. In fact, the last example mentioned belongs to a specific
subcategory of range queries called comparison queries (Boneh and Waters
2007). This kind of search query can be very useful to avoid multiple single-
keyword searches.

Occurrence search
SE schemes with this property allow a data user to issue a query to the cloud
server that includes both a search term and a value. This value specifies the
minimum number of times that the chosen keyword must appear in a document for
it to be retrieved in the search results. This feature can be very helpful to
measure the importance of our keyword within each document in the database
(Handa et al. 2019).

Ranked search
This feature’s main purpose is to enhance the data user’s search experience by
retrieving only relevant documents that match the query. To achieve this,
various scoring functions have been adopted from the information retrieval
research community, Handa et al. (2019). The most frequently used scoring
function is known as TF-IDF, where TF stands for Term Frequency, indicating
the significance of that keyword in the document, and IDF stands for Inverted
Document Frequency. indicating the significance of the keyword over all
documents in the database (Pham et al. 2019).

####  2.1.4 Other Functionalities

There are other functionalities that SE schemes may have and are important for
some scenarios. For example, regarding access control functionalities, the
ability to authorize and revoke DUs is crucial.

Authorize and Revoke users
As the name indicates, this feature in a SE scheme means that the data owner
can grant new users search capability as well as revoke this ability. There
are not many SE schemes with this functionality, and the ones that exist are
inefficient and impractical. This is because enabling this functionality
requires compromising security (Andola et al. 2022a).

Static or Dynamic
Another important functionality in a SE scheme for real-world applications is
the ability to allow dynamic updates. A SE scheme is considered static if no
document is added, deleted, or updated after building the encrypted database.
Therefore, the entire set of data has to be available before data encryption.
In contrast, a SE system is said to be dynamic if users can modify, add, or
delete documents without compromising the security of the encrypted data or
the ability to search and retrieve it. Dynamic SE schemes are more flexible
and more suitable for real-world applications. However, static SE schemes are
typically more efficient and less complicated to implement than dynamic ones,
making them a better option for simple scenarios where the data is relatively
stable, and no frequent updates are needed. It is important to notice that, in
a dynamic and index-based SE scheme, the index must be updated efficiently
when a change is made to the document collection, and this has to be done
without adding any leakage (Handa et al. 2019).

Verifiability
In most applications, the CS in a SE system is considered semi-trusted,
meaning it may retrieve incomplete or incorrect results to the DU (Handa et
al. 2019). Therefore, it is important for a SE scheme to allow the DU to
verify the search results retrieved by the CS. Such a SE scheme is designated
as a verifiable SE scheme. As would be expected, this kind of scheme would
suffer from higher computational overhead on all sites (at DO, at DU, and at
the CS) when compared to a SE scheme not allowing verifiability (Sharma 2023).
Result verification may include: correctness (if the results retrieved
correspond to the query); completeness, if all the relevant documents are
retrieved; and freshness if the latest version of the documents is returned to
the DU (Handa et al. 2019).

Delegate
This functionality allows an authorized user to delegate the search capability
to another user. This functionality mainly appears in asymmetric SE schemes,
sometimes referred to as Public Key Encryption with Keyword Search. These SE
schemes include proxy re-encryption, that is, they have a semi-trusted third-
party server (proxy server) that converts a ciphertext created using the DO’s
public key into a ciphertext that can be decrypted by the delegated user
(Sharma 2023). Although this is not a very common type of SE, there are
already several works addressing this feature (Noorallahzade et al. 2022).

##  3 Homomorphic Encryption

The main idea behind a HE scheme is to allow computations to be performed over
encrypted data without the need to decrypt it first. This concept was
introduced by Rivest et al. (1978a) and was originally called “privacy
homomorphism”. A HE scheme is, therefore, any encryption scheme where the
encryption function is a homomorphism. Formally speaking, let $M$ denote the
set of plaintexts and $C$ the set of ciphertexts. Let $\odot_{M}$ and
$\odot_{C}$ be operations in $M$ and $C$, respectively. An encryption scheme
is said to be Homomorphic if for any encryption key $k$, the encryption
function $E$ satisfies the property below,

$\forall m_{1},m_{2}\in M,E(m_{1}\odot_{M}m_{2})\leftarrow
E(m_{1})\odot_{C}E(m_{2}),$ (1)

where $\leftarrow$ means “can be directly obtained from”. That is, in (1),
$E(m_{1}\odot_{M}m_{2})$ can be directly obtained from
$E(m_{1})\odot_{C}E(m_{2})$ without having to perform any decryption.

HE schemes can be divided into three categories depending on the type and
number of operations allowed by the system: Partially Homomorphic Encryption
(PHE), Somewhat Homomorphic Encryption (SWHE), and Fully Homomorphic
Encryption (FHE).

###  3.1 Partially Homomorphic Encryption

After the publication of Rivest et al.’s work, Cryptography researchers began
searching for a homomorphic encryption scheme that allowed computations on
encrypted data using more than one operation. However, over the next two
decades, most attempts resulted in schemes that only allowed one type of
operation, which are the ones known as PHE schemes. In these schemes, the
homomorphic property is only satisfied by one operation, such as addition or
multiplication, an unlimited number of times.

One example of a PHE scheme is the well-known RSA public key cryptosystem,
introduced by Rivest et al. (1978b). It only supports the usual product
operation and is deterministic, meaning that using the same key to encrypt the
same plaintext will always result in the same ciphertext.

Some years later, in 1982, Goldwasser and Micali published the first
probabilistic PHE scheme which inspired most of the PHE schemes published in
the following decades, such as Benaloh (1994), which was a generalization of
Goldwasser et al.’s scheme, and Naccache and Stern (1998) which was an
improvement on Benaloh’s scheme.

Elgamal (1985) introduced a PHE which also allows only the usual product, and,
Paillier (1999) published a PHE which allows only the usual sum. This latter
scheme is the most frequently used in SE schemes that use HE, as will be seen
in Section 5 section.

###  3.2 Somewhat Homomorphic Encryption

In 2005, Boneh et al. (2005) proposed the first HE scheme capable of
performing two operations: an arbitrary number of additions and just one
multiplication, followed by an arbitrary number of additions. These are the
kind of HE schemes that are called SWHE, since the homomorphic property is
satisfied by more than an operation but a limited number of times.

SWHE schemes were proposed shortly after the first HE scheme. However, they
were not as appealing as PHE, due to their limitations. Nonetheless, towards
the end of the century, they became much more complete, serving as a stepping
stone to achieving a FHE scheme, that is, a HE scheme that allows for more
than one operation an unlimited number of times. In fact, many researchers
believe that the scheme of Boneh et al. (2005) was an important stepping stone
towards an FHE scheme.

###  3.3 Fully Homomorphic Encryption

In these type of HE schemes, the homomorphic property is satisfied by a set of
operations an unlimited amount of times.

This category is considered by many as the “Holy Grail” of Cryptography, since
it allows computations to be performed freely over encrypted data. It was in
2009 that Gentry published the first FHE scheme. In his thesis, Gentry not
only proposed an FHE scheme but also provided a method for constructing a
general FHE scheme from a scheme with limited but sufficient homomorphic
evaluation capacity (Marcolla et al. 2022). Since then, HE has triggered
significant interest, and novel constructions on FHE have been proposed
following Gentry’s idea, being BGV (Brakerski et al. 2012), FV (Fan and
Vercauteren 2012), TFHE (Chillotti et al. 2020), and CKKS (Cheon et al. 2017)
the most representative.

A security liability that is common among HE schemes is the accumulation of
encryptions of $0$, i.e., if an attacker is able to accumulate enough
encryptions of $0$ then the security of the scheme might be at risk. To
overcome this problem, many schemes disguise encryptions of $0$ with what is
called _noise_. However, this noise tends to increase with the number of
computations performed, which may lead to incorrect decryption in the end.
Gentry introduced the main idea of bootstrapping to solve this problem.
However, bootstrapping is computationally expensive, and its complex
mathematical foundations make Gentry’s scheme not practical for real-life
scenarios.

According to Acar et al. (2018), there are four main categories of FHE schemes
that have been developed since Gentry’s work in 2009:

  * •

Ideal Lattices - In this category there are essentially optimizations of
Gentry’s scheme. Examples of this category include the work of Gentry and
Halevi (2011) and the work of Scholl and Smart (2011).

  * •

Integers - First appearance in 2010, by van Dijk et al. (2010). The main
motivation behind these schemes its the simplicity of the concept, however
they are not practical, which makes this the least favorite category for
researchers;

  * •

(Rings) Learning With Error, (R)LWE - It was originated in 2011, by Brakerski
and Vaikuntanathan. These schemes are based on the LWE problem, which is
considered one of the hardest problems to solve in practical time, even for
post-quantum algorithms. RLWE is an algebraic variant of LWE, which is more
efficient for applications;

  * •

$N^{th}$ degree-truncated polynomial ring unit - Like FHE schemes, which are
known for their efficiency and use of Multi-Key FHE, these schemes allow
computations between data encrypted with distinct keys. An HE scheme of this
type was first proposed by López-Alt et al. (2012).

Due to its huge potential for cryptographic applications, HE schemes have
already been proposed to solve a wide range of problems in several areas,
including in Big Data and Cloud Computing, Secure Image Processing, Medical
applications, Electronic Voting Systems, Private Information Retrieval, and
Biometric Verifications, as referred by Challa (2020) and Alloghani et al.
(2019).

##  4 Analysis of SE schemes that utilize HE

In this section, we review and analyse the 23 research works which resulted
from the selection process presented in Section 1. We only considered the
proposed schemes in which it is clear how HE is used. The goal of this
analysis is to study their functionalities, taking in consideration the
characteristics presented in Figure 2, and identify which of those
characteristics leverage the utilization of HE and the type of HE which is
used. Table 1 list the selected works and gives an overview of their
functionalities. It also identifies the characteristics that are achieved
using HE. This table serves as a complete resource for identifying and
accessing the works that were analysed in this study, ensuring transparency
and facilitating future references.

Table 1: Categorization of selected SE schemes that utilize HE

Article | Search Structure |  | Search Functionalities |  | Other Functionalities |  | User
---|---|---|---|---|---|---|---
Index |  | Seq.
---
Scan
|  | Single
---
Keyword
| Multi
---
Keyword
| RE/
---
Wildcard
Conj. | Disj. | Range | Phrase |  | Ranked
---
Search
| Verif. |  | Auth./ Revoke
---
User
Dynamic |  | Single | Multi
Malik et al. (2023) |  | x |  | x |  |  |  |  |  |  |  |  |  |  |  |  | x |
Iqbal et al. (2022) |  | x |  | x |  |  |  |  |  |  |  |  |  |  |  |  | x |
Liu et al. (2022) | x |  |  |  | x |  |  |  |  |  | h |  |  |  |  |  |  | x
Gan et al. (2022) | x |  |  | x |  |  |  |  |  |  |  |  |  |  | h |  |  | x
Wang et al. (2022) | x |  |  |  | x |  | h |  |  |  |  |  |  |  |  |  |  | x
Andola et al. (2022b) | x |  |  |  | x |  |  |  |  |  | h |  |  |  |  |  |  | x
Choi et al. (2021) |  | x |  | x |  |  |  |  |  |  |  |  |  |  |  |  | x |
Yin et al. (2021) | x |  |  |  | x | h | h | h |  |  |  |  |  |  |  |  | x |
Prakash and Elizabeth (2021) | x |  |  |  | x |  |  |  |  |  |  |  |  |  | h |  |  | x
Tosun and Savaş (2021) | x |  |  |  | x |  |  |  |  |  | h |  |  |  |  |  |  | x
Hou et al. (2022) | x |  |  |  | x |  | x |  |  | h |  |  |  |  | h |  |  | x
Zhang et al. (2020) | x |  |  | x |  |  |  |  |  |  | h |  |  |  |  |  | x |
Elizabeth and Prakash (2020) | x |  |  |  | x |  |  |  |  |  | h |  | x |  | h |  |  | x
Li et al. (2020) | x |  |  |  | x |  |  |  |  |  | h |  |  |  | h |  | x |
Yang et al. (2020c) | x |  |  |  | x | h | h | h |  |  | h |  |  | x |  |  |  | x
Wen et al. (2020) |  | x |  | x |  |  |  |  |  |  |  |  |  |  |  |  | x |
Yang et al. (2020b) | x |  |  |  | x |  |  |  |  |  | h |  |  | x |  |  |  | x
Boucenna et al. (2019) | x |  |  |  | x |  |  |  |  |  | h |  |  |  |  |  |  | x
Guo et al. (2019) | x |  |  |  |  |  |  |  | h |  |  |  |  |  |  |  |  | x
Shen et al. (2019) | x |  |  |  | x |  | x |  |  | h |  |  |  |  |  |  |  | x
Akavia et al. (2018) |  | x |  | x |  |  |  |  |  |  |  |  |  |  |  |  | x |
Elizabeth et al. (2018) | x |  |  |  | x |  |  |  |  |  | h |  |  |  | h |  |  | x
Wu et al. (2018) | x |  |  |  | x |  | h |  |  |  |  |  | h |  |  |  |  | x
x: indicates that a scheme has a certain property |  |  |  |  |  |  |  |  |  |  |  |  |
h: indicates that a scheme uses HE to achieve a certain property |  |  |  |  |  |  |  |  |  |  |  |  |

Our analysis is divided into the following categories: Search Structure,
Search Functionalities, and Other Functionalities. We have not devoted a
section to the category “Multiplicity of users” because this functionality is
mentioned whenever we analyse one of the selected works. It is important to
notice that it is out of the scope of this work to provide a detailed
explanation of the cryptographic constructions, which can be found in the
referenced works.

###  4.1 Search Structure

The search structure of a SE scheme can involve either a sequential scan of
the entire database or an index-based approach, where an index is created to
facilitate the search process, as mentioned in Section 2. In this analysis, we
will focus on the sequential scan-based SE schemes, as all the others are
index-based, and they will be discussed in the next sections. Additionally, it
is important to recall that the concept of secure search is similar to that of
SE, and consequently, both approaches will be included in this analysis.
Notice that secure search methods typically involve verifying all the
documents in the database to find the ones that match the query, which is
similar to a sequential scan process.

The work of Akavia et al. (2018) is the first of the selected papers to
introduce a method to perform secure search on FHE encrypted data. The authors
claim that this is realized by a polynomial of degree logarithmic (rather than
linear) in the number of array entries data. The core of their secure search
protocol is the computation of a sketch of the first query match, which is
done using an approach they call SPiRiT. This method returns the first record
in an encrypted array of data matching a lookup value. Their proposed scheme
can use any standard semantically secure FHE in which a prime number $p$ can
be chosen as the plaintext modulus parameter so that the homomorphic
operations are addition and multiplication modulo $p$. They claim to have a
single communication round and that the communication overhead only grows with
input and output sizes.

In 2020, Wen et al. proposed a searching method to be used in a secure search
scheme, meant for a single-user setting, named LEAF. This method relies on
three novel techniques: Localization, Extraction, and Reconstruction.
Localization is used to divide the original database array into smaller
intervals of equal length and to identify the first one that contains a
matching item. It returns the encrypted indexes of the interval containing the
matched item. Extraction is used to extract the interval containing the first
matched item for subsequent search operations on that interval and
Reconstruction is used to combine the information from these two techniques in
order to properly locate our desired data, without needing to decrypt
anything. It is worth mentioning that these authors claim that secure search
roughly contains two steps, i.e. _matching_ , and _searching_. In the matching
step, the server compares the encrypted search query (from the client) with
all encrypted items in the database, and returns another encrypted array of 0s
and 1s with 1 indicating the corresponding database item satisfying the query.
The searching step returns all 1’s indexes and corresponding items to the
client. Therefore, their work focuses on the searching step
FHE is used in this scheme to encrypt both sensitive data and search queries.
In fact, one of the main goals of this scheme is to optimize the use of FHE in
Secure Search by reducing the number of necessary computations, namely the
number of multiplications.
Moreover, the authors also propose a variant of this scheme, named LEAF+,
which uses lazy bootstrapping. On the upside, the bootstrapping step can
control the computational depth required by the algorithm, and the greater the
database size, the greater the optimization effect. On the other hand, when
the size of the database is small, this variant will be ineffective, since it
brings many extra multiplication operations and computation depth.

Choi et al., in 2021, suggested a secure search method that uses a standard
CPA-secure (leveled) FHE, meant for single use, that also performs a
sequential scan over the encrypted database to perform a search. In fact, in
their approach, the computational task of secure search is divided in two
steps called matching and fetching, which correspond to the _mathching_ and
_searching_ phases of Wen et al.’s approach. In the matching step, the cloud
server compares the encrypted search query with all encrypted records in the
database using the homomorphic properties of the underlying FHE scheme to find
the ones that correspond to that query. Then, in the fetching step, those
corresponding records are retrieved from the database, also using the
homomorphic properties, and made available to the data user, which can then
decrypt them. Regarding the fetching procedure, the authors propose two novel
retrieving algorithms, namely the COIE scheme (based on power sums or bloom
filters) and CODE scheme (based on bloom filter sets), and compare the
performance of these algorithms with other well known retrieving algorithms
like LEAF+ (Wen et al. 2020) and PIR.

In 2022, Iqbal et al. proposed a mechanism to securely search encrypted audio
data that has been outsourced to CS in a medical context, and which also
performs a sequential scan. Their approach involves using the BGV FHE scheme
to encrypt the data files, which are then sent to the cloud server for
storage. When a search is requested, the CS performs a sequential scan on the
stored encrypted files using homomorphic operations to find the documents that
contain the searched keyword. Then, the retrieved documents are decrypted
using the BGV scheme. In the experiments performed by Iqbal et al., the open-
source programming library HElib version 2.1.0 was used. This library allows
using BGV with bootstrapping and to apply enhancements such as the ciphertext
packing technique by Smart–Vercauteren and the optimization technique by
Gentry–Halevi–Smart (Halevi and Shoup 2014).

In the recent work of Malik et al., published in 2023, a Single Keyword SE
scheme that uses PHE is presented, which uses the Paillier cryptosystem
(Paillier 1999) to protect airport data that is outsourced to cloud servers.
This scheme uses HE to perform search operations and provides a high level of
security by hiding search patterns using trapdoors. Two approaches were
proposed, one which exploits the deterministic properties of the Paillier
cryptosystem, referred to as the “efficient SKSE”, and the other which takes
advantage of its probabilistic properties, named the “secure SKSE”. The former
is suitable for scenarios that prioritize a lightweight approach over
security. In contrast, the latter is more appropriate for scenarios in which
the security has priority over performance. Both approaches use a sequential
scan search structure and are designed for a single-user scenario where the
airport acts as both the DO and DU of the encrypted data.

In this scheme, original data files are encrypted twice. The first encryption
uses the Advanced Encryption Standard (AES) (Dworkin et al. 2001), after which
the encrypted files are uploaded to the CS. The second encryption uses the
Paillier cryptosystem to encrypt the original files, and the resulting
encrypted data is also uploaded to the CS. These are the encrypted files that
will be used to perform the sequential scan. As an output of this scan, the
system retrieves an encrypted result which, after being decrypted by the DU
using Paillier’s scheme, allows recovering the identifiers of the files
containing the searched keyword. AES is then employed to decrypt these files
and recover the original data.

###  4.2 Search Functionalities

In this section, we analyze the selected works that address search
functionalities. We have divided this section based on the following
characteristics: Regular Expressions and Wildcards, Conjunctive Search, Range
Search, Phrase Search, and Ranked Search. We do not provide separate sections
devoted to the ability to allow a multi-keyword search or disjunctive search,
because all the works that possess those functionalities also possess other
search functionalities and are analysed in their corresponding sections. Also,
the papers that have a specified characteristic can be easily identified in
Table 1.

####  4.2.1 Regular Expressions and Wildcards

SE Schemes allowing wildcard queries are spare, and only two were found during
our research. The first scheme in question was proposed by Yang et al. in
2020c. In that work, they presented a novel index-based SE scheme designed for
a multi-user environment. The proposed scheme allows wildcard queries as well
as user authorization and revocation. Additionally, the user can issue “AND”
or “OR” queries on search keywords and can also obtain the top-$k$ documents
that have the highest relevance scores.

This scheme uses a simple index approach. More specifically, a document index
contains three pieces of information: the document ID, its corresponding
keywords, and the key utilized in the symmetric encryption scheme used to
protect the documents. The index is encrypted using a PHE scheme, namely
Paillier’s cryptosystem, before being outsourced to the cloud server. On the
other hand, the documents themselves are encrypted with any secure symmetric
encryption scheme.

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: $\text{*}+Y_{1}$, $Y_{1}+\text{*}$ and $Y_{1}+\text{*}+Y_{2}$,
($Y_{1},Y_{2}$ are strings of any size). When two wildcards are present in the
query, we have the following possibilities: $\text{*}+Y_{1}+\text{*}$,
$Y_{1}+\text{*}+Y_{2}+\text{*}$, $\text{*}+Y_{1}+\text{*}+Y_{2}$ and
$Y_{1}+\text{*}+Y_{2}+\text{*}+Y_{3}$ ($Y_{1},Y_{2},Y_{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. 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: $\text{*}+s+\text{*}$ and $s1+\text{*}+s2$, where $s$,
$s1$, and $s2$ 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.

In this scheme, the sensitive data is encrypted using a symmetric key
encryption scheme indistinguishable under a chosen-plaintext attack, such as
AES, and the tree index is encrypted using an FHE scheme, such as BGV, and a
pseudorandom function. The FHE scheme is used to encrypt the ID of each node
in the tree, and the pseudorandom function is used to encrypt the
concatenation of all edges labels along the path from the root to that node.

Based on the properties of the FHE scheme, the authors also designed an
algorithm to calculate the intersection of search results for different
searched keywords and therefore achieve the compound substring query on
multiple attributes. The compound formula, in this case, consists of
conjunctive and disjunctive expressions of the substrings queried and,
consequently, this scheme allows conjunctive and disjunctive queries as
defined in Section 2.

We have not found any literature proposing a SE scheme that enables the use of
regular expressions and utilizes HE.

####  4.2.2 Conjunctive Search

The ability to perform a conjunctive search is very attractive, and among the
selected works, six of them allow this functionality. However, only 4 of those
papers make use of HE to facilitate the conjunctive search. Most of those
papers possess other search functionalities and are analysed in the
corresponding sections. Interestingly, only one work provides conjunctive
search and no other search functionality. This work is duo to Wang et al.,
which, in 2022, proposed an index-based SE scheme, for a multi-user setting,
that supports conjunctive keyword search and uses a special PHE scheme to hide
the search pattern. Specifically, their work exploits the additive homomorphic
encryption scheme PBC (Bresson et al. 2003), along with an auxiliary server,
to efficiently achieve the conjunctive keyword search property while ensuring
that the data user cannot learn anything other than the desired search result.
In fact, the auxiliary server is introduced to allow the system to achieve the
desired properties by adopting what the authors refer to as the double
trapdoor decryption mechanism, which is available in this scheme.

To achieve the conjunctive keyword search property, the authors use the
polynomial representation of a multiset and encrypt the polynomials using the
BCP cryptosystem to maintain their confidentiality. The cloud server and the
auxiliary server then work together using both additive and multiplicative
homomorphic properties to perform the search.

This work does not detail what kind of encryption scheme is used to encrypt
the documents before uploading them to the database.

####  4.2.3 Phrase Search

The use of Homomorphic Encryption to enable Phrase Search in SE schemes is not
very common. In fact, only 2 out of the 23 analysed SE schemes are capable of
performing phrase search and use HE to allow that functionality. The first one
was proposed in 2019, by Shen et al, and is named P3. This scheme is meant for
a multi-user setting and supports multi-keyword search, specifically phrase
search, and conjunctive keyword search. The main idea of the scheme is to
build an inverted index containing not only the document identifiers where
each keyword appears, but also the location of each keyword in those
documents.

To protect the location information, the scheme encrypts it using a PHE scheme
from Boneh et al. (2005), whose homomorphic properties allow the server to
analyse if two encrypted keywords are adjacent. Moreover, this enables the DU
to obtain precise search results from a single interaction with the cloud
server. Note that phrase search is a specific type of conjunctive query where
the position of queried keywords matters.

The document identifiers and keywords are protected using other techniques,
specifically a pseudorandom permutation primitive and a secure kNN technique,
respectively.

Subsequently, in 2022, Hou et al. proposed a SE scheme that also uses the PHE
scheme from Boneh et al. to protect the location of keywords and enable phrase
search. However, they propose a different structure for the index, which they
call a virtual binary tree. This index tree is only a logical structure used
to store the keywords and related information. Its elements are stored in a
hash table, if they are a leaf node, or are mapped to a bloom filter
otherwise. Homomorphic properties are used similarly to the work of Shen et
al. (2019), allowing the scheme to check if the keywords are adjacent.
Additionally, their approach allows for dynamic updates, which is an advantage
when compared to the previous scheme.

####  4.2.4 Range Search

The ability to perform range search is another functionality which is not
usual to have in SE schemes that use HE. In our research, only one work, duo
to Guo et al., was found. This work was published in 2019, and it presents a
probabilistic threshold range search scheme meant for the multi-user setting
in the IoT context. This scheme addresses the problem of performing range
searches over multidimensional uncertain data while allowing false positives
by returning all the encrypted data that have a probability, of being within
the range of interest, higher than a given threshold value.

The concept of the scheme is that DOs obtain uncertain data from the IoT
devices, which are modelled as multidimensional objects. As such, each IoT
object is represented by an uncertain region and its probabilistic density
function. A piece of data collected from such an object is called instance and
comprises three components: the identification of the object, the coordinates
of the instance, and its probability.

Their approach utilizes a KD-tree, which is a data structure for indexing
$d$-dimensional point data distributed in a $d$-dimensional space. Each node
in the KD-tree consists of one instance and its corresponding range,
calculated based on the instance’s coordinates. The nodes are encrypted using
an Order Preserving Encryption (OPE) scheme, while the instance probabilities
are encrypted using Paillier’s cryptosystem

It is noteworthy that the scheme relies on two cloud servers. Specifically,
the first cloud server is responsible for: storing both the encrypted data and
the encrypted KD-tree, performing KD-tree searches, and sending the results to
the second server. Then, the second server is entitled to filter the results
based on the threshold provided in the search query, and sending the obtained
encrypted documents to the DU.

When the first cloud server receives a query, it conducts a search over the
KD-tree by comparing the values of the instances’ coordinates and using the
homomorphic addition of the Paillier cryptosystem to calculate the upper and
lower appearance probability of each IoT object with respect to the search, so
the results fall within the range queried. The results are then sent to the
second server for filtering, and finally, the filtered results are sent to the
data user.

####  4.2.5 Ranked Search

The ability to perform a ranked search is the most frequently observed feature
in SE that use HE, with 10 out of the 23 analysed works having this property.
Furthermore, all of these works utilize HE to achieve that functionality.

In 2018, Elizabeth et al. proposed a multi-user Top-$k$ Ranked SE (TSED)
scheme that allows dynamic updates. The scheme is based on an inverted index,
which uses a binary vector for each keyword to indicate whether each file
contains that keyword (similar to the Z-index proposed by Wu et al. in 2018).

In this scheme, sensitive data is encrypted using a secure symmetric
encryption scheme, such as AES. Two PHE schemes are then used to encrypt the
two components of the inverted index. Specifically, Paillier’s cryptosystem is
used to encrypt each keyword, while Goldwasser-Micali (GM) (Goldwasser and
Micali 1982) is used to encrypt each binary index vector.

TSED scheme allows for top-$k$ ranked searches using the TF-IDF rule. This
process is done by a secure coprocessor which is responsible for computing the
scores for the query keyword using the encrypted score index, ranking
according to its relevance to the query, and returning the top-$k$ document
identifiers to the cloud server which then retrieves the corresponding
documents do the data user.

A variation of this scheme was proposed in 2020, also by Elizabeth et al.,
which was designated verifiable top-$k$ ranked SE over encrypted cloud data
with dynamic updates (VSED). This scheme, besides its dynamic and ranked
search capabilities similar to the VSED scheme, it also has the verifiability
capability.

In VSED scheme, a similar encrypted inverted index is constructed, but now the
authors use a secret orthogonal vector and the Paillier cryptosystem (Paillier
1999). Both the index and a trapdoor which is used when performing searches
are encrypted using the PHE scheme, as well as the ranking score which is
computed beforehand and, similarly to what is done in TSDE, a secure
coprocessor is used to find the top-$k$ ranked searches based in the TF-IDF
rule.

The Paillier cryptosystem is also used in the update process, which is done
using two different algorithms: one to add new keywords and the other one to
delete existing ones.

To verify the query results returned by the cloud server, this scheme uses the
well known mechanism for message authentication named HMAC (Krawczyk et al.
1997).

Regarding the sensitive data, it can be encrypted using a secure symmetric
encryption scheme such as AES, as in TSED.

In 2019, Boucenna et al. proposed a SE scheme, named Secure Inverted Index
based SE (SIIS), meant for a multi-user setting, which supports ranked search
using HE. In fact, this scheme also allows user access rights management by
using a CP-ABE to encrypt the data collection. As the name of the scheme
indicates, it involves the construction of inverted indices. More
specifically, two separate inverted indices are used. One is used for storing
similarity scores, which are computed by applying the double score weighting
formula (Boucenna et al. 2016). The second inverted index is constructed in
order to manage the users’ access rights to the data collection, and reduce
the number of false positives generated by using the dummy documents technique
(Cao et al. 2014) to allow keyword privacy. The entries in this second index
correspond to the users’ IDs, which points to the set of documents to which
they have access. Both indexes are then encrypted using the FHE scheme BGV
whose homomorphic properties are used to perform the search.

In 2020, Zhang et al. proposed a secure ranked search model over encrypted
data in hybrid cloud computing, meant for a single-user setting. Hybrid cloud
computing refers to the use of a public and private cloud, where the latter is
mainly used to perform costly computations that would have to be performed on
the client’s side otherwise. In this scheme, the private cloud has the ability
to encrypt and decrypt data and most communication rounds are done between the
private and public clouds.

In this proposal, the authors use the Ocapi BM25 ranking model (Whissell and
Clarke 2011), and a not specified FHE scheme is used to encrypt the term
frequency TF and inverse document frequency IDF separately, on the private
cloud. This information is then used to build an inverted index, which is done
in the public cloud.

Regarding the encryption of the sensitive data, it can be performed with any
secure symmetric encryption scheme, such as AES. Finally, the proposed scheme
also relies on a retrieval technique to be used by the private cloud to
download the encrypted documents, although none is specified by the authors.

In the same year, Li et al. (2020), proposed a Two-Server Ranked Dynamic SE
scheme (TS-RDSE), meant for a single-user setting, which supports multi-
keyword search. This scheme uses two cloud servers to perform the searching
and sorting, with one of them being responsible for storing the encrypted data
and the other one for storing the secret key. This scheme uses orthogonal
vectors and two PHE schemes, namely Paillier’s and GM, in the encryption of an
inverted-index, which contains TF-IDF scores that are used to perform ranked
search. More specifically, the index is divided into a search index, which
uses both Paillier and GM for encryption, and a weight index, which uses only
Paillier.

Since the encryption of the index is based on both PHE schemes, TS-RDSE
protocols for adding or deleting documents also take advantage of the
homomorphic properties in order to efficiently update the index.

Regarding the encryption of sensitive data, it can be encrypted with any
secure symmetric encryption scheme.

In 2020b, Yang et al. proposed an index-based SE scheme meant for the multi-
user setting which support multiple data owners. This scheme also supports
multi-keyword queries, top-$k$ ranked results and user authorization/
revocation.

The authors use a PHE scheme, more specifically the Paillier cryptosystem with
threshold decryption (PCTD) to encrypt the index, which is constituted by the
keywords along with their weight, documents IDs and documents keys (the weight
of a keyword can be computed using TF-IDF rule, for example). Given a certain
query, the authors propose a novel algorithm to compute the relevance scores
regarding such query, named Secure Multiple Keyword Search Protocol Across
Domains (MKS).

The encryption of the files themselves is performed by any secure symmetric
encryption scheme.

In 2021, Tosun et al. proposed a new multi-user SE scheme, named Fully Secure
Document Similarity (FSDS) which combines Secure K Nearest Neighbour (SK-NN),
a secure algorithm that operates on data sets in Euclidean space and measures
similarity using Euclidean distance, with SWHE. In this scheme, the sensitive
data and the search queries are represented as TF - IDF vectors which are
encrypted with a variant of SK-NN that the authors named mSk-NN. The
searchable index, which is generated from the documents using TF-IDF
representation, is encrypted first with the mSK-NN, and then by a SWHE scheme
named FV (Fan and Vercauteren 2012). The overall concept of the scheme is to
compute the $k$ nearest neighbours to a given query using the cosine
similarity comparison metric. The authors claim that using a combination of
mSK-NN and SWHE results in a more efficient and secure system, compared to an
approach that only uses SWHE to encrypt the queries. This is because the
amount of computations required is minimized.

Liu et. al proposed, in 2022, an index-based multi-keyword SE scheme which
uses FHE to support ranked search, namely, to retrieve the top-$k$ documents
most relevant according to the search query. The documents themselves are
encrypted using a symmetric encryption scheme (not specified), while an FHE
scheme is used to encrypt the indexes and the search queries. The FHE used was
developed by the same authors and is named Fully Homomorphic Order-Preserving
Encryption (FHOPE) (Liu et al. 2018). This encryption method supports
homomorphic addition, homomorphic multiplication, and order comparison over
encrypted data. As such, it is used to support the search operation and
calculation of relevance score over the encrypted data. In this system, the
data owner is responsible for extracting the keywords, encrypting the
searchable index with FHOPE and uploading it to a cloud server. The data user
is responsible for sending the search query to the cloud server, which
performs the search operation and the ranking score operation, and it then
returns the most relevant top-$k$ documents to the data user.

In the same year, Andola et al. (2022b) proposed a SE scheme, meant for a
multi-user setting, that supports multi-keyword queries and uses HE properties
to construct and search over an index. This scheme also allows ranked search,
which is achieved using term frequency and inverse document frequency TF-IDF.
The authors use Elliptic Curve based ElGamal (Menezes et al. 1996) to encrypt
the index, and regarding the encryption of sensitive data, it can be performed
with any secure symmetric encryption scheme.

###  4.3 Other Functionalities

In this section, we analyse 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 6 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 used in real world
applications, not many works have been proposed in the literature 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 1.

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

Prakash et al. proposed, in 2021, 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 reconstructing the outsourced encrypted index,
and the homomorphic properties are used on both the search and update
processes.

Furthermore, the proposed scheme achieves forward privacy due to the
probabilistic nature of the Paillier cryptosystem and the use 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.

In 2022, Gan et al. proposed a new dynamic searchable symmetric encryption
scheme for multi-client settings that uses XOR homomorphic function to ensure
forward privacy. To achieve efficient multi-client search and forward privacy,
the authors introduced two novel data structures: private links and a public
search tree. During the search process, each client can choose to search their
own private link or 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 (2020).

The former paper is due to Wu et al. and it was published in 2018. Their work
proposed a Verifiable Public Key Encryption With Keyword Search based on HE
meant for the multi-user setting.
In this scheme, sensitive data is encrypted using a standard proxy re-
encryption public key algorithm. 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 (van Dijk et al. 2010), and a homomorphic hash function. The main purpose
of this scheme is to avoid the use of 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 and highlight their significant
implications on the design of the studied approaches. Specifically, we will
discuss the types of HE shcemes 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).

Figure 3: Types of HE schemes used in SE Table 2: HE schemes used in selected
SE approaches

Article | PHE |  | SWHE |  | FHE
---|---|---|---|---|---
Paillier | EC El Gamal | XOR | Boneh | PCTD | GM | BCP |  | FV |  | BGV | FHOPE | BFV | DGHV
Malik et al. (2023) | x |  |  |  |  |  |  |  |  |  |  |  |  |
Iqbal et al. (2022) |  |  |  |  |  |  |  |  |  |  | x |  |  |
Liu et al. (2022) |  |  |  |  |  |  |  |  |  |  |  | x |  |
Gan et al. (2022) |  |  | x |  |  |  |  |  |  |  |  |  |  |
Wang et al. (2022) |  |  |  |  |  |  | x |  |  |  |  |  |  |
Andola et al. (2022b) |  | x |  |  |  |  |  |  |  |  |  |  |  |
Choi et al. (2021) |  |  |  |  |  |  |  |  |  |  |  |  |  |
Yin et al. (2021) |  |  |  |  |  |  |  |  |  |  | x |  |  |
Prakash and Elizabeth (2021) | x |  |  |  |  |  |  |  |  |  |  |  |  |
Tosun and Savaş (2021) |  |  |  |  |  |  |  |  | x |  |  |  |  |
Hou et al. (2022) |  |  |  | x |  |  |  |  |  |  |  |  |  |
Zhang et al. (2020) |  |  |  |  |  |  |  |  |  |  |  |  |  |
Elizabeth and Prakash (2020) | x |  |  |  |  | x |  |  |  |  |  |  |  |
Li et al. (2020) | x |  |  |  |  |  |  |  |  |  |  |  |  |
Yang et al. (2020c) | x |  |  |  |  |  |  |  |  |  |  |  |  |
Wen et al. (2020) |  |  |  |  |  |  |  |  |  |  |  |  | x |
Yang et al. (2020b) |  |  |  |  | x |  |  |  |  |  |  |  |  |
Boucenna et al. (2019) |  |  |  |  |  |  |  |  |  |  | x |  |  |
Guo et al. (2019) | x |  |  |  |  |  |  |  |  |  |  |  |  |
Shen et al. (2019) |  |  |  | x |  |  |  |  |  |  |  |  |  |
Akavia et al. (2018) |  |  |  |  |  |  |  |  |  |  | x |  |  |
Elizabeth et al. (2018) | x |  |  |  |  | x |  |  |  |  |  |  |  |
Wu et al. (2018) |  |  |  |  |  |  |  |  |  |  |  |  |  | x

Finally, we also observed that more than a half of the schemes that rely on a
PHE scheme use either the Paillier cryptosystem (Malik et al. 2023, PINDEX
2021, Li et al. 2020, Yang et al. 2020c, Guo et al. 2019), a combination of
the Paillier cryptosystem with GM (VSED 2020, TSED 2018) or the Paillier
cryptosystem with threshold decryption (Yang et al. 2020b). 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 (Gan et al. 2022), BCP (Wang et al. 2022), EC El Gamal (Andola et
al. 2022b) and Boneh (Hou et al. 2022, Shen et al. 2019).
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 (FSDS 2021). On the other hand, FHE schemes are used in 9 articles,
where the BGV (Iqbal et al. 2022, Yin et al. 2021, Boucenna et al. 2019,
Akavia et al. 2018) and BFV (LEAF 2020) are utilized the most, leveraging
HElib, which is an open-source software library that implements some HE
schemes. Table 2 lists the selected works and identifies the HE schemes they
use.

###  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.

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 Fuzzy Keyword
search. Figure 5 illustrates the number of works that support each search
functionality, considering the functionalities that appeared at least once.

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 (2022),
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. (2016) and used in the work of Boucenna et al.
(2019)).
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 (Tosun
and Savaş 2021, Yang et al. 2020b), or they include another entity in the
framework, such as a coprocessor (Elizabeth and Prakash 2020, Elizabeth et al.
2018), a collaborate server (Li et al. 2020) or a private cloud (Zhang et al.
2020), which have access to the private key and are responsible for ranking
search results.

Regarding the multiplicity of keywords, we observed that the great majority
supports multi-keyword queries. There are, however, some articles that only
support single keyword queries (Malik et al. 2023, Iqbal et al. 2022, Gan et
al. 2022, Zhang et al. 2020, Akavia et al. 2018). Moreover, the ones that
support multi-keyword queries can be further split into two distinct
categories: multi-keyword aimed at ranked search and multi-keyword meant for
conjunctive or disjunctive queries.

Some of the articles allow only for conjunctive queries (Wang et al. 2022, Wu
et al. 2018, Hou et al. 2022, Shen et al. 2019), 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. (2021) and the one by
Yang et al. (2020c). 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 (Yang et al. 2020c), some
other schemes allow for multi-keyword queries specifically for ranked search
(Liu et al. 2022, Andola et al. 2022b, Tosun and Savaş 2021, Elizabeth and
Prakash 2020, Li et al. 2020, Yang et al. 2020b, Boucenna et al. 2019). From
all these papers, only the VSED scheme (Elizabeth and Prakash 2020) 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 (Elizabeth and Prakash 2020, Elizabeth et al. 2018, Li et
al. 2020). Hou et al. (2022) 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. (2021) 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. (2021) and Li et al. (2020)
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 (Yang et al. 2020c, 2020b), 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. (2023), presented an application where the
single entity is an airport, and Iqbal et al. (2022) presented a use case
where both the DO and DU are the same hospital.

Figure 6: Multiplicity of users

Regarding the schemes that are meant for a multi-user setting, the majority
rely on user authorization (Liu et al. 2022, Andola et al. 2022b, Tosun and
Savaş 2021, Yang et al. 2020c, Yang et al. 2020b, Boucenna et al. 2019, Shen
et al. 2019, Wu et al. 2018). Note also that Yang et al. (2020b) proposed a
multi-user SE scheme that allows DUs to perform search queries over the data
of multiple DOs simultaneously. From the remaining schemes, it is worth
highlighting the work of Gan et al. (2022), which achieves the multi-user
functionality by allowing users to search through a private link, a public
search tree, or both.

##  6 Conclusion and Future work

In this work, we provided a comprehensive analysis of the research trends on
SE schemes that use HE. 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 analysed 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 analysed 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
conjunctive/disjunctive queries. However, fuzzy keyword search functionality
was not found in any of the analysed works.

In future research, there is a need to explore and improve upon various
functionalities when searching over encrypted data using HE schemes. While
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
analysed works, only one study (Wu et al. 2018) 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 (Zhang et al.,
2020; Wan et al., 2018). 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,
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., 2019), or OPE for
facilitating ciphertext comparison (e.g. it is used in FASE, 2022), 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. (2013), 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.

## Declaration of competing interest

The authors declare that they have no competing interests.

## Data availability

No data was used for the research described in the article.

## Acknowledgements

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).

## References

  * Acar et al. (2018) Acar, A., Aksu, H., Uluagac, A., Conti, M., 2018\.  A survey on homomorphic encryption schemes: Theory and implementation.  ACM Computing Surveys 51.
  * Agrawal (2021) Agrawal, S., 2021.  A survey on recent applications of cloud computing in education: Covid-19 perspective.  Journal of Physics: Conference Series 1828, 012076.
  * Akavia et al. (2018) Akavia, A., Feldman, D., Shaul, H., 2018.  Secure Search on Encrypted Data via Multi-Ring Sketch, in: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, Association for Computing Machinery, New York, NY, USA. pp. 985–1001.
  * Alloghani et al. (2019) Alloghani, M., Alani, M.M., Al-Jumeily, D., Baker, T., Mustafina, J., Hussain, A., Aljaaf, A.J., 2019.  A systematic review on the status and progress of homomorphic encryption technologies.  Journal of Information Security and Applications 48, 102362.
  * Andola et al. (2022a) Andola, N., Gahlot, R., Yadav, V., Venkatesan, S., Verma, S., 2022a.  Searchable encryption on the cloud: a survey.  Journal of Supercomputing 78, 9952–9984.
  * Andola et al. (2022b) Andola, N., Prakash, S., Yadav, V.K., Raghav, Venkatesan, S., Verma, S., 2022b.  A secure searchable encryption scheme for cloud using hash-based indexing.  Journal of Computer and System Sciences 126, 119–137.
  * Bader and Michala (2021) Bader, J., Michala, A., 2021\.  Searchable Encryption with Access Control in Industrial Internet of Things (IIoT).  Wireless Communications and Mobile Computing 2021\.
  * Benaloh (1994) Benaloh, J., 1994.  Dense probabilistic encryption, in: Proceedings of the workshop on selected areas of cryptography, pp. 120–128.
  * Boneh et al. (2005) Boneh, D., Goh, E.J., Nissim, K., 2005.  Evaluating 2-DNF Formulas on Ciphertexts, in: Kilian, J. (Ed.), Theory of Cryptography, Springer, Berlin, Heidelberg. pp. 325–341.
  * Boneh et al. (2007) Boneh, D., Kushilevitz, E., Ostrovsky, R., Skeith, W.E., 2007\.  Public Key Encryption That Allows PIR Queries, in: Menezes, A. (Ed.), Advances in Cryptology - CRYPTO 2007, Springer, Berlin, Heidelberg. pp. 50–67.
  * Boneh and Waters (2007) Boneh, D., Waters, B., 2007\.  Conjunctive, Subset, and Range Queries on Encrypted Data, in: Vadhan, S.P. (Ed.), Theory of Cryptography, Springer, Berlin, Heidelberg. pp. 535–554.
  * Boucenna et al. (2016) Boucenna, F., Nouali, O., Kechid, S., 2016.  Concept-based Semantic Search over Encrypted Cloud Data:, in: Proceedings of the 12th International Conference on Web Information Systems and Technologies, SCITEPRESS - Science and and Technology Publications, Rome, Italy. pp. 235–242.
  * Boucenna et al. (2019) Boucenna, F., Nouali, O., Kechid, S., Tahar Kechadi, M., 2019\.  Secure Inverted Index Based Search over Encrypted Cloud Data with User Access Rights Management.  Journal of Computer Science and Technology 34, 133–154.
  * Brakerski et al. (2012) Brakerski, Z., Gentry, C., Vaikuntanathan, V., 2012.  (Leveled) fully homomorphic encryption without bootstrapping, in: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, Association for Computing Machinery, New York, NY, USA. pp. 309–325.
  * Brakerski and Vaikuntanathan (2011) Brakerski, Z., Vaikuntanathan, V., 2011\.  Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages, in: Rogaway, P. (Ed.), Advances in Cryptology – CRYPTO 2011, Springer, Berlin, Heidelberg. pp. 505–524.
  * Bresson et al. (2003) Bresson, E., Catalano, D., Pointcheval, D., 2003.  A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications, in: Laih, C.S. (Ed.), Advances in Cryptology - ASIACRYPT 2003, Springer, Berlin, Heidelberg. pp. 37–54.
  * Bösch et al. (2014) Bösch, C., Hartel, P., Jonker, W., Peter, A., 2014\.  A Survey of Provably Secure Searchable Encryption.  ACM Computing Surveys 47, 18:1–18:51.
  * Cao et al. (2014) Cao, N., Wang, C., Li, M., Ren, K., Lou, W., 2014\.  Privacy-Preserving Multi-Keyword Ranked Search over Encrypted Cloud Data.  IEEE Transactions on Parallel and Distributed Systems 25, 222–233.
  * Challa (2020) Challa, R., 2020.  Homomorphic Encryption: Review and Applications.  Lecture Notes on Data Engineering and Communications Technologies 37, 273–281.
  * Cheon et al. (2017) Cheon, J.H., Kim, A., Kim, M., Song, Y., 2017.  Homomorphic Encryption for Arithmetic of Approximate Numbers, in: Takagi, T., Peyrin, T. (Eds.), Advances in Cryptology – ASIACRYPT 2017, Springer International Publishing, Cham. pp. 409–437.
  * Chillotti et al. (2020) Chillotti, I., Gama, N., Georgieva, M., Izabachène, M., 2020\.  TFHE: Fast Fully Homomorphic Encryption Over the Torus.  Journal of Cryptology 33, 34–91.
  * Choi et al. (2021) Choi, S.G., Dachman-Soled, D., Gordon, S.D., Liu, L., Yerukhimovich, A., 2021.  Compressed Oblivious Encoding for Homomorphically Encrypted Search, in: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, Association for Computing Machinery, New York, NY, USA. pp. 2277–2291.
  * van Dijk et al. (2010) van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V., 2010\.  Fully Homomorphic Encryption over the Integers, in: Gilbert, H. (Ed.), Advances in Cryptology – EUROCRYPT 2010, Springer, Berlin, Heidelberg. pp. 24–43.
  * Dong et al. (2013) Dong, Q., Guan, Z., Wu, L., Chen, Z., 2013.  Fuzzy keyword search over encrypted data in the public key setting.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7923 LNCS, 729–740.
  * Dowsley et al. (2017) Dowsley, R., Michalas, A., Nagel, M., Paladi, N., 2017\.  A survey on design and implementation of protected searchable data in the cloud.  Computer Science Review 26, 17–30.
  * Dworkin et al. (2001) Dworkin, M., Barker, E., Nechvatal, J., Foti, J., Bassham, L., Roback, E., Dray, J., 2001.  Advanced Encryption Standard (AES).  URL: https://doi.org/10.6028/NIST.FIPS.197. Accessed May 22 2023.
  * Elgamal (1985) Elgamal, T., 1985.  A public key cryptosystem and a signature scheme based on discrete logarithms.  IEEE Transactions on Information Theory 31, 469–472.
  * Elizabeth and Prakash (2020) Elizabeth, B., Prakash, A., 2020\.  Verifiable top-k searchable encryption for cloud data.  Sadhana - Academy Proceedings in Engineering Sciences 45.
  * Elizabeth et al. (2018) Elizabeth, B., Prakash, A., Uthariaraj, V., 2018.  TSED: Top-k ranked searchable encryption for secure cloud data storage.  Advances in Intelligent Systems and Computing 645, 113–121.
  * Fan and Vercauteren (2012) Fan, J., Vercauteren, F., 2012\.  Somewhat practical fully homomorphic encryption.  Cryptology ePrint Archive, Paper 2012/144.  URL: https://eprint.iacr.org/2012/144. Accessed Feb 24 2023.
  * Gan et al. (2022) Gan, Q., Wang, X., Huang, D., Li, J., Zhou, D., Wang, C., 2022.  Towards multi-client forward private searchable symmetric encryption in cloud computing.  IEEE Transactions on Services Computing 15, 3566–3576.
  * Gentry (2009) Gentry, C., 2009.  A Fully Homomorphic Encryption Scheme.  PhD Thesis. Stanford University. Stanford, CA, USA.
  * Gentry and Halevi (2011) Gentry, C., Halevi, S., 2011\.  Implementing Gentry’s Fully-Homomorphic Encryption Scheme, in: Paterson, K.G. (Ed.), Advances in Cryptology – EUROCRYPT 2011, Springer, Berlin, Heidelberg. pp. 129–148.  doi:10.1007/978-3-642-20465-4_9.
  * Goldwasser and Micali (1982) Goldwasser, S., Micali, S., 1982\.  Probabilistic encryption & how to play mental poker keeping secret all partial information, in: Proceedings of the fourteenth annual ACM symposium on Theory of computing, Association for Computing Machinery, New York, NY, USA. pp. 365–377.
  * González-Martínez et al. (2015) González-Martínez, J.A., Bote-Lorenzo, M.L., Gómez-Sánchez, E., Cano-Parra, R., 2015.  Cloud computing and education: A state-of-the-art survey.  Computers and Education 80, 132 – 151.
  * Guo et al. (2019) Guo, C., Zhuang, R., Jie, Y., Choo, K.K., Tang, X., 2019\.  Secure range search over encrypted uncertain IoT outsourced data.  IEEE Internet of Things Journal 6, 1520–1529.
  * Halevi and Shoup (2014) Halevi, S., Shoup, V., 2014\.  Algorithms in HElib, in: Garay, J.A., Gennaro, R. (Eds.), Advances in Cryptology – CRYPTO 2014, Springer, Berlin, Heidelberg. pp. 554–571.
  * Han et al. (2016) Han, F., Qin, J., Hu, J., 2016\.  Secure searches in the cloud: A survey.  Future Generation Computer Systems 62, 66–75.
  * Handa et al. (2019) Handa, R., Krishna, C.R., Aggarwal, N., 2019.  Searchable encryption: A survey on privacy-preserving search schemes on encrypted outsourced data.  Concurrency and Computation: Practice and Experience 31, e5201.
  * Hou et al. (2022) Hou, J., Liu, Y., Hao, R., 2022.  Privacy-preserving phrase search over encrypted data, in: Proceedings of the 4th International Conference on Big Data Technologies, Association for Computing Machinery, New York, NY, USA. p. 154–159.
  * How and Heng (2022) How, H.B., Heng, S.H., 2022\.  Blockchain-Enabled Searchable Encryption in Clouds: A Review.  Journal of Information Security and Applications 67, 103183.
  * Iqbal et al. (2022) Iqbal, Y., Tahir, S., Tahir, H., Khan, F., Saeed, S., Almuhaideb, A.M., Syed, A.M., 2022.  A novel homomorphic approach for preserving privacy of patient data in telemedicine.  Sensors 22.
  * Krawczyk et al. (1997) Krawczyk, D.H., Bellare, M., Canetti, R., 1997.  HMAC: Keyed-Hashing for Message Authentication.  RFC 2104.
  * Li et al. (2020) Li, Y., Zhou, F., Xu, Z., Ge, Y., 2020.  An efficient two-server ranked dynamic searchable encryption scheme.  IEEE Access 8, 86328–86344.  doi:10.1109/ACCESS.2020.2992773.
  * Liu et al. (2022) Liu, G., Yang, G., Bai, S., Wang, H., Xiang, Y., 2022\.  Fase: A fast and accurate privacy-preserving multi-keyword top-k retrieval scheme over encrypted cloud data.  IEEE Transactions on Services Computing 15, 1855–1867.
  * Liu et al. (2018) Liu, G., Yang, G., Wang, H., Xiang, Y., Dai, H., 2018\.  A Novel Secure Scheme for Supporting Complex SQL Queries over Encrypted Databases in Cloud Computing.  Security and Communication Networks 2018, e7383514.
  * Liu et al. (2023) Liu, J., Zhao, B., Qin, J., Zhang, X., Ma, J., 2023\.  Multi-Keyword Ranked Searchable Encryption with the Wildcard Keyword for Data Sharing in Cloud Computing.  The Computer Journal 66, 184–196.
  * López-Alt et al. (2012) López-Alt, A., Tromer, E., Vaikuntanathan, V., 2012.  On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption.  Proceedings of the forty-fourth annual ACM symposium on Theory of computing , 1219–1234.
  * Malik et al. (2023) Malik, H., Tahir, S., Tahir, H., Ihtasham, M., Khan, F., 2023.  A homomorphic approach for security and privacy preservation of Smart Airports.  Future Generation Computer Systems 141, 500–513.
  * Marcolla et al. (2022) Marcolla, C., Sucasas, V., Manzano, M., Bassoli, R., Fitzek, F., Aaraj, N., Marcolla, C., 2022.  Survey on Fully Homomorphic Encryption, Theory, and Applications.  Proceedings of the IEEE 110, 1572–1609.
  * Menezes et al. (1996) Menezes, A.J., Vanstone, S.A., Oorschot, P.C.V., 1996.  Handbook of Applied Cryptography.  1st ed., CRC Press, Inc., USA.
  * Moumtzoglou et al. (2014) Moumtzoglou, A., Kastania, A.N., Ghosh, R., Papapanagiotou, I., Boloor, K., 2014.  A survey on research initiatives for healthcare clouds, in: Cloud Computing Applications for Quality Health Care Delivery. IGI Global, Hershey, PA, USA, pp. 1–18.
  * Naccache and Stern (1998) Naccache, D., Stern, J., 1998\.  A new public key cryptosystem based on higher residues, in: Proceedings of the 5th ACM conference on Computer and communications security, ACM, San Francisco California USA. pp. 59–66.
  * Netwrix (2022) Netwrix, 2022.  Cloud Data Security Report.  Technical Report. Netwrix.  URL: https://www.netwrix.com/download/collaterals/Netwrix{_}Cloud{_}Data{_}Security{_}Report{_}2022.pdf. Accessed May 16 2023.
  * Noorallahzade et al. (2022) Noorallahzade, M., Alimoradi, R., Gholami, A., 2022.  A Survey on Public Key Encryption with Keyword Search: Taxonomy and Methods.  International Journal of Mathematics and Mathematical Sciences 2022.
  * Paillier (1999) Paillier, P., 1999.  Public-Key Cryptosystems Based on Composite Degree Residuosity Classes, in: Stern, J. (Ed.), Advances in Cryptology — EUROCRYPT ’99, Springer, Berlin, Heidelberg. pp. 223–238.
  * Pham et al. (2019) Pham, H., Woodworth, J., Amini Salehi, M., 2019.  Survey on secure search over encrypted data on the cloud.  Concurrency and Computation: Practice and Experience 31, e5284.
  * Pillai and Lal (2022) Pillai, B., Lal, N., 2022.  Blockchain-based Asymmetric Searchable Encryption: A Comprehensive Survey.  International Journal of Engineering Trends and Technology 70, 355–365.
  * Poh et al. (2017) Poh, G.S., Chin, J.J., Yau, W.C., Choo, K.K.R., Mohamad, M.S., 2017.  Searchable Symmetric Encryption: Designs and Challenges.  ACM Computing Surveys 50, 40:1–40:37.
  * Prakash and Elizabeth (2021) Prakash, A.J., Elizabeth, B.L., 2021\.  Pindex: Private multi-linked index for encrypted document retrieval.  PLOS ONE 16, 1–22.
  * Rivest et al. (1978a) Rivest, R.L., Adleman, L., Dertouzos, M.L., 1978a.  On data banks and privacy homomorphisms.  Foundations of Secure Computation, Academia Press , 169–179.
  * Rivest et al. (1978b) Rivest, R.L., Shamir, A., Adleman, L., 1978b.  A method for obtaining digital signatures and public-key cryptosystems.  Communications of the ACM 21, 120–126.
  * Scholl and Smart (2011) Scholl, P., Smart, N.P., 2011\.  Improved Key Generation for Gentry’s Fully Homomorphic Encryption Scheme, in: Chen, L. (Ed.), Cryptography and Coding, Springer, Berlin, Heidelberg. pp. 10–22.
  * Sharma (2023) Sharma, D., 2023.  Searchable encryption : A survey.  Information Security Journal 32, 76–119.
  * Shen et al. (2019) Shen, M., Ma, B., Zhu, L., Du, X., Xu, K., 2019\.  Secure phrase search for intelligent processing of encrypted data in cloud-based iot.  IEEE Internet of Things Journal 6, 1998–2008.
  * Song et al. (2000) Song, D.X., Wagner, D., Perrig, A., 2000.  Practical techniques for searches on encrypted data, in: Proceeding 2000 IEEE Symposium on Security and Privacy. S&P 2000, pp. 44–55.
  * Suguna et al. (2018) Suguna, M., Ramalakshmi, M., Cynthia, J., Prakash, D., 2018\.  A survey on cloud and internet of things based healthcare diagnosis, in: 2018 4th International Conference on Computing Communication and Automation (ICCCA), pp. 1–4.
  * Tosun and Savaş (2021) Tosun, T., Savaş, E., 2021\.  FSDS: A practical and fully secure document similarity search over encrypted data with lightweight client.  Journal of Information Security and Applications 59, 102830.
  * Wang et al. (2022) Wang, Y., Sun, S.F., Wang, J., Liu, J.K., Chen, X., 2022\.  Achieving searchable encryption scheme with search pattern hidden.  IEEE Transactions on Services Computing 15, 1012–1025.
  * Wang et al. (2016) Wang, Y., Wang, J., Chen, X., 2016.  Secure searchable encryption: a survey.  Journal of Communications and Information Networks 1, 52–65.
  * Wen et al. (2020) Wen, R., Yu, Y., Xie, X., Zhang, Y., 2020.  LEAF: A Faster Secure Search Algorithm via Localization, Extraction, and Reconstruction, in: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, Association for Computing Machinery, New York, NY, USA. pp. 1219–1232.
  * Whissell and Clarke (2011) Whissell, J.S., Clarke, C.L.A., 2011\.  Improving document clustering using Okapi BM25 feature weighting.  Information Retrieval 14, 466–487.
  * Wu et al. (2018) Wu, D., Gan, Q., Wang, X., 2018.  Verifiable Public Key Encryption with Keyword Search Based on Homomorphic Encryption in Multi-User Setting.  IEEE Access 6, 42445–42453.
  * Xu et al. (2021) Xu, W., Wang, B., Lu, R., Qu, Q., Chen, Y., Hu, Y., Maglaras, L., 2021.  Efficient private information retrieval protocol with homomorphically computing univariate polynomials.  Sec. and Commun. Netw. 2021.
  * Yang et al. (2020a) Yang, P., Xiong, N.N., Ren, J., 2020a.  Data security and privacy protection for cloud storage: A survey.  IEEE Access 8, 131723–131740.
  * Yang et al. (2020b) Yang, Y., Liu, X., Deng, R.H., 2020b.  Multi-User Multi-Keyword Rank Search Over Encrypted Data in Arbitrary Language.  IEEE Transactions on Dependable and Secure Computing 17, 320–334.
  * Yang et al. (2020c) Yang, Y., Liu, X., Deng, R.H., Weng, J., 2020c.  Flexible wildcard searchable encryption system.  IEEE Transactions on Services Computing 13, 464–477.
  * Yin et al. (2021) Yin, F., Lu, R., Zheng, Y., Tang, X., Jiang, Q., 2021\.  Achieve efficient and privacy-preserving compound substring query over cloud.  Sec. and Commun. Netw. 2021.
  * Zhang et al. (2020) Zhang, J., Shen, S., Huang, D., 2020.  A secure ranked search model over encrypted data in hybrid cloud computing, in: Lu, W., Wen, Q., Zhang, Y., Lang, B., Wen, W., Yan, H., Li, C., Ding, L., Li, R., Zhou, Y. (Eds.), Cyber Security, Springer Singapore, Singapore. pp. 29–36.
  * Zhang et al. (2018) Zhang, R., Xue, R., Liu, L., 2018.  Searchable Encryption for Healthcare Clouds: A Survey.  IEEE Transactions on Services Computing 11, 978–996.
  * Zheng et al. (2021) Zheng, J., Zhang, J., Zhang, X., Li, H., 2021.  Symmetric searchable encryption scheme that supports phrase search.  Microsystem Technologies 27, 1721–1727.