Differentialy-Private Stochastic Gradient Descent (DP-SGD) is the benchmark for protecting sensitive data while training deep neural networks. However, it relies on fixed or heuristic schedules for key parameters such as noise multiplier and clipping threshold, often leading to suboptimal privacy-utility trade-offs. We propose a novel, curvature-aware training framework that dynamically adapts DP-SGD parameters based on the geometry of the loss surface. Leveraging public data, we estimate the local curvature via dominant Hessian eigenvalues and use this signal to compute an expected excess risk (EER) metric. This EER guides real-time adjustments of the DP-SGD mechanism. Our method operates in highly non-convex settings, beyond the limitations of prior EER-based strategies that assume convexity or PL conditions. Experimental results on MNIST, CIFAR-10, and SVHN demonstrate that our approach consistently improves model accuracy and convergence speed under tight privacy constraints, existing baselines.

Large Language Models (LLMs) have become central to modern NLP applications, yet their reliance on sensitive training data introduces significant privacy risks. Traditional approaches to differential privacy, such as DP-SGD, apply uniform noise at the gradient level and treat all features equally, ignoring the inherent correlations in structured sequence data. In this work, we propose a novel forward-pass privacy mechanism that applies per-attribute differential privacy across correlated sequence inputs. Our framework leverages the Matrix-Variate Gaussian (MVG) mechanism to inject structured, directional noise during the forward computation, enabling fine-grained privacy control that aligns with attribute sensitivity. Privacy budgets are assigned on a per-token basis using an Inverse Gaussian Distribution, allowing position-aware adaptation across input sequences. To propagate these budgets through the model, we introduce a data-independent Layer-Wise Contribution Propagation (LCP) algorithm that maps input sensitivity to output features, even in transformer architectures. We validate our method on the SST-2 sentiment classification benchmark, demonstrating improved utility over existing approaches such as DPSGD and DP-Forward, particularly under strict privacy regimes. Our results highlight the benefits of structured noise in preserving utility while ensuring strong, attribute-level privacy in models trained on correlated sequential data.

Bilinear maps are used as an essential cryptographic building block in many of the advanced encryption algorithms today, such as searchable encryption, identity-based encryption, group signatures, etc. Numerous data and application privacy techniques make use of such primitives. However, the performance overhead of bilinear map encryption, and in particular that of the \em pairing operation, which is the predominant operation on bilinear maps, is still quite high. In this paper, we investigate in-depth the sequence of steps required to compute bilinear map pairings, and we identify the performance footprint of each step. We devise an implementation based on FPGA which reduces the overhead of bilinear pairings, in terms of both execution time and resource utilization (i.e., lookup tables and flip-flop units required). Our extensive performance evaluation shows that the proposed approach significantly outperforms benchmarks, and represents an important step towards the wide-scale deployment of bilinear map-based encryption protocol for large-scale applications.

and we propose a spatial indexing algorithm that accounts for fairness. Our KD-tree inspired approach significantly improves fairness while maintaining high learning accuracy, as shown by extensive experimental results on real data.

BLE beacon networks are widely adopted for IoT and smart city applications, but they are susceptible to security threats, including piggybacking and spoofing attacks. These attacks can infringe on or even jeopardize the profitability of network owners. To address this issue, BLE beacon packets are often encrypted or updated periodically, which requires frequent synchronization between individual beacons and a centralized server, consuming significant resources. We propose a novel crowd-assisted, secure BLE identifier (ID) updating framework that significantly reduces network overhead. The proposed framework quantifies mobile crowdsourcing participant presence to dynamically adjust the pool size of the required beacon IDs. Our experiments, which factor in real-life user presence information, prove the practicality of our framework, which reduced the network resource consumption by up to 90%.

Abstract Location-based alerts have gained increasing popularity in recent years, whether in the context of healthcare (e.g., COVID-19 contact tracing), marketing (e.g., location-based advertising), or public safety. However, serious privacy concerns arise when location data are used in clear in the process. Several solutions employ searchable encryption (SE) to achieve secure alerts directly on encrypted locations. While doing so preserves privacy, the performance overhead incurred is high. We focus on a prominent SE technique in the public-key setting–hidden vector encryption, and propose a graph embedding technique to encode location data in a way that significantly boosts the performance of processing on ciphertexts. We show that the optimal encoding is NP-hard, and we provide three heuristics that obtain significant performance gains: gray optimizer, multi-seed gray optimizer and scaled gray optimizer. Furthermore, we investigate the more challenging case of dynamic alert zones, where the area of interest changes over time. Our extensive experimental evaluation shows that our solutions can significantly improve computational overhead compared to existing baselines.

Voice assistant systems (VAS), such as Google Assistant or Amazon Alexa, provide convenient means for users to interact verbally with online services. VAS is particularly important for users with severe health conditions or motor skills impairment. At the same time, voice commands may contain highly-sensitive information about individuals. Therefore, sharing such data with service providers must be done in a carefully controlled and transparent manner in order to prevent privacy breaches. One important challenge is identifying which voice commands contain sensitive information. Different individuals are likely to have distinct interpretations of what is sensitive and what must be kept private, depending on gender, age, cultural background, etc. Furthermore, even for the same individual, the context in which a command is issued can result in significantly different sensitivity perceptions. We introduce a framework named VPASS that supports the management of personalized privacy requirements for VAS systems. Specifically, we propose mechanisms to quantify two key aspects: the amount of information disclosure and the level of privacy sensitivity that each voice command has. Our mechanisms employ deep transfer learning techniques for processing voice commands and can accurately detect privacy-sensitive commands based on an individual’s prior history of VAS interaction. Finally, VPASS generates monthly reports or immediate privacy alerts based on the privacy policies pre-defined by users.

Several "data-for-good" projects [1, 5, 12] initiated by major companies (e.g., Meta, Google) release to the public spatio-temporal datasets to benefit COVID-19 spread modeling [17, 47, 64] and understand human mobility [14, 24]. Most often, spatio-temporal data are provided in the form of snapshot high resolution population density information, where the released statistics capture population counts in small areas for short time periods. Since high resolution is required for utility (e.g., in modeling COVID hotspots) privacy risks are elevated. To prevent malicious actors from using the data to infer sensitive details about individuals, the released datasets must be first sanitized. Typically, [1, 5, 7, 12], differential privacy (DP) is employed as protection model, due to its formal protection guarantees that prevent an adversary to learn whether a particular individual's data has been included in the release or not.

