Several secure data outsourcing systems incorporate various cryptographic techniques to balance security, functionalities, and efficiency. However, their security properties can be ad hoc and sometimes obscure. Our recent work, Secure Normal Form (SNF) [ICDE’24], presents a principled approach that allows data owners to define acceptable leakages of nonsensitive aspects of their data. This approach enables efficient processing of queries while ensuring no unintended leakage of sensitive information. In this paper, we discuss the benefits and challenges of implementing SNF within advanced computational environments and modern data management architectures. We argue that its applicability may extend beyond merely offloading secure query execution to the cloud.

Existing secure data outsourcing systems offer users ways to select from different cryptographic primitives supported by the system to encrypt their data to strike a balance between data confidentiality and query performance. Though prior work have identified the danger of mixing cryptographic primitives, they fall short of providing a systematic approach to guide users to prevent such cross-cryptographic leakages. Inspired by the database design theory, we envision Secure Normal Form, a new approach to normalize encrypted databases such that the leakages of the partitioned databases are limited to the users' specifications. In this work, we propose a new architecture to support secure normal form. This system includes several new components for secure data outsourcing: (i) an inference mechanism that reasons about additional leakages from weaker encryption techniques, based on semantic data properties (e.g., dependence between attribute values); (ii) a normalization mechanism that converts relational data into secure normal forms, so that the information leaked by the representation is limited to that specified by the user; and (iii) a secure query execution approach over encrypted data in secure normal forms. Our initial experimental results validate the performance improvement over naïve baseline and show that a careful data representation can be allowed without compromising security. We believe that our paper opens a new direction in secure data management.

Simply restricting the computation to non-sensitive part of the data may lead to inferences on sensitive data through data dependencies. Prior work on preventing inference control through data dependencies detect and deny queries which may lead to leakage, or only protect against exact reconstruction of the sensitive data. These solutions result in poor utility, and poor security respectively. In this paper, we present a novel security model calledfull deniability. Under this stronger security model, any information inferred about sensitive data from non-sensitive data is considered as a leakage. We describe algorithms for efficiently implementing full deniability on a given database instance with a set of data dependencies and sensitive cells. Using experiments on two different datasets, we demonstrate that our approach protects against realistic adversaries while hiding only minimal number of additional non-sensitive cells and scales well with database size and sensitive data.

As location data have been increasingly adopted in location-based advertising (LBA), revealing locations to untrusted service providers has raised severe privacy concerns. Recent studies propose obfuscation mechanisms built upon geo-indistinguishability (geo-IND) to provide formal privacy guarantee. Unfortunately, due to the high degree of spatiotemporal regularity in human mobility pattern, the privacy cost will be unacceptably high in this situation, leading to accurate inference of user real locations. In this study, we identify this privacy risk in LBA scenarios under long-term and multi-platform assumption. We demonstrate an attacker can infer 75%∼90% of top-1 locations within a range of only 200 meters. To address it, we proposePrivLocAd, a novel system which can provide longitudinal privacy guarantee. The novelty of PrivLocAd stems from a novel surrogate-based obfuscation, which generates multiple surrogate locations to improve the privacy-utility trade-off. In addition, two novel obfuscation mechanisms, the two-stage Gaussian and multi-level surrogate generation mechanism in charge of surrogate generation can achieve the longitudinal privacy guarantee in intra- and inter-platform condition respectively. Our experimental results demonstrate PrivLocAd is able to defend against the attack, which reduces the inference rate to less than 1% of user top-1 locations in the 200 meter range.

A line of work has looked at the problem of recovering an input from distance queries. In this setting, there is an unknown sequence s ∈ {0,1}^{≤ n}, and one chooses a set of queries y ∈ {0,1}^𝒪(n) and receives d(s,y) for a distance function d. The goal is to make as few queries as possible to recover s. Although this problem is well-studied for decomposable distances, i.e., distances of the form d(s,y) = ∑_{i=1}^n f(s_i, y_i) for some function f, which includes the important cases of Hamming distance, 𝓁_p-norms, and M-estimators, to the best of our knowledge this problem has not been studied for non-decomposable distances, for which there are important special cases such as edit distance, dynamic time warping (DTW), Fréchet distance, earth mover’s distance, and so on. We initiate the study and develop a general framework for such distances. Interestingly, for some distances such as DTW or Fréchet, exact recovery of the sequence s is provably impossible, and so we show by allowing the characters in y to be drawn from a slightly larger alphabet this then becomes possible. In a number of cases we obtain optimal or near-optimal query complexity. We also study the role of adaptivity for a number of different distance functions. One motivation for understanding non-adaptivity is that the query sequence can be fixed and the distances of the input to the queries provide a non-linear embedding of the input, which can be used in downstream applications involving, e.g., neural networks for natural language processing.

