Data inconsistency often arises from multiple observed sensory data due to varying participant reliability for crowdsensing systems. Truth discovery, which includesWeight EstimationandTruth Aggregation, for estimating participant reliability weights and aggregating uploaded values from inconsistent observations respectively, has emerged as an effective solution to address this issue. While local differential privacy (LDP) provides strong privacy guarantees by allowing participants to perturb their data locally before submission, existing LDP-based studies are either designed for static scenarios or compromise on privacy and accuracy trade-off for data streams, satisfying only weaker versions of LDP or mere differential privacy. To effectively and efficiently obtain truths over streams under rigorous LDP, we proposeNANOwhich is locally differeNtially privAte truth discovery via updatiNg time stamp determinatiOn. The main idea lies in its integration of Laplacian noise for privacy protection and inherent Gaussian noise representing natural data variability for effective weight and truth estimations, coupled with the adaptive determination of updating time stamps. InNANO, to obtain theWeight EstimationandTruth Aggregationunder LDP, we design a mixed noise-aware truth discovery methodMixTDby modeling the mixed noise. To capture the dynamic nature of weight and truth evolutions, we develop a changing-aware updating time stamp determination methodCUDto selectively re-conduct truth discovery at specific time stamps. We also introduce a dynamic privacy budget management strategy, which accumulates unused budgets from skipped updates for critical timestamps. In this way,Weight EstimationandTruth Aggregationare limited to critical time stamps, which significantly reduces the privacy budget segmentation and computational costs. We demonstrate thatNANOprovides rigorous LDP guarantees while achieving bounded utility and computational complexity. Extensive experimental results over four real-world datasets and three synthetic datasets showcase thatNANOoutperforms the state-of-the-arts by at least 20% improvement with negligible extra efficiency loss.

Adversarial attack and defense have been extensively explored in classification tasks, but their study in semantic segmentation remains limited. Moreover, current attacks fail to act as strong underlying attacks for adversarial training (AT), making it difficult to achieve segmentation robustness against strong attacks. In this paper, we present RP-PGD, a novel Region-and-Prototype based Projected Gradient Descent attack tailored to fool segmentation models. In particular, we propose a region-based attack, which leverages a spatial-temporal way to separate the pixels into three disjoint regions, and highlights the attack on the crucial True Region and Boundary Region. Moreover, we introduce a prototype-based attack to disrupt the feature space, further enhancing the attack capability. To boost the robustness of segmentation models, we inject adversaries generated by RP-PGD into the clean data and perform AT. Extensive experiments on multiple datasets showcase that RP-PGD generates adversaries with faster convergence and stronger attack effectiveness, surpassing state-of-the-art attacks by a large margin. Consequently, RP-PGD serves as a strong underlying attack for segmentation models to perform AT, assisting them in defending against a variety of strong attacks without incurring additional computational costs during inference.

Nonparametric contextual bandit is an important model of sequential decision making problems. Under $\alpha$-Tsybakov margin condition, existing research has established a regret bound of $\tilde{O}\left(T^{1-\frac{\alpha+1}{d+2}}\right)$ for bounded supports. However, the optimal regret with unbounded contexts has not been analyzed. The challenge of solving contextual bandit problems with unbounded support is to achieve both exploration-exploitation tradeoff and bias-variance tradeoff simultaneously. In this paper, we solve the nonparametric contextual bandit problem with unbounded contexts. We propose two nearest neighbor methods combined with UCB exploration. The first method uses a fixed $k$. Our analysis shows that this method achieves minimax optimal regret under a weak margin condition and relatively light-tailed context distributions. The second method uses adaptive $k$. By a proper data-driven selection of $k$, this method achieves an expected regret of $\tilde{O}\left(T^{1-\frac{(\alpha+1)\beta}{\alpha+(d+2)\beta}}+T^{1-\beta}\right)$, in which $\beta$ is a parameter describing the tail strength. This bound matches the minimax lower bound up to logarithm factors, indicating that the second method is approximately optimal.

Out-of-distribution (OOD) fine-tuning has emerged as a promising approach for anomaly segmentation. Current OOD fine-tuning strategies typically employ global-level objectives, aiming to guide segmentation models to accurately predict a large number of anomaly pixels. However, these strategies often perform poorly on small anomalies. To address this issue, we propose an instance-level OOD fine-tuning framework, dubbed LNOIB (Leaving No OOD Instance Behind). We start by theoretically analyzing why global-level objectives fail to segment small anomalies. Building on this analysis, we introduce a simple yet effective instance-level objective. Moreover, we propose a feature separation objective to explicitly constrain the representations of anomalies, which are prone to be smoothed by their in-distribution (ID) surroundings. LNOIB integrates these objectives to enhance the segmentation of small anomalies and serves as a paradigm adaptable to existing OOD fine-tuning strategies, without introducing additional inference cost. Experimental results show that integrating LNOIB into various OOD fine-tuning strategies yields significant improvements, particularly in component-level results, highlighting its strength in comprehensive anomaly segmentation.