Fairness in data-driven decision-making studies scenarios where individuals from certain population segments may be unfairly treated when being considered for loan or job applications, access to public resources, or other types of services. In location-based applications, decisions are based on individual whereabouts, which often correlate with sensitive attributes such as race, income, and education. While fairness has received significant attention recently, e.g., in machine learning, there is little focus on achieving fairness when dealing with location data. Due to their characteristics and specific type of processing algorithms, location data pose important fairness challenges. We introduce the concept of spatial data fairness to address the specific challenges of location data and spatial queries. We devise a novel building block to achieve fairness in the form of fair polynomials. Next, we propose two mechanisms based on fair polynomials that achieve individual spatial fairness, corresponding to two common location-based decision-making types: distance-based and zone-based. Extensive experimental results on real data show that the proposed mechanisms achieve spatial fairness without sacrificing utility.

Mobile apps and location-based services generate large amounts of location data. Location density information from such datasets benefits research on traffic optimization, context-aware notifications and public health (e.g., disease spread). To preserve individual privacy, one must sanitize location data, which is commonly done using differential privacy (DP). Existing methods partition the data domain into bins, add noise to each bin and publish a noisy histogram of the data. However, such simplistic modelling choices fall short of accurately capturing the useful density information in spatial datasets and yield poor accuracy. We propose a machine-learning based approach for answering range count queries on location data with DP guarantees. We focus on countering the sources of error that plague existing approaches (i.e., noise and uniformity error) through learning, and we design a neural database system that models spatial data such that density features are preserved, even when DP-compliant noise is added. We also devise a framework for effective system parameter tuning on top of public data, which helps set important system parameters without expending scarce privacy budget. Extensive experimental results on real datasets with heterogeneous characteristics show that our proposed approach significantly outperforms the state of the art.

Location data are widely used in mobile apps, ranging from location-based recommendations, to social media and navigation. A specific type of interaction is that of location-based alerts, where mobile users subscribe to a service provider (SP) in order to be notified when a certain event occurs nearby. Consider, for instance, the ongoing COVID-19 pandemic, where contact tracing has been singled out as an effective means to control the virus spread. Users wish to be notified if they came in proximity to an infected individual. However, serious privacy concerns arise if the users share their location history with the SP in plaintext. To address privacy, recent work proposed several protocols that can securely implement location-based alerts. The users upload their encrypted locations to the SP, and the evaluation of location predicates is done directly on ciphertexts. When a certain individual is reported as infected, all matching ciphertexts are found (e.g., according to a predicate such as “10 feet proximity to any of the locations visited by the infected patient in the last week”), and the corresponding users notified. However, there are significant performance issues associated with existing protocols. The underlying searchable encryption primitives required to perform the matching on ciphertexts are expensive, and without a proper encoding of locations and search predicates, the performance can degrade a lot. In this paper, we propose a novel method for variable-length location encoding based on Huffman codes. By controlling the length required to represent encrypted locations and the corresponding matching predicates, we are able to significantly speed up performance. We provide a theoretical analysis of the gain achieved by using Huffman codes, and we show through extensive experiments that the improvement compared with fixed-length encoding methods is substantial. © 2021 Copyright held by the owner/author(s).

Mobile apps that use location data are pervasive, spanning domains such as transportation, urban planning and healthcare. Important use cases for location data rely on statistical queries, e.g., identifying hotspots where users work and travel. Such queries can be answered efficiently by building histograms. However, precise histograms can expose sensitive details about individual users. Differential privacy (DP) is a mature and widely-adopted protection model, but most approaches for DP-compliant histograms work in a data-independent fashion, leading to poor accuracy. The few proposed data-dependent techniques attempt to adjust histogram partitions based on dataset characteristics, but they do not perform well due to the addition of noise required to achieve DP. We identify density homogeneity as a main factor driving the accuracy of DP-compliant histograms, and we build a data structure that splits the space such that data density is homogeneous within each resulting partition. We show through extensive experiments on large-scale real-world data that the proposed approach achieves superior accuracy compared to existing approaches.

Skyline computation is an increasingly popular query, with broad applicability to many domains. Given the trend to outsource databases, and due to the sensitive nature of the data (e.g., in healthcare), it is essential to evaluate skylines on encrypted datasets. Research efforts acknowledged the importance of secure skyline computation, but existing solutions suffer from several shortcomings: (i) they only provide ad-hoc security; (ii) they are prohibitively expensive; or (iii) they rely on assumptions such as the presence of multiple non-colluding parties in the protocol. Inspired by solutions for secure nearest-neighbors, we conjecture that a secure and efficient way to compute skylines is through result materialization. However, materialization is much more challenging for skylines queries due to large space requirements. We show that pre-computing skyline results while minimizing storage overhead is NP-hard, and we provide heuristics that solve the problem more efficiently, while maintaining storage at reasonable levels. Our algorithms are novel and also applicable to regular skyline computation, but we focus on the encrypted setting where materialization reduces the response time of skyline queries from hours to seconds. Extensive experiments show that we clearly outperform existing work in terms of performance, and our security analysis proves that we obtain a small (and quantifiable) data leakage.

Association rule mining discovers patterns in large data repositories, and benefits diverse application domains such as healthcare, marketing, etc. However, mining datasets that contain data about individuals may cause significant privacy breaches. Recent research addresses the privacy threats that arise when mining sensitive data, and several techniques allow data mining with differential privacy guarantees. However, existing methods only discover rules that have very large support, i.e., occur in a large fraction of the dataset transactions (typically, more than 50 percent). This is a serious limitation, as numerous high-quality rules do not reach such high frequencies (e.g., rules about rare diseases, or luxury merchandise). We propose a method that focuses on mining high-quality association rules with moderate and low frequencies. We employ a novel technique for rule extraction that combines the exponential mechanism of differential privacy with reservoir sampling. The proposed algorithm allows us to directly mine association rules, without the need to compute noisy supports for large numbers of itemsets. Our experimental evaluation shows that our technique is able to sample low- and moderate-support rules with good precision, clearly outperforming existing solutions.

Mobile devices with rich features can record videos, traffic parameters or air quality readings along user trajectories. Although such data may be valuable, users are seldom rewarded for collecting them. Emerging digital marketplaces allow owners to advertise their data to interested buyers. We focus on geo-marketplaces, where buyers search data based on geo-tags. Such marketplaces present significant challenges. First, if owners upload data with revealed geo-tags, they expose themselves to serious privacy risks. Second, owners must be accountable for advertised data, and must not be allowed to subsequently alter geo-tags. Third, such a system may be vulnerable to intensive spam activities, where dishonest owners flood the system with fake advertisements. We propose a geo-marketplace that addresses all these concerns. We employ searchable encryption, digital commitments, and blockchain to protect the location privacy of owners while at the same time incorporating accountability and spam-resilience mechanisms. We implement a prototype with two alternative designs that obtain distinct trade-offs between trust assumptions and performance. Our experiments on real location data show that one can achieve the above design goals with practical performance and reasonable financial overhead.

