Fully homomorphic encryption (FHE) is a powerful technique that allows unlimited computations on encrypted data without decryption. However, FHE will incur huge computation and storage costs, making it difficult to be applied in real environments. To improve the efficiency of FHE, some optimized schemes have been proposed based on the trusted execution environment (TEE), which offer a lighter and lower overhead solution for FHE optimizations to a certain extent. However, they heavily rely on the confidentiality of the TEE, and their performance is still limited. To solve the above problems, we propose an efficient TEE-assistance CKKS scheme without bootstrapping, named TCKKS, which has the characteristics of security, efficiency, low memory, and scalability. First, to weaken the trust assumption of TEE, we consider TEE to be honest-but-curious, meaning the enclave's algorithm provider will execute the algorithm honestly but might monitor the data in the enclave. Based on this assumption, we design a lightweight secure multiplication protocol (SMP) and a secure rotation protocol (SRP) for TCKKS to efficiently achieve ciphertext multiplication and rotation operations. Then, to further improve the performance of TCKKS, we optimize the arithmetic operations and encryption/decryption operations based on the characteristics of our protocols. Moreover, we prove the security of SMP and SRP under the simulation-based real/ideal worlds model and further demonstrate the security of TCKKS based on the RLWE problem. In addition, extensive experiments indicate that TCKKS has a better performance than mainstream libraries, such as RNS-HEAAN, PALISADE and SEAL.

Promoting data sharing is one of the critical strategies for thriving in the digital age, and enormous demand for location-based services propels data sharing in the Internet of Vehicles (IoV), particularly in the case of integrating mobile crowdsensing (MCS). However, data security and privacy concerns are increasingly posing serious challenges to the development of data sharing. Although a slew of works have been designed to achieve secure data sharing in IoV, they are inadequate for addressing the privacy issues identified in the data sharing model and often suffer from performance limitations. In this work, we propose an efficient and secure data sharing scheme under the MCS-integrated IoV. Specifically, motivated by the distributed point function (DPF), we design a double-output DPF and leverage it to construct a secure updating scheme that protects full privacy while ensuring high efficiency. Then, based on the XOR filter and a series of subtle transformations, we carefully design a secure spatial test protocol to determine whether a point falls within an arbitrary spatial range efficiently. Afterward, we propose a secure retrieving protocol by using the idea of shared shuffling, in which the offline sub-protocol is presented to generate random masks, and the online sub-protocol is designed to quickly retrieve the desired data items. After formally proving the security of our proposed schemes, we experimentally evaluate their efficiency by comparing them with the alternative solutions, and the results indicate that our proposed schemes offer superior performance, particularly in terms of communication overheads.

Searchable encryption (SE) allows users to perform private queries on encrypted databases. Although SE schemes can protect data privacy, some often pursue high performance while allowing certain leakages, such as search and access patterns. Exploiting such leakage together with other knowledge similar to the user’s database, an attacker can recover queries. State-of-the-art attacks (Nie et al., USENIX’ 24) on single-keyword queries achieve accuracies exceeding 90%. More recently, the community has focused on the more challenging attack of recovering multikeyword queries, with the most advanced attacks (Liu et al., TIFS’ 25) achieving over 80% accuracy. Although these attacks can effectively recover queries, they all rely on a large amount of similar document, requiring the attacker to possess documents equivalent in volume to the database. This naturally raises a question: Can we achieve higher-accuracy attacks using less similar data? Less information makes attacks easier to implement. Motivated by this, we present Mirage, an attack that recovers both single-keyword and multi-keyword queries while requiring only partial similar data. Our core idea is to first identify some special queries and design a series of novel algorithms to recover them. Then, partially reconstruct the database index and recover the remaining queries. Extensive experiments conducted across various real-world datasets demonstrate the effectiveness of our attack. The results show that when the attacker observes 51 time intervals and obtains only 0.5% of similar documents in each interval, Mirage achieves 91.6% and 95.4% accuracy on the Enron and Lucene datasets for single-keyword queries, respectively. For multi-keyword queries, Mirage achieves up to 90.7% and 93.5% recovery accuracy, respectively.

In the advancing field of information technology, the Industrial Internet of Things (IIoT) plays a pivotal role across various domains. To fully leverage the massive data generated by IIoT, the Balanced Iterative Reducing and Clustering using Hierarchies (BIRCH) algorithm is well-suited for clustering large-scale time series data due to its incremental and order-sensitive design. Although aggregating multisource data on cloud servers becomes a practical and effective approach, it raises privacy concerns. Existing privacy-preserving BIRCH schemes designed to mitigate these concerns, however, rely on homomorphic encryption for atomic operations and reveal the insertion path of sample points, resulting in significant limitations in performance and security. To address these issues, we propose SBIRCH, a novel secure BIRCH scheme. Specifically, we first introduce oblivious hierarchical updates to preserve insertion paths. Then, we present a shuffling-based obfuscation technique to protect intermediate clustering results during node splitting. In addition, we optimize division operations on encrypted data, delivering high precision and significantly improving efficiency. Security analysis confirms that our scheme effectively protects multisource data, intermediate clustering results, and clustering relationships. While maintaining consistent security, experimental evaluations demonstrate that our scheme achieves substantial improvements in computational efficiency and markedly reduces communication overheads compared to existing schemes.

Merging multi-source time series data in cloud servers significantly enhances the effectiveness of analyses. However, privacy concerns are hindering time series analytics in the cloud. Responsively, numerous secure time series analytics schemes have been designed to address privacy concerns. Unfortunately, existing schemes suffer from severe performance issues, making them impractical for real-world applications. In this work, we propose novel secure time series analytics schemes that break through the performance bottleneck by substantially improving both communication and computational efficiency without compromising security. To attain this, we open up a new technique roadmap that leverages the idea of mixed model. Specifically, we design a non-interactive secure Euclidean distance protocol by tailoring homomorphic secret sharing to suit subtractive secret sharing. Additionally, we devise a different approach to securely compute the minimum of three elements, simultaneously reducing computational and communication costs. Moreover, we delicately introduce a rotation concept, design a rotation-based hybrid comparison mode, and finally propose our fast secure top-$k$protocol that can dramatically reduce comparison complexity. With the above secure protocols, we propose a practical secure time series analytics scheme with exceptional performance and a security-enhanced scheme that considers stronger adversaries. Formal security analyses demonstrate that our proposed schemes can achieve the desired security requirements, while the comprehensive experimental evaluations illustrate that our schemes outperform the state-of-the-art scheme in both computation and communication.

In the modern digital landscape, integrating geographic locations and textual descriptions within a geo-textual dataset enhances location-based services (LBS) via spatial keyword queries, as these queries combine spatial and textual information to deliver more precise and personalized results. Additionally, the advent of cloud computing allows data owners to outsource data management and services to the cloud, boosting scalability but introducing efficiency challenges due to complex encryption. Although many schemes have been proposed for spatial keyword queries on encrypted geo-textual data, none supports matching a query keyword set with the keyword sets of multiple objects, a common query type in LBS. Imagine a user seeking to rent a house close to his/her workplace, with easy access to conveniences like supermarkets. By using nearby-fit spatial keyword queries, we can match the desired house with a house-type target object and its nearby amenities, offering more practical and flexible recommendations than traditional spatial keyword queries. Hence, in this article, we introduce an efficient and privacy-preserving scheme called the privacy-preserving weighted nearby-fit spatial keyword (PWNSK) query scheme. First, we design a target-oriented spatial keyword (TOSK) tree for data organization and a TOSK tree-based weighted nearby-fit spatial keyword (WNSK) query algorithm for efficient pruning by simultaneously utilizing locations, keywords, and distances from nearby objects to target objects. For privacy, we develop several protocols, including one for polynomial coefficient re-encoding, based on polynomial coefficient encoding and fully homomorphic encryption. Building on these protocols, we introduce our PWNSK scheme. A thorough security analysis confirms its robustness, while extensive experiments also showcase its effectiveness.

With the rapid development of cloud computing, online health monitoring systems are becoming increasingly prevalent. To protect medical data privacy while supporting search operations, Dynamic Searchable Symmetric Encryption (DSSE) technology has been widely used in health monitoring systems. For better monitoring of patient status, keyword range query is also a necessary requirement for the DSSE scheme. Furthermore, in the multi-user setting, user revocation usually leads the owner to download and re-encrypt all indexes, resulting in significant computational overhead. In this paper, we propose a lightweight revocable DSSE scheme with range query support. First, we propose a novel and privacy-preserving range query algorithm that defends plaintext inference attacks. Second, we design a singly linked list structure based on delegatable pseudorandom functions and key-updatable pseudorandom functions, which support lightweight user revocation. Rigorous security analysis proves the security of our proposed range query scheme and demonstrates that our scheme can achieve forward and backward privacy. Experimental evaluations show that our scheme is highly efficient.

Weighted set sampling has been proven essential for generating discrete numbers based on their weights and found broad applications in recommendation systems. The extension of this method, known as weighted range set sampling (WRSS), specifies a query range and applies weighted set sampling to the data within that range. With the proliferation of cloud computing, outsourcing encrypted data and data processing tasks to cloud servers has become a common practice to overcome data storage and processing challenges while protecting data privacy. Existing studies have proposed many privacy-preserving solutions for various customized query and data processing tasks, none have specifically addressed privacy-preserving WRSS. In response to this gap, our paper introduces an efficient and privacy-preserving WRSS scheme. We begin by leveraging the three-party secret sharing (TPSS) scheme as a foundation to design an enhanced three-party secret sharing (eTPSS) scheme with superior storage and computational efficiency. Building upon the eTPSS scheme, we introduce a series of private algorithms to safeguard WRSS privacy. Our scheme integrates the use of a binary search tree and the alias method for WRSS, ensuring privacy through eTPSS-based private algorithms. A thorough security analysis under the simulation-based real/ideal worlds model showcases the effectiveness of our proposed scheme. The proposed scheme's efficiency has been substantiated through extensive experiments, demonstrating that our scheme marks a significant advancement in addressing the challenges posed by privacy-preserving WRSS.

Vertical federated learning for boosting trees has gained significant attention due to its ability to enable participants to collaboratively train high-quality models while preserving data privacy. However, existing privacy-preserving vertical boosting tree schemes suffer from high computation and communication costs or potential security vulnerabilities. Recently, SGBoost, a federated outsourced training and inference scheme, was proposed to address these challenges. However, its performance and security still require significant improvements. Therefore, we propose SGBoost+, an efficient and privacy-preserving vertical boosting tree framework for federated outsourced training and inference. Building upon the strengths of SGBoost, we introduce an RLWE-based lossless and secure internal node construction and an efficient oblivious inference algorithm to finish the model training and inference, significantly enhancing both security and efficiency. To reduce communication cost, we design a ciphertext compression algorithm for model training, which drastically minimizes data transmission costs. Additionally, we analyze the security of a symmetric encryption scheme, specify the required security conditions and parameters, and optimize our model inference based on its improved and secure version. Detailed security analysis confirms that SGBoost+offers strong privacy guarantees. Extensive experiments demonstrate that SGBoost+achieves efficient model training and inference with significantly lower computation and communication costs compared to state-of-the-art schemes.

Cross-modal semantic retrieval systems face significant privacy risks due to storing plaintext data on cloud servers. We propose PCSR, a privacy-preserving framework enabling semantic search directly on encrypted high-dimensional data. It consists of three essential modules: a cross-modal encoder, an approximate nearest neighbor (ANN) search algorithm, and an encryption algorithm. Specifically, we utilize CLIP, a deep neural network model, to extract features of images and texts. We design two ANN search methods for high-dimensional feature vectors by utilizing the space partitioning technique and Singular Value Decomposition algorithms, respectively. Furthermore, we employ adapted Random Matrix Multiplication (RMM) for efficient and secure vector similarity computations. Our rigorous security analysis demonstrates that our proposed schemes are secure. We conduct experiments on four datasets and systematically compare the performance of different encrypted retrieval methods. The superior performance validates the feasibility and efficiency of our proposed schemes.