Protection of local differential privacy (LDP) proto-cols against manipulation attacks is an important and challenging problem. We hope to design an attack-agnostic framework, which does not rely on any knowledge of attackers. An early work [1] restricts the attacker's capability by converting each sample into a binary signal. However, the compression of signal leads to severe loss of information, and thus results in unnecessary sacrifice of utility, especially when$\epsilon > 1$. In this paper, we propose a general estimation framework RobustLDP for robust estimation under LDP. The general idea is to send carefully crafted pre-defined information to all users, and then aggregate the feedback at the server. We strike a better tradeoff between preserving information and restricting the attacker's capability. We instantiate RobustLDP for frequency estimation and mean estimation in$\ell_{1}$and$\ell_{2}$support, which serve as building blocks for more advanced tasks. We also establish theoretical guarantees for all possible attacks. The result shows that our method significantly outperforms the existing one for$\epsilon > 1$. Extensive experiments on multiple real-world datasets validate the effectiveness of our method.

In this paper, we investigate one of the most fundamental non-convex learning problems-ReLU regression-in the Differential Privacy (DP) model. Previous studies on private ReLU regression heavily rely on stringent assumptions, such as constant-bounded norms for feature vectors and labels. We relax these assumptions to a more standard setting, where data can be i.i.d. sampled from $O(1)$-sub-Gaussian distributions. We first show that when $\varepsilon = \tilde{O}(\sqrt{\frac{1}{N}})$ and there is some public data, it is possible to achieve an upper bound of $\Tilde{O}(\frac{d^2}{N^2 \varepsilon^2})$ for the excess population risk in $(\epsilon, \delta)$-DP, where $d$ is the dimension and $N$ is the number of data samples. Moreover, we relax the requirement of $\epsilon$ and public data by proposing and analyzing a one-pass mini-batch Generalized Linear Model Perceptron algorithm (DP-MBGLMtron). Additionally, using the tracing attack argument technique, we demonstrate that the minimax rate of the estimation error for $(\varepsilon, \delta)$-DP algorithms is lower bounded by $\Omega(\frac{d^2}{N^2 \varepsilon^2})$. This shows that DP-MBGLMtron achieves the optimal utility bound up to logarithmic factors. Experiments further support our theoretical results.

Membership inference attacks (MIAs) compromise the privacy of training data through interrogating a victim machine learning model and inferring whether or not a query sample is in the training data. Existing defenses against MIAs include preprocessing the training data of the model, modifying loss functions, and perturbing the inference output. However, all these mechanisms have to change either the training or inference process, which might be out of reach of the defenders, especially when the models are deployed in a third-party cloud service. In this article, we propose preprocessing the query samples before feeding them into the models for inference. Specifically, we design aMembership Cleansermodule to remove the member information in the query sample by moving it closer to non-member area in the feature space. The membership cleanser does not modify the training or inference process of the machine learning model, so it can be applied to any machine learning system. Through extensive evaluation on four datasets against different models, our approach consistently outperforms the state-of-the-art defense mechanisms in resilience and practicality against various MIAs while retaining good inference accuracy.

Numerical vector aggregation plays a crucial role in privacy-sensitive applications, such as distributed gradient estimation in federated learning and statistical analysis of key-value data. In the context of local differential privacy, this study provides a tight minimax error bound of$O(\frac{ds}{n\epsilon ^{2}})$, where$d$represents the dimension of the numerical vector and$s$denotes the number of non-zero entries. By converting the conditional/unconditional numerical mean estimation problem into a frequency estimation problem, we develop an optimal and efficient mechanism called Collision. In contrast, existing methods exhibit sub-optimal error rates of$O(\frac{d^{2}}{n\epsilon ^{2}})$or$O(\frac{ds^{2}}{n\epsilon ^{2}})$. Specifically, for unconditional mean estimation, we leverage the negative correlation between two frequencies in each dimension and propose the CoCo mechanism, which further reduces estimation errors for mean values compared to Collision. Moreover, to surpass the error barrier in local privacy, we examine privacy amplification in the shuffle model for the proposed mechanisms and derive precisely tight amplification bounds. Our experiments validate and compare our mechanisms with existing approaches, demonstrating significant error reductions for frequency estimation and mean estimation on numerical vectors.

Passwords are widely used for authentication in Internet applications. Recently, users tend to adopt graphical passwords instead of traditional alphanumeric passwords, since it is much easier for humans to remember images than verbal representations. However, the existing graphical password authentication systems generally suffer from three main issues. 1) It is required to remember and perform complicated operations during the registration/login phases, which significantly limits the systems’ usability; 2) The users’ passwords are simply stored as plaintexts in servers, and thus the security is compromised; 3) The users need to register/login to each server separately when they are applied in multi-server environment. To address the above issues, we propose a user-friendly and secure Google map-based graphical password (FS-GMGP) system using tolerant distance and homomorphic encryption. By using a homomorphic encryption scheme, each user encrypts his password point and response point selected on Google map, while the servers compute and decrypt the distance between the two encrypted points and then compare the resulting value with a tolerant distance for authentication. Moreover, the FS-GMGP system is extended for multi-server environment. The evaluation results and security analysis show that the FS-GMGP and its extended version achieve desirable usability and security in single-server environment and multi-server environment, respectively.

