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.

Fully Homomorphic Encryption (FHE) allows computations on encrypted data. However, FHE faces significant performance overhead due to the time-consuming homomorphic multiplications and bootstrapping operations, which limits its practical applications. Meanwhile, many FHE optimization schemes have been proposed based on a Trusted Execution Environment (TEE), but they heavily rely on the trustworthiness of the TEE. In outsourcing scenarios, the TEE owner might be a third-party service provider, posing a risk of data leakage for users. To address these issues, we propose an efficient BGV scheme with semi-honest TEE assistance. We consider the TEE to be honest-but-curious, meaning the TEE owner might eavesdrop on the user's data during computation. Based on this assumption, we design a new BGV homomorphic multiplication protocol that operates in a smaller ciphertext space without compromising the original security level and substantially improves computational efficiency. With the assistance of a semi-honest TEE, our multiplication protocol eliminates the need for the switch key, reducing initialization time and supporting an unlimited number of homomorphic multiplication operations without bootstrapping. Furthermore, we provide a security proof using a simulationbased real/ideal world model. Extensive experiments show that our scheme outperforms mainstream libraries such as SEAL, OpenFHE, and Helib.

The cloud-edge computing model has been expected to play a revolutionary role in promoting the quality of future generation large-scale Internet of Things (IoT) services. However, security and privacy in data sharing remain crucial issues hindering the success of cloud-edge IoT services. While some solutions based on attribute-based encryption (ABE) have been proposed to address these issues, they still face practical challenges such as attribute privacy leakage, resource-constrained devices, dynamic user groups, inflexible and inefficient service response. To address these challenges, this paper proposes a privacy-preserving fine-grained data sharing scheme with dynamic service (PF2DS), which implements access control by calculating the inner product between an attribute vector and an access vector. PF2DS is also capable of providing dynamic user group services through an efficient and indirect user revocation mechanism that periodically updates the key-embedded leaf nodes. Building on PF2DS, edge-assisted PF2DS (EPF2DS) delegates most of the operations to the edge device, which facilitates the performance of resource-constrained IoT devices. EPF2DS also supports efficient and asynchronous keyword search over the ciphertexts stored in the cloud. We demonstrate the security by the rigorous security proof. Both theoretical comparisons and experimental simulations demonstrate the practicality and superiority of our schemes over existing works.

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.

The diverse properties of wireless networks are fulfilled with the assistance of digital twin (DT), which utilizes a virtual model of the physical object (PO) to provide predictions and control decisions. However, the open wireless channels and key leakage of compromised entities (including DT and PO) pose significant security issues, highlighting the need for secure data transmission schemes. Meanwhile, it is impractical to directly apply the existing works and cryptographic primitives to DT-empowered wireless networks (DTWNs) due to the absence of a solution to capture the security requirements comprehensively. Moreover, the essential characteristics for protecting historical data cannot be met. Therefore, this paper proposes a security-enhanced data transmission scheme with fine-grained and flexible revocation by customizing a novel cryptographic primitive named forward-secure puncturable signed encryption (FS-PSE). Our scheme enables confidential data dissemination/acquisition between the physical and virtual space while ensuring authentication of the real-time information and feedback results. In addition, three revocation modes are defined. Based on these modes, the entities can flexibly revoke any decryption-&-signature, decryption, and signature capability in a fine-grained approach, thereby providing security protections for the historically transmitted data even though the entity is compromised. Moreover, our scheme is instantiated with a concrete FS-PSE construction and extended to support outsourced computing to improve efficiency. Finally, the formal security proof and performance evaluation demonstrate the security and practicality of our scheme.

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.

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.

Low Earth orbit satellite constellations with seamless network coverage and onboard computers enable autonomous on-orbit anomaly identification of remote wind turbines. However, they face several challenges. First, limited visible periods caused by orbital characteristics mandate that one satellite holds anomalies and the other collects surveillance data. Second, passively injected satellites could intercept and grasp onboard message flows. Third, a restricted onboard energy supply budget restrains intersatellite communications and onboard computations. With the above challenges, we propose a secure on-orbit anomaly identification (SOAI) scheme between a pair of satellites through an$\text{XOR}$filter, which further exploits laconic private set intersection to eliminate false positives. The secure on-orbit anomaly querying scheme achieves the verifiable querying of anomalies derived from$\text{SOAI}$. Comprehensive security analysis shows that the$\text{SOAI}$scheme achieves confidentiality under a simulation-based real/ideal world model. Moreover, we compare the$\text{SOAI}$scheme with two baseline schemes in terms of communication overheads and computational costs, and evaluation results show that our scheme outperforms the compared schemes, and our scheme is feasible in the OneWeb constellation near the polar regions.