The proliferation of location-centric applications results in massive amounts of individual location data that can benefit domains such as transportation, urban planning, etc. However, sensitive personal data can be derived from location datasets. In particular, co-location of users can disclose one's social connections, intimate partners, business associates, etc. We derive a powerful inference attack that makes extensive use of background knowledge in order to expose an individual's co-locations. We also show that existing techniques for location protection, which do not focus specifically on co-locations, distort data excessively, resulting in sanitized datasets with poor utility. We propose three privacy mechanisms that are customized for co-locations, and provide various trade-offs in terms of user privacy and data utility. Our extensive experimental evaluation on a real geo-social network dataset shows that the proposed approaches achieve good data utility and do a good job of protecting against discovery of co-locations, even when confronted with a powerful adversary.

poster Public Access Share on An Empirical Study of Differentially-Private Analytics for High-Speed Network Data Authors: Oana-Georgiana Niculaescu University of Massachusetts, Boston, MA, USA University of Massachusetts, Boston, MA, USAView Profile , Gabriel Ghinita University of Massachusetts, Boston, MA, USA University of Massachusetts, Boston, MA, USAView Profile Authors Info & Claims CODASPY '18: Proceedings of the Eighth ACM Conference on Data and Application Security and PrivacyMarch 2018 Pages 149–151https://doi.org/10.1145/3176258.3176944Published:13 March 2018Publication History 0citation118DownloadsMetricsTotal Citations0Total Downloads118Last 12 Months21Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In Spatial Crowdsourcing (SC), a set of spatio-temporal tasks are outsourced to a set of workers, i.e., individuals with mobile devices who physically travel to task locations. The process of matching workers to tasks is performed by a SC server. To perform matching, the SC server needs access to worker locations. However, the SC server may not be trustworthy. Current solutions for protecting locations of workers assume that a trusted cellular service provider (CSP) knows the identities and locations of workers and sanitizes locations before sharing them with the SC server. In practice, the CSP may not have the technical ability, nor the proper incentives to perform the sanitization task. Thus, location protection must be performed by a Location Privacy Provider (LPP). To prevent identity disclosure to the LPP, we propose a novel solution based on anonymous credentials which preserves worker privacy. Our solution allows registered workers to log on to the LPP and receive tasks from the SC-server anonymously. In addition, our solution assures the confidentiality and integrity of spatial tasks. Our implementation and experiments demonstrate that our solution is practical.

High-speed research networks (e.g., Internet2, Geant) represent the backbone of large-scale research projects that bring together stakeholders from academia, industry and government. Such projects have increasing demands on throughput (e.g., 100Gbps line rates), and require a high amount of configurability. Collecting and sharing traffic data for such networks can help in detecting hotspots, troubleshooting, and designing novel routing protocols. However, sharing network data directly introduces serious privacy breaches, as an adversary may be able to derive private details about individual users (e.g., personal preferences or activity patterns). Our objective is to sanitize high-speed research network data according to the de-facto standard of differential privacy (DP), thus supporting benefic applications of traffic measurement without compromising individuals' privacy. In this paper, we present an initial framework for computing DP-compliant big data analytics for high-speed research network data. Specifically, we focus on sharing data at flow-level granularity, and we describe our initial steps towards an environment that relies on Hadoop and HBase to support privacy-preserving NetFlow analytics.

Recent years witnessed a tremendous growth in the area of mobile computing. Users with mobile devices are able to access services customized to their geographical coordinates, and to engage in complex interactions with other users in their proximity. However, in addition to its many benefits, sharing location with service providers and other users also introduces serious privacy threats. If not properly addressed, the loss of location privacy can bring significant harm to mobile users. Currently, there is a low level of awareness among mobile users with respect to the contingent threats on location privacy, and to the approaches available to mitigate such threats. We propose an educational capture-the-flag (CTF) - style tool designed to raise the level of awareness about the dangers of uncontrolled sharing of location data, and to illustrate prominent location protection techniques. The game-based approach represents an effective and engaging educational tool, suitable for high-school and college students, as well as computer-literate general population mobile users.

Spatial Crowdsourcing (SC) is a transformative platform that engages individuals in collecting and analyzing environmental, social, and other spatio-temporal information. SC outsources spatio-temporal tasks to a set of workers, i.e., individuals with mobile devices that perform the tasks by physically traveling to specified locations. However, current solutions require the workers to disclose their locations to untrusted parties. In this paper, we introduce a framework for protecting location privacy of workers participating in SC tasks. We propose a mechanism based on differential privacy and geocasting that achieves effective SC services while offering privacy guarantees to workers. We address scenarios with both static and dynamic (i.e., moving) datasets of workers. Experimental results on real-world data show that the proposed technique protects location privacy without incurring significant performance overhead.

Provenance workflows capture movement and transformation of data in complex environments, such as document management in large organizations, content generation and sharing in in social media, scientific computations, etc. Sharing and processing of provenance workflows brings numerous benefits, e.g., improving productivity in an organization, understanding social media interaction patterns, etc. However, directly sharing provenance may also disclose sensitive information such as confidential business practices, or private details about participants in a social network. We propose an algorithm that privately extracts sequential association rules from provenance workflow datasets. Finding such rules has numerous practical applications, such as capacity planning or identifying hot-spots in provenance graphs. Our approach provides good accuracy and strong privacy, by leveraging on the exponential mechanism of differential privacy. We propose an heuristic that identifies promising candidate rules and makes judicious use of the privacy budget. Experimental results show that the our approach is fast and accurate, and clearly outperforms the state-of-the-art. We also identify influential factors in improving accuracy, which helps in choosing promising directions for future improvement.

Mobile users participate in numerous social media applications that revolve around user locations, and receive customized services and recommendations tailored to their whereabouts. Large amounts of trajectory data become available as a byproduct of such services. Studying such data reveals travel patterns which can benefit transportation planning, public safety, etc. However, disclosing such data may lead to serious breaches of privacy. We propose a privacy-preserving approach to mining representative travel patterns using differential privacy (DP). Our solution consists of a sampling algorithm based on the exponential mechanism (EM) of DP which uses public road network information to increase sanitization accuracy. Extensive experimental results on realistic workloads show that the proposed protection technique preserves data precision and is computationally efficient.

Private Information Retrieval (PIR) protocols allow users to search for data items stored at an untrusted server, without disclosing to the server the search attributes. Several computational PIR protocols provide cryptographic-strength guarantees for the privacy of users, building upon well-known hard mathematical problems, such as factorisation of large integers. Unfortunately, the computational-intensive nature of these solutions results in significant performance overhead, preventing their adoption in practice. In this paper, we employ graphical processing units (GPUs) to speed up the cryptographic operations required by PIR. We identify the challenges that arise when using GPUs for PIR and we propose solutions to address them. To the best of our knowledge, this is the first work to use GPUs for efficient private information retrieval, and an important first step towards GPU-based acceleration of a broader range of secure data operations. Our experimental evaluation shows that GPUs improve performance by more than an order of magnitude.