Local differential privacy (LDP) provides lightweight and provable privacy protection and has wide applications in private data collection. Key-value data, as a popular NoSQL structure, requires simultaneous frequency and mean estimations of each key, which poses a challenge to traditional LDP-based collection methods. Despite many schemes proposed for the privacy protection of key-value data, they inadequately solve the condensed perturbation for keys and the advanced combination of privacy budgets, leading to suboptimal estimation accuracy. To address this issue, we propose an efficient key-value collection scheme (COKV) with tight privacy budget composition. In our scheme, we first design a padding and sampling protocol for key-value data to avoid privacy budget splitting. Second, to enhance the utility of key perturbation, we design a key perturbation primitive and optimize the perturbation range to improve computational efficiency. After that, we propose a key-value association perturbation algorithm whose value perturbation strategy guarantees the output expectation equals the original value. Finally, we demonstrate that through a tight privacy budget composition, COKV can provide higher data utility under the same privacy level. Theoretical analysis shows that COKV possesses lower frequency and mean estimations variance. Extensive experiments on both synthetic and real-world datasets also indicate that COKV outperforms the current state-of-the-art methods for secure key-value data collection.

The rapid development of big data and Internet of Things has promoted the formation of data silos, and cloud computing has facilitated the outsourcing of vertically distributed data to cloud servers. In outsourced query scenarios, building query indexes is crucial for balancing data utility and data privacy protection. The hypercube tree is a widely used index for multi-dimensional data, supporting various query types. Although secure hypercube tree-based queries have been extensively studied in existing works, they are not applicable for building a hypercube tree over vertically distributed ciphertext data. To address this issue, we propose the first efficient and secure hypercube tree building scheme for vertically distributed data, named SCTBuild. We first design a flexible three-party secret sharing (fTPSS) scheme, allowing data owners to flexibly configure secret sharing forms based on real-world computational, communication, and storage constraints. Then, we design a communication-efficient data outsourcing algorithm, a secure data permutation algorithm, and a secure data comparison algorithm based on the fTPSS scheme. After that, we propose our SCTBuild scheme based on the aforementioned algorithms, in which data owners first perform pre-computation on their data to improve tree-building efficiency. We prove that our fTPSS scheme, private algorithms, and the SCTBuild scheme are semantically secure in the simulation-based real and ideal worlds security model; and conduct experiments to validate their high efficiency.

Logistic regression is a widely used and efficient machine learning algorithm for data analysis. However, data is often distributed among different participants, and building high-quality models often involves data interaction, which might easily lead to sensitive information leakage. While some schemes have been proposed to address the data security issue through privacy-preserving technologies such as multi-party computation, homomorphic encryption, and trusted execution environment (TEE), they still suffer from some limitations in terms of security, efficiency, and model integrity and are not suitable for the secure outsourcing training. Therefore, in this paper, we propose an efficient and lossless integrity-preserving training for high-dimensional logistic regression over vertically partitioned data. First, we utilize a block strategy to encrypt the data in batches and outsource them to a cloud with TEE to achieve the non-interactive training. Considering TEE’s limited memory, we employ random sampling technology to achieve mini-batch training within TEE, which ensures the data security. We find that the cloud might launch the active attacks to drop the model accuracy, such as lazy attack and replacement attack. To prevent the attacks, we introduce an integrity protection mechanism to verify data integrity and reduce verification frequency using a mixed-probability checking method, including fixed and random probability checking. Detailed analysis has confirmed that our scheme is secure and integrity-preserving. Extensive experiments have demonstrated that our scheme can achieve lossless, non-interactive, and efficient model training.

Big data have witnessed a growing trend towards vertically distributed storage, with various queries on vertically organized data recognized as effective means for unlocking data's inherent value. Several solutions have emerged for enabling privacy-preserving queries on vertically distributed data using secure multi-party computation techniques. However, these approaches often involve substantial communication overheads among data owners and place significant computational burdens on them, rendering them impractical for resource-constrained data owners. Outsourcing vertically distributed queries to the cloud can substantially alleviate the computational burdens on data owners, and efficient index construction is crucial for outsourced queries on vertical data. In light of this, we present the pioneering “Privacy-Preserving k-d Tree Building” (PTreeB) scheme for vertically distributed outsourced data in this study. Our scheme begins with the development of a private random dimension choosing algorithm (PCDim) and a private equality test (PET) algorithm, leveraging additive Paillier homomorphic encryption. Subsequently, these algorithms, along with various efficiency-enhancing strategies, including pre-sorting each data owner's data and adopting a dual-key system for data privacy protection, form the foundation of our PTreeB scheme. We rigorously demonstrate the security of our scheme, and its efficiency is validated through extensive experimentation.

Machine learning-based trajectory-user linking (TUL) task, which explores human mobility patterns and identifies known users from anonymous trajectories, is widely applied in location-based personalized recommendation systems. However, TUL models implicitly and inadvertently retain users historical trajectories in training data, which could be revealed under malicious inference and analysis. To address this issue, we propose UNIRE, a knowledge transfer-style TUL model aggregation framework to protect sensitive training data. Specifically, teacher TUL models are trained with private users trajectories and then utilized to collaboratively annotate a sensitive-trajectories-isolated dataset. Leveraging this teacher-labeled dataset, student TUL model can be trained and released as the secure aggregation of teacher models, preventing attackers from arbitrarily accessing or exposing the private trajectories. Meanwhile, differential privacy is applied for safeguarding the knowledge transfer process, ensuring that aggregation information from individual teacher models is indistinguishable. Furthermore, we introduce trajectory Equalization and Pseudo Classification as data alignment and accuracy optimization mechanisms for training and aggregating, respectively. Finally, security analysis and extensive experiments indicate that UNIRE framework achieves effective sensitive training data preservation and performance-improved TUL models aggregation, compared to state-of-the-art baselines.

Graph data structures’ ability of representing vertex relationships has made them increasingly popular in recent years. Amid this trend, many property graph datasets have been collected and made public to facilitate a variant of queries such as the aggregate queries that will be extensively exploited in this paper. While cloud deployment of both the datasets and query services is intriguing, it could raise privacy concerns related to user queries and results. In past years, many works on graph privacy have been put forth, however they either do not consider query privacy or cannot be adapted for aggregate queries. Some others consider queries over encrypted graphs but cannot protect access pattern privacy. In particular, when deploying them to handle queries over public graph datasets, the cloud server can infer additional information related to user queries. Aiming at this challenge, we propose a privacy-preserving property graph aggregate query scheme in this paper. Specifically, we first design new privacy-preserving vertex matching and matching update techniques, which securely initialize and update the mapping between vertices in the dataset and the user-specified patterns, respectively. Based on them, we construct our proposed scheme to achieve aggregate queries over public property graphs. Rigid security analysis shows that our proposed scheme can protect the privacy of user queries and results as well as achieve access pattern privacy. In addition, extensive experiments also demonstrate the efficiency of our scheme in terms of computational overheads.

Community search over graphs, which is believed as a powerful tool for locating subgraphs of closely related vertices, has received considerable attention in recent years, and$k$-truss is such a popular community search metric to obtain subgraphs in which every edge forms$(k-2)$triangles. In this paper, we particularly consider$k$-truss community query services, which will return all$k$-truss communities containing a given query vertex. As is known, when the size of graph grows, for achieving better performance, it is natural for a service provider to outsource the services to a powerful cloud. However, this stresses the need for privacy-preserving$k$-truss community query services, as the cloud server is not fully trustable. Over the past years, many schemes focusing on privacy-preserving graph computation have been put forth, but none of them can well support privacy-preserving$k$-truss community queries. Aiming at this challenge, we first propose a privacy-preserving$k$-truss community query scheme ($k$TCQ) by constructing boolean circuits with homomorphic encryption technique and a table-based index. After that, we also design an efficiency-enhanced version ($k$TCQ+) based on a stream cipher scheme to reduce the encrypted index's size and improve the query efficiency. Detailed security analysis shows that both$k$TCQ and$k$TCQ+ can well preserve data privacy and access pattern privacy, and extensive experimental results also demonstrate that$k$TCQ+ can observably reduce the size of encrypted index and the query time by$12\times$and$5.9\times$, respectively.

As one of the most popular queries in big data era, the$k$nearest neighbors ($k$NN) query plays a significant role in various applications, such as medical diagnosis, signal processing, and recommendation systems. Meanwhile, driven by the advancement of the cloud service, an emerging trend among applications is to outsource the dataset and the corresponding$k$NN query services to the cloud. However, as the cloud is not fully trusted, those applications will face vital privacy concerns, and thus they usually encrypt data before outsourcing them to the cloud. Because encrypted data are outsourced to cloud, the$k$NN query over encrypted data has become increasingly attractive, and many solutions have been put forth in recent years. However, existing solutions cannot fully satisfy the objects of returning exact query results, protecting database privacy and query privacy, achieving high query efficiency, and imposing low computational costs at the user side. To address these issues, in this paper, we propose a new practical and privacy-preserving$k$NN query scheme. Specifically, we first refine the general security requirements for the matrix encryption by systematically analyzing existing algorithms. Then, we design a novel asymmetric matrix encryption (AME) to securely achieve Euclidean distance computation and two distances comparison in a single-party and non-interactive way. Then, based on the AME scheme, we propose a privacy-preserving$k$NN query scheme, in which a max-heap of size$k$is used to accelerate query efficiency. Detailed security analysis shows that our proposed scheme is really privacy-preserving. In addition, extensive performance evaluations are conducted, and the results demonstrate that our proposed scheme is also highly efficient.

Big data and bursting cloud computing technologies have facilitated an increasing trend of outsourcing data-driven services to the cloud, where the reverse kNN (RkNN) query is a popularly outsourced query service. The RkNN query aims to retrieve objects having the query object as kNN and widely applied in the product recommendation. Considering privacy concerns, the outsourced query services are demanded to protect data privacy, and consequently a series of privacy-preserving query solutions have been put forth. Nevertheless, RkNN query over high-dimensional data has not been studied to date. In this work, we design the first efficient and privacy-preserving RkNN query scheme over encrypted high-dimensional data, named PHRkNN. Specifically, we first introduce a pivot filter condition for the RkNN query and utilize it to deliberately design a pivot filter R-tree (PFR-tree) to organize the high-dimensional dataset such that the RkNN query has sublinear query efficiency. Then, we propose our PHRkNN scheme by designing some homomorphic encryption based private algorithms and applying them to privately achieve PFR-tree based RkNN query. After that, we propose an oblivious PHRkNN scheme on the basis of the PHRkNN scheme by designing a private random tree permutation (PRTP) algorithm to protect the access pattern privacy. The security of our PHRkNN scheme and oblivious PHRkNN scheme is proved by the simulation-based security analysis. The performance is verified through computational costs and communication overheads evaluation.

With the rapid advancements in machine learning and the widespread adoption of Model-as-a-Service (MaaS) platforms, there has been significant attention on convolutional neural network (CNN) inference services. However, traditional inference services over plaintext data and models are susceptible to the risks of data and model leakage. Although several privacy-preserving CNN inference schemes utilizing trusted execution environment (TEE) and cryptography have been proposed, their security models and performance still have limitations in some scenarios. Aiming at the above challenges, we present an oblivious neural network prediction scheme with semi-honest TEE, namely ToNN, which ensures the security of users’ inputs, outputs, and the model itself. Specifically, based on the limited memory of the TEE, we design secure protocols to perform CNN calculations securely and efficiently, which are friendly to support the single instruction multiple data technique. Additionally, we propose a look-up-table method to optimize the convolution and pooling layers calculations. A detailed security analysis under the simulation-based real/ideal worlds model shows that ToNN can achieve the desired security. Extensive simulation results further demonstrate that ToNN can improve the performance of linear calculations by$\textbf {4.86}\times $and non-linear calculation by$\textbf {37.68}\times $, and can be implemented effectively with low computation and communication costs.