The shuffle model employs a shuffler to anonymize and permute user messages, thereby enhancing privacy/utility trade-offs compared to the local model. Ideally, it assumes perfect message anonymity protection against adversaries, allowing each user to hide among a large population. However, in contexts like mobile/edge networks or in scenarios where the shuffler is curious, this assumption is frequently unrealistic. In this study, we demonstrate the vulnerability of the shuffle model to communication side-channel attacks, which substantially compromise privacy amplification via shuffling. We categorize side-channel information in the shuffle model into three types: (i) in-out information, revealing the victim user’s participation and timing, (ii) message-cardinality information, indicating the victim’s message count, and (iii) message-length information, disclosing the victim’s message length(s). Numerical results indicate these attacks increase privacy loss by 200% to 4100%, revealing secret value with probability more than 90%. After theoretically analyzing the remaining privacy amplification effects, we suggest several countermeasures and principles to alleviate degradation caused by these attacks: (a) appending padding bits to each message to counter message-length attacks, (b) maximizing query parallelization to elude in-out attacks and increase the population for privacy amplification, and (c) sending dummy messages to exchange communication costs for improved privacy amplification effects. The newly proposed paradigms and principles significantly save privacy budget in comparison to current models under attack.

Local Differential Privacy (LDP) enables an untrusted server to collect and analyze sensitive data while preserving user privacy. Recent studies reveal that LDP protocols are vulnerable to poisoning attacks, in which an adversary can manipulate aggregated frequencies by controlling malicious users to send forged data to the server. Some countermeasures have been proposed to mitigate poisoning attacks, but they have limitations: 1) requiring prior knowledge of the attack type; 2) exhibiting poor resistance to the adaptive maximal gain attack, i.e., MGA-A. To address the two limitations, in this paper, we propose a novel detection scheme named Group Filter Detection (GFD) to defend against poisoning attacks on LDP frequency estimation. GFD is a universal defense scheme, which can be applied to any LDP frequency estimation protocol without the prior knowledge of attack types, and exhibits high robustness against various poisoning attacks. GFD can first identify the adversary’s target itemset and then filters the suspicious perturbed data (from malicious users). In this way, GFD can exclude malicious data with high confidence, thereby improving the accuracy of LDP frequency estimation. Compared with the existing solutions, experimental results demonstrate the highest effectiveness of GFD.

Deep neural network (DNN) models embody the intellectual property of a model owner, as the process of training the DNN model is a complex and resource-intensive task that requires significant investments in data preparation and computing resources. Numerous efforts have been made to protect the intellectual property of DNN models. However, existing methods often come with a critical limitation: they lack robustness, proving effective only in specific intellectual property threat scenarios or they either sacrifice the utility/accuracy of the model owner’s classifier because it interferes with the classifier’s training. To address these issues, we propose GMFIP, a novel generator-based model fingerprinting technology tailored for DNN intellectual property protection. GMFIP stands out for its robustness, extending its utility to various intellectual property threat scenarios rather than specific ones. Furthermore, GMFIP ensures that the utility/accuracy of the model is not affected by protection measures. Specifically, GMFIP begins with the training of the generator, which lays the groundwork for the model fingerprint. The generator generates fingerprints of the unique properties of the source model for verifying model ownership. To further improve the quality of these fingerprints, an extra selection phase dedicated to refining the fingerprints is integrated. Moreover, GMFIP is complemented by a binary classifier, which adapts the threshold setting to get optimal results. Our empirical evaluation includes an ablation study over four state-of-the-art technologies and three image benchmark datasets. Our results demonstrate that GMFIP outperforms other state-of-the-art technologies in effectively distinguishing pirated models from benign models.

The exponential growth of data in the Internet of Vehicles (IoV) has created opportunities to improve traffic safety and efficiency through data trading. However, establishing trust among highly mobile and resource-constrained vehicles poses significant challenges for effective data trading in IoV. To address this issue, we propose a lightweight blockchain-based data trading scheme (LBDT), which ensures secure and efficient data trading in IoV. We introduce a proof-of-reputation (PoR) consensus mechanism to establish trustworthiness for data trading. Specifically, we use a progressive reputation mechainism to support the PoR consensus. LBDT utilizes a parallel-chain structure for the PoR consensus to minimize communication and storage costs while reducing transaction confirmation latency. Additionally, we adopt a double auction mechanism as an incentivizing strategy to encourage vehicle participation in data trading. We evaluate the performance of LBDT through extensive experiments. The experimental results demonstrate that LBDT is highly effective and secure, achieving a transaction latency of approximately 4 seconds. Moreover, LBDT successfully mitigates communication and storage overheads by over 90%, thus establishing its superiority over state-of-the-art solutions under comparable conditions.

We study online data analytics with differential privacy (DP) in decentralized settings. Specifically, online data analytics with local DP protection is widely adopted in real-world applications. Despite numerous endeavors in this field, significant gaps in utility and functionality remain when compared to its offline counterpart. We present an optimal, streamable mechanism:ExSub, for local DP sparse vector estimation. The mechanism enables a range of online analytics on streaming binary vectors, including multi-dimensional binary, categorical, or set-valued data. By leveraging the negative correlation of occurrence events in the sparse vector, we attain an optimal error rate under local privacy constraints, only requiring streamable computations. To surpass the error barrier of local privacy, we also studyExSubrandomizer in the newly emerging (single-message) shuffle model of DP, and provide nearly-tight privacy amplification bounds therein. Additionally, we leverage the online shuffle model that independently permutes users' messages at each timestamp, to design a simplified randomization strategy that can approximately reach Gaussian accuracy in central DP. Through experiments with both synthetic and real-world datasets,ExSubmechanism in the local model have been shown to reduce error by$40\%-60\%$compared to SOTA approaches. TheExSubin the shuffle model can further reduce over$85\%$error, and the online shuffle protocol reduces over$99.7\%$error.