Association rule mining allows discovering of patterns in large data repositories, and benefits diverse application domains such as healthcare, marketing, social studies, etc. However, mining datasets that contain data about individuals may cause significant privacy breaches, and disclose sensitive information about one's health status, political orientation or alternative lifestyle. Recent research addressed the privacy threats that arise when mining sensitive data, and several techniques allow data mining with differential privacy guarantees. However, existing methods only discover rules that have very large support, i.e., occur in a large fraction of the dataset transactions (typically, more than 50%). This is a serious limitation, as numerous high-quality rules do not reach such high frequencies (e.g., rules about rare diseases, or luxury merchandise).

Spatial Crowdsourcing (SC) is a novel and transformative platform that engages individuals, groups and communities in the act of collecting, analyzing, and disseminating environmental, social and other spatio-temporal information. SC outsources a set of spatio-temporal tasks to a set of workers, i.e., individuals with mobile devices that perform the tasks by physically traveling to specified locations of interest. Protecting location privacy is an important concern in SC, as an adversary with access to individual whereabouts can infer sensitive details about a person (e.g., health status, political views). Due to the challenging nature of protecting worker privacy in SC, solutions for this problem are quite complex, and require tuning of several parameters to obtain satisfactory results. In this paper, we propose PrivGeoCrowd, a toolbox for interactive visualization and tuning of SC private task assignment methods. This toolbox is useful for several real-world entities that are involved in SC, such as: mobile phone operators that want to sanitize datasets with worker locations, spatial task requesters, and SC-service providers that match workers to tasks.

Large-scale sensor networks are deployed in numerous application domains, and the data they collect are used in decision-making for critical infrastructures. Data are streamed from multiple sources through intermediate processing nodes that aggregate information. A malicious adversary may introduce additional nodes in the network or compromise existing ones. Therefore, assuring high data trustworthiness is crucial for correct decision-making. Data provenance represents a key factor in evaluating the trustworthiness of sensor data. Provenance management for sensor networks introduces several challenging requirements, such as low energy and bandwidth consumption, efficient storage and secure transmission. In this paper, we propose a novel lightweight scheme to securely transmit provenance for sensor data. The proposed technique relies on in-packet Bloom filters to encode provenance. We introduce efficient mechanisms for provenance verification and reconstruction at the base station. In addition, we extend the secure provenance scheme with functionality to detect packet drop attacks staged by malicious data forwarding nodes. We evaluate the proposed technique both analytically and empirically, and the results prove the effectiveness and efficiency of the lightweight secure provenance scheme in detecting packet forgery and loss attacks.

Monitoring location updates from mobile users has important applications in several areas, ranging from public safety and national security to social networks and advertising. However, sensitive information can be derived from movement patterns, so protecting the privacy of mobile users is a major concern. Users may only be willing to disclose their locations when some condition is met, for instance in proximity of a disaster area, or when an event of interest occurs nearby. Currently, such functionality is achieved using searchable encryption. Such cryptographic primitives provide provable guarantees for privacy, and allow decryption only when the location satisfies some predicate. Nevertheless, they rely on expensive pairing-based cryptography (PBC), and direct application to the domain of location updates leads to impractical solutions.

Provenance workflows capture the data movement and the operations changing the data in complex applications such as scientific computations, document management in large organizations, content generation in social media, etc. Provenance is essential to understand the processes and operations that data undergo, and many research efforts focused on modeling, capturing and analyzing provenance information. Sharing provenance brings numerous benefits, but may also disclose sensitive information, such as secret processes of synthesizing chemical substances, confidential business practices and private details about social media participants' lives. In this paper, we study privacy-preserving provenance workflow publication using differential privacy. We adapt techniques designed for sanitization of multi-dimensional spatial data to the problem of provenance workflows. Experimental results show that such an approach is feasible to protect provenance workflows, while at the same time retaining a significant amount of utility for queries. In addition, we identify influential factors and trade-offs that emerge when sanitizing provenance workflows.

Mobile users engage in novel and exciting location-based social media applications (e.g., geosocial networks, spatial crowdsourcing) in which they interact with other users situated in their proximity. In several application scenarios, users define their own proximity zones of interest (typically in the form of polygonal regions, such as a collection of city blocks), and want to find other users with whom they are in a mutual enclosure relationship with respect to their respective proximity zones. This boils down to evaluating two point-in-polygon enclosure conditions, which is easy to achieve for revealed user locations and proximity zones. However, users may be reluctant to share their whereabouts with their friends and with social media service providers, as location data can help one infer sensitive details such as an individual's health status, financial situation or lifestyle choices. In this paper, we propose a mechanism that allows users to securely evaluate mutual proximity zone enclosure on encrypted location data. Our solution uses homomorphic encryption, and supports convex polygonal proximity zones. We provide a security analysis of the proposed solution, we investigate performance optimizations, and we show experimentally that our approach scales well for datasets of millions of users.

Latest generation mobile devices allow users to receive services tailored to their current locations. Location-based service providers perform spatial queries based on the user locations, but may also share them with various third parties. User whereabouts may disclose sensitive details about an individual's health status, political views or lifestyle choices, and therefore must be thoroughly protected. Private information retrieval (PIR) methods support blind execution of range and NN queries with cryptographic-strength security, but incur significant performance overhead. We employ graphical processing units (GPUs) to speed up the crypto operations required by PIR. We identify the challenges that arise when using GPUs for this purpose, and we propose solutions to address them. To the best of our knowledge, this is the first work to use GPUs for efficient private spatial information retrieval, and an important first step towards GPU-based acceleration of a broader range of secure spatial data operations.

Mining frequent subgraphs from a large collection of graph objects is an important problem in several application domains such as bio-informatics, social networks, computer vision, etc. The main challenge in subgraph mining is efficiency, as (i) testing for graph isomorphisms is computationally intensive, and (ii) the cardinality of the graph collection to be mined may be very large. We propose a two-step filter-and-refinement approach that is suitable to massive parallelization within the scalable MapReduce computing model. We partition the collection of graphs among worker nodes, and each worker applies the filter step to determine a set of candidate subgraphs that are locally frequent in its partition. The union of all such graphs is the input to the refinement step, where each candidate is checked against all partitions and only the globally frequent graphs are retained. We devise a statistical threshold mechanism that allows us to predict which subgraphs have a high chance to become globally frequent, and thus reduce the computational overhead in the refinement step. We also propose effective strategies to avoid redundant computation in each round when searching for candidate graphs, as well as a lightweight graph compression mechanism to reduce the communication cost between machines. Extensive experimental evaluation results on several real-world large graph datasets show that the proposed approach clearly outperforms the existing state-of-the-art and provides a practical solution to the problem of frequent subgraph mining for massive collections of graphs.