The increasing prevalence of cloud computing drives the exploration of various secure query schemes over encrypted data, among which secure spatial keyword query has drawn a great deal of attention due to its broad application in location-based services. However, most existing schemes are either limited to the boolean keyword test or incapable of protecting access pattern privacy. Although the state-of-the-art secure spatial keyword query scheme can support keyword similarity while preserving access pattern privacy, it is unable to cope with the arbitrary spatial range, which is more general, and has limitations in efficiency and security. In this paper, we propose a new secure spatial keyword similarity query scheme that can support arbitrary spatial ranges and enhance the efficiency and security of the state-of-the-art scheme at the same time. Specifically, we first present a new homomorphic encryption technique by improving the popular symmetric homomorphic encryption (SHE). After that, we propose a novel approach to make supporting arbitrary spatial ranges over encrypted data possible, in which a spatial encoding technique is designed to improve performance. Finally, by designing a pack-based solution to protect access pattern privacy, our proposed scheme can hide the number of query results while optimizing performance. We formally prove the security of our proposed scheme and conduct experiments to evaluate its performance. The results indicate that our proposed scheme outperforms the state-of-the-art scheme in both the computational costs and communication overhead.

Outsourcing big data to cloud servers has gained prominence, and growing concerns about privacy, alongside privacy-related regulations, underscore the need to encrypt data before sending them to the cloud. Nevertheless, encryption significantly hampers the query capabilities of data, particularly in the case of vertically distributed data. This paper focuses on developing secure and efficient similarity query schemes for vertically distributed data in cloud environments. As is known, current solutions are constrained by limitations in query efficiency, approximate query results, and their ability to support vertical data. To address these issues, we introduce two novel schemes: a Fast Similarity Query Scheme (FSQ) and a Non-interactive Similarity Query Scheme (NoSQ) for outsourced distributed data. In the FSQ scheme, we enhance query efficiency by designing a trusted execution environment (TEE) assisted fast secret sharing (FSS) scheme and a series of FSS-based private algorithms, enabling secure data index construction and fast similarity query processing. For the NoSQ scheme, we eliminate communication overheads by designing a TEE assisted non-interactive secret sharing (NoSS) scheme and a series of NoSS-based private algorithms. Both schemes have undergone rigorous security validation using a simulation-based real/ideal worlds model, and their efficiency has been confirmed through comprehensive experiments.

With the pervasiveness of GPS-enabled devices, mobile users can directly visit the best travel routes matching their interests and obtain a better user experience via location-based travel recommendation services. As the number of queries grows, the travel agency for location-based travel recommendations tends to outsource its recommendation services to the cloud server. Since the travel agency’s popular travel routes and raw trajectory data from mobile users contain sensitive information, privacy protection should be guaranteed. Although some schemes have been proposed to solve the privacy problems, no previous works related to the location-based recommendation are proposed over mobile users’ raw trajectories. To solve this problem, we propose a privacy-preserving travel recommendation scheme based on stay points over the raw encrypted trajectory data. Specifically, we first propose an adapted longest common subsequence computation algorithm to measure the similarity of two trajectories. Second, to support some computations under ciphertext, we design several secure two-party computation (S2PC) primitives (e.g., secure division, secure mean coordinate, and secure comparison) based on the Paillier cryptosystem. Third, we implement secure stay points extraction and adapted longest common subsequence computation protocols via these secure computation primitives. Finally, we analyze the security of our proposed scheme in the semi-honest model and show that the privacy of mobile users’ trajectories, query results, and the travel agency’s popular travel routes are well protected. Meanwhile, we evaluate the performance of each secure computation primitive and conduct extensive experiments on synthetic datasets, and the experimental results show that our scheme is practical in the real applications.

With the rapid growth of Internet data volumes, Big Data analysis technologies have gradually permeated all aspects of life. However, the existence of data silos and the promulgation of relevant regulations make it challenging to apply these technologies. In this context, federated learning provides a feasible solution. Especially, XGBoost schemes for vertical federated learning have attracted much attention due to the widespread use of XGBoost. However, these schemes have limitations in terms of security or efficiency. To address these issues, we propose an efficient and privacy-preserving vertical federated learning framework based on the XGBoost algorithm, namely ELXGB, which achieves secure data alignment, XGboost training, and inference services. First, we design two node split algorithms based on homomorphic encryption and differential privacy, which securely and efficiently achieve tree node generation to construct the global model. Then, we utilize attribute obfuscation and direction obfuscation to achieve a secure inference algorithm, which avoids sensitive information leakage and protects the global model. Additionally, the global model of ELXGB is designed to be centralized, which does not require all participants to stay online for inference. Detailed security analysis demonstrates that ELXGB is privacy-preserving. Moreover, extensive experiments on real-world datasets indicate that ELXGB achieves high efficiency without sacrificing model accuracy.

The ever-growing data scale and increasingly strict privacy restraint have recently drawn extensive attention to federated learning (FL) as a multi-party machine learning paradigm for achieving high-quality model construction without data collection. Nevertheless, uploading local models in FL can still be exploited by adversaries to infer participants' sensitive data. Furthermore, it is possible for malicious participants to manipulate the global model by submitting poisonous local models. To tackle these challenges, this paper proposes an efficient and privacy-preserving federated learning framework against poisoning adversaries, namely ELFL, which can ensure the confidentiality of local models while effectively resisting data poisoning attacks. Specifically, we first design a grouped secure aggregation algorithm, through which the aggregation server can compute the summations of local models inside logic groups but cannot see individual ones. Then, based on grouped aggregations, our poisoning defense mechanism could detect and quickly phase out malicious participants from training candidates. Moreover, the computational complexity of participants is independent of their total number, so it is suitable for large-scale scenes. Detailed security analysis demonstrates the security of ELFL. Experimental results show that ELFL could maintain a high accuracy against representative data poisoning attacks, and its computational and communication overhead is indeed low.

Set similarity query is a fundamental query type in various applications, such as clinical diagnosis, online shopping, and mobile crowdsensing. Meanwhile, as the prevalence of outsourced query services, privacy-preserving set similarity query has been considerablely studied. However, to the best of our knowledge, most previously reported solutions suffer from applicability, efficiency, or security issues. Aiming at addressing these issues, we propose an efficient and privacy-preserving set similarity range query scheme (EPSet), where Jaccard similarity is employed as the similarity metric. Specifically, the set similarity range query is first transformed into multi-dimensional range queries by leveraging the triangle inequality of Jaccard distance. Then, a pivot-based k-d tree is designed for indexing the dataset and processing the set similarity query. After that, we design homomorphic encryption based privacy-preserving filter/refinement protocols, respectively named as PPF and PPR, to protect set similarity query privacy, and propose our EPSet scheme. The security of our scheme is proved under the simulation-based real/ideal model, and the performance is validated thorugh the extensive experiment evaluation.

Similarity range query over string sequences plays a significant role in bioinformatics, entity extraction, data mining and information retrieval. Meanwhile, with the popularity of cloud computing, a new paradigm is to outsource the similarity range query service to the cloud. However, existing solutions still have suffer from security and query efficiency drawbacks. To address these issues, we propose an efficient and private similarity range query scheme over encrypted string sequences. Specifically, we first organize string sequences into inverted index and design an inverted index based efficient similarity range query algorithm by applying several filter strategies. Second, based on public-key homomorphic encryption, we design a set of privacy-preserving protocols to protect the privacy of inverted index based range queries. Based on this, we propose a private and computationally efficient similarity range query scheme. Finally, we analyze the security of our scheme and conduct experiments to evaluate its performance, and the results indicate that our proposed scheme is computationally effective.

As the mobile Internet grows rapidly, location-based services (LBSs) are widely applied in the tourism and transportation fields. To fully mine the data collected, location service providers (LSPs) intend to offer various query services to users, which include eclipse query. The eclipse query can generalize nearest neighbor queries and skyline queries and allow users to set more rough and customizable preference ranges. In addition, with the boom of cloud computing, more and more LSPs hope to leverage the cloud to offer better query services. Given that the data could potentially contain confidential information, the data are required to be encrypted prior to outsourcing them. Therefore, eclipse queries need to be executed on the ciphertext. Although several schemes for eclipse queries have been proposed in existing works, they have little focus on privacy issues. To address this issue, we propose an efficient and privacy-preserving scheme for eclipse queries (EPEQ) in this paper. First, we develop a MinValue tree to construct an index for the dataset. Then, by utilizing the MinValue tree and a symmetric homomorphic encryption technique, we design a secure minimum value comparison protocol to obtain a skyline data and a secure undominated data acquisition protocol to obtain the data not skyline dominated by the skyline data. After that, we present our scheme. We analyze the security of the EPEQ scheme and perform experimental evaluations, demonstrating the security and efficiency of our EPEQ scheme.

The hidden Markov model (HMM) has played a pivotal role in various IoT applications due to its ability to model time-varying sequences. Since the datasets usually live in isolated islands and their privacy naturally demands to be seriously considered, the HMM should be trained in a privacy-preserving manner. A typical HMM training framework is federated learning, in which a federated server and many data owners collaboratively train an HMM without revealing data owners' data to the federated server and the trained model to data owners. Since existing HMM training schemes are computationally intensive, we propose an efficient and privacy-preserving federated learning scheme for HMM training to address the efficiency issue in this paper. First, we transform all HMM training computations into matrices- and vectors-based computations over real domains. Then, we introduce our federated HMM training scheme by applying matrix encryption to protect the HMM training privacy. After that, we show that our scheme is privacy-preserving through a rigorous analysis on the security of our scheme. We illustrate that our scheme is efficient through extensive experimental evaluation on the performance of our scheme.

With the rapid development of machine learning, MLaaS has infiltrated into many fields such as image recognition, natural language processing, medical diagnosis, and so on. However, in MLaaS, data interaction between users and service providers is inevitable, and both users' private data and servers' model parameters are at risk of privacy disclosure. In order to solve this problem, homomorphic encryption is an extensively used technique to process private information over ciphertexts. However, since homomorphic encryption only supports linear operations, approximation techniques are required to calculate nonlinear functions, which leads to the loss of prediction accuracy and heavy computation overhead. Therefore, in this paper, we propose a secure neural network prediction scheme combining the trusted execution environment and homomorphic encryption with different security assumptions. Specifically, we first define the security model of TEE-assisted neural network prediction. Then, by combining a lightweight homomorphic encryption technique with TEE, we design secure neural network prediction protocols under different security levels, with which neural network prediction can be securely processed with high performance and accuracy. Finally, we evaluate the performance of our scheme on the MNIST, Fashion-MNIST, and KMNIST datasets, and the results demonstrate that our scheme indeed improves the prediction efficiency and accuracy compared to traditional homomorphic encryption-based schemes with polynomial approximation.

With the popularity of location-based social networks (LBSNs), locations and social relationships have been considered to be important factors in point-of-interest (POI) recommendation services. The boom of cloud computing has driven data owners to outsource the LBSN data and the POI recommendation services to the cloud with powerful computing and storage capabilities. However, as the data usually contains sensitive information, it should be encrypted before being out-sourced, and consequently, the POI recommendation has to be processed over encrypted data. Although several privacy-preserving LBSNs-based POI recommendation schemes have been proposed, they are either inapplicable to the outsourcing scenario or have issues with the recommendation accuracy. Aiming at addressing these issues, in this paper, we propose an efficient and privacy-preserving LBSNs-based POI recommendation scheme (PLPR). Specifically, we first index the users' social relationships with Bloom filters and then organize the user resident location and social relationship dataset into a Vantage Point (VP) tree. Then, we design an efficient LSBNs-based POI recommendation algorithm based on the VP tree. After that, we design a privacy-preserving range determination protocol (PRD) and a privacy-preserving neighbor determination protocol (PND) to respectively protect the privacy of locations and social relationships in the designed algorithm and propose our PLPR scheme. Security analysis shows that our scheme is privacy-preserving, and performance evaluation demonstrates that our scheme is also efficient.

