Federated learning (FL) has attracted increasing attention in recent years due to its data privacy preservation and great applicability to large-scale user scenarios. However, when FL faces numerous clients, it is inevitable to emerge the non-independent and identically distributed (non-iid) data between clients, which brings an enormous challenge for model training and performance analysis like convergence. Besides, due to the non-iid data, the participating clients of FL tend to be extremely heterogeneous so the number of samplings among clients causes a sampling variance problem, which induces a huge variation in convergence. More importantly, although FL can foster privacy security via locally retaining the training data, if local data is secret and sensitive, FL should have more powerful privacy protection to resist the cloud server or third party to infer private information from shared models or intermediate gradients. Facing the non-iid and privacy challenges, we propose a differential privacy (DP) based non-iid FL algorithm called DPNFL to jointly tackle these two issues. Specifically, motivated by the DP and its variants, we are the first to adopt the truncated concentrated differential privacy technique under the FL scenario to more tightly track end-to-end privacy loss, while requiring less noise injection for the same level of DP. To avoid the sampling variance problem, we enable the server to sample the partial clients uniformly without replacement, which also guarantees unbiased sampling. To further improve the algorithm performance, we also propose an adaptive version of DPNFL named AdDPNFL, which adopts the adaptive optimization on the server-side to simultaneously alleviate the impact of non-iid data and DP noise on model utility. Finally, we perform extensive experiments to validate the effectiveness and superiority of our algorithms.

Supporting efficient and secure location-based skyline queries on encrypted data, such as private data outsourced to cloud-based systems, remains an ongoing challenge for efficiency due to significant computational costs in the ciphertext domain. To accelerate privacy-preserving skyline queries, the secure index intuitively contributes to an increase in efficiency. However, designing such a secure index is a challenge while protecting the unlinkability of queries. Meanwhile, there exist little work that can commendably assure efficiency and security. In this paper, we demonstrate SecSky, an efficient solution for supporting secure location-based skyline queries through the secure index. To support SecSky, we devise a novel unified structure, named secure R-tree (SR-tree) index, without privacy leakage (especially indirect privacy). Subsequently, we propose a novel secure location-based dominance protocol, which is utilized to calculate the dominance relationship on the SR-tree. Using this protocol as the building block, our secure location-based skyline query protocol integrates SR-tree, permutation and perturbation techniques to facilitate query processing so as to dramatically reduce the computational overhead. Meanwhile, our proposed solution avoids compromising the privacy of datasets, queries, dominance relationship and skyline results. Finally, we analyze the complexity and security of SecSky. Findings from the experimental evaluation show that our proposed scheme outperforms several other protocols by at least 3 orders of magnitude in terms of query efficiency.

Supporting secure location-based services on encrypted data that is outsourced to cloud computing platforms remains an ongoing challenge for efficiency due to expensive ciphertext calculation overhead. Furthermore, since the clouds may not be trustworthy or even malicious, data security and result authenticity has caused huge concerns. Unfortunately, little work can enable query efficiency, dataset confidentiality and result authenticity to be commendably guaranteed. In this paper, we demonstrate the potential of supporting secure and verifiable location-based skyline queries (SVLSQ). First, we devise a novel and unified structure, named semi-blind R-tree (SR-tree), which protects the query unlinkability. Based on SR-tree, we propose an authenticated data structure, named secure and verifiable scope R-tree (SVSR-tree). Then, we develop several secure protocols based on SVSR-tree to accelerate the query efficiency and reduce the size of verification objects. Our method avoids compromising the privacy of datasets, queries, results and access patterns. Meanwhile, it authenticates the soundness and completeness of the skyline results while preserving privacy. Finally, we analyze the complexity and security of SVLSQ. Findings from the performance evaluation illustrate that SVLSQ is a dramatically efficient method in terms of query (no less than 3 orders of magnitude faster than other solutions) and verification.

Deep learning is increasingly popular, partly due to its widespread application potential, such as in civilian, government and military domains. Given the exacting computational requirements, cloud computing has been utilized to host user data and model. However, such an approach has potential privacy implications. Therefore, in this paper, we propose a method to protect user’s privacy in the inference phase of deep learning workflow. Specifically, we use an intermediate layer to separate the entire neural network into two parts, which are respectively deployed on the user device and the cloud server. Theencoder, deployed on the user device, is used for raw data transformation, which removes the need for users to upload raw data to the cloud directly. However, we also demonstrate there exists potential for privacy leakage in the intermediate features of the neural network through two concrete experiments. In other words, the encoder on its own does not provide adequate privacy protection. Therefore, we also propose an approach to achievePrivacy-preserving Feature Extraction based on Adversarial Training (P-FEAT), where the goal of privacy attacking tasks and the goal of target tasks are adversarial in terms of sensitive attributes. By imposing privacy constraints during the feature extraction, we can reduce the contribution of the extracted features to the privacy leakage. In this way, privacy protection capability of theencodercan be further strengthened. We then demonstrate the effectiveness of P-FEAT using a large number of experiments, whose findings show that P-FEAT can significantly reduce the threats of privacy attacking tasks while maintaining high accuracy of the target tasks.