Location-tagged social media have an increasingly important role in shaping behavior of individuals. With the help of location recommendations, users are able to learn about events, products or places of interest that are relevant to their preferences. User locations and movement patterns are available from geosocial networks such as Foursquare, mass transit logs or traffic monitoring systems. However, disclosing movement data raises serious privacy concerns, as the history of visited locations can reveal sensitive details about an individual's health status, alternative lifestyle, etc. In this paper, we investigate mechanisms to sanitize location data used in recommendations with the help of differential privacy. We also identify the main factors that must be taken into account to improve accuracy. Extensive experimental results on real-world datasets show that a careful choice of differential privacy technique leads to satisfactory location recommendation results.

Spatial Crowdsourcing (SC) is a transformative platform that engages individuals, groups and communities in the act of collecting, analyzing, and disseminating environmental, social and other spatio-temporal information. The objective of SC is to outsource a set of spatio-temporal tasks to a set of workers , i.e., individuals with mobile devices that perform the tasks by physically traveling to specified locations of interest. However, current solutions require the workers, who in many cases are simply volunteering for a cause, to disclose their locations to untrustworthy entities. In this paper, we introduce a framework for protecting location privacy of workers participating in SC tasks. We argue that existing location privacy techniques are not sufficient for SC, and we propose a mechanism based on differential privacy and geocasting that achieves effective SC services while offering privacy guarantees to workers. We investigate analytical models and task assignment strategies that balance multiple crucial aspects of SC functionality, such as task completion rate, worker travel distance and system overhead. Extensive experimental results on real-world datasets show that the proposed technique protects workers' location privacy without incurring significant performance metrics penalties.

Mobile devices with geo-positioning capabilities (e.g., GPS) enable users to access information that is relevant to their present location. Users are interested in querying about points of interest (POI) in their physical proximity, such as restaurants, cafes, ongoing events, etc. Entities specialized in various areas of interest (e.g., certain niche directions in arts, entertainment, travel) gather large amounts of geo-tagged data that appeal to subscribed users. Such data may be sensitive due to their contents. Furthermore, keeping such information up-to-date and relevant to the users is not an easy task, so the owners of such data sets will make the data accessible only to paying customers. Users send their current location as the query parameter, and wish to receive as result the nearest POIs, i.e., nearest-neighbors (NNs). But typical data owners do not have the technical means to support processing queries on a large scale, so they outsource data storage and querying to a cloud service provider. Many such cloud providers exist who offer powerful storage and computational infrastructures at low cost. However, cloud providers are not fully trusted, and typically behave in an honest-but-curious fashion. Specifically, they follow the protocol to answer queries correctly, but they also collect the locations of the POIs and the subscribers for other purposes. Leakage of POI locations can lead to privacy breaches as well as financial losses to the data owners, for whom the POI data set is an important source of revenue. Disclosure of user locations leads to privacy violations and may deter subscribers from using the service altogether. In this paper, we propose a family of techniques that allow processing of NN queries in an untrusted outsourced environment, while at the same time protecting both the POI and querying users' positions. Our techniques rely on mutable order preserving encoding (mOPE), the only secure order-preserving encryption method known to-date. We also provide performance optimizations to decrease the computational cost inherent to processing on encrypted data, and we consider the case of incrementally updating data sets. We present an extensive performance evaluation of our techniques to illustrate their viability in practice.

With the emergence of cloud computing and location-based services, owners of spatial data (e.g., collections of geo-tagged photos, social network location check-ins, etc.) have the option to outsource services such as storage and query processing to a cloud service provider. However, providers of such services are not trusted to properly execute queries, so clients must be given assurance that the results are trustworthy. Therefore, authentication of database queries is needed to ensure correctness and completeness of the results provided by the cloud provider. One type of spatial query that is prominent in practice is the spatial skyline query (SSQ), which allows clients to retrieve results according to specific preferences. In this paper, we propose a solution for authenticating spatial skyline queries that focuses on reducing communication cost compared to existing solutions (MR-Trees). By using a flexible partitioning of the domain coupled with an efficient heuristic, we obtain communication costs that are up to three times lower than existing state-of-the-art.

Regularly releasing the aggregate statistics about data streams in a privacy-preserving way not only serves valuable commercial and social purposes, but also protects the privacy of individuals. This problem has already been studied under differential privacy, but only for the case of a single continuous query that covers the entire time span, e.g., counting the number of tuples seen so far in the stream. However, most real-world applications are window-based, that is, they are interested in the statistical information about streaming data within a window, instead of the whole unbound stream. Furthermore, a Data Stream Management System (DSMS) may need to answer numerous correlated aggregated queries simultaneously, rather than a single one. To cope with these requirements, we study how to release differentially private answers for a set of sliding window aggregate queries. We propose two solutions, each consisting of query sampling and composition. We first selectively sample a subset of representative sliding window queries from the set of all the submitted ones. The representative queries are answered by adding Laplace noises in a way satisfying differential privacy. For each non-representative query, we compose its answer from the query results of those representatives. The experimental evaluation shows that our solutions are efficient and effective.

Monitoring user location updates has important applications in public safety, national security, etc. However, sensitive information can be derived from movement patterns, so user locations must be disclosed only when some condition is met, for instance in proximity of a disaster area. Searchable encryption techniques provide provable guarantees for privacy, and allow decryption only when the location satisfies some predicate. Nevertheless, they rely on expensive pairing-based cryptography, and direct application to location updates leads to impractical solutions. We propose an efficient technique that leads to significant gains in performance by reducing the amount of pairing operations. We also implement an optimization that reuses results to expensive mathematical operations. Experimental results show that the proposed techniques significantly improve performance compared to the baseline.

Sensor networks are being increasingly deployed in many application domains ranging from environment monitoring to supervising critical infrastructure systems (e.g., the power grid). Due to their ability to continuously collect large amounts of data, sensor networks represent a key component in decisionmaking, enabling timely situation assessment and response. However, sensors deployed in hostile environments may be subject to attacks by adversaries who intend to inject false data into the system. In this context, data trustworthiness is an important concern, as false readings may result in wrong decisions with serious consequences (e.g., large-scale power outages). To defend against this threat, it is important to establish trust levels for sensor nodes and adjust node trustworthiness scores to account for malicious interferences. In this paper, we develop a game-theoretic defense strategy to protect sensor nodes from attacks and to guarantee a high level of trustworthiness for sensed data. We use a discrete time model, and we consider that there is a limited attack budget that bounds the capability of the attacker in each round. The defense strategy objective is to ensure that sufficient sensor nodes are protected in each round such that the discrepancy between the value accepted and the truthful sensed value is below a certain threshold. We model the attack-defense interaction as a Stackelberg game, and we derive the Nash equilibrium condition that is sufficient to ensure that the sensed data are truthful within a nominal error bound. We implement a prototype of the proposed strategy and we show through extensive experiments that our solution provides an effective and efficient way of protecting sensor networks from attacks.