With the development of location based service and online social networking, geo-social-based points of interest (POIs) recommendation has received wide attention, which comprehensively considers the geographic and social factors. The popularity of cloud computing techniques have driven the emerging trend of outsourcing the geo-social-based POI recommendation service to the cloud. However, the cloud server is not fully trusted, leading to the raising concerns of data privacy. Although many privacy-preserving schemes have been proposed for the geo-social-based POI recommendation, they can only return approximate query results. Aiming at addressing this issue, in this paper, we propose an efficient and privacy-preserving geo-social-based POI recommendation scheme, called TRIPE, with accurate query results. Specifically, we first leverage the Quadtree to organize the geographic data and the MinHash method to index the social data. Then, we design a Quadtree-based POI filtering algorithm and a MinHash-based POI filtering algorithm to filter out some POIs that do not meet geo-social POI recommendation threshold. Meanwhile, we employ the BGV homomorphic encryption to protect the privacy of Quadtree-based/MinHash-based POI filtering algorithms and propose our TRIPE scheme based on these algorithms. Security analysis shows that TRIPE is privacy-preserving, and experimental results show that TRIPE is efficient.

Cloud computing's ease of management and on-demand availability features have triggered the boom of outsourcing query services to the cloud. Considering the not-fully trustfulness of the cloud server, the outsourced query services should take the data privacy into consideration, especially when sensitive data are involved. Although many query types have been studied in the context of cloud computing, the range-based reverse k nearest neighbors (RkNN) query is still an unexplored area, which searches data records having any record in the query range as kNN and has wide applications in the taxi dispatching and advertisement placement. As a steppingstone, we propose the first efficient and privacy-preserving range-based RkNN query (PRRkNN) scheme in the cloud. We first design a modified R-tree (MR-tree) to organize the dataset and introduce an efficient MR-tree based RkNN query algorithm to handle RkNN queries with sublinear query efficiency. Then, we propose a sign-preserving matrix encryption (SPME) scheme to privately determine the sign of the scalar product between two records and deploy Paillier homomorphic encryption to introduce a two-party multiplication protocol for secure multiplication between a matrix and a vector. After that, we leverage the SPME scheme and the multiplication protocol to design our PRRkNN scheme. In addition, security analysis shows that our PRRkNN scheme achieves the desired security; and the performance evaluation verifies its efficiency.

With the ubiquity of Internet of Things, location-based service (LBS) providers have collected huge volumes of individuals’ trajectories, which are valuable for some applications, e.g., store location choosing for merchants. However, directly publishing raw trajectories to applications may violate individuals’ data privacy and lead to unexpected loss. Although many trajectory synthesis methods under differential privacy have been proposed to privately publish trajectories data, they cannot sufficiently preserve the semantic information of trajectories. Aiming at this issue, in this article, we introduce a semantic-preserving scheme to synthesize trajectories for publishing under differential privacy. Specifically, we first design a hierarchical graphical model (HGM) to capture the semantic feature of trajectories. Then, we propose a metric, named the correlation score, to measure the relationship between two locations, which can well capture the geographic feature of trajectories. After that, we propose a private trajectory synthesis algorithm by first adding Laplace noises to the extracted features and then synthesizing trajectories based on the noisy features and the Markov chain theory. Privacy analysis demonstrates that our scheme can protect the privacy of trajectories. In addition, performance evaluation illustrates that our synthetic trajectories maintain good utility semantically and geographically.

Recently, researchers have demonstrated that learned index can improve query performance while reducing the storage overhead. It potentially offers an opportunity to address the spatial query processing challenges caused by the surge in location-based services. Although several learned indexes have been proposed to process spatial data, the main idea behind these approaches is to utilize the existing one-dimensional learned models, which requires either converting the spatial data into one-dimensional data or applying the learned model on individual dimensions separately. As a result, these approaches cannot fully leverage or take advantage of the information regarding the spatial distribution of the original spatial data. To this end, in our previous work, we proposed a spatial (multi-dimensional) interpolation function based learned model to develop a spatial learned index and designed efficient range and $k$ NN query strategies over it. However, there are some limitations in the proposed learned model, such as the prediction accuracy and index building time. In this paper, we address the limitations of our previous work and propose a new spatial learned model by employing the characteristics of the spatial interpolation functions and a novel dynamic encoding technique. Detailed experiments are conducted with real-world datasets. The results indicate that our new proposed learned model is better than our previous one in terms of building time, prediction accuracy, and storage overhead simultaneously, and the new learned spatial index is better than the existing learned spatial indexes in query execution time and index building time.

Genomic data is being produced rapidly by both individuals and enterprises, and outsourcing this ever-increasing data into clouds is promising for cutting the cost of data owners and mining the wealth of genomic data at a larger scale. However, genome carries sensitive information about individuals, and it is challenging to securely and efficiently perform analysis on remotely hosted genomic databases. In this paper, we present a privacy-preserving range-constrained intersection query scheme on genomic data. To achieve security and efficiency, we propose a protocol to fulfill range-constrained intersection query, named PriRanGe. With PriRanGe, a client can securely query genomic data in a specific range in a database while keeping this whole process private. The security of our design targets genomic database confidentiality, query range/result confidentiality, and access pattern protection, and the advantage in efficiency is due to most employed primitives are symmetric. We thoroughly evaluated our design by security proof, experimental analysis and comparison to the state-of-the-art works, all of which support the conclusion that this design is both secure and fast.

Bipartite graphs have been widely adopted in applications such as e-healthcare thanks to their ability to model various real-world relationships. Meanwhile, (,)-core query services over bipartite graphs are recognized as a promising approach for finding communities, i.e., closely related sets of vertices in a bipartite graph. As the bipartite graph grows, service providers tend to outsource the services to the cloud. However, there are privacy concerns related to the dataset, queries, and results. Although many schemes have been proposed for privacy-preserving graph analysis, they cannot be directly adopted to handle accurate (,)-core queries. Aiming at the challenges, under the two-server setting, this paper constructs two privacy-preserving schemes with different security levels to handle (,)-core queries. In the proposed schemes, a graph is represented as an index containing two tables and further encrypted by a symmetric homomorphic encryption scheme, and then the servers securely traverse the index. Detailed security analysis shows that both schemes can achieve access pattern privacy, while the security-enhanced one can further protect the structure of the query requests and results. In addition, extensive performance evaluations are conducted to indicate the efficiency of our proposed schemes.

The advances in Internet of Things, Big Data, and machine learning technologies have greatly transformed our daily lives into much more intelligent ones by offering various promising services. Among those services, the discrete Fréchet distance (DFD) range query, which aims to obtain a set of trajectories whose distances to a given query trajectory do not exceed a given threshold, has been widely applied to support applications such as vehicle trajectory clustering and other data processing tasks. Meanwhile, due to the huge data volume issue in the Big Data era, there is a trend towards outsourcing various query services to the cloud for achieving a better performance. However, since the cloud is not fully trustable, designing privacy-preserving query services becomes a research focus. Over the past years, many schemes focusing on privacy-preserving trajectory analysis have been proposed, but none of them can well support privacy-preserving DFD range queries. Aiming at addressing this challenge, this paper proposes a novel privacy-preserving DFD range query scheme, in which queries are conducted in a filtration-and-verification manner and the privacy of the dataset and queries can be preserved. Specifically, by indexing the dataset with two R-trees, a query can be conducted by i) querying the two R-trees to obtain a candidate set and ii) verifying each trajectory in the set, which involve two basic operations, namely, rectangle intersection detection and proximity detection. To preserve the privacy of the dataset and queries, we build the two basic operations upon a novel Inner-Product Preserving Encryption (IPPE) scheme, which is proved to be selectively secure with trivial leakages. Besides, extensive experiments are conducted, and the results demonstrate that our proposed scheme can significantly reduce the computational cost by effectively reducing the candidate set’s size.

As a popular and practical query type in location-based services, the spatial keyword query has been extensively studied in both academia and industry. Meanwhile, with the growing demand for data privacy, many privacy-preserving spatial keyword query schemes have been proposed to deal with queries over encrypted data. However, none of the existing schemes preserve access pattern privacy, and the recent research illustrates that leaking such privacy may incur inference attacks and thus disclose sensitive information. In addition, most existing schemes only consider the boolean keyword search, which is not quite practical and flexible in real-world applications. To address the above issues, in this paper, we propose two privacy-preserving spatial keyword similarity query schemes that can preserve full and partial access pattern privacy, respectively. First, we present a basic privacy-preserving spatial keyword similarity query scheme (PPSKS) by integrating a secure set membership test (SSMT) technique with secure circuits. After that, to improve performance, we propose a tree-based scheme (PPSKS+) by employing a new index called FR-tree together with a predicate encryption technique that can encrypt FR-tree. Formal security analysis shows that: i) our proposed schemes can protect outsourced data, query requests, and query results; ii) our PPSKS scheme can hide full access patterns, while the PPSKS+ scheme preserves$m$-access pattern privacy. Extensive experiments are also conducted, and the results indicate that our tree-based PPSKS+ scheme is much more efficient, almost two orders of magnitude better than our linear search PPSKS scheme in performing queries.

Skyline queries, especially those variants that allow users to define their own query criteria, are very promising and practical techniques in multi-criteria decision making applications. Meanwhile, the growing data volume drives the service providers to outsource their data to the cloud for reaping economic benefits. However, privacy concerns compel the outsourced data to be encrypted and require to perform the skyline queries over encrypted data. To achieve the privacy-preserving skyline queries, many schemes were proposed in the literature. However, those existing solutions cannot fully support the user-defined query criteria in skyline queries, and most of them employ a two-server model to support skyline queries over ciphertexts, which needs multi-round communications between the deployed two servers. In this article, we propose a privacy-preserving user-defined skyline query scheme in a single-server model, which eliminates extra communications. Specifically, we first formally define the user-defined skyline query. Then, based on the idea of converting order relations into computing the inner products of two multi-dimensional points, we design three predicate encryption schemes. Finally, we adopt these predicate encryption schemes to construct our proposed scheme. Detailed security analysis shows that these predicate encryption schemes are selectively secure, and the proposed user-defined skyline query scheme is privacy-preserving. In addition, extensive experiments are conducted, and the results show that our proposed scheme outperforms the alternative scheme by up to an order of magnitude in terms of computational costs when performing user-defined skyline queries.

Outsourcing encrypted time series data and query services to a cloud has been widely adopted by data owners for economic considerations. However, it inevitably lowers data utility and query efficiency. Existing secure skyline query schemes either leak critical information or are inefficient. In this paper, we propose an efficient and privacy-preserving interval skyline query scheme by employing symmetric homomorphic encryption (SHE). Specifically, we first devise a secure sort protocol to sort the encrypted dataset and a secure high-dimensional dominance check protocol to securely determine dominance relations of time series data, in which a dominance check tree is presented. With these secure protocols, we propose our secure skyline computation protocol that can ensure both security and efficiency. Furthermore, to deal with the characteristics of time series data, we design a look-up table to index time series for quick query response. The security analysis shows that our proposed scheme can protect outsourced data, query results, and single-dimensional privacy and hide access patterns. In addition, we evaluate our proposed scheme and compare the core component of our scheme with the state-of-the-art solution, and the results indicate that our protocol outperforms the compared solution by two orders of magnitude in the computational cost and at least 23× in the communication cost.