Graph analysis is fundamental in real-world applications. Traditional approaches rely on SPARQL-like languages or clicking-and-dragging interfaces to interact with graph data. However, these methods either require users to possess high programming skills or support only a limited range of graph analysis functionalities. To address the limitations, we propose a large language model (LLM)-based framework called Chat-Graph. With ChatGraph, users can interact with graphs through natural language, making it easier to use and more flexible than traditional approaches. The core of ChatGraph lies in generating chains of graph analysis APIs based on the understanding of the texts and graphs inputted in the user prompts. To achieve this, ChatGraph consists of three main modules: an API retrieval module that searches for relevant APIs, a graph-aware LLM module that enables the LLM to comprehend graphs, and an API chain-oriented finetuning module that guides the LLM in generating API chains. We have implemented ChatGraph and will showcase its usability and efficiency in four scenarios using real-world graphs.

Online data analytics with local privacy protection is widely adopted in real-world applications. Despite numerous endeavors in this field, significant gaps in utility and functionality remain when compared to its offline counterpart. This work demonstrates that private data analytics can be conducted online without excess utility loss, even at a constant factor. We present an optimal, streamable mechanism for local differentially private sparse vector estimation. The mechanism enables a range of online analytics on streaming binary vectors, including multi-dimensional binary, categorical, or set-valued data. By leveraging the negative correlation of occurrence events in the sparse vector, we attain an optimal error rate under local privacy constraints, only requiring streamable computations during the input’s data-dependent phase. Through experiments with both synthetic and real-world datasets, our proposals have been shown to reduce error rates by 40% to 60% compared to SOTA approaches.

As one of the most fundamental non-convex learning problems, ReLU regression under differential privacy (DP) constraints, especially in high-dimensional settings, remains a challenging area in privacy-preserving machine learning. Existing results are limited to the assumptions of bounded norm $ \|\mathbf{x}\|_2 \leq 1$, which becomes meaningless with increasing data dimensionality. In this work, we revisit the problem of DP ReLU regression in high-dimensional regimes. We propose two innovative algorithms DP-GLMtron and DP-TAGLMtron that outperform the conventional DPSGD. DP-GLMtron is based on a generalized linear model perceptron approach, integrating adaptive clipping and Gaussian mechanism for enhanced privacy. To overcome the constraints of small privacy budgets in DP-GLMtron, represented by $\widetilde{O}(\sqrt{1/N})$ where $N$ is the sample size, we introduce DP-TAGLMtron, which utilizes a tree aggregation protocol to balance privacy and utility effectively, showing that DP-TAGLMtron achieves comparable performance with only an additional factor of $O(\log N)$ in the utility upper bound. Moreover, our theoretical analysis extends beyond Gaussian-like data distributions to settings with eigenvalue decay, showing how data distribution impacts learning in high dimensions. Notably, our findings suggest that the utility upper bound could be independent of the dimension $d$, even when $d \gg N$. Experiments on synthetic and real-world datasets also validate our results.

The shuffle model of differential privacy provides promising privacy-utility balances in decentralized, privacy-preserving data analysis. However, the current analyses of privacy amplification via shuffling lack both tightness and generality. To address this issue, we propose the variation-ratio reduction as a comprehensive framework for privacy amplification in both single-message and multi-message shuffle protocols. It leverages two new parameterizations: the total variation bounds of local messages and the probability ratio bounds of blanket messages, to determine indistinguishability levels. Our theoretical results demonstrate that our framework provides tighter bounds, especially for local randomizers with extremal probability design, where our bounds are exactly tight. Additionally, variation-ratio reduction complements parallel composition in the shuffle model, yielding enhanced privacy accounting for popular sampling-based randomizers employed in statistical queries (e.g., range queries, marginal queries, and frequent itemset mining). Empirical findings demonstrate that our numerical amplification bounds surpass existing ones, conserving up to 30% of the budget for single-message protocols, 75% for multi-message ones, and a striking 75%-95% for parallel composition. Our bounds also result in a remarkably efficient Õ ( n ) algorithm that numerically amplifies privacy in less than 10 seconds for n = 10 8 users.

How to achieve distributed differential privacy (DP) without a trusted central party is of great interest in both theory and practice. Recently, the shuffle model has attracted much attention. Unlike the local DP model in which the users send randomized data directly to the data collector/analyzer, in the shuffle model an intermediate untrusted shuffler is introduced to randomly permute the data, which have already been randomized by the users, before they reach the analyzer. The most appealing aspect is that while shuffling does not explicitly add more noise to the data, it can make privacy better. The privacy amplification effect in consequence means the users need to add less noise to the data than in the local DP model, but can achieve the same level of differential privacy. Thus, protocols in the shuffle model can provide better accuracy than those in the local DP model. What looks interesting to us is that the architecture of the shuffle model is similar to private aggregation, which has been studied for more than a decade. In private aggregation, locally randomized user data are aggregated by an intermediate untrusted aggregator. Thus, our question is whether aggregation also exhibits some sort of privacy amplification effect? And if so, how good is this “aggregation model” in comparison with the shuffle model. We conducted the first comparative study between the two, covering privacy amplification, functionalities, protocol accuracy, and practicality. The results as yet suggest that the new shuffle model does not have obvious advantages over the old aggregation model. On the contrary, protocols in the aggregation model outperform those in the shuffle model, sometimes significantly, in many aspects.