In vehicular digital twin networks (VDTNs), digital twin (DT) can assist the vehicle in data handling and report traffic data to the management server, thereby providing enhanced and scalable services for intelligent transport systems. However, the reported data may suffer from forgery and eavesdropping attacks due to the transmission on the open channel. In addition, a critical threat in VDTNs is the physical vehicle capture attack, namely, an adversary is capable of compromising the vehicle to obtain the current secret key, which can break the reliability of historical reported data and make the services provided by DT unavailable. Puncturable signature (PS) is a promising solution to eliminate these concerns, despite that the existing PS constructions have non-negligible false-positive errors and impose a significant cost on practical deployments. In this paper, we design a novel PS and apply it to privacy-aware data reporting protocol (PA-DRP) for VDTNs. Specifically, the designed PS adopts a derivationbased way to achieve puncturing functionality, which is free from false-positive errors while extremely reducing the storage overhead of the secret keys. Meanwhile, we employ the designed PS to construct PA-DRP that enjoys authentication and forward security. Additionally, PA-DRP not only allows DT to remove privacy-sensitive information from the signed data but also provides fuzzy identity for protecting the real identity of the vehicle. Furthermore, the security analysis and performance evaluation demonstrate that the designed PS and PA-DRP not only can withstand various security and privacy assaults for VDTNs but also are efficient and practical.

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.

Human-Object Interaction (HOI) detection, which aims to identify humans and objects with interactive behaviors in images and predict the behaviors between them, is of great significance for semantic understanding. The existing works primarily focus on exploring the fine-grained semantic features of humans and objects, as well as the spatial relationships between them. However, these methods do not leverage the contextual information within the interaction area, which could potentially be valuable for predicting interaction behavior. To investigate the impact of contextual information on behavior prediction, we propose a novel approach to extract both independent and interactive features and fuse them. Specifically, our method is capable of extracting interaction features from the interaction region. These features are then merged with fine-grained independent features of humans and objects. Finally, the fused features are utilized to predict interaction behavior. In addition, the feature fusion module does not add extra storage and computation costs to our method. Experiments demonstrate the effectiveness of our method, achieving state-of-the-art performance on two benchmark HOI datasets, namely HCO-DET and V-COCO.

The low-Earth orbit (LEO) satellite constellation holds immense potential for offshore wind farm surveillance since it can provide all-day and all-weather monitoring capabilities facilitated by satellite collaboration. However, it faces significant challenges. First, limited downlink transmission bandwidth constrained by ground stations and constraint on-orbit resources necessitate selective data downloads, focusing only on differences between consecutive data sets. Second, a passively injected satellite in open space poses a risk of unauthorized data extraction from neighboring satellites. Third, onboard energy constraints limit the feasibility of computationally intensive cryptographic operations. To tackle these challenges for the first time, we propose a novel secure and efficient on-orbit comparison (SEOC) scheme. Our solution begins with introducing a lightweight matrix encryption-based secure inner product (MSIP) technique tailored for secure on-orbit comparison. We further enhance communication efficiency by integrating a Cuckoo filter to reduce costs, complementing a novel difference comparison tree (DCTree) structure to manage false positives. Through comprehensive security analysis, the$\textsf {MSIP}$technique achieves selective security, and the$\textsf {SEOC}$scheme is secure under the universally composable (UC) framework. At last, performance evaluations demonstrate the high efficiency of our approach in terms of computational costs and communication overheads, which adapts to the limited on-orbit resources.

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.

As a practical machine learning method, the K-nearest neighbors (KNN) classification has received widespread attention. The achievement of the KNN classification relies heavily on a large amount of labeled data. However, in the real world, data is often held by different data owners. How to realize efficient joint computing among multiple data owners under the premise of protecting data security and privacy is an urgent problem to be solved. In this paper, we construct a secure multi-party KNN classification scheme (SecKNN) based on function secret sharing (FSS) technology, which is a novel cryptographic primitive and can achieve cheap communication and computation costs for secure computation. Compared with the existing works, our scheme dramatically reduces computational overhead and runs roughly 50.8 times faster than the state-of-the-art approach. Furthermore, our scheme supports the secure KNN classification under general distance functions such as Euclidean distance, Manhattan distance, and Hamming distance. To implement our SecKNN scheme, we design two efficient FSS schemes for Hamming distance function, which implements secure two-party and multi-party Hamming distance computation in a single round. They can be considered as independent research results. Finally, we give formal security proofs for the proposed protocols and validate the effectiveness and efficiency of our protocols through experiments.

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.