The advance of cloud computing has driven an emerging trend of outsourcing the rapidly growing data and query services to a powerful cloud for easing the local storage and computing pressure. Meanwhile, when taking data privacy into account, data are usually outsourced to the cloud in an encrypted form. As a result, query services have to be performed over the encrypted data. Among all kinds of query services, the reverse kNN query is highly popular in various applications, such as taxi dispatching and targeted push of multimedia information, but its privacy has not received sufficient attention. To our best knowledge, many existing privacy-preserving reverse kNN query schemes still have some limitations on the query result accuracy, dataset privacy, and flexible support for the choice of the query object and the parameter k. Aiming at addressing these limitations, in this paper, we propose an efficient and privacy-preserving reverse kNN query scheme over encrypted data, named PRkNN. Specifically, we first design a modified M-tree (MM-tree) to index the dataset and further present an MM-Tree based reverse kNN query algorithm in the filter and refinement framework. Then, we leverage the lightweight matrix encryption to carefully design a filter predicate encryption scheme (FPE) and a refinement predicate encryption scheme (RPE); and propose our PRkNN scheme by applying them to protect the privacy of the MM-Tree based reverse kNN query algorithm. Detailed security analysis shows that FPE and RPE schemes are selectively secure, and our PRkNN scheme can preserve both query privacy and dataset privacy. In addition, we conduct extensive experiments to evaluate the performance of our scheme, and the results demonstrate that our scheme is efficient.

Location-based services (LBSs) provide enhanced functionality of mobile applications and convenience for mobile users, which plays a more and more remarkable role in people’s daily life. In LBSs, spatial range query is an essential tool for users to find interesting points in a specific region. However, during spatial range query, it is necessary for data owners and query users to exchange their location data, and the leakage of private location information has drawn significant attention in both governmental and social aspects. Meanwhile, most existing location privacy protection schemes only focus on achieving regular geometry range query over static location datasets. In this paper, we present an efficient and privacy-preserving arbitrary polygon range query scheme, named EPAPRQ. With EPAPRQ, the arbitrary and fine-grained polygon range query can be executed over a dynamic and time-series location dataset with privacy protection. Specifically, in EPAPRQ, an arbitrary polygon range query algorithm is first introduced with sub-range query technique. Then, to protect the private location information of the data owner and query users, a series privacy-preserving data computation protocols are constructed with a symmetric homomorphic encryption algorithm, and a ciphertext-based location dataset updating strategy is also designed. Finally, we propose a double filtration method through combining the quadtree index structure and minimum bounded rectangle, which is able to greatly improve the query efficiency over ciphertexts. Detailed security analysis shows that the sensitive location information in EPAPRQ can be well protected. Furthermore, we evaluate the performance of EPAPRQ in the real map, and the results demonstrate that EPAPRQ is indeed efficient.

The advance of cloud computing has driven a new paradigm of outsourcing large-scale data and data-driven services to public clouds. Due to the increased awareness of privacy protection, many studies have focused on addressing security and privacy issues in outsourced query services. Although many privacy-preserving schemes have been proposed for various query types, the set reverse k nearest neighbors (RkNN) query is still an unexplored area. Even if some existing schemes can be adapted to achieve privacy-preserving set RkNN queries, they will suffer from linear search efficiency. As a steppingstone, in this paper, we propose an efficient and privacy-preserving set RkNN query scheme over encrypted data with sublinear query efficiency. Specifically, we first design an inverted prefix index to organize the set dataset and propose an algorithm to traverse the index with sublinear search efficiency. Then, we propose two oblivious data comparison protocols based on a symmetric homomorphic encryption (SHE) scheme and design the private filter/refinement protocols to preserve the privacy of index searching. After that, we propose an access pattern privacy-preserving set RkNN query scheme by using private filter/refinement protocols. Rigorous security analysis demonstrates that our scheme can protect data privacy and access pattern privacy. Experimental results indicate that our scheme is more efficient than the available naive solution in terms of computational costs and communication overheads.

The boom of cloud computing has stimulated the prevalence of outsourced query services, and privacy concerns further motivate extensive studies on privacy-preserving queries in the cloud. Graph similarity query is one critical query type, in which the similarity between two graphs is usually measured by graph edit distance (GED). Although many schemes have been proposed for GED computation/graph similarity query, they do not consider data privacy and are not applicable to the cloud computing scenario. To address this issue, in this paper, we propose the first efficient and privacy-preserving graph similarity query (PGSim) scheme in the filter and verification framework. Specifically, we first identify the pivot filter property of GED and use the property to design a pivot R-tree based filter algorithm, which can efficiently retrieve candidate graphs for graph similarity query. Then, we design a vertex mapping (VM) tree to index all vertex mappings between two graphs and develop a GED query verification algorithm to verify candidate graphs. After that, we design a suite of private algorithms based on a symmetric homomorphic encryption scheme and apply them to propose a pivot R-tree based filter predicate encryption (PRFilter) scheme and a private GED query verification (PGQVerify) algorithm. Based on the PRFilter scheme and the PGQVerify algorithm, we propose our PGSim scheme. Rigorous security analysis shows that our scheme is selectively secure. Performance evaluation also demonstrates the high efficiency of our scheme.

The aggregated reverse kNN (ARkNN) query aims to identify one query record with the maximum influence set and has become a powerful tool to support optimal decision-making in crowdsensing. Considering data privacy and query privacy, ARkNN queries should be performed in a private manner. Unfortunately, existing schemes cannot support privacy-preserving ARkNN queries over crowd-sensed data. To address this issue, we propose two efficient and privacy-preserving ARkNN query schemes with different security levels, named the BARQ scheme and the EARQ scheme, where the former can only protect data privacy while the latter can protect both data privacy and query privacy. Specifically, we first formalize the models of privacy-preserving ARkNN queries and propose our BARQ scheme based on a random response (RR) frequency oracle. Then, we design a privacy-preserving hardware-assisted reverse kNN query determination (PRkD) scheme for privately determining whether a query record is among the RkNN of a data record. After that, we present our EARQ scheme by leveraging the PRkD scheme to protect query privacy and integrating the RR frequency oracle to protect data privacy. In addition, our rigorous security analysis demonstrates that the BARQ scheme can well protect data privacy, and the EARQ scheme can protect both data privacy and query privacy. Extensive experimental results illustrate that they have high accuracy in query results and are efficient in computational costs and communication overheads.

The optimal location selection is one type of the location-based services (LBS) that aims to find the best location for a new facility from some candidate facilities given a set of existing facilities and a set of customers. Due to reliable and flexible cloud services, outsourcing such heavy-computation tasks has been a popular trend. However, since the cloud is not fully trusted, and the location data contains the sensitive information, privacy protection becomes an essential requirement for these services. Although some related works have been proposed to provide privacy protection, the privacy of data and queries, accuracy of query results, and multiple features of location data are not considered by them simultaneously. In this paper, we propose a privacy-preserving optimal location query scheme PPOLQ that supports multiple-condition filter and queries over multiple data providers in outsourced environments. Specifically, we first design a secure division protocol and a secure inner product protocol based on the Paillier algorithm and the random masking technique, respectively. After that, based on the proposed algorithms, the additive homomorphic encryption, and the secure two-party computation techniques, we develop a privacy-preserving optimal location query scheme. Finally, we analyze the security of our proposed algorithms and scheme in the semi-honest model. Meanwhile, we implement all algorithms and the proposed scheme, and our implementation is open source at Gitee. We also evaluate their performances using synthetic datasets, and extensive experiments show that our scheme is practical for the real-world applications.

The Internet of Things (IoT) boom has enabled Internet Service Providers (ISPs) to collect an enormous amount of high-dimensional data. Performing range queries on such data can effectively reuse them to help ISPs offer better services. Owing to the low cost and high resource utilization of cloud computing, an increasing number of ISPs are inclined to outsource data and services to it. However, as the cloud is not fully trusted, data need to be encrypted before being outsourced, which inevitably hinders many query services, e.g., range queries. Various schemes were proposed for privacy-preserving range queries, yet they struggled to extend to high-dimensional scenarios and did not support dimension selection. Aiming at this challenge, in this article, we propose an efficient and privacy-preserving high-dimensional range query scheme (PHRQ) based on an iMinMax tree while supporting dimension selection. Specifically, we first build an iMinMax tree for high-dimensional data and utilize a symmetric homomorphic encryption technique to design a suite of privacy-preserving protocols to achieve secure high-dimensional range queries. Then, we design a sub-dimensional range determination protocol to support dimension selection. Further, based on the iMinMax tree and our privacy-preserving protocols, we propose our PHRQ scheme. Finally, security analysis shows that our scheme is privacy-preserving, and performance evaluation demonstrates that our scheme is efficient in high-dimensional range query processing.

Secure queries are fundamental to data security, particularly in cloud databases. In data analytics, one of the common and practical queries is the iceberg query that can find aggregate values above a specified threshold. However, existing secure aggregate query schemes: 1) are unable to support secure iceberg queries equipped with the HAVING clause; 2) only consider additive aggregate functions; and 3) suffer from performance issues due to the use of homomorphic encryption to encrypt databases. In this article, we present a secure iceberg query scheme, SecBerg, to support both addition-based and comparison-based aggregate functions and ensure high efficiency and security simultaneously. To make it possible, we propose a secure bitmap index system to encode database values and pioneer the use of the arithmetic secret sharing technique to protect databases in the cloud environment. Furthermore, we carefully design efficient and secure protocols over arithmetic secret sharing to construct our SecBerg. Extensive evaluations are conducted, and the results indicate that SecBerg is significantly more efficient than the state-of-the-art relevant scheme in computational overhead and can attain orders of magnitude performance improvement at best.

Reverse k nearest neighbor (RkNN) query has been widely applied in the targeted push of information. Many schemes for the RkNN query on encrypted data have been proposed for coordinating the emerging trend of outsourcing data to the cloud. However, none of them supports the spatial data with many features, a prevalent data type in location-based services, e.g., each user in online dating apps usually has a spatial location and many personality trait features. Meanwhile, incorporating features with the spatial data endows the spatial-feature-based RkNN query to provide more precise services than the spatial-based RkNN query. Therefore, as a steppingstone, we propose an efficient and privacy-preserving spatial-feature-based RkNN scheme in this work for the first time. Specifically, we first design a modified intersection and union R tree (MIUR-tree) to index the spatial and feature data. Then, we introduce an MIUR-tree based RkNN query algorithm in the filter and refinement framework to efficiently process RkNN queries. After that, based on a symmetric homomorphic encryption (SHE) scheme, we design a private filter protocol and a private refinement protocol, and leverage them to propose our RkNN query scheme. Rigorous security analysis demonstrates that our scheme is privacy-preserving, and extensive experiments indicate that our scheme is computationally efficient.

The advance of artificial intelligence has stimulated the rapid development of multi-biometric recognition that recognizes users based on their multiple biometric features. Since biometric features are private information of users, multi-biometric recognition has to be processed in a privacy-preserving way. Although many approaches have been proposed for privacy-preserving multi-biometric recognition, they have some limitations in security and performance. Aiming at this challenge, we propose a privacy-preserving multi-biometric recognition scheme. In this scheme, we first utilize a neural network to train a face and voiceprint fusion model, which obtains better fusion layer parameters and improves the accuracy of fusion recognition. Then, we design an efficient and privacy-preserving multi-biometric recognition scheme based on the MK-CKKS cryptosystem in the decentralized model, which does not rely on a trusted third party to increase its universality. The scheme can guarante recognition accuracy by utilizing a feature-level fusion mechanism, reaching EERs as low as 0.66%. Security analysis shows that the privacy of biometric information and recognition results can be guaranteed. Experimental results validates the efficiency of our scheme.

