Generate-then-Verify: Reconstructing Data from Limited Published Statistics

• URL: http://arxiv.org/abs/2504.21199v1
• Date: Tue, 29 Apr 2025 22:06:04 GMT
• Title: Generate-then-Verify: Reconstructing Data from Limited Published Statistics
• Authors: Terrance Liu, Eileen Xiao, Pratiksha Thaker, Adam Smith, Zhiwei Steven Wu,
• Abstract summary: We focus on the regime where many possible datasets match the published statistics, making it impossible to reconstruct the entire private dataset perfectly.<n>We introduce a novel integer programming approach that first $textbfgenerates$ a set of claims and then $textbfverifies$ whether each claim holds for all possible datasets.<n>We evaluate our approach on the housing-level microdata from the U.S. Decennial Census release, demonstrating that privacy violations can still persist even when information published about such data is relatively sparse.
• Score: 22.649631494395653
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of reconstructing tabular data from aggregate statistics, in which the attacker aims to identify interesting claims about the sensitive data that can be verified with 100% certainty given the aggregates. Successful attempts in prior work have conducted studies in settings where the set of published statistics is rich enough that entire datasets can be reconstructed with certainty. In our work, we instead focus on the regime where many possible datasets match the published statistics, making it impossible to reconstruct the entire private dataset perfectly (i.e., when approaches in prior work fail). We propose the problem of partial data reconstruction, in which the goal of the adversary is to instead output a $\textit{subset}$ of rows and/or columns that are $\textit{guaranteed to be correct}$. We introduce a novel integer programming approach that first $\textbf{generates}$ a set of claims and then $\textbf{verifies}$ whether each claim holds for all possible datasets consistent with the published aggregates. We evaluate our approach on the housing-level microdata from the U.S. Decennial Census release, demonstrating that privacy violations can still persist even when information published about such data is relatively sparse.

Related papers

• DUPRE: Data Utility Prediction for Efficient Data Valuation [49.60564885180563]
  Cooperative game theory-based data valuation, such as Data Shapley, requires evaluating the data utility and retraining the ML model for multiple data subsets.<n>Our framework, textttDUPRE, takes an alternative yet complementary approach that reduces the cost per subset evaluation by predicting data utilities instead of evaluating them by model retraining.<n>Specifically, given the evaluated data utilities of some data subsets, textttDUPRE fits a emphGaussian process (GP) regression model to predict the utility of every other data subset.
  arXiv  Detail & Related papers  (2025-02-22T08:53:39Z)
• Synthetic Census Data Generation via Multidimensional Multiset Sum [7.900694093691988]
  We provide tools to generate synthetic microdata solely from published Census statistics. We show that our methods work well in practice, and we offer theoretical arguments to explain our performance.
  arXiv  Detail & Related papers  (2024-04-15T19:06:37Z)
• Scaling Laws for Data Filtering -- Data Curation cannot be Compute Agnostic [99.3682210827572]
  Vision-language models (VLMs) are trained for thousands of GPU hours on carefully curated web datasets. Data curation strategies are typically developed agnostic of the available compute for training. We introduce neural scaling laws that account for the non-homogeneous nature of web data.
  arXiv  Detail & Related papers  (2024-04-10T17:27:54Z)
• Efficient Approximate Recovery from Pooled Data Using Doubly Regular Pooling Schemes [1.7403133838762448]
  We analyze an approximate reconstruction algorithm that estimates the hidden bits in a greedy fashion. Our analysis is uniform in the degree of noise and the sparsity of $sigma$.
  arXiv  Detail & Related papers  (2023-02-28T19:31:40Z)
• Membership Inference Attacks against Synthetic Data through Overfitting Detection [84.02632160692995]
  We argue for a realistic MIA setting that assumes the attacker has some knowledge of the underlying data distribution. We propose DOMIAS, a density-based MIA model that aims to infer membership by targeting local overfitting of the generative model.
  arXiv  Detail & Related papers  (2023-02-24T11:27:39Z)
• Confidence-Ranked Reconstruction of Census Microdata from Published Statistics [45.39928315344449]
  A reconstruction attack on a private dataset takes as input some publicly accessible information about the dataset. We show that our attacks can not only reconstruct full rows from the aggregate query statistics $Q(D)Rmm$, but can do so in a way that reliably ranks reconstructed rows by their odds. Our attacks significantly outperform those that are based only on access to a public distribution or population from which the private dataset $D$ was sampled.
  arXiv  Detail & Related papers  (2022-11-06T14:08:43Z)
• Partially-Aligned Data-to-Text Generation with Distant Supervision [69.15410325679635]
  We propose a new generation task called Partially-Aligned Data-to-Text Generation (PADTG) It is more practical since it utilizes automatically annotated data for training and thus considerably expands the application domains. Our framework outperforms all baseline models as well as verify the feasibility of utilizing partially-aligned data.
  arXiv  Detail & Related papers  (2020-10-03T03:18:52Z)
• Identifying Statistical Bias in Dataset Replication [102.92137353938388]
  We study a replication of the ImageNet dataset on which models exhibit a significant (11-14%) drop in accuracy. After correcting for the identified statistical bias, only an estimated $3.6% pm 1.5%$ of the original $11.7% pm 1.0%$ accuracy drop remains unaccounted for.
  arXiv  Detail & Related papers  (2020-05-19T17:48:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.