Large-scale sensor networks are being deployed in numerous application domains, and often the data they collect are used in decision-making for critical infrastructures. Data are streamed from multiple sources through intermediate processing nodes that aggregate information. A malicious adversary may tamper with the data by introducing additional nodes in the network, or by compromising existing ones. Therefore, assuring high data trustworthiness in such a context is crucial for correct decision-making. Data provenance represents a key factor in evaluating the trustworthiness of sensor data. Provenance management for sensor networks introduces several challenging requirements, such as low energy and bandwidth consumption, efficient storage and secure transmission. In this paper, we propose a novel light-weight scheme to securely transmit provenance for sensor data. The proposed technique relies on in-packet Bloom filters to encode provenance. In addition, we introduce efficient mechanisms for provenance verification and reconstruction at the base station. We evaluate the proposed technique both analytically and empirically, and the results prove its effectiveness and efficiency for secure provenance encoding and decoding.

In-network aggregation is an essential operation which reduces communication overhead and power consumption of resource-constrained sensor network nodes. Sensor nodes are typically organized into an aggregation tree, whereby aggregator nodes collect data from multiple data source nodes, and perform a reduction operation such as sum, average, minimum, etc. The result is then forwarded to other aggregators higher in the hierarchy toward a base station (or sink node) that receives the final outcome of the in-network computation. However, despite its performance benefits, aggregation introduces several difficult security challenges with respect to data confidentiality, integrity and authenticity. In today's outsource-centric computing environments, the aggregation task may be delegated to a third party that is not fully trusted. In addition, even in the absence of outsourcing, nodes may be compromised by a malicious adversary with the purpose of altering aggregation results. To defend against such threats, several mechanisms have been proposed, most of which devise aggregation schemes that rely on cryptography to detect that an attack has occurred. Although they prevent the sink from accepting an incorrect result, such techniques are vulnerable to denial-of-service if a compromised node alters the aggregation result in each round. Several more recent approaches also identify the malicious nodes and exclude them from future computation rounds. However, these incur high communication overhead as they require flooding or other expensive communication models to connect individual nodes with the base station. We propose a flexible aggregation structure (FAS) and an advanced ring structure (ARS) topology that allow secure aggregation and efficient identification of malicious aggregator nodes for the SUM operation. Our scheme uses only symmetric key cryptography, outperforms existing solutions in terms of performance, and guarantees that the aggregate result is correct and that malicious nodes are identified.

Real-world entities are not always represented by the same set of features in different data sets. Therefore, matching records of the same real-world entity distributed across these data sets is a challenging task. If the data sets contain private information, the problem becomes even more difficult. Existing solutions to this problem generally follow two approaches: sanitization techniques and cryptographic techniques. We propose a hybrid technique that combines these two approaches and enables users to trade off between privacy, accuracy, and cost. Our main contribution is the use of a blocking phase that operates over sanitized data to filter out in a privacy-preserving manner pairs of records that do not satisfy the matching condition. We also provide a formal definition of privacy and prove that the participants of our protocols learn nothing other than their share of the result and what can be inferred from their share of the result, their input and sanitized views of the input data sets (which are considered public information). Our method incurs considerably lower costs than cryptographic techniques and yields significantly more accurate matching results compared to sanitization techniques, even when privacy requirements are high.

Modern computer systems are built on a foundation of software components from a variety of vendors. While critical applications may undergo extensive testing and evaluation procedures, the heterogeneity of software sources threatens the integrity of the execution environment for these trusted programs. For instance, if an attacker can combine an application exploit with a privilege escalation vulnerability, the operating system (OS) can become corrupted. Alternatively, a malicious or faulty device driver running with kernel privileges could threaten the application. While the importance of ensuring application integrity has been studied in prior work, proposed solutions immediately terminate the application once corruption is detected. Although, this approach is sufficient for some cases, it is undesirable for many critical applications. In order to overcome this shortcoming, we have explored techniques for leveraging a trusted virtual machine monitor (VMM) to observe the application and potentially repair damage that occurs. In this paper, we describe our system design, which leverages efficient coding and authentication schemes, and we present the details of our prototype implementation to quantify the overhead of our approach. Our work shows that it is feasible to build a resilient execution environment, even in the presence of a corrupted OS kernel, with a reasonable amount of storage and performance overhead.

Several models for incorporating spatial constraints into role-based access control (RBAC) have been proposed, and researchers are now focusing on the challenge of ensuring such policies are enforced correctly. However, existing approaches have a major shortcoming, as they assume the server is trustworthy and require complete disclosure of sensitive location information by the user. In this work, we propose a novel framework and a set of protocols to solve this problem. Specifically, in our scheme, a user provides a service provider with role and location tokens along with a request. The service provider consults with a role authority and a location authority to verify the tokens and evaluate the policy. However, none of the servers learn the requesting user's identity, role, or location. In this paper, we define the protocols and the policy enforcement scheme, and present a formal proof of a number of security properties.

Data represent an extremely important asset for any organization. Confidential data such as military secrets or intellectual property must never be disclosed outside the organization. Therefore, one of the most severe threats in the case of cyber-insider attacks is the loss of confidential data due to exfiltration. A malicious insider who has the proper credentials to access the organization databases may, over time, send data outside the organization network through a variety of channels, such as email, crafted HTTP requests that encapsulate data, etc. Existing security tools for detection of cyber-attacks focus on protecting the boundary between the organization and the outside world. Numerous network-level intrusion detection systems (IDS) exist, which monitor the traffic pattern and attempt to infer anomalous behavior. While such tools may be effective in protecting against external attacks, they are less suitable when the data exfiltration is performed by an insider who has the proper credentials and authorization to access resources within the organization. In this paper, we argue that DBMS-layer detection and prevention systems are the best alternative to defend against data exfiltration because: (1) DBMS access is performed through a standard, unique language (SQL) with well-understood semantics; (2) monitoring the potential disclosure of confidential data is more effective if done as close as possible to the data source; and (3) the DBMS layer already has in place a thorough mechanism for enforcing access control based on subject credentials. By analyzing the pattern of interaction between subjects and the DBMS, it is possible to detect anomalous activity that is indicative of early signs of exfiltration. In the paper, we outline a taxonomy of cyber-insider dimensions of activities that are indicative of data exfiltration, and we discuss a high-level architecture and mechanisms for early detection of exfiltration by insiders. We also outline a virtualization-based mechanism that prevents insiders from exfiltrating data, even in the case when they manage to gain control over the network. The protection mechanism relies on explicit authorization of data transfers that cross the organizational boundary.