Weighted similarity query has been an essential primitive to enable personalized disease diagnosis in eHealthcare. With the prevalence of cloud computing, a new paradigm is to outsource weighted similarity range query services to the cloud. Meanwhile, the query services are usually processed over encrypted data considering data privacy. Although many existing schemes are available to achieve privacy-preserving weighted similarity query over encrypted data, they have some security and query efficiency drawbacks. This paper addresses this problem by proposing an efficient and privacy-preserving weighted similarity range query scheme. First, we employ a k-d tree to index the outsourced dataset and present a k-d tree based weighted similarity range query algorithm. Then, we propose our scheme by applying the MASPE scheme to protect the privacy of the k-d tree based weighted similarity queries. Privacy preservation of our scheme is proved through security analysis. Efficiency improvement is confirmed by the extensive experiments that indicate that our scheme improves 7 x query efficiency than the state-of-the-art scheme.

Similarity queries have been widely employed to offer more effective medical care to patients in eHealthcare. As a special query, similarity query with user-defined weights, which allows users (i.e., doctors in eHealthcare) to define the weight for the distance metric, has received particular interest recently. In order to make the weighted similarity query service more flexible and reliable, healthcare centers tend to outsource the healthcare data and the corresponding similarity query service to a powerful cloud. However, due to privacy concerns, healthcare centers usually demand to encrypt the data before outsourcing them to the cloud. Although some existing privacy-preserving similarity query schemes can be adapted to handle weighted similarity range queries, they may face issues in either the practicality or the accuracy of query results. Aiming at addressing these issues, in this paper, we design an efficient privacy-preserving weighted similarity range query (EPW-Sim) scheme, which is practical and can return accurate query results. Specifically, we first discover a lower bound for the distance metric, i.e., weighted Euclidean distance, and further leverage the lower bound as a filtration condition to design an efficient weighted similarity range query algorithm. Second, we apply a modified asymmetric-scalar-product encryption (MASPE) scheme to preserve the privacy of the designed algorithm and propose our EPW-Sim scheme. Finally, we analyze the security of our scheme and conduct experiments to validate its efficiency, and the results demonstrate that our scheme is privacy-preserving and efficient.

The rapidly growing location-based services enable service providers to accumulate plentiful descriptions on points of interest (POIs), which can be used to support expressive POI queries. In this article, we study a type of POI query, named feature-based group$k$nearest neighbor query over road networks, in which a user has a feature set and several locations and wishes to find$k$closest POIs that have similar sets of features to the query. As the POI data sets grow, service providers tend to outsource their data sets to a powerful yet not-fully trusted cloud, which calls for privacy preservation on data sets and user queries. Although many schemes have been proposed for privacy-preserving POI queries, none of them can simultaneously support privacy-preserving set similarity and road network distance comparison. To address this challenge, we propose an efficient and private feature-based group nearest neighbor query scheme. In our scheme, we achieve privacy-preserving distance comparison by employing the road network hypercube embedding technique, and design an encrypted index based on B+-tree for privacy-preserving set similarity range queries. Security analysis shows our proposed scheme can preserve the privacy of the data set and queries, and performance evaluation also demonstrates it is computationally efficient.

With the popularity of intelligent terminals and the advances of mobile Internet, carpooling service, which reduces the travel cost of each user by allowing multiple users to share one car, has received considerable attention and makes our life more convenient. However, the vigorous development of carpooling services still faces severe challenges in users’ location or route privacy. In this article, we propose an efficient and privacy-preserving route matching scheme called TAROT for carpooling services. With TAROT, users can enjoy high-quality carpooling services while without revealing sensitive location and route information. Specifically, based on a Goldwasser–Micali-based equality determination algorithm (GMEDA), we design an accurate similarity computation algorithm (ASCA), which allows users to get accurate carpooling results over ciphertexts. Meanwhile, the reverse Minhash (RM) method is also designed to construct a dissimilar route filter algorithm (DRFA), which can filter out dissimilar routes in advance and reduce computational costs and communication overheads. Security analysis shows that TAROT can protect users’ location privacy. In addition, TAROT is also evaluated with many random maps, and the simulation results demonstrate that TAROT is highly efficient.

Wireless body area network (WBAN) and big data techniques indubitably enable the online medical diagnosis system to be more practical. In the system, to make a more accurate diagnosis, doctors wish to obtain some archived medical data records, which are similar to the sensed patient data, to learn from the prior diagnoses. As a practically useful similarity search, the dynamic skyline query can provide doctors with similar data records having all possible relative weights of attributes. Driven by the powerful cloud, the data owner often outsources encrypted data and the corresponding services, e.g., dynamic skyline query services here, to a third-party cloud. As a result, it is required to perform the dynamic skyline query over encrypted data. However, existing schemes are either insecure or inefficient. To address the issue, in this article, we propose an efficient and privacy-preserving dynamic skyline query scheme and use it in an online medical diagnosis system. Specifically, based on symmetric homomorphic encryption (SHE), we present a set of efficient and secure protocols to achieve various operations, such as less than comparison, equality test, and dominance determination, without leaking any sensitive information to the cloud. With these secure protocols, we carefully design our dynamic skyline query scheme to attain full security and high efficiency at the same time. Detailed security analysis shows that our proposed scheme is indeed privacy-preserving. With extensive experimental evaluations, we show that our proposed scheme outperforms the alternative scheme by two orders of magnitude in the computational cost and at least$8.1\times $in the communication cost.

Aggregate nearest neighbor (ANN) query, which can find an optimal location with the smallest aggregate distance to a group of query users’ locations, has received considerable attention and been practically useful in many real-world location-based applications. Nevertheless, query users still hesitate to use these applications due to privacy concerns, as there is a worrisome that the location-based service (LBS) providers may abuse their locations after collecting them. In this article, to tackle this issue, we propose a novel privacy-preserving aggregate query (PPAQ) scheme to select an optimal location for query users in road networks. Specifically, we first analyze the problem of the ANN query in road networks and identify two basic operations, i.e., addition and comparison, in the query. Then, we carefully design efficient addition and comparison circuits to securely add and compare two bit-based inputs, respectively. With these two secure circuits, we propose our PPAQ scheme, which can simultaneously protect the users’ locations, query results, and access patterns from leaking. Detailed security analysis shows that our proposed scheme is indeed privacy-preserving. In addition, extensive performance evaluations are conducted, and the results indicate that our proposed scheme has an acceptable efficiency for non-real-time applications.

Healthcare data explosion and cloud computing booming have motivated healthcare centers to outsource their healthcare data and data-driven services to a powerful cloud. Nevertheless, due to privacy concerns, the data are usually encrypted before being outsourced, which will degrade the data utility and make it challenging to implement data-driven services. Although the multidimensional range query over encrypted data, as one of the most popular outsourced services in eHealthcare, has been extensively studied, existing solutions still have some limitations in efficiency, privacy, and practicality. Aiming at this challenge, in this article, we design an efficient and privacy-preserving multidimensional range query (PMRQ) scheme. We first build an R-tree to index the data set and reduce the R-tree-based range queries to the multidimensional range intersection problem. Then, by delicately designing a data comparison algorithm and a homomorphic encoding technique, we present an encoding-based range intersection algorithm. After that, by employing matrix encryption to protect the privacy of the encoding-based range intersection algorithm, we design a multidimensional range intersection predicate encryption (MRIPE) scheme. Based on the MRIPE scheme, we then propose our PMRQ scheme. A detailed security analysis illustrates that our PMRQ scheme is privacy preserving, and experimental results demonstrate that it is computationally efficient.

The thriving of the Internet of Things (IoT) has become the enabler of smart eHealthcare, which greatly benefits patients by providing various data-driven healthcare monitoring services. Among those promising services, the time-series activities-based healthcare monitoring service is highly regarded due to its popularity. Meanwhile, with the rapidly growing volume of healthcare data, an emerging trend is to outsource the time-series activities-based healthcare monitoring models and the corresponding services to a cloud, which, however, inevitably entails privacy concerns. Although many existing works have put forth some solutions for privacy-preserving time-series activities-based healthcare monitoring, they are not applicable to the outsourced scenario with a single-server setting. To address the challenge, in this article, we propose an efficient and privacy-preserving forward algorithm (PPFA) and further apply PPFA to construct a remote healthcare monitoring scheme over the cloud. To the best of our knowledge, our PPFA is the first privacy-preserving forward algorithm over cloud while without any accuracy loss. In addition, our remote healthcare monitoring scheme is also the first privacy-preserving hidden Markov model-based healthcare monitoring scheme in the single-server setting. Detailed security analysis shows that our PPFA and healthcare monitoring scheme are indeed privacy preserving. In addition, extensive simulations are conducted, and the results also demonstrate their efficiencies.

It is believed that online disease risk assessment system has great potential to alleviate the medical treatment problems for the future smart city and communities, as it can excavate disease risk factors from a large number of patient features, provide diagnostic references for doctors, and save medical treatment time for patients. However, the flourish of online disease risk assessment service still faces severe challenges including information privacy and security. In this article, based on the naïve Bayesian classification, we propose an efficient and privacy-preserving diseaserisk assessment scheme over multi-outsourced vertical datasets, named CARER. With CARER, the e-healthcare provider can securely train a disease risk predication model over vertically distributed medical data from multiple medical centers (i.e., hospitals), and provide privacy-preserving disease risk predication services for users (i.e., patients and doctors). During the model training and disease risk prediction phases, all sensitive data are operated over ciphertexts without decryption. As a result, the private information of medical centers, e-healthcare provider, and users can be well protected. Detailed security analysis shows that CARER can resist various known security threats. In addition, we evaluate the performance of CARER with real medical datasets, and the results demonstrate that CARER is efficient.

Similarity query over time series data plays a significant role in various applications, such as signal processing, speech recognition, and disease diagnosis. Meanwhile, driven by the reliable and flexible cloud services, encrypted time series data are often outsourced to the cloud, and as a result, the similarity query over encrypted time series data has recently attracted considerable attention. Nevertheless, existing solutions still have issues in supporting similarity queries over time series data with different lengths, query accuracy and query efficiency. To address these issues, in this article, we propose a new efficient and privacy-preserving similarity range query scheme, where the time warp edit distance (TWED) is used as the similarity metric. Specifically, we first organize time series data into a$k$d-tree by leveraging TWED’s triangle inequality, and design an efficient similarity range query algorithm for the$k$d-tree. Second, based on a symmetric homomorphic encryption technique, we carefully devise a suite of privacy-preserving protocols to provide a security guarantee for$k$d-tree based similarity range queries. After that, by using the similarity range query algorithm and these protocols, we propose our privacy-preserving similarity range query scheme, in which we elaborate on two strategies to make our scheme resist against the cloud inference attack. Finally, we analyze the security of our scheme and conduct extensive experiments to evaluate its performance, and the results indicate that our proposed scheme is indeed privacy-preserving and efficient.

Set similarity search, aiming to search the similar sets to a query set, has wide application in today's recommendation services. Meanwhile, the rapid advance in cloud technique has promoted the boom of data outsourcing. However, since the cloud is not fully trustable and the data may be sensitive, data should be encrypted before outsourced to the cloud. Undoubtedly, data encryption will hinder some basic functionalities, e.g., set similarity search. For achieving set similarity search over encrypted data, many solutions were proposed, yet they either only satisfy weak security requirements, or only achieve approximate similarity, or have low efficiency or under the model of two cloud servers. Therefore, in this article, we propose a new efficient and privacy-preserving exact set similarity search scheme under a single cloud server. Specifically, we first design a symmetric-key predicate encryption (SPE-Sim) scheme, which can support similarity search over binary vectors. Then, we represent the set records to be binary vectors and employ the B+ tree to build an index for them. After that, based on SPE-Sim and the B+ tree-based index, we propose our scheme and it can achieve efficient set similarity search while preserving the privacy of set records and query contents. Finally, security analysis and performance evaluation indicate that our scheme is privacy-preserving and efficient.