The low Earth orbit (LEO) satellite edge computing paradigm provides remote sites with flexible, reliable, and scalable edge computing capabilities. Characterized by the orbital motion patterns and harsh space environments, the LEO satellite edge computing faces unique security challenges in terms of the secure collaboration of multiple satellites and the intellectual property protection of models. Under the unique space environment and security demands, we propose a secure satellite edge computing framework in this paper. By taking a remote electricity line outage identification use case as an example, our framework first achieves the secure delegation of the line outage identification task among multiple satellites, which is realized through a secure query$(\mathsf {SQuery})$scheme to check the availability of the target time slot. Meanwhile, we also design a SHE-enabled secure inner-product encryption ($\mathsf {SSIPE}$) protocol, to achieve the secure multinomial logistic regression (MLR) based line outage identification on-orbit. To reduce the complexity brought by the computationally intensive homomorphic multiplication between two ciphertexts, we further grasp the idea and design a “divide-and-conquer” based secure query ($\mathsf {DSQuery}$) scheme, which converts this homomorphic multiplication operation between ciphertexts into the homomorphic addition operation. As far as we know, this is the first scheme investigating the secure task delegation among different satellites on-orbit. Besides, detailed security analyses are performed to demonstrate the security properties of confidentiality and authentication. In performance evaluations, we test and compare the computational and communication overhead of our scheme and other straightforward schemes. Simulation results show that the$\mathsf {DSQuery}$scheme greatly reduces the computational cost, which saves the stringent on-orbit computation resources of LEO satellites.

Geographic information system (GIS) enables operations for capturing, manipulating, analyzing, and displaying the spatial characteristics of objects on Earth's surface. As the objects in GISs are mostly location-dependent, various location privacy-preserving schemes are proposed to support the secure spatial query and analysis. However, existing location privacy-preserving mechanisms mainly focus on the$k$-nearest neighbor ($k$NN) queries and range queries and fail to consider the practical geographic implementation with quad-trees. We propose an efficient and privacy-preserving point-of-interest (POI) query scheme along the movement trajectory under the quad-tree setup in a two-server mode. Specifically, we first convert the secure identification of the target lowest-level tile into a series of private information retrieval (PIR) processes and securely derive the target POIs along the movement trajectory within the identified tile by constructing a linear polynomial passing through the origin and destination for secure distance comparison. Our scheme also supports the efficient loading of POIs contained in the adjacent tiles with privacy preservation. Security analysis demonstrates that ours can achieve the security goals of privacy preservation and confidentiality. We execute performance evaluations to show and validate the system efficiency, i.e., computational costs and communication overheads.

Vehicular social networks (VSNs), as the convergence of social networks and vehicular ad hoc networks, have brought many useful services to vehicle communication by collecting and sharing data between vehicles. In order to efficiently share data and satisfy the growing requirement of privacy protection, data owners typically encrypt and outsource the data to the cloud. Nevertheless, encryption undoubtedly reduces the availability of shared data, e.g., keyword search. Although a number of schemes supporting keyword search of shared data have been put forward, they still have issues with respect to security, functionality, and efficiency. In this paper, a server-assisted data sharing (SADS) system with support for conjunctive keyword search is presented. Specifically, to resist online keyword guessing attack, we devise an advanced keyword derivation mechanism to derive the keyword set, in which the conception of verifiable parallel oblivious unpredictable function is proposed to check whether the assisted server honestly responds to the derived keyword request. Moreover, the computation and communication costs of keyword trapdoor in SADS are constant. Concurrently, SADS achieves the anonymous data sharing and traceability of malicious vehicle data owner. The security of SADS is formally proved and analyzed. Performance evaluation also shows that our system is efficient and practical.