Recent years have witnessed the adoption of differential privacy (DP) in practical database systems like PINQ, FLEX, and PrivateSQL. Such systems allow data analysts to query sensitive data while providing a rigorous and provable privacy guarantee. However, the existing design of these systems does not distinguish data analysts of different privilege levels or trust levels. This design can have an unfair apportion of the privacy budget among the data analyst if treating them as a single entity, or waste the privacy budget if considering them as non-colluding parties and answering their queries independently. In this paper, we propose DProvDB, a fine-grained privacy provenance framework for the multi-analyst scenario that tracks the privacy loss to each single data analyst. Under this framework, when given a fixed privacy budget, we build algorithms that maximize the number of queries that could be answered accurately and apportion the privacy budget according to the privilege levels of the data analysts.

A line of work has looked at the problem of recovering an input from distance queries. In this setting, there is an unknown sequence$s \in \{0,1\}^{\leq n}$, and one chooses a set of queries$y \in \{0,1\}^{ \mathcal {O}(n)}$and receives$d(s,y)$for a distance function$d$. The goal is to make as few queries as possible to recover$s$. Although this problem is well-studied for decomposable distances, i.e., distances of the form$d(s,y) = \sum _{i=1}^{n} f(s_{i}, y_{i})$for some function$f$, which includes the important cases of Hamming distance,$\ell _{p}$-norms, and$M$-estimators, to the best of our knowledge this problem has not been studied for non-decomposable distances, for which there are important instances including edit distance, dynamic time warping (DTW), Fréchet distance, earth mover’s distance, and others. We initiate the study and develop a general framework for such distances. Interestingly, for some distances such as DTW or Fréchet, exact recovery of the sequence$s$is provably impossible, and so we show by allowing the characters in$y$to be drawn from a slightly larger alphabet this then becomes possible. In a number of cases we obtain optimal or near-optimal query complexity. One motivation for understanding non-adaptivity is that the query sequence can be fixed and provide a non-linear embedding of the input, which can be used in downstream applications involving, e.g., neural networks for natural language processing.

As geo-location data has been increasingly adopted as a high-profile feature in targeted advertising, exposing user real locations to untrusted cloud services or advertisers has raised severe privacy concerns. To protect location privacy with formal guarantee, a wide-stretched line of recent studies focuses on injecting controlled geo-indistinguishability (geo-IND) noise as per each location exposure. However, in advertising, over the course of 2 years, a single user can report and contribute near 1k location data points on average, which allows a longitudinal attacker to infer some statistics from the perturbed locations.In this study, we demonstrate the above-mentioned privacy risk via revealing an inference attack mechanism, coined as a longitudinal location exposure attack. This novel attack illustrates the possibility of recovering 75%∼90% of user top-1 locations (within only 200-meter range) among 37k users. In light of this deficiency, we propose a novel edge-assisted location privacy protection system, entitled Edge-PrivLocAd, that is adapted to location-based advertising. The novelty of Edge-PrivLocAd stems from our n-fold Gaussian mechanism, which adds permanent noise to the statistical user location profile and thus can defend against longitudinal attackers while balancing the privacy-utility trade-off. In addition, our system incorporates a posterior-based sampling technique into the location re-mapping process, that boosts location utility without privacy loss. We develop a fully-functioning prototype and empirically evaluate the proposed system. Our experimental results show that Edge-PrivLocAd is practical and scalable in real-world scenarios.

We study the problem of answering queries when (part of) the data may be sensitive and should not be leaked to the querier. Simply restricting the computation to non-sensitive part of the data may leak sensitive data through inference based on data dependencies. While inference control from data dependencies during query processing has been studied in the literature, existing solution either detect and deny queries causing leakage, or use a weak security model that only protects against exact reconstruction of the sensitive data. In this paper, we adopt a stronger security model based on full deniability that prevents any information about sensitive data to be inferred from query answers. We identify conditions under which full deniability can be achieved and develop an efficient algorithm that minimally hides non-sensitive cells during query processing to achieve full deniability. We experimentally show that our approach is practical and scales to increasing proportion of sensitive data, as well as, to increasing database size.