In recent years, organizations ranging from defense and other government institutions to commercial enterprises, research labs, etc., have witnessed an increasing amount of sophisticated insider attacks that manage to bypass existing security controls. Insider threats are staged by either disgruntled employees, or employees engaged in malicious activities such as industrial espionage. The objectives of such threats range from sabotage, e.g., in order to disrupt the completion of a project, to exfiltration of sensitive data such as trade secrets, patents, etc. Insiders are often skilled and motivated individuals with good knowledge of internal security measures in the organization. They devise effective and carefully planned attacks, prepared over long periods of time and customized to inflict maximum damage. Such attacks are difficult to detect and protect against, because insiders have the proper credentials to access services and systems within the organization, and possess knowledge that may allow them to deceive network defense controls. As a result, a large number of hosts may be taken over, allowing malicious insiders to maintain control over the network even after leaving the organization.

Assessing the trustworthiness of location data corresponding to individuals is essential in several applications, such as forensic science and epidemic control. To obtain accurate and trustworthy location data, analysts must often gather and correlate information from several independent sources, e.g., physical observation, witness testimony, surveillance footage, etc. However, such information may be fraudulent, its accuracy may be low, and its volume may be insufficient to ensure highly trustworthy data. On the other hand, recent advancements in mobile computing and positioning systems, e.g., GPS-enabled cell phones, highway sensors, etc., bring new and effective technological means to track the location of an individual. Nevertheless, collection and sharing of such data must be done in ways that do not violate an individual's right to personal privacy.

Existing research on privacy-preserving data publishing focuses on relational data: in this context, the objective is to enforce privacy-preserving paradigms, such as k-anonymity and ℓ-diversity, while minimizing the information loss incurred in the anonymizing process (i.e., maximize data utility). Existing techniques work well for fixed-schema data, with low dimensionality. Nevertheless, certain applications require privacy-preserving publishing of transactional data (or basket data), which involve hundreds or even thousands of dimensions, rendering existing methods unusable. We propose two categories of novel anonymization methods for sparse high-dimensional data. The first category is based on approximate nearest-neighbor (NN) search in high-dimensional spaces, which is efficiently performed through locality-sensitive hashing (LSH). In the second category, we propose two data transformations that capture the correlation in the underlying data: 1) reduction to a band matrix and 2) Gray encoding-based sorting. These representations facilitate the formation of anonymized groups with low information loss, through an efficient linear-time heuristic. We show experimentally, using real-life data sets, that all our methods clearly outperform existing state of the art. Among the proposed techniques, NN-search yields superior data utility compared to the band matrix transformation, but incurs higher computational overhead. The data transformation based on Gray code sorting performs best in terms of both data utility and execution time.

Private Information Retrieval (PIR) protocols allow users to learn data items stored at a server which is not fully trusted, without disclosing to the server the particular data element retrieved. Several PIR protocols have been proposed, which provide strong guarantees on user privacy. Nevertheless, in many application scenarios it is important to protect the database as well. In this paper, we investigate the amount of data disclosed by the the most prominent PIR protocols during a single run. We show that a malicious user can stage attacks that allow an excessive amount of data to be retrieved from the server. Furthermore, this vulnerability can be exploited even if the client follows the legitimate steps of the PIR protocol, hence the malicious request can not be detected and rejected by the server. We devise mechanisms that limit the PIR disclosure to a single data item.

Private matching between datasets owned by distinct parties is a challenging problem with several applications. Private matching allows two parties to identify the records that are close to each other according to some distance functions, such that no additional information other than the join result is disclosed to any party. Private matching can be solved securely and accurately using secure multi-party computation (SMC) techniques, but such an approach is prohibitively expensive in practice. Previous work proposed the release of sanitized versions of the sensitive datasets which allows blocking, i.e., filtering out sub-sets of records that cannot be part of the join result. This way, SMC is applied only to a small fraction of record pairs, reducing the matching cost to acceptable levels. The blocking step is essential for the privacy, accuracy and efficiency of matching. However, the state-of-the-art focuses on sanitization based on k-anonymity, which does not provide sufficient privacy. We propose an alternative design centered on differential privacy, a novel paradigm that provides strong privacy guarantees. The realization of the new model presents difficult challenges, such as the evaluation of distance-based matching conditions with the help of only a statistical queries interface. Specialized versions of data indexing structures (e.g., kd-trees) also need to be devised, in order to comply with differential privacy. Experiments conducted on the real-world Census-income dataset show that, although our methods provide strong privacy, their effectiveness in reducing matching cost is not far from that of k-anonymity based counterparts.

Private matching (or join) of spatial datasets is crucial for applications where distinct parties wish to share information about nearby geo-tagged data items. To protect each party's data, only joining pairs of points should be revealed, and no additional information about non-matching items should be disclosed. Previous research efforts focused on private matching for relational data, and rely either on space-embedding or on SMC techniques. Space-embedding transforms data points to hide their exact attribute values before matching is performed, whereas SMC protocols simulate complex digital circuits that evaluate the matching condition without revealing anything else other than the matching outcome.

Mobile Ad-hoc Networks (MANETs) enable users in physical proximity to each other to exchange data without the need for expensive communication infrastructures. Each user represents a node in the network, and executes a neighbor discovery Typically, nodes broadcast beacon messages that are received by other participants within the sender's communication range. Routing strategies are computed on-line based on the locations of nearby nodes, and geocasting is employed to deliver data packets to their destinations. However, mobile users may be reluctant to share their exact locations with other participants, since location can disclose private details about a person's lifestyle, religious or political affiliations, etc. A common approach to protect location privacy is to replace exact coordinates with coarser-grained regions, based on the privacy profile of each user. In this paper, we investigate protocols that support MANET routing without disclosing exact positions of nodes. Each node defines its own privacy profile, and reports a cloaked location information to its neighbors. We adopt a novel strategy to advertise beacons, to prevent inference of node locations. We also propose packet forwarding heuristics that rely on cloaking regions, rather than point locations. Our extensive experimental evaluation shows that the proposed routing scheme achieves low delays and high packet delivery ratios, without incurring significant overhead compared to conventional MANET routing protocols.

Mobile devices with positioning capabilities allow users to participate in novel and exciting location-based applications. For instance, users may track the whereabouts of their acquaintances in location-aware social networking applications, e.g., GoogleLatitude. Furthermore, users can request information about landmarks in their proximity. Such scenarios require users to report their coordinates to other parties, which may not be fully trusted. Reporting precise locations may result in serious privacy violations, such as disclosure of lifestyle details, sexual orientation, etc. A typical approach to preserve location privacy is to generate a cloaking region (CR) that encloses the user position. However, if locations are continuously reported, an attacker can correlate CRs from multiple timestamps to accurately pinpoint the user position within a CR.