While online medical diagnosis provides significant convenience to users, it also incurs the risk of privacy breaches, which inspired the emergence of various privacy-preserving online medical schemes. Nonetheless, existing schemes either compromise partial privacy to third parties or rely on cryptographic methods with high computational complexity. In particular, they do not anticipate user’s disputes to the extent that there is no audit process to guarantee the correctness of the diagnosis results and the fairness of the schemes. Consequently, we propose an efficient and privacy-preserving online medical diagnosis scheme based on additive secret sharing (ASS). First, the anonymity of the user is provided in the medical diagnosis process, which ensures that the cloud cannot link the diagnosis results to the user. Then, we devise a minimum value protocol and a range comparison protocol to enhance the security of the online diagnosis. In addition, considering user’s disputes that arise in realistic scenarios (e.g., malicious users may cheat the diagnosis system for personal benefits), we construct a blockchain-based audit process to detect user’s behaviors and settle controversies. Finally, we demonstrate the security and efficiency of the proposed scheme with theoretical analysis and experimental evaluation.

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.

Outsourcing decision tree (DT) inference to cloud servers can be beneficial for model providers who wish to share their model with potential clients. However, model owners may not want to publicly disclose all model details due to the investment of time and money that is put into training their models. Therefore, ensuring model privacy while making models available to clients is of grave importance to the model provider. To ensure the privacy of the DT models, the client query, and the final classification of the model, several privacy preserving DT schemes have been proposed. However, most existing schemes require significant communication or computational overhead. In this paper, we propose a privacy preserving scheme for DT inference, which is characterized by employing Bloom filters to hide the original DT structure while providing reliable classification results. Security and performance analysis verify the security and efficiency of our proposed 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.

Graph technology has been attracting interest due to its ability in modeling complex network and real-world relationships in various applications. Subgraph matching queries are useful tools that can be used to extract structural insights from graph dataset. As the accuracy of subgraph matching queries increases with graph size, it is natural to consider providing subgraph matching query services over a graph federation, which can form a larger graph by combining graphs from multiple data owners. However, the downside combining data is that it may provoke privacy concerns related to the graph datasets and user queries. Although many schemes have been proposed for privacy-preserving subgraph matching queries, they either cannot be extended to graph federation scenarios or do not consider query privacy. Aiming at this challenge, in this paper we construct an efficient and privacy-preserving subgraph matching query scheme in graph federation with two data owners. In the proposed scheme, the two data owners jointly compute the neighboring signatures of all vertices without disclosing their graph datasets to each other. Upon receiving a subgraph matching query, the data owners together respond with a subgraph which includes all subgraphs matching the pattern in the combined graph. Security analysis shows that our proposed scheme can well preserve data and query privacy. Extensive experiments further demonstrate that the scheme is efficient in terms of computation and communication.

Worker selection that is often outsourced to a cloud server is crucial for the success of the Mobile Crowdsensing (MCS) system, in which the spatial constraint plays a fundamental role in selecting workers. To protect the location information involved in the spatial constraint, several privacy-preserving worker selection schemes were proposed. However, they either only support a specific spatial range or cannot trace the workers who leak secret keys. In this paper, we propose a traceable and privacy-preserving worker selection scheme that can support arbitrary spatial ranges when selecting workers and trace the worker when his/her secret key is leaked to the cloud server for inferring location information. Security analysis demonstrates the privacy preservation and traceability of our proposed scheme, and the evaluation results illustrate its efficiency.

The explosions of mobile communications and the Internet of Things (IoT) have spawned a new distributed computing paradigm—spatial crowdsourcing, in which workers actively participate in spatiotemporal computing tasks for earning commissions, facilitating the development of urban sharing economic services. Furthermore, to reduce users’ storage space and computational overhead, the server assignment model (SAM) is widely used, which means that crowdsourcing platforms collect sensitive information about tasks and workers, e.g., locations and interests, to perform task assignments accurately. However, in the real world, crowdsourcing platforms are not fully trustworthy and may reveal sensitive information about workers and tasks, which can reduce users’ motivation to use crowdsourcing services. Therefore, how to assign tasks efficiently and securely is still an urgent problem to be solved. In this article, we propose a privacy-preserving task assignment scheme (PPTA), in which the crowdsourcing platform efficiently implements the nearest task assignments without revealing sensitive information about tasks and workers. In PPTA, we utilize inner product functional encryption to achieve circular range queries and multikeyword queries. Considering that workers usually prefer to query the nearest tasks for reducing travel costs, we use the grid location intersection to enable the nearest task assignment. In particular, we design a SAM algorithm, which can improve task assignment rates in multitask and multiworker scenarios. In addition, our scheme can implement user accountability and user revocation, which enhances the security and practicality of the scheme. Finally, we demonstrate the privacy preservation through security theoretical proofs and show the efficiency by constructing extensive comparative experiments, which respectively illustrate the security and the effectiveness of our scheme.

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.

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.

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.

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.