It is undeniable that Internet of Things (IoT) in big data era can provide us with huge volumes of multi-dimensional data, transforming our society into a much more intelligent one. In order to fit for the multi-dimensional data processing in big data era, multi-dimensional range queries, especially over cloud platform, have received considerable attention in recent years. However, as the cloud server is not fully trustable, designing multi-dimensional range queries over encrypted data becomes a research trend, and many solutions have been proposed in the literature. Nevertheless, most existing solutions suffer from the leakage of the single-dimensional privacy, and such leakage would severely put the data at risk. Although a few existing works have addressed the problem of single-dimensional privacy, they are impractical in some real scenarios due to the issues of inefficiency, inaccuracy, and two-cloud-server requirement. Aiming at solving these issues, in this article, we propose a practical and privacy-preserving multi-dimensional range query (PRQ) scheme. Specifically, in our proposed PRQ scheme, we first index the multi-dimensional dataset with an R-tree and reduce R-tree based range queries to the problem of point intersection and range intersection. Then, by employing the lightweight matrix encryption technique, we design two novel algorithms for PRQ, i.e., multi-dimensional point intersection predicate encryption (PIPE) and multi-dimensional range intersection predicate encryption (RIPE), which can preserve the privacy of the proposed point intersection algorithm and range intersection algorithm, and further preserve the single-dimensional privacy of the proposed PRQ scheme. Detailed security analysis shows that our proposed PRQ scheme is indeed privacy-preserving. In addition, extensive simulations are conducted, and the results also demonstrate its efficiency.

It has been witnessed that Aggregate Reverse Skyline (ARS) query has recently received a wide range of practical applications due to its marvelous property of identifying the influence of query requests. Nevertheless, the query users may hesitate to participate in such query services as the query requests and query results may leak sensitive personal data or valuable business data assets to the service providers. To tackle the concerns, a promising solution is to encrypt the query requests, conduct the ARS queries over encrypted query requests without decrypting, and return the encrypted query results. Unfortunately, many existing solutions are either deployed over a two-server model or unable to fully preserve query privacy. In this paper, we propose a novel privacy-preserving aggregate reverse skyline query (PPARS) scheme on a single server model while ensuring full query privacy. Specifically, we first transform the problem of ARS query into a combination of set membership test and logical expressions. Then, by employing the prefix encoding technique, bloom filter technique, and fully homomorphic encryption, we run the transformed logical expressions to obtain the encrypted aggregate values without leaking query requests, query results, and access patterns. Furthermore, we propose an interpolation-based packing technique to improve the communication efficiency of PPARS. Detailed and formal security analysis demonstrates that our proposed schemes can guarantee strong security. In addition, extensive experiments are conducted, and the results validate the efficiency of our proposed schemes.

Similarity queries, giving a way to disease diagnosis based on similar patients, have wide applications in eHealthcare and are essentially demanded to be processed under fine-grained access policies due to the high sensitivity of healthcare data. One efficient and flexible way to implement such queries is to outsource healthcare data and the corresponding query services to a powerful cloud. Nevertheless, considering data privacy, healthcare data are usually outsourced in an encrypted form and required to be accessed in a privacy-preserving way. In the past years, many schemes have been proposed for privacy-preserving similarity queries. However, none of them is applicable to achieve data access control and access pattern privacy preservation. Aiming at this challenge, we propose an efficient and access pattern privacy-preserving similarity range query scheme with access control (named EPSim-AC). In our proposed scheme, we first design a novel tree structure, called$k$-d-PB tree, to index healthcare data and introduce an efficient$k$-d-PB tree based similarity query algorithm with access control. Second, to balance the search efficiency and access pattern privacy of$k$-d-PB tree, we also define a weakened access pattern privacy, called$k$-d-PB tree’s$\beta $-access pattern unlinkability. After that, we preserve the privacy of$k$-d-PB tree based similarity queries with access control through a symmetric homomorphic encryption scheme and present our detailed EPSim-AC scheme. Finally, we analyze the security of our scheme and also conduct extensive experiments to evaluate its performance. The results demonstrate that our scheme can guarantee$k$-d-PB tree’s$\beta $-access pattern unlinkability and has high efficiency.

Set containment search, which aims to retrieve all set records containing a specific query set, has received considerable attention. Meanwhile, due to the dramatic growth of data, data owners tend to outsource their data to the cloud and deploy the cloud server to offer the set containment search services. However, as the cloud server is not fully trustable and the data may be sensitive, a straightforward strategy for the data owners is to encrypt the data before outsourcing them. Although the encryption technique can preserve data privacy, it inevitably hinders the functionality of set containment search. Many existing studies on the set containment search over outsourced data still suffer from the search efficiency and security issues. In this article, aiming at the above issues, we propose an efficient and privacy-preserving set containment search scheme. Specifically, we first deploy an asymmetric scalar-product-preserving encryption technique to design a set containment/intersection encryption (SCIE-Enc) scheme. Then, we build a radix tree to represent the set records. Based on the radix tree and SCIE-Enc construction, we present our scheme that can achieve efficient set containment search while preserving the privacy of set records, query sets, and query results, as indicated in our security analysis and performance evaluation.

As a consequence of advance in the Internet of Things (IoT) and big data technology, smart eHealthcare has emerged and greatly enabled patients to enjoy high-quality healthcare services in disease prediction, clinical decision making and healthcare surveillance. Meanwhile, in order to support the dramatic increase of healthcare data, healthcare centers often outsource the on-premises data to a powerful cloud and deploy the cloud server to manage the data. However, since the healthcare data usually contain some sensitive information and also the cloud server is not fully trusted, healthcare centers need to encrypt the data before outsourcing them to the cloud. Unfortunately, data encryption inevitably hinders some advanced applications of the data like the similarity range query in cloud. Although many studies on similarity range query over encrypted data have been reported, most of them still have some limitations in security, efficiency and practicality. Aiming at this challenge, in this article, we propose a new efficient privacy-preserving similarity range query (EPSim) scheme. Specifically, we first present a modified asymmetric scalar-product-preserving encryption (ASPE) scheme and prove it is selectively secure. Then, we introduce a Quadsector tree to represent the data, and employ a filtration condition to design an efficient algorithm for efficient similarity range queries over the Quadsector tree. Finally, we propose our EPSim scheme by integrating the modified ASPE scheme and Quadsector tree. Detailed security analysis indicates that our proposed EPSim scheme is really secure. In addition, extensive performance evaluations are conducted, and the results also demonstrate it is efficient and practical.

Dynamic symmetric searchable encryption (SSE), which enables a data user to securely search and dynamically update the encrypted documents stored in a semi-trusted cloud server, has received considerable attention in recent years. However, the search and update operations in many previously reported SSE schemes will bring some additional privacy leakages, e.g., search pattern privacy, forward privacy and backward privacy. To the best of our knowledge, none of the existing dynamic SSE schemes preserves the search pattern privacy, and many backward private SSE schemes still leak some critical information, e.g., the identifiers containing a specific keyword currently in the database. Therefore, aiming at the above challenges, in this article, we design a practical SSE scheme, which not only supports the search pattern privacy but also enhances the backward privacy. Specifically, we first leverage the$k$-anonymity and encryption to design an obfuscating technique. Then, based on the obfuscating technique, pseudorandom function and pseudorandom generator, we design a basic dynamic SSE scheme to support single keyword queries and simultaneously achieve search pattern privacy and enhanced backward privacy. Furthermore, we also extend our proposed scheme to support more efficient boolean queries. Security analysis demonstrates that our proposed scheme can achieve the desired privacy properties, and the extensive performance evaluations also show that our proposed scheme is indeed efficient in terms of communication overhead and computational cost.

With the flourish of Wireless Body Area Network (WBAN), the online medical monitoring system has attracted extensive attention. Meanwhile, due to the limited resources, the hospital tends to outsource the medical services to the cloud and requires the patients' data to be encrypted before uploading. It is bound to raise a challenge in data availability, e.g., the reverse skyline query that is widely used in monitoring systems. In this paper, we propose a privacy-preserving online medical monitoring system, in which the cloud can answer the reverse skyline query over encrypted data and return the monitored data of high-risk patients to a doctor. To achieve this goal, we first design four secure protocols that can ensure the security of operands while minimizing the communication costs between two cloud servers. Based on these privacy-preserving protocols, we propose two privacy-preserving reverse skyline query schemes that can be used in the monitoring system. Security analysis shows that our proposed scheme is indeed privacy-preserving, and performance evaluations also demonstrate the efficiency of our scheme in terms of computation and communication.

As the growing proportion of aging population, the demand for sustainable, high quality, and timely healthcare services has become increasingly pressing, especially since the outbreak of COVID-19 pandemic in the early of 2020. To meet this demand, a promising strategy is to introduce cloud computing and digital twin techniques into the healthcare systems, where the cloud server is employed for storing healthcare data and offering efficient query services, and the digital twin is used for building digital representation for patients and leverages the query services of the cloud server to monitor healthcare states of patients. Although several cloud computing and digital twin based healthcare monitoring frameworks have been proposed, none of them has considered the data privacy issue, yet the leakage of the private healthcare information may cause catastrophic losses to patients. Aiming at the challenge, in this paper, we propose an efficient and privacy-preserving similarity query based healthcare monitoring scheme over digital twin cloud platform, named PSim-DTH. Specifically, we first formalize a similarity query based healthcare monitoring model over digital twin cloud platform. Then, we deploy a partition-based tree (PB-tree) to index the healthcare data and introduce matrix encryption to propose a privacy-preserving PB-tree based similarity range query (PSRQ) algorithm. Based on PSRQ algorithm, we propose our PSim-DTH scheme. Both security analysis and performance evaluation are extensively conducted, and the results demonstrate that our proposed PSim-DTH scheme is really privacy-preserving and efficient.

Similarity query over genomic sequences has played a significant role in personalized medicine and has applications in various fields, including DNA alignment and genomic sequencing. Since handling genomic sequences requires massive storage and considerable computational capacity, service providers prefer to process similarity queries over genomic sequences on cloud servers rather than at the client side. Due to the sensitivity of genomic sequences, preserving the privacy of queries has attracted considerable attention, and as a result, genomic sequences are demanded to be outsourced in an encrypted form. Although many schemes have been proposed for similarity queries over encrypted genomic data, they are either inefficient or have limitations in supporting the dynamic update of the dataset. To address the challenges, we propose an efficient and privacy-preserving similarity range query scheme, namely EPSim-GS. First, we introduce how to build a hash table to index the dataset, and present a similarity range query algorithm based on the hash table. Then, we design two cloud-based privacy-preserving protocols based on the Paillier cryptosystem to support the similarity range query algorithm over the encrypted dataset. After that, we propose EPSim-GS by leveraging the two privacy-preserving protocols. We then analyze the security of EPSim-GS and prove that it is privacy-preserving. Finally, we perform experiments to evaluate the scheme’s performance, and the results indicate that it is computationally efficient.

A corpus of recent work has revealed that the learned index can improve query performance while reducing the storage overhead. It potentially offers an opportunity to address the spatial query processing challenges caused by the surge in location-based services. Although several learned indexes have been proposed to process spatial data, the main idea behind these approaches is to utilize the existing one-dimensional learned models, which requires either converting the spatial data into one-dimensional data or applying the learned model on individual dimensions separately. As a result, these approaches cannot fully utilize or take advantage of the information regarding the spatial distribution of the original spatial data. To this end, in this paper, we exploit it by using the spatial (multi-dimensional) interpolation function as the learned model, which can be directly employed on the spatial data. Specifically, we design an efficient SPatial inteRpolation functIon based Grid index (SPRIG) to process the range and kNN queries. Detailed experiments are conducted on real-world datasets. The results indicate that, compared to the traditional spatial indexes, our proposed learned index can significantly improve the index building and query processing performance with less storage overhead. Moreover, in the best case, our index achieves up to an order of magnitude better performance than ZM-index in range queries and is about 2.7 × , 3 × , and 9 × faster than the multi-dimensional learned index Flood in terms of index building, range queries, and kNN queries, respectively.