Triangle count is a critical parameter in mining relationships among people in social networks. However, directly publishing the findings obtained from triangle counts may bring potential privacy concern, which raises great challenges and opportunities for privacy-preserving triangle counting. In this paper, we choose to use differential privacy to protect triangle counting for large scale graphs. To reduce the large sensitivity caused in large graphs, we propose a novel graph projection method that can be used to obtain an upper bound for sensitivity in different distributions. In particular, we publish the triangle counts satisfying the node-differential privacy with two kinds of histograms: the triangle count distribution and the cumulative distribution. Moreover, we extend the research on privacy preserving triangle counting to one of its applications, the local clustering coefficient. Experimental results show that the cumulative distribution can fit the real statistical information better, and our proposed mechanism has achieved better accuracy for triangle counts while maintaining the requirement of differential privacy.

The need to efficiently store and query large scale graph datasets is evident in the growing number of data-intensive applications, particularly to maximize the mining of intelligence from these data (e.g., to inform decision making). However, directly releasing graph dataset for analysis may leak sensitive information of an individual even if the graph is anonymized, as demonstrated by the re-identification attacks on the DBpedia datasets. A key challenge in the design of graph sanitization methods is scalability, as existing execution models generally have significant memory requirements. In this paper, we propose a novel k-decomposition algorithm and define a new information loss matrix designed for utility measurement in massively large graph datasets. We also propose a novel privacy preserving framework that can be seamlessly integrated with graph storage, anonymization, query processing, and analysis. Our experimental studies show that the proposed solution achieves privacy-preserving, utility, and efficiency.

Triangle count is a critical parameter in mining relationships among people in social networks. However, directly publishing the findings obtained from triangle counts may bring potential privacy concern, which raises great challenges and opportunities for privacy-preserving triangle counting. In this paper, we choose to use differential privacy to protect triangle counting for large scale graphs. To reduce the large sensitivity caused in large graphs, we propose a novel graph projection method that can be used to obtain an upper bound for sensitivity in different distributions. In particular, we publish the triangle counts satisfying the node-differential privacy with two kinds of histograms: the triangle count distribution and the cumulative distribution. Moreover, we extend the research on privacy preserving triangle counting to one of its applications, the local clustering coefficient. Experimental results show that the cumulative distribution can fit the real statistical information better, and our proposed mechanism has achieved better accuracy for triangle counts while maintaining the requirement of differential privacy.

In this paper, we address the problem of finding k -nearest neighbors (KNN) in sequence databases using the edit distance. Unlike most existing works using short and exact n -gram matchings together with a filter-and-refine framework for KNN sequence search, our new approach allows us to use longer but approximate n -gram matchings as a basis of KNN candidates pruning. Based on this new idea, we devise a pipeline framework over a two-level index for searching KNN in the sequence database. By coupling this framework together with several efficient filtering strategies, i.e. the frequency queue and the well-known Combined Algorithm (CA), our proposal brings various enticing advantages over existing works, including 1) huge reduction on false positive candidates to avoid large overheads on candidate verifications; 2) progressive result update and early termination; and 3) good extensibility to parallel computation. We conduct extensive experiments on three real datasets to verify the superiority of the proposed framework.

Graphs are popular models for representing complex structure data and similarity search for graphs has become a fundamental research problem. Many techniques have been proposed to support similarity search based on the graph edit distance. However, they all suffer from certain drawbacks: high computational complexity, poor scalability in terms of database size, or not taking full advantage of indexes. To address these problems, in this paper, we propose SEGOS, an indexing and query processing framework for graph similarity search. First, an effective two-level index is constructed off-line based on sub-unit decomposition of graphs. Then, a novel search strategy based on the index is proposed. Two algorithms adapted from TA and CA methods are seamlessly integrated into the proposed strategy to enhance graph search. More specially, the proposed framework is easy to be pipelined to support continuous graph pruning. Extensive experiments are conducted on two real datasets to evaluate the effectiveness and scalability of our approaches.

The skyline operator has received considerable attention from the database community, due to its importance in many applications including multicriteria decision making, preference answering, and so forth. In many applications where uncertain data are inherently exist, i.e., data collected from different sources in distributed locations are usually with imprecise measurements, and thus exhibit kind of uncertainty. Taking into account the network delay and economic cost associated with sharing and communicating large amounts of distributed data over an internet, an important problem in this scenario is to retrieve the global skyline tuples from all the distributed local sites with minimum communication cost. Based on the well-known notation of the probabilistic skyline query over centralized uncertain data, in this paper, we propose the notation of distributed skyline queries over uncertain data. Furthermore, two communication- and computation-efficient algorithms are proposed to retrieve the qualified skylines from distributed local sites. Extensive experiments have been conducted to verify the efficiency, the effectiveness and the progressiveness of our algorithms with both the synthetic and real data sets.