With the proliferation of smart devices with various onboard sensors, mobile crowdsourcing has attracted consider-able interest, in which task scheduling is an essential service for allocating tasks to workers. As the number of workers increases, the service provider prefers to outsource the service to a powerful cloud, and the messages from the workers and the task owners should be protected. Currently, the existing works on privacy-preserving task allocation cannot simultaneously achieve strong privacy protection and dynamic update. Aiming at this challenge, we propose a privacy-preserving outsourced task scheduling scheme, in which the cloud servers can obliviously conduct task scheduling and update the workers' information based on the scheduling results. To this end, we design three secure protocols under a two-server model, which can protect the protocols' input and output against the cloud servers. The security analysis demonstrates that our proposed scheme can achieve strong privacy protection, and the experimental results indicate the scheme's efficiency in computing and communication.

Applying skyline queries to medical data can considerably benefit medical analysis in eHealthcare. However, as medical data often involves sensitive personal data, privacy concerns have become a significant impediment to the development of eHealthcare. Although several privacy-preserving skyline query schemes in eHealthcare have been put forth, they need a trusted platform to generate and assign secret keys for the multi-source scenario. In addition, those schemes incur non-trivial computational costs on resource-limited entities. To address these limitations, we propose a novel privacy-preserving skyline query scheme, named PPsky, based on arithmetic secret sharing, in which a series of secure protocols are designed to handle the basic operations in skyline queries. Security analysis illustrates that our PPsky scheme is privacy-preserving, and the evaluation results also validate the efficiency of our PPsky 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.

Worker selection is one of the most fundamental problems in Mobile Crowdsensing (MCS) applications. In this paper, we formulate a practical worker selection scenario in MCS services where the selected workers should meet both the spatial and temporal constraints. To protect participants’ (both the task requestor and the workers) personal information from being disclosed, we design a privacy-preserving worker selection scheme based on the Symmetric Homomorphic Encryption (SHE) technique. Besides, we devise a pre-filtering process to further increase the efficiency of the worker assignment process. Security analysis shows that our proposed scheme can achieve the desirable security properties. In addition, extensive experiments are conducted to validate the effectiveness of the proposed 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.

Mobile Crowdsourcing (MCS) is a newly-emerged sensing paradigm where a group of workers is selected to collect and share real-time data for a particular task. With the recent advances of Internet of Things (IoTs), cloud computing, and 5G network, MCS has drawn great attention in recent years. Worker selection is one of the most fundamental problems in MCS, as the selected workers’ qualifications play a significant role in the service quality. In this paper, by extending the research scope of previous literature, we formulate a novel worker selection problem in MCS that incorporates spatial-temporal constraints over workers’ tentative future trajectories. Specifically, each worker is required to submit a tentative future trajectory in advance and the MCS platform only selects qualified workers who meet both the spatial and temporal constraints. To increase the efficiency of worker selection, we propose a hybrid indexing approach to efficiently index workers’ spatial-temporal information by combining MX-CIF quadtree and Interval tree. Besides, we design a greedy algorithm, which considers both the reliability of the selected workers and the overall budget at the same time. Furthermore, to protect workers’ sensitive spatial-temporal information from being disclosed to untrusted parties, we design a privacy-preserving technique by transferring workers’ real spatial-temporal information to the approximate data with restricted information. Security analysis shows that the proposed solution is privacy-preserving. Extensive experiments are conducted, and the results demonstrate that our scheme outperforms the baseline methods.

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.

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.

Outsourcing data to the cloud has become popular due to the big data challenges. However, security concerns compel the outsourced data to be encrypted before sending them to the cloud, which lowers their utility and efficiency. The range query plays a significant role in common queries. Consequently, how to efficiently support the range query over encrypted data has become an important challenge. Previously reported schemes either achieve efficiency only in a specific operation or have severe defects in scalability. To address these limitations, we propose a framework, called SOREL, which simultaneously considers security, efficiency and scalability. Specifically, we first propose a new efficient and Secure Order Revealing Encryption (SORE) scheme, which is more secure than bit-based ORE schemes. Then, by employing the proposed SORE scheme, we design a novel index within our framework SOREL to support efficient updating and query operations over encrypted data. Detailed security analysis shows that our SOREL achieves the desirable security requirements. Additionally, results from extensive evaluations indicate that i) SORE outperforms other alternative schemes by at least 8; and ii) SOREL is at least 3faster than the comparative schemes with range query operation in the best case while ensuring the competitiveness with insertion operation.

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.

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.

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.

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.