Sampling schemes can provide fast approximate answers to aggregation queries. However, weighted sampling must create a sample for each measure column, which leads to expensive storage cost for any table with dozens of columns. To address this issue, we generalize both measure-biased sampler and priority sampler, which can compress the samples but still provide fast approximate answers to both distribution query and subset-sum query within a user-specified error bound. We also extend the priority sampler to support multiple types of aggregates for arbitrary subset. Our generalized samplers achieve a remarkable improvement over the original samplers in terms of the error metrics.

Private learning for vertical decision trees (PVDT) is an emerging paradigm that allows multiple parties to execute cooperative training and inference of decision trees on vertically partitioned datasets, without revealing either party%'s data or model. The state-of-the-art PVDT schemes employ the secret-sharing-based secure multi-party computation (MPC) to admit low computational cost and low bandwidth. Nevertheless, existing schemes need many communication rounds for computing concrete protocols in PVDT, like the less-than comparison, division, etc. This property is not suited for large-communication-latency networks such as WAN. In this work, we present a two-party PVDT framework, calledSwan, to enable a secure, accurate, and fast realization of vertical decision trees. At the core of Swan, we design a secure and parallel protocol for$N$-input multiplication with one communication round. This forms the cornerstone for a series of secure and communication-efficient computation protocols specifically tailored to less-than comparison and division. Along the way, we use these optimized protocols to refine the training and inference processes of PVDT, achieving a significant reduction in both communication costs and rounds. Experimental results show Swan provides top-notch accuracy, and achieves a$10.2\times$and$2.8\times$improvement in online training and inference latency over WAN compared to prior art.

Clustering is widely used for data analysis that partitions a set of data into multiple clusters, where objects in the same cluster have similar properties. Data for clustering analysis often comes from different data sources, which makes it important to maintain data privacy. However, existing privacypreserving clustering schemes either require the support of prior knowledge or are just applicable for small datasets due to impractical costs. To solve this issue, we follow a classical approximate DBSCAN clustering algorithm and adapt it to the privacy-preserving context. Concretely, to construct our secure approximate clustering algorithm, we propose a series of basic secure computation protocols among additively secret-shared values. In addition, we design a crypto-friendly grid partitioning method based on which an efficient and privacy-preserving approximation DBSCAN scheme is derived. Theoretical analysis and experimental results show that our scheme achieves almost the same cluster quality compared to the plain-text exact DBSCAN. Our extensive experiments on different datasets demonstrate that our scheme is accurate and efficient.

Federated learning (FL) has gained popularity in the field of machine learning, which allows multiple participants to collaboratively learn a highly-accurate global model without exposing their sensitive data. However, FL is susceptible to poisoning attacks, in which malicious clients manipulate local model parameters to corrupt the global model. Existing FL frameworks based on detecting malicious clients suffer from unreasonable assumptions (e.g., clean validation datasets) or fail to balance robustness and efficiency. To address these deficiencies, we propose FedDMC, which implements robust federated learning by efficiently and precisely detecting malicious clients. Specifically, FedDMC first applies principal component analysis to reduce the dimensionality of the model parameters, which retains the primary parameter feature and reduces the computational overhead for subsequent clustering. Then, a binary tree-based clustering method with noise is designed to eliminate the effect of noisy points in the clustering process, facilitating accurate and efficient malicious client detection. Finally, we design a self-ensemble detection correction module that utilizes historical results via exponential moving averages to improve the robustness of malicious client detection. Extensive experiments conducted on three benchmark datasets demonstrate that FedDMC outperforms state-of-the-art methods in terms of detection precision, global model accuracy, and computational complexity.

Density-based clustering algorithms such as DBSCAN, are highly effective in handling large datasets and identifying clusters of arbitrary shapes, playing a crucial role in data analysis fields like outlier detection and social networks. Outsourcing DBSCAN to the cloud brings substantial benefits but also raises major privacy concerns regarding the private input data of data owners. Existing private DBSCAN methods often face challenges of inefficiency or potential privacy leakage, hindering their practical deployment. To address these challenges, we introduce FSS-DBSCAN, a three-server MPC platform designed for outsourced private density-based clustering using function secret sharing (FSS). This solution guarantees clustering quality equivalent to plaintext algorithms, ensures comprehensive privacy protection, and achieves top-tier efficiency. The high performance of FSS-DBSCAN is driven by two pivotal strategies. First, we devise an MPC-friendly DBSCAN algorithm that is highly compatible with efficient secret-sharing-based cryptographic protocols and benefits from GPU acceleration. Second, we construct novel FSS-based protocols tailored for complex operations integral to our DBSCAN variant, such as Euclidean distance comparison and point assignment, and further optimize their computation through tensorization techniques. We implement our platform as an extensible system on top of PyTorch that leverages GPU hardware acceleration for cryptographic and tensorized operations. These innovations enable FSS-DBSCAN to significantly outperform ppDBSCAN (AsiaCCS 2021), reducing the clustering time for 5000 samples to approximately 2 hours, achieving an$83.4\times $speed improvement.

Query with aggregates is one of the most important classes of ad-hoc queries. Since query response time is critical in many scenarios, small errors are usually tolerable for query processing. In this work, we adopt sampling to provide fast approximate answers to distribution query and subset-sum query. On the one hand, uniform sampler is sub-optimal. On the other hand, both measure-biased sampler and priority sampler need to create a sample for each measure column. It leads to expensive storage cost, when there are dozens or hundreds of measure columns in the table. To address this issue, we generalize both measure-biased sampler and priority sampler, which can compress the samples but still provide fast approximate answers to both distribution query and subset-sum query within a user-specified error bound. Besides, we establish the relationship between measure-biased sampler and priority sampler by constructing a measure-biased sample from a priority sample. We also extend the priority sampler to support multiple types of aggregates for arbitrary subset. In the extensive experimental evaluation, our generalized samplers achieve a remarkable improvement over the original samplers in terms of the error metrics.