In many mobile applications, user-generated data are presented as set-valued data. To tackle potential privacy threats in analyzing these valuable data, local differential privacy has been attracting substantial attention. However, existing approaches only provide sub-optimal utility and are expensive in computation and communication for set-valued data distribution estimation and heavy-hitter identification. In this paper, we propose a utility-optimal and efficient set-valued data publication method (i.e.,Wheel mechanism). On the user side, the computational complexity is only$O(\min \lbrace m\log m, m e^\epsilon \rbrace )$and communication costs are$O(\epsilon +\log m)$bits, where$m$is the number of items,$d$is the domain size and$\epsilon$is the privacy budget, while existing approaches usually depend on$O(d)$or$O(\log d)$($d \gg m$). Our theoretical analyses reveal the estimation errors have been reduced from the previously known$O(\frac{m^{2} d}{n\epsilon ^{2}})$to the optimal rate$O(\frac{m d}{n\epsilon ^{2}})$. Additionally, for heavy-hitter identification, we present a variant of the Wheel mechanism as an efficient frequency oracle, entailing only$O(\sqrt{n})$computational complexity. This heavy-hitter protocol achieves an identification bar of$\tilde{O}(\frac{1}{\epsilon }\sqrt{\frac{m}{n} \log d})$, reducing by a factor of$\sqrt{m}$relative to existing protocols. Extensive experiments demonstrate our methods are 3-100x faster than existing approaches and have optimized statistical efficiency.

Taking the steganalytic discriminators as the adversaries, the existing Generative Adversarial Networks (GAN)-based steganographic approaches learn the implicit cost functions to measure the embedding distortion for steganography. However, the steganalytic discriminators in these approaches are trained by the stego-samples with insufficient diversity, and their network structures offer very limited representational capacity. As a result, these steganalytic discriminators will not exhibit robustness to various steganographic patterns, which causes learning suboptimal cost functions, thus compromising the anti-steganalysis capability. To address this issue, we propose a novel GAN-based steganographic approach, in which the Diversified Inverse-Adversarial Training (DIAT) strategy and the Steganalytic Feature Attention (SteFA) structure are designed to train a robust steganalytic discriminator. Specifically, the DIAT strategy provides the steganalytic discriminator with an expanded feature space by generating diversified adversarial stego-samples; the SteFA structure enables the steganalytic discriminator to capture more various steganalytic features by employing the channel-attention mechanism on higher-order statistics. Consequently, the steganalytic discriminator can build a more precise decision boundary to make it more robust, which facilitates learning a superior steganographic cost function. Extensive experiments demonstrate that the proposed steganographic approach achieves promising anti-steganalysis capability over the state-of-the-arts under the same embedding payloads.

Knowledge distillation has emerged as a scalable and effective way for privacy-preserving machine learning. One remaining drawback is that it consumes privacy in a client-level manner. In order to attain fine-grained privacy accountant and improve utility, this work proposes a model-free reverse k-NN labeling method towards record-level private knowledge distillation, where each private record is employed for labeling at most k queries. Theoretically, we provide bounds of labeling error rate under the centralized/local model of differential privacy. Experimentally, we demonstrate that it achieves new state-of-the-art accuracy in MNIST/SVHN/CIFAR-10 dataset with one order of magnitude lower of privacy loss.

Current few-shot segmentation (FSS) approaches have made tremendous achievements based on prototypical learning techniques. However, due to the scarcity of the support data provided, FSS methods still suffer from the intra-class and inter-class gaps. In this paper, we propose a uniform network to fill both the gaps, termed FGNet. It consists of the novel design of a Self-Adaptive Module (SAM) to emphasize the query feature to generate an enhanced prototype for self-alignment. Such a prototype caters to each query sample itself since it contains the underlying intra-instance information, which gets around the intra-class appearance gap. Moreover, we design an Inter-class Feature Separation Module (IFSM) to separate the feature space of the target class from other classes, which contributes to bridging the inter-class gap. In addition, we present several new losses and a method termed B-SLIC, which help to further enhance the separation performance of FGNet. Experimental results show that FGNet reduces both the gaps for FSS by SAM and IFSM respectively, and achieves state-of-the-art performances on both PASCAL-5i and COCO-20i datasets compared with previous top-performing approaches.