Social networking and content sharing service providers, e.g., Facebook and Google Maps, enable their users to upload and share a variety of user-generated content, including location data such as points of interest. Users wish to share location data through an (untrusted) service provider such that trusted friends can perform spatial queries on the data. We solve the problem by transforming the location data before uploading them. We contribute spatial transformations that re-distribute locations in space and a transformation that employs cryptographic techniques. The data owner selects transformation keys and shares them with the trusted friends. Without the keys, it is infeasible for an attacker to reconstruct the exact original data points from the transformed points. These transformations achieve different tradeoffs between query efficiency and data security. In addition, we describe an attack model for studying the security properties of the transformations. Empirical studies suggest that the proposed methods are secure and efficient.

The problem of private location-based queries has been intensively researched in recent years. Several location protection algorithms exist, most of which use some form of location cloaking. However, existing work focuses on the analysis of privacy and performance, and less on the user's perspective on location privacy. We developed a prototype of the PROBE system with an emphasis on visualization of the location cloaking process, which improves user experience and increases privacy awareness.

Releasing detailed data ( microdata ) about individuals poses a privacy threat, due to the presence of quasi-identifier (QID) attributes such as age or zip code. Several privacy paradigms have been proposed that preserve privacy by placing constraints on the value of released QIDs. However, in order to enforce these paradigms, data publishers need tools to assist them in selecting a suitable anonymization method and choosing the right system parameters. We developed TIAMAT , a tool for analysis of anonymization techniques which allows data publishers to assess the accuracy and overhead of existing anonymization techniques. The tool performs interactive, head-to-head comparison of anonymization techniques, as well as QID change-impact analysis. Other features include collection of attribute statistics, support for multiple information loss metrics and compatibility with commercial database engines.

Recent research studied the problem of publishing microdata without revealing sensitive information, leading to the privacy-preserving paradigms of k -anonymity and l -diversity. k -anonymity protects against the identification of an individual's record. l -diversity, in addition, safeguards against the association of an individual with specific sensitive information. However, existing approaches suffer from at least one of the following drawbacks: (i) l -diversification is solved by techniques developed for the simpler k -anonymization problem, causing unnecessary information loss. (ii) The anonymization process is inefficient in terms of computational and I/O cost. (iii) Previous research focused exclusively on the privacy-constrained problem and ignored the equally important accuracy-constrained (or dual) anonymization problem. In this article, we propose a framework for efficient anonymization of microdata that addresses these deficiencies. First, we focus on one-dimensional (i.e., single-attribute) quasi-identifiers, and study the properties of optimal solutions under the k -anonymity and l -diversity models for the privacy-constrained (i.e., direct) and the accuracy-constrained (i.e., dual) anonymization problems. Guided by these properties, we develop efficient heuristics to solve the one-dimensional problems in linear time. Finally, we generalize our solutions to multidimensional quasi-identifiers using space-mapping techniques. Extensive experimental evaluation shows that our techniques clearly outperform the existing approaches in terms of execution time and information loss.

Existing research on privacy-preserving data publishing focuses on relational data: in this context, the objective is to enforce privacy-preserving paradigms, such as k- anonymity and lscr-diversity, while minimizing the information loss incurred in the anonymizing process (i.e. maximize data utility). However, existing techniques adopt an indexing- or clustering- based approach, and work well for fixed-schema data, with low dimensionality. Nevertheless, certain applications require privacy-preserving publishing of transaction data (or basket data), which involves hundreds or even thousands of dimensions, rendering existing methods unusable. We propose a novel anonymization method for sparse high-dimensional data. We employ a particular representation that captures the correlation in the underlying data, and facilitates the formation of anonymized groups with low information loss. We propose an efficient anonymization algorithm based on this representation. We show experimentally, using real-life datasets, that our method clearly outperforms existing state-of-the-art in terms of both data utility and computational overhead.

Mobile devices equipped with positioning capabilities (e.g., GPS) can ask location-dependent queries to Location Based Services (LBS). To protect privacy, the user location must not be disclosed. Existing solutions utilize a trusted anonymizer between the users and the LBS. This approach has several drawbacks: (i) All users must trust the third party anonymizer, which is a single point of attack. (ii) A large number of cooperating, trustworthy users is needed. (iii) Privacy is guaranteed only for a single snapshot of user locations; users are not protected against correlation attacks (e.g., history of user movement).

Nowadays, mobile users with global positioning devices canaccess Location Based Services (LBS) and query about pointsof interest in their proximity. For such applications to succeed,privacy and confidentiality are essential. Encryptionalone is not adequate; although it safeguards the systemagainst eavesdroppers, the queries themselves may disclosethe location and identity of the user. Recently, there havebeen proposed centralized architectures based on K-anonymity,which utilize an intermediate anonymizer between themobile users and the LBS. However, the anonymizer mustbe updated continuously with the current locations of allusers. Moreover, the complete knowledge of the entire systemposes a security threat, if the anonymizer is compromised.In this paper we address two issues: (i) We show thatexisting approaches may fail to provide spatial anonymityfor some distributions of user locations and describe a noveltechnique which solves this problem. (ii) We propose Prive,a decentralized architecture for preserving the anonymityof users issuing spatial queries to LBS. Mobile users self-organizeinto an overlay network with good fault toleranceand load balancing properties. Prive avoids the bottleneckcaused by centralized techniques both in terms of anonymizationand location updates. Moreover, the system state isdistributed in numerous users, rendering Prive resilient toattacks. Extensive experimental studies suggest that Priveis applicable to real-life scenarios with large populations ofmobile users.

The increasing trend of embedding positioning capabilities (for example, GPS) in mobile devices facilitates the widespread use of location-based services. For such applications to succeed, privacy and confidentiality are essential. Existing privacy-enhancing techniques rely on encryption to safeguard communication channels, and on pseudonyms to protect user identities. Nevertheless, the query contents may disclose the physical location of the user. In this paper, we present a framework for preventing location-based identity inference of users who issue spatial queries to location-based services. We propose transformations based on the well-established K-anonymity concept to compute exact answers for range and nearest neighbor search, without revealing the query source. Our methods optimize the entire process of anonymizing the requests and processing the transformed spatial queries. Extensive experimental studies suggest that the proposed techniques are applicable to real-life scenarios with numerous mobile users.

Distributed hash tables (DHT) algorithms obtain good lookup performance bounds by using deterministic rules to organize peer nodes into an overlay network. To preserve the invariants of the overlay network, DHTs use stabilization procedures that reorganize the topology graph when participating nodes join or fail. Most DHTs use periodic stabilization, in which peers perform stabilization at fixed intervals of time, disregarding the rate of change in overlay topology; this may lead to poor performance and large stabilization-induced communication overhead. We propose a novel adaptive stabilization framework that takes into consideration the continuous evolution in network conditions. Each peer collects statistical data about the network and dynamically adjusts its stabilization rate based on the analysis of the data. The objective of our scheme is to maintain nominal network performance and to minimize the communication overhead of stabilization.