In cloud computing, remote accesses over the cloud data inevitably bring the issue of trust. Despite strong encryption schemes, adversaries can still learn sensitive information from encrypted data by observing data access patterns. Oblivious RAMs (ORAMs) are proposed to protect against access pattern attacks. However, directly deploying ORAM constructions in an encrypted database brings large computational overhead. In this work, we focus on oblivious joins over a cloud database. Existing studies in the literature are restricted to either primary-foreign key joins or binary equi-joins. Our major contribution is to support general band joins and multiway equi-joins. For oblivious join without ORAMs, we extend the existing binary equi-join algorithm to support general band joins obliviously. For oblivious join with ORAMs, we integrate$B$-tree indices into ORAMs for each input table and retrieve blocks through the indices in join processing. The key point is to avoid retrieving tuples that make no contribution to the final join result and bound the number of accesses to each$B$-tree index. The effectiveness and efficiency of our algorithms are demonstrated through extensive evaluations over real-world datasets. Our method shows orders of magnitude speedup for oblivious multiway equi-joins in comparison with baseline algorithms.

Oblivious RAMs (ORAMs) are proposed to completely hide access patterns. However, most ORAM constructions are expensive and not suitable to deploy in a database for supporting query processing over large data. In this work, we design a practical oblivious query processing framework to enable efficient query processing over a cloud database. In particular, we focus on processing multiple range and kNN queries asynchronously and concurrently with high throughput. The key idea is to integrate indices into ORAM which leverages a suite of optimization techniques (e.g., oblivious batch processing and caching). Our construction shows an order of magnitude speedup in comparison with other baselines over large datasets.

Many individuals and companies choose the public cloud as their data and IT infrastructure platform. But remote accesses over the data inevitably bring the issue of trust. Despite strong encryption schemes, adversaries can still learn sensitive information from encrypted data by observing data access patterns. Oblivious RAMs (ORAMs) are proposed to protect against access pattern attacks. However, directly deploying ORAM constructions in an encrypted database brings large computational overhead.

Cognition involves locally segregated and globally integrated processing. This process is hierarchically organized and linked to evidence from hierarchical modules in brain networks. However, researchers have not clearly determined how flexible transitions between these hierarchical processes are associated with cognitive performance. Here, we designed a multisource interference task (MSIT) and introduced the nested-spectral partition (NSP) method to detect hierarchical modules in brain functional networks. By defining hierarchical segregation and integration across multiple levels, we showed that the MSIT requires higher network segregation in the whole brain and most functional systems but generates higher integration in the control system. Meanwhile, brain networks have more flexible transitions between segregated and integrated configurations in the task state. Crucially, higher functional flexibility in the resting state, less flexibility in the task state and more efficient switching of the brain from resting to task states were associated with better task performance. Our hierarchical modular analysis was more effective at detecting alterations in functional organization and the phenotype of cognitive performance than graph-based network measures at a single level.

Increasingly, individuals and companies adopt a cloud service provider as a primary data and IT infrastructure platform. The remote access of the data inevitably brings the issue of trust. Data encryption is necessary to keep sensitive information secure and private on the cloud. Yet adversaries can still learn valuable information regarding encrypted data by observing data access patterns. To solve such problem, Oblivious RAMs (ORAMs) are proposed to completely hide access patterns. However, most ORAM constructions are expensive and not suitable to deploy in a database for supporting query processing over large data. Furthermore, an ORAM processes queriessynchronously, hence, does not provide high throughput forconcurrent query processing. In this article, we design a practicaloblivious query processing frameworkto enable efficient query processing over a cloud database. In particular, we focus on processing multiple range and$k$NN queriesasynchronously and concurrently with high throughput. The key idea is to integrate indices into ORAM which leverages a suite of optimization techniques (e.g., oblivious batch processing and caching). The effectiveness and efficiency of our oblivious query processing framework is demonstrated through extensive evaluations over large datasets. Our construction shows an order of magnitude speedup in comparison with other baselines.

The wide presence of large graph data and the increasing popularity of storing data in the cloud drive the needs for graph query processing on a remote cloud. But a fundamental challenge is to process user queries without compromising sensitive information. This work focuses on privacy preserving subgraph matching in a cloud server. The goal is to minimize the overhead on both cloud and client sides for subgraph matching, without compromising users' sensitive information. To that end, we transform an original graph $G$ into a privacy preserving graph Gk, which meets the requirement of an existing privacy model known as k-automorphism. By making use of the symmetry in a k-automorphic graph, a subgraph matching query can be efficiently answered using a graph Go, a small subset of Gk. This approach saves both space and query cost in the cloud server. We also anonymize the query graphs to protect their label information using label generalization technique. To reduce the search space for a subgraph matching query, we propose a cost model to select the more effective label combinations. The effectiveness and efficiency of our method are demonstrated through extensive experimental results on real datasets.

Many companies choose the cloud as their data and IT infrastructure platform. The remote access of the data brings the issue of trust. Despite the use of strong encryption schemes, adversaries can still learn valuable information regarding encrypted data by observing the data access patterns. To that end, one can hide the access patterns, which may leak sensitive information, using Oblivious RAMs (ORAMs). Numerous works have proposed different ORAM constructions, but they have never been thoroughly compared against and tested on large databases. There are also no open source implementation of these schemes. These limitations make it difficult for researchers and practitioners to choose and adopt a suitable ORAM for their applications. To address this issue, we provide a thorough study over several practical ORAM constructions, and implement them under the same library. We perform extensive experiments to provide insights into their performance characteristics with respect to efficiency, scalability, and communication cost.