Online service providers benefit from collecting and analyzing preference data from users, including both implicit preference data (e.g., watched videos of a user) and explicit preference data (e.g., ranking data over candidates). However, it brings ethical and legal issues of data privacy at the same time. In this paper, we study the problem of aggregating individual's preference data in the local differential privacy (LDP) setting. One naive approach is to add Laplace random noises, which however suffers from low statistical utility and is fragile to LDP-specific poisoning attacks. Therefore, we propose a novel mechanism to improve the utility and the robustness simultaneously: theadditive mechanism. The additive mechanism randomly outputs a subset of candidates with a probability proportional to their total scores. For preference data with Borda rule over$d$items, its mean squared error bound is optimized from$O(\frac{d^{5}}{n\epsilon ^{2}})$to$O(\frac{d^{4}}{n\epsilon ^{2}})$, and its maximum poisoning risk bound is reduced from$+\infty$to$O(\frac{d^{2}}{n\epsilon })$. We also theoretically investigate minimax lower bounds of$\epsilon$-LDP preference data aggregation, and prove the error rate of$O(\frac{d^{4}}{n\epsilon ^{2}})$is optimal for the Borda rule. Experimental results validate that our proposed approaches averagely reduce estimation error by 50% and are more robust to adversarial poisoning attacks.

Bridging the advantages of differential privacy in both centralized model (i.e., high accuracy) and local model (i.e., minimum trust), the shuffle privacy model has potential applications in many privacy-sensitive scenarios, such as mobile user data aggregation and federated learning. Since messages from users are anonymized by semi-trusted shufflers (e.g., anonymous channels, edge servers), every user could hide message among other users’ messages and inject only part of noises (a.k.a. privacy amplification). However, existing works assume that the participating user population is known in advance, which is unrealistic for dynamic environments (e.g., mobile computing, vehicular networks). In this work, we study the shuffle privacy model with a random participating population, and give privacy amplification bounds for population size with commonly encountered binomial, Poisson, sub-Gaussian distribution and etc. For further improving accuracy, we formulate and derive optimal dummy sizes for both non-adaptive and adaptive dummies. Finally, to break the error barrier due to the constraint of sending one single message per user, we design a multi-message shuffle private protocol supporting random population. Experiment results show that our approaches reduce more than 60% error when compared to the local model and naive approaches. We hope this work provides tailored solutions of shuffle privacy for dynamic mobile/distributed computing.

Numerical vector aggregation has numerous applications in privacy-sensitive scenarios, such as distributed gradient estimation in federated learning, and statistical analysis on key-value data. Within the framework of local differential privacy, this work gives tight minimax error bounds of O(d s/(n epsilon^2)), where d is the dimension of the numerical vector and s is the number of non-zero entries. An attainable mechanism is then designed to improve from existing approaches suffering error rate of O(d^2/(n epsilon^2)) or O(d s^2/(n epsilon^2)). To break the error barrier in the local privacy, this work further consider privacy amplification in the shuffle model with anonymous channels, and shows the mechanism satisfies centralized (14 ln(2/delta) (s e^epsilon+2s-1)/(n-1))^0.5, delta)-differential privacy, which is domain independent and thus scales to federated learning of large models. We experimentally validate and compare it with existing approaches, and demonstrate its significant error reduction.

Generative Adversarial Network (GAN) has already made a big splash in the field of generating realistic "fake" data. However, when data is distributed and data-holders are reluctant to share data for privacy reasons, GAN’s training is difficult. To address this issue, we propose private FL-GAN, a differential privacy generative adversarial network model based on federated learning. By strategically combining the Lipschitz limit with the differential privacy sensitivity, the model can generate high-quality synthetic data without sacrificing the privacy of the training data. We theoretically prove that private FL-GAN can provide strict privacy guarantee with differential privacy, and experimentally demonstrate our model can generate satisfactory data.

Attributed graph data is powerful to describe relational information in various areas, such as social links through numerous web services and citation/reference relations in the collaboration network. Taking advantage of attributed graph data, service providers can model complex systems and capture diversified interactions to achieve better business performance. However, privacy concern is a huge obstacle to collect and analyze user's attributed graph data. Existing studies on protecting private graph data mainly focus on edge local differential privacy(LDP), which might be insufficient in some highly sensitive scenarios. In this paper, we present a novel privacy notion that is stronger than edge LDP, and investigate approaches to analyze attributed graphs under this notion. To neutralize the effect of excessively introduced noise, we propose PrivAG, a privacy-preserving framework that protects attributed graph data in the local setting while providing representative graph statistics. The effectiveness and efficiency of PrivAG framework is validated through extensive experiments.

Most user-generated data in online services are presented as set-valued data, e.g., visited website URLs, recently used Apps by a person, and etc. These data are of great value to service providers, but also bring privacy concerns if collected and analyzed directly. To tackle potential privacy threatens, local differential privacy (LDP) attracts increasing attention nowadays. However, existing approaches only provide sub-optimal error bound for set-valued data distribution estimation with LDP. Besides, it is computational expensive and communication expensive to use for high dimensional set-valued data, considering large domains in real scenarios. Thus, existing approaches are unpractical to use on resource-constrained user-side devices (e.g., smartphones and wearable devices). In this paper, we propose a utility-optimal and efficient set-valued data publication method (i.e., wheel mechanism ). On the user side, each user contributes only one numerical value to represent their privatized data. The computational complexity is O (min{ m log m , me ɛ }) and communication cost is O (log( me ɛ )) bits, while existing approaches usually depend on O ( d ) or O (log d ), where m is the number of items in the set-valued data ( m ≡ 1 for categorical data), d is the domain size (usually d ≫ m ) and ɛ is the privacy budget. On the server side, the estimator takes numerical values from users as input and derives an unbiased distribution estimation. Theoretical results show that estimation error bounds are improved from previously known [EQUATION] to the optimal rate [EQUATION]. Results on extensive experiments demonstrate that our proposed wheel mechanism is 3-100× faster than existing approaches, meanwhile has optimal statistical efficiency.