Enabled by the flourishing Internet-of-Things technology, smart cities can offer a variety of smart services to our daily lives and have received considerable attention in recent years. As a pivotal component of smart cities, location-based services (LBSs) have been deeply exploited by both academia and industry. Meanwhile, since cloud computing can provide reliable and flexible IT resources, many LBS services have been outsourced to the cloud for offering better services. Nevertheless, as the cloud is not fully trusted, privacy preservation becomes an essential requirement for these services. Over the past years, many privacy-preserving location-based k-nearest neighbor ( kNN) query schemes over the cloud have been proposed. However, most of them are subjected to an inevitable design defect, i.e., whenever a user queries twice at the same location, the cloud can identify and return the same query result to the query user, and such information together with third-party data breaches could be exploited by the cloud for some location disclosures. Although some existing schemes can cope with the issue, they are not quite practical, as they will bring heavy overheads on the query user side. In this article, aiming to address the above challenge, we propose a novel oblivious location-based kNN query scheme, in which the cloud cannot link two queries even if they are initiated by query users at the same location. Specifically, based on the modified Paillier cryptosystem, we first present three privacy-preserving protocols, namely, oblivious absolute value calculation, sorting, and top- k extraction. Then, by integrating these three protocols, we propose our novel oblivious location-based kNN query scheme. The detailed security analysis shows that our proposed scheme really enhances the privacy preservation in LBS queries. In addition, extensive performance analysis and experiments are conducted, and the results indicate that our proposed scheme is also efficient for the query user.

The sixth-generation (6G) communication technology has been attracting great interests from both industry and academia, as it is regarded as a promising approach to achieve more stable and low-latency communication. These promising features of 6G make it an enabler for cybertwin, a technique to create digital representations for physical objects to implement various functionalities. In this article, we consider a cybertwin-based spatiotemporal keyword query service over a dynamic message data set in intelligent transportation system (ITS) scenarios. Particularly, in the considered service, publishers upload messages to the cloud, and each cybertwin predictively launches queries to retrieve messages on behalf of the corresponding vehicle, such that each vehicle can timely receive messages that are of its interest whenever it arrives at a location. Nevertheless, as the cloud is not fully trustable, there exist privacy concerns related to the messages and queries. Up to now, although many schemes have been proposed to handle privacy-preserving spatial, temporal, or keyword queries, none of them can simultaneously support queries containing both spatial, temporal, and keyword criteria on dynamic data sets. Aiming at the issue, we design a layered index based on segment trees to dynamically organize messages containing both spatial, temporal, and keyword information. Moreover, based on a symmetric homomorphic encryption scheme, we encrypt the messages and queries and present a two-server privacy-preserving spatiotemporal keyword query scheme. We analyze the security of the proposed scheme and also conduct extensive experiments to evaluate its performance. The results show that our proposed scheme is indeed privacy preserving and computationally efficient.

The emergence of mobile crowdsensing (MCS) has provided us with unprecedented opportunities for both sensing coverage and data transmission. However, in many MCS applications, the MCS workers are usually required to report the location information of the assigned tasks, which inevitably reveals the workers' location information, even trajectories, and severely impedes the popularization of the MCS system. It is believed that the query on the most-frequent location, e.g., querying the most congested location over a period in a city, is one of the most popular statistics queries in the MCS system, but it may disclose workers' location information. To address the issue, in this article, we propose a location privacy-preserving scheme for outsourced most-frequent item query in the MCS system, where two noncollusive semi-trusted cloud servers cooperatively handle the most-frequent item query. Specifically, by employing our pseudonymization mechanism, transposition cipher, ciphertext packing technique, and order-preserving merge function, our proposed scheme can efficiently answer the most-frequent item query while ensuring the privacy of both workers' personal information and query results. Detailed security analysis shows that our proposed scheme is privacy-preserving. In addition, extensive experiments are conducted, and the results show that our proposed scheme outperforms alternative schemes in terms of computational costs and communication overhead.

By integrating various connected devices, it is possible for smart cities to optimize the efficiency of various aspects of city operations. In particular, connected vehicles in smart cities, which are coordinated by Intelligent Transportation Systems (ITS), can not only enjoy enhanced safety and efficiency, but also offer content dissemination services through smart cities. In order to achieve effective content dissemination, a vehicle selection approach usually needs to be involved to select a limited number of vehicles while disseminating content to a city as wide as possible. However, such an approach inevitably requires the trajectories of vehicles, which are private to the vehicles. In this paper, to preserve the trajectory privacy of the vehicles during the vehicle selection, we propose a privacy-preserving vehicle selection scheme for effective content dissemination. Specifically, in the proposed scheme, given encrypted trajectories of n vehicles, a cloud with two non-collusive servers can select k vehicles that jointly cover an approximately optimal area of the city. Detailed security analysis and performance evaluation show that our proposed scheme can not only preserve the privacy of vehicles' trajectories, but also achieve efficient vehicle selection with an approximately optimal coverage.

The advance of smart eHealthcare and cloud computing techniques has propelled an increasing number of healthcare centers to outsource their healthcare data to the cloud. Meanwhile, in order to preserve the privacy of the sensitive information, healthcare centers tend to encrypt the data before outsourcing them to the cloud. Although the data encryption technique can preserve the privacy of the data, it inevitably hinders the query functionalities over the outsourced data. Among all practical query functionalities, the similarity range query is one of the most popular ones. However, to our best knowledge, many existing studies on the similarity range query over outsourced data still suffer from the efficiency issue in the query process. Therefore, in this paper, aiming at improving the query efficiency, we propose an efficient privacy-preserving similarity range query scheme based on the precomputed distance technique. In specific, we first introduce a pre-computed distance based similarity range query (PreDSQ) algorithm, which can improve the query efficiency by precomputing some distances. Then, we propose our privacy-preserving similarity query scheme by applying an asymmetric scalar-product-preserving encryption technique to preserve the privacy of the PreDSQ algorithm. Both security analysis and performance evaluation are conducted, and the results show that our proposed scheme is efficient and can well preserve the privacy of data records and query requests.

The vision of future intelligent information society will be globally data driven, enabled by Internet of Things (IoT) techniques. In any IoT-enabled applications, huge volumes of time-series data are continuously generated by IoT devices, which will be fed for high-level functions. Among these functions, the max aggregation query over a specific time interval is one of the frequently used operations. However, due to the limited resources in IoT devices, a common way to deal with the max aggregation query is to involve powerful cloud servers. Nevertheless, as the sensed data from IoT devices and its pattern (e.g., local ranking sequences) are usually private and the cloud servers are not fully trusted, the data should be encrypted before being outsourced to cloud servers. Obviously, the data encryption will incur some efficiency issues. In this paper, to mitigate the privacy and efficiency issues, we propose an efficient and privacy-preserving max aggregation query scheme for time-series data in IoT scenarios. Specifically, we first employ a segment tree based data structure to represent the data collected by IoT devices. Then, to protect the privacy, we leverage two encryption techniques to encrypt the data structure. With the encrypted data structure, our proposed scheme can handle a ranged max aggregation query with O(log L) time complexity, where L is the range length of the query. Detailed security analysis and performance evaluation show that our scheme can not only preserve the privacy of data and its local ranking sequences, but also achieve efficient ranged max aggregation query.

Fog-enhanced Internet of Things (IoT), which can locally process data at the network edge for better response to the IoT field and pre-computation for further efficient process at the cloud side, has attracted substantial studies in recent years. However, as the fog device is not fully trustable at the network edge, more advancement in efficiency and privacy should be considered to persuade enterprises to migrate to fog and cloud environments. With this in mind, in this paper, we propose a new communication-efficient privacy-preserving range query in the fog-enhanced IoT. The proposed scheme is characterized by employing Paillier homomorphic cryptosystem and ingenious Bloom filter data structure for simultaneously achieving better privacy and higher efficiency in the count aggregation in a privacy-preserving range query scenario. More precisely, $(n+|E|)\log n$-bit communication efficiency can be achieved by our proposed scheme where $n, |E|$ are respectively the range size and the ciphertext size. Detailed security analysis shows that our proposed scheme really achieves the privacy preservation in the range query. Extensive experiments are conducted, and the results demonstrate the efficiency of our proposed scheme.

The convergence of Internet of Things (IoT) and smart healthcare technologies has opened up various promising applications that can significantly improve the quality of healthcare services. Among those applications, predicting patients’ physical health based on their routine activities data collected from IoT devices is one of the most popular applications, where patients’ data are considered as time-series activities and patients’ physical health can be predicted by a classification model. Though many existing works have been exploited in this application, they either impose the computational costs of the classification on the healthcare center (e.g., hospitals) or delegate the cloud to process the classification without considering the privacy issues. However, since the healthcare center may not be powerful in computing and the cloud is not fully trusted, there is a high demand in offloading the computational cost of the healthcare center to the cloud while preserving the privacy of classification result against the cloud. Aiming at this challenge, in this paper, we present a novel privacy-preserving time-series activities classification algorithm by using hidden markov model (HMM). Specifically, we first design a variant of forward algorithm of HMM and further introduce a privacy-preserving variant of forward (PPVF) protocol for the variant of forward algorithm. Then, based on the PPVF protocol, we propose our classification algorithm, which can offload the computational cost of the healthcare center to the cloud and preserve the privacy of classification result. Finally, security analysis and performance show that our proposal is not only privacy-preserving but also efficient in terms of lower computational cost.

The advance of Internet-of-Things (IoT) techniques has promoted an increasing number of organizations to explore more mission-critical solutions. However, the response latency, bandwidth usage, and reliability are still challenging issues in the traditional IoT. To tackle these challenges, the fog-based IoT has become popular and the range query is one of the most frequently used operations in fog-based IoT, where given a range query, a fog node will return the aggregated data from IoT devices to the query user. Because the fog nodes are not fully trusted, there is a desire to design a privacy-preserving range query scheme in the fog-based IoT. However, most of existing privacy-preserving range query schemes are not efficient in terms of communication overhead, especially for a large-size range. Therefore, it is still a challenging issue to design a communication-efficient range query in fog-based IoT. Aiming at this challenge, in this article, we propose a new privacy-preserving range query scheme in the fog-based IoT. Specifically, we first devise an efficient homomorphic encryption scheme for maintaining data privacy and security in a range query. Then, we present a novel range decomposition technique to compile the range query, which can transform a given range query [L, U], where 0 ≤ L ≤ U ≤ n - 1, into a semi-triangular structure, and enable our proposed scheme to achieve O(log3n) communication efficiency. The detailed security analysis shows that our proposed scheme is really privacy preserving, and the extensive performance evaluation demonstrates that our proposed scheme is efficient in terms of low communication overhead and the computational cost.

Data collected from various data sources are destined to be logically interrelated but geographically distributed. Top-k query is an efficient way to find the most important objects from high volumes of data. A common way to process the top-k query over distributed data is to bring them to a centralized entity (e.g. cloud). However, there are privacy considerations during the top-k query when dealing with sensitive data (e.g. eHealthcare data) in such method. Apart from data privacy, efficiency also needs to be taken into consideration. Existing focuses on top-k query do not (fully) consider the data privacy or efficiency. In order to deal with the mentioned disadvantages, in this paper, we propose an efficient and privacy-preserving top-k query scheme over vertically distributed data. Specifically, we first design a data filtering technique to reduce the number of transmitted data from each data source to the centralized entity, which can greatly reduce the communication overhead and computational cost. Then, we propose a privacy-preserving top-k query scheme over encrypted data by deploying the homomorphic encryption technique, which can well preserve the private information and achieve the functionality at the same time. Besides, security analysis shows that the proposed scheme is privacy-preserving and performance evaluation validates the efficiency of the proposed scheme.