As information security is increasingly valued, privacy-preserving data mining has become a research hotspot in the field of big data and signal processing. We propose a new differentially private greedy decision forest algorithm called DPGDF to help improve the accuracy of privacy-preserving data mining. Unlike previous algorithms that only employed greedy decision trees or random forests, our algorithm uses a combination of greedy trees and parallel combination theory to construct a greedy decision forest and coordinate privacy protection and prediction accuracy to achieve the best balance. Combined with smooth sensitivity, the introduction of noise is minimized, making the prediction accuracy of the algorithm notably better than the current state-of-the-art algorithms. Experiments on the UCI datasets show that the prediction accuracy of our algorithm is about 10% higher than that of those algorithms.

Local differential privacy (LDP), as a strong and practical notion, has been applied to deal with privacy issues in data collection. However, existing LDP-based strategies mainly focus on utility optimization at a single privacy level while ignoring various privacy preferences of data providers and multilevel privacy demands for statistics. In this poster, we for the first time propose a framework to optimize the utility of histogram estimation with these two privacy requirements. To clarify the goal of privacy protection, we personalize the traditional definition of LDP. We design two independent approaches to minimize the utility loss: Advanced Combination, which composes multilevel results for utility optimization, and Data Recycle with Personalized Privacy, which enlarges sample size for an estimation. We demonstrate their effectiveness on privacy and utility. Moreover, we embed these approaches within a Recycle and Combination Framework and prove that the framework stably achieves the optimal utility by quantifying its error bounds. On real-world datasets, our approaches are experimentally validated and remarkably outperform baseline methods.

Recently, local differential privacy (LDP), as a strong and practical notion, has been applied to deal with privacy issues in data collection. However, existing LDP-based strategies mainly focus on utility optimization at a single privacy level while ignoring various privacy preferences of data providers and multilevel privacy demands for statistics. In this paper, we for the first time propose a framework to optimize the utility of histogram estimation with these two privacy requirements. To clarify the goal of privacy protection, we personalize the traditional definition of LDP. We design two independent approaches to minimize the utility loss: Advanced Combination, which composes multilevel results for utility optimization, and Data Recycle with Personalized Privacy, which enlarges the sample size for an estimation. We demonstrate their effectiveness on privacy and utility, respectively. Moreover, we embed these approaches within a Recycle and Combination Framework and prove that the framework stably achieves the optimal utility by quantifying its error bounds. On real-world datasets, our approaches are experimentally validated and remarkably outperform baseline methods.

For the purpose of improving the quality of services, softwares or online services are collecting various of user data, such as personal information and locations. Such data facilitates mining statistical knowledge of users, but threatens users' privacy as it may reveal sensitive information (e.g., identities and activities) about individuals. This work considers distribution estimation over user-contributed data meanwhile providing rigid protection of their data with local ε-differential privacy (ε-LDP), which sanitizes each user's data on the client's side (e.g, on the user's mobile device). Our privacy protection covers both qualitative data (e.g., categorical data) and discrete quantitative data (e.g., location data). Specifically, for categorical data, we derive an optimal ε-LDP mechanism (termed as k-subset mechanism) from mutual information perspective, and further show its optimality over existing approaches within the context of discrete distribution estimation; for discrete quantitative data that have arbitrary distance metric, we provide an efficient extension of k-subset mechanism by proposing a variant of the popular Exponential Mechanism (EM) to tackle the asymmetry issue on the data domain. Experiments on real-world datasets and simulated scenarios show that our mechanism is highly efficient and reduces nearly a fraction of exp(- ε/2) error for distribution estimation when compared to existing approaches.

Set-valued data is useful for representing a rich family of information in numerous areas, such as market basket data of online shopping, apps on mobile phones and web browsing history. By analyzing set-valued data that are collected from users, service providers could learn the demographics of the users, the patterns of their usages, and finally, improve the quality of services for them. However, privacy has been an increasing concern in collecting and analyzing users' set-valued data, since these data may reveal sensitive information (e.g., identities, preferences and diseases) about individuals. In this work, we propose a privacy preserving aggregation mechanism for set-valued data: PrivSet. It provides rigorous data privacy protection locally (e.g., on mobile phones or wearable devices) and efficiently (its computational overhead is linear to the item domain size) for each user, and meanwhile allowing effective statistical analyses (e.g., distribution estimation of items, distribution estimation of set cardinality) on set-valued data for service providers. More specifically, in PrivSet, within the constraints of local e-differential privacy, each user independently responses with a subset of the set-valued data domain with calibrated probabilities, hence the true positive/false positive rate of each item is balanced and the performance of distribution estimation is optimized. Besides presenting theoretical error bounds of PrivSet and proving its optimality over existing approaches, we experimentally validate the mechanism, the experimental results illustrate that the estimation error in PrivSet has been reduced by half when compared to state-of-the-art approaches.

Software defined networking (SDN) is becoming increasingly prevalent for its programmability that enables centralized network configuration and management. With the growth of SDNs, a cluster of controllers cooperatively manages more and more switches/flows in a network to avoid the single-controller congestion/failure and improve the control-plane robustness. Under the architecture with multiple controllers, it is expected to minimize the maximum response time on these controllers to provide better QoS for users. To achieve this target, two previous methods are mainly used, the static scheme and the dynamic scheme. However, these methods may lead to an increase of the control-plane communication overhead/delay. In this paper, we propose to minimize the maximum response time on controllers through flow redirecting, which is implemented by installing wildcard rules on switches. We formulate the minimum controller response time problem, which takes the flow-table size and link capacity constraints into account, as an integer linear program, and prove its NP-Hardness. Two algorithms with bounded approximation factors are designed to solve this problem. We implement the proposed methods on our SDN testbed. The testing results and extensive simulation results show that our proposed algorithm can reduce the maximum controller response time by about 50%-80% compared with the static/dynamic methods under the same controller cost, or reduce the number of controllers by 30% compared with the dynamic method while preserving almost the same controller response time.

The categorical data that have natural ordering between categories are termed ordinal data, which are pervasive in numerous areas, including discrete sensor readings, metering data or preference options. Though aggregating such ordinal data from the population is facilitating plenty of crowdsourcing applications, contributing such data is privacy risky and may reveal sensitive information (e.g. locations, identities) about individuals. This work studies ordinal data aggregation for distribution estimation meanwhile locally preserving individuals' data privacy (such as on their mobile devices). Under ε-geo-indistinguishable constraints, which capture intrinsic dissimilarity between ordinal categories in the framework of differential privacy, we provide an efficient and effective locally private mechanism: Subset Exponential Mechanism (SEM) for ordinal data distribution estimation. The mechanism randomly responds with a fixed-size subset of the categories with calibrated probability assignment. Specially for uniform ordinal data, we propose a circling technique to symmetrically randomizing categories and estimating frequencies of categories, hence the computational/space costs and estimation performance of SEM are further optimized. Besides contributing theoretical error bounds of SEM, we also evaluate the mechanism on extensive scenarios, the evaluation results show that SEM reduces distribution estimation error on average by exp(ϵ/2) factor over existing private mechanisms.

Spatial Crowdsourcing (SC) nowadays has become a popular research topic studying how to outsource a set of spatial-temporal tasks to workers at specific locations. However, there exists a significant security concern: existing location privacy techniques are not applicable to SC. In this paper, we focus on protecting the worker location privacy against the semi-honest adversaries model while preserving the functionality of SC system. By introducing a semi-honest third party and using additive homomorphic encryption, we present a secure task assignment protocol for SC. More specifically, we propose an efficient protocol to securely compute the worker travel cost and select minimum cost worker in the encrypted domain, which reveals nothing about location privacy. We theoretically analyze that our protocol is secure as all encrypted private data are computationally indistinguishable. Extensive experimental results on real-world and synthetic datasets show that the proposed protocol can protect worker location privacy while keeping high task assignment rate.

Histogram estimation is one of the fundamental tasks in crowdsourcing data aggregation. Since contributing data reveal more or less information about individuals' identifications and activities, participants need to preserve privacy of data according to their own levels of privacy concern. However, most of the existing work only aggregates data with an identical privacy level. In this paper, we propose an aggregation scheme for histogram estimation, wherein participants can publish their data at personalized differential-privacy levels. The aggregator also benefits from potential wider engagement or more honest data. Specially, since privacy levels under personalized privacy policy are sensitive information for participants, our scheme permits participants to keep their privacy levels secret even from the aggregator. We also show how to further optimize the estimation accuracy under given privacy levels by choosing specific randomization strategies.

The popularity of mobile devices has far expanded the application scenarios of spatial crowdsensing, due to its ability to provide fine-grained multi dimensional sensor readings associated with location information. Privacy is one of the fundamental issues in crowdsensing, as these location-based sensor readings may reveal identities or activities of participants. In this paper, we adopts the state-of-art location privacy definition geo-indistinguishability, provide an efficient and effective privacy preserving histogram aggregation mechanism BFMM (Bit Flipping Matrix Mechanism) for fine-grained multi dimensional location-based data. Theoretical analyses and experimental results demonstrate the efficiency and effectiveness of our approach for fine-grained multidimensional location-based data. Specifically, the aggregation accuracy of our approach averagely outperforms existing methods by a factor of number of buckets in the histogram.

As the size of smartphone touchscreens becomes larger and larger in recent years, operability with single hand is getting worse especially for female users. We envision that user experience can be significantly improved if smartphones are able to detect the current operating hand and adjust the UI subsequently. In this paper, we propose a novel scheme that leverages user-generated touchscreen traces to recognize current operating hand accurately, with the help of a supervised classifier constructed from twelve different kinds of touchscreen trace features. As opposed to existing solutions that all require users to select the current operating hand or dominant hand manually, our scheme follows a more convenient and practical manner, and allows users to change operating hand frequently without any harm to user experience. We conduct a series of real-world experiments on Samsung Galaxy S4 smartphones, and evaluation results demonstrate that our proposed approach achieves 94.1% accuracy when deciding with a single trace only, and the false positive rate is as low as 2.6%.