Pith. sign in

REVIEW 3 major objections 6 minor 19 references

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

T0 review · 3 major / 6 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Even when released statistics cannot pin down the entire private dataset, an attacker can still certify specific records that every consistent dataset must contain.

desk verdict Novel partial-reconstruction problem, but a load-bearing error in the query-padding encoding leaves the empirical claims unsupported as written. read the letter →

arxiv 2504.21199 v2 pith:CWQTI5QU submitted 2025-04-29 stat.ML cs.CRcs.LG

Terrance Liu , Eileen Xiao , Adam Smith , Pratiksha Thaker , Zhiwei Steven Wu This is my paper · ORCID
classification stat.MLcs.CRcs.LG
keywords reconstructionattackpartialdatasinglingoutintegerprogrammingverifiedclaimscensusprivacyaggregatestatisticsmarginalqueries
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper investigates whether an attacker can learn private records with certainty from published aggregate statistics even when those statistics are too sparse to pin down the whole dataset. The authors' answer is yes: they introduce partial data reconstruction, where the adversary outputs a subset of rows and/or columns that every dataset consistent with the published statistics must contain, and call such statements verified claims. They evaluate the approach on household-level microdata and block-level Summary File 1 tables from the 2010 U.S. Decennial Census, a setting where prior full-reconstruction methods fail on every block because multiple datasets match the statistics. Nevertheless, roughly 40% of the evaluated blocks contain at least one household that can be singled out with certainty using 8 of the 10 columns, and over 80% do so using 6 columns. The finding matters because it shows that privacy violations from statistical releases do not require reconstructing everything: sparse information can still certify individual records.

What carries the argument

The central object is the verified claim $R(a,m)$ — the statement that exactly $m$ rows of the private dataset match a partial assignment $a$ over some columns — together with the integer-programming feasibility test that certifies it. The Generate step solves the constraint satisfaction problem $Q(D)=Q(X)$ (in a one-hot-encoded representation of rows) for $K$ distinct synthetic datasets $X$, collects every claim that holds in each, and intersects those sets to form candidates. The Verify step then tries to find a dataset $X$ that satisfies the same statistics but has a number of rows matching $a$ different from $m$; if the solver proves no such $X$ exists, the claim is verified because every dataset consistent with the statistics must satisfy it. Big-M indicator constraints and binary variables encode 'row matches assignment' and 'multiplicity differs from $m$', and the solver's infeasibility certificate is what converts an empirical search into a certainty claim.

What would settle it

Pick any block the paper reports as containing a verified singleton claim with $k=8$ columns and check that claim by exhaustive enumeration or by an independent solver using exact arithmetic instead of floating-point tolerances: if a dataset $D'$ of the same size satisfying the block's 621 statistics exists in which the claimed household has multiplicity different from 1, that single feasible $D'$ shows the claim is not guaranteed by the published statistics.

Watch

Extended reading notes

Core claim

The central claim is that full reconstruction is not the right threshold for privacy risk. For a dataset $D$ and a set of counting queries $Q(D)$, the paper defines a claim $R(a,m)$ as the assertion that exactly $m$ rows match a partial assignment $a$ over some subset of columns, and calls the claim verified if every dataset $D'$ with $Q(D')=Q(D)$ also satisfies $COUNT(a,D')=m$. The paper shows that even when the feasible set of datasets is large enough that no entire block is uniquely determined, a substantial number of such claims survive. Using 621 block-level marginal queries from the Census Summary File 1 on 500 blocks, the authors find no block that can be fully reconstructed, yet they verify singleton claims ($m=1$) that single out real households: about 40% of blocks have at least one household fixed by an 8-column assignment, and more than 10% of households across all evaluated blocks are uniquely identified by some 8-column claim. The mechanism is the generate-then-verify integer program: generate many synthetic datasets consistent with $Q(D)$, intersect their claim sets to obtain candidates, then keep a claim only after proving that no feasible dataset refutes it.

Load-bearing premise

The load-bearing premise is that the Generate step really enumerates every claim worth checking across the sampled synthetic datasets and that the integer solver's infeasibility verdicts are correct; if either fails, the reported verification rates are lower bounds rather than an exact account of what the statistics certify.

Editorial extensions

If this is right

  • Release designers should not treat non-uniqueness of the feasible set as safety: on the evaluated census blocks, sparse statistics still certify individual households.
  • A meaningful fraction of households are uniquely pinned by a subset of columns: over 10% by 8 columns and over a quarter by 6 columns across the evaluated blocks.
  • The phenomenon is not purely an artifact of trivial single-count queries: after removing all queries that evaluate to 1, about 10% of households are still singled out by 6-column claims.
  • The verified claims are surprising under demographic priors: with a tract- or state-level prior, the median baseline probability of a verified claim is below 2%, so guessing from aggregate demographics would rarely reproduce them.
  • The attack's feasibility depends on integer-programming scale; the authors note that larger datasets or richer query sets can make the computation far more demanding, so small blocks like those in the census are the vulnerable regime.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the same generate-then-verify pattern should transfer to any release of overlapping k-way marginals; the key quantity to study is the 'certified core' of the feasible set, i.e., the sub-tuples present in every feasible dataset, as a function of query set, domain size, and block size $N$.
  • Editorial inference: the number of distinct synthetic datasets needed before the candidate intersection stabilizes could serve as a cheap diagnostic; if additional solutions keep shrinking the intersection, the reported verification rates are likely undercounting certified claims, whereas a quickly stabilizing intersection suggests the rates are near the true values.
  • Editorial inference: the reliance on a solver's infeasibility certificate means the guarantee is only as strong as the solver's arithmetic; replacing the big-M formulation with exact rational arithmetic would turn these empirical findings into a provable bound, which seems worth checking for the specific blocks reported.
  • Editorial inference: a natural stress test is to add differentially private noise to the 621 queries and measure how much noise removes all verified singleton claims for blocks of size 10; that would map the gap between sparse release and safe release.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper introduces partial tabular data reconstruction: instead of reconstructing an entire private dataset from published aggregate statistics, the adversary outputs claims R(a,m) stating that exactly m rows match a partial assignment a, and certifies these claims as guaranteed correct if they hold in every dataset consistent with the published statistics. The proposed method first generates candidate claims by sampling K consistent synthetic datasets and taking the intersection of the claims appearing in them, then verifies each candidate by solving an integer program that asks whether a consistent dataset exists in which the claim's multiplicity is violated; infeasibility certifies the claim. The evaluation uses 2010 Census household-level microdata (10 columns, 621 block-level queries from Summary File 1) and reports that many verified singleton claims exist even though no block is uniquely reconstructable. Ablation experiments remove queries whose published counts are 0 or 1 and still find nontrivial numbers of singled-out households.

Significance. If the results hold, this is a conceptually valuable contribution: it formalizes a notion of guaranteed partial reconstruction, shows that full dataset reconstruction is not necessary for a successful attack, and provides an IP-based verification method whose logical core (a claim is verified if no consistent dataset refutes it) is sound. The baseline probability analysis is useful for calibrating how surprising the verified claims are. The paper does not provide code or data, and the main empirical claims currently rest on an incomplete method description and a formal error in the query-padding construction, so the significance is contingent on a corrected and reproducible specification. The framing of partial reconstruction as a research problem is likely to be influential regardless.

major comments (3)
  1. [§5.1.3, Eq. (6)] The padding construction is incorrect. The paper states that queries with r<r_max sub-predicates are padded with rows q_pad = 1_d, but for a one-hot encoded record x with k columns, x·q_pad^T = k, not 1. Consequently, for every padded query, the vector Z[i,:,k] contains an entry equal to k and can never equal 1_rmax, so Equation (6) counts zero rows for all such queries. Since the published statistics include nonzero 1-way marginals, constraint (9) would force those counts to zero and make Problem 1 infeasible, contradicting the claim in §3.1.1 that every block has feasible reconstructions. If the implementation used a different padding rule, the paper must describe it; as written, the described method does not support the reported empirical results.
  2. [§2.3 and §5.4.2] The claim-enumeration procedure is not specified at a level that permits reproduction or assessment of exactness. The paper says it identifies all claims R(a,m) for each generated synthetic dataset, but the domain X' over 10 census columns contains roughly 7.4 million partial assignments per row, making a brute-force enumeration over all attribute subsets and multiplicities for N≈10 rows and K=100 datasets intractable as described. The paper does not state which subsets of columns are enumerated, whether enumeration is restricted to k≥6 at generation time, or how duplicate claims across rows are handled. If enumeration is incomplete, the reported reconstruction rates in Figure 3 and Table 4 are lower bounds rather than exact figures, and the procedure cannot be independently reproduced.
  3. [§3.1.1 and Table 4] The country-median sample is described as five blocks of size N=10 from each of the 50 states, which should contain 2,500 households total, but Table 4 reports a total of 2,430 households for that sample, yielding an average of 9.72 per block. This discrepancy indicates undocumented exclusions or variable block sizes and needs clarification, because the per-block averages and the claim that the country-median block size is 10 households are otherwise inconsistent.
minor comments (6)
  1. [Abstract] The abstract contains a typo: ``asubset'' should be ``a subset''.
  2. [Table 2 and Table 6] The column abbreviation ``HTT2'' appears in Table 2 (query 11) and Table 6; this should be ``HHT2'' for consistency with the text and Appendix A.
  3. [Figure 3 caption] The caption says ``out of 50'' for the number of blocks, but the rows are described as 250 blocks each (5 per state); clarify whether the y-axis plots blocks or states.
  4. [§4.1] The phrase ``In almost cases'' should read ``In almost all cases''.
  5. [Table 5] The caption states ``250 total blocks,'' but the table reports ``Total 2500'' for the number of households; the caption and table should clearly distinguish block counts from household counts, and the country-median total should be reconciled with Table 4.
  6. [§5.1.3 and §5.1.2] After padding, the notation shifts between 1_r and 1_rmax; unify the notation and define the padded query matrix dimensions explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the verified claims are logical entailments of the published statistics, computed by an independently specified constraint-satisfaction check, not by fitting or by self-citation.

full rationale

The paper's central operation is Definition 1: a claim R(a,m) is verified if COUNT(a,D') = m for every dataset D' with Q(D') = Q(D). The verification step (Problem 3) directly encodes the negation of this condition, asking whether any D' exists with Q(D') = Q(D) and COUNT(a,D') != m, and declares the claim verified only when that problem is infeasible. This is a computational implementation of the definition, not a redefinition of the output in terms of itself: the claim is derived from the published statistics through an independent feasibility check. The generation step (Section 2.3) only produces candidate claims from K feasible datasets and then intersects them; it does not define verified claims, and the final verification is performed separately against the full constraint set. No free parameters are fitted to the ground truth, and the baseline probabilities in Section 3.2 are used only for comparison, not as inputs to the reconstruction. The self-citations to Dick et al. [15] and Steed et al. [5] are contextual or used for the baseline prior, which is not load-bearing for the central verified-claim results. Any concerns about the IP encoding, query padding, or solver tolerances are correctness and robustness issues, not circularity: they do not make the derived claims equivalent to the inputs by construction. The paper is self-contained in the sense that its claimed verification results reduce to solving the stated integer programs, and the logic of that reduction is not circular.

Assumptions & free parameters 3 free parameters · 3 assumptions · 0 invented entities

The method relies on standard mathematical programming tools and public census data products. The parameters K, M, and the time limit are engineering choices that do not affect the guarantee offered by verified claims. No new physical or theoretical entities are postulated.

free parameters (3)
  • K (number of generated datasets) = 100
    Chosen by hand; controls the size of the claim intersection and computational load. It does not affect correctness: any claim true for all feasible datasets appears in every generated dataset, so it is always in the intersection.
  • M (big-M constant) = unspecified (stated only as M >> N)
    Used in verification constraints 10-17; a large constant. Its value could affect numerical stability, though the paper reports tight solver tolerances.
  • Gurobi time limit = 180 seconds
    Claims whose verification IP times out are marked unverified, which can only reduce recall, not create false positives.
assumptions (3)
  • domain assumption Gurobi returns correct feasibility/infeasibility answers for the integer programs with the stated tolerance settings.
    The verification step concludes a claim is guaranteed only if a solver proves infeasibility; this depends on the solver being correct for these big-M formulations.
  • domain assumption The published SF1 statistics are exact and consistent for the PPMF ground-truth data.
    The 2010 Summary File 1 counts are treated as exact aggregates of the microdata; the method assumes no noise or inconsistency.
  • domain assumption The Privacy-Protected Microdata File (PPMF) is a faithful surrogate for the private 2010 Census microdata for evaluating the attack.
    Since the true microdata are not public, the PPMF is used as ground truth; the paper acknowledges it is statistically similar but synthetic.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Generate-then-Verify: Reconstructing Data from Limited Published Statistics." pith.science (2026). https://pith.science/paper/CWQTI5QU

@misc{pith2026250421199,
  author       = {Pith},
  title        = {Pith review of: Generate-then-Verify: Reconstructing Data from Limited Published Statistics},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CWQTI5QU}},
  note         = {Machine review of arXiv:2504.21199}
}
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.

Figures

Figures reproduced from arXiv: 2504.21199 by the authors.

Figure 1
Figure 1. We provide a visual diagram of example claims studied in our work. On the left-hand side is the private dataset, [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. We plot the distribution of block sizes for blocks [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. We present results for verified singleton claims collected from experiments on 5 blocks selected from each state (250 total on each row). Top row: 5 blocks whose size are equal the median block size of the respective state are selected. Bottom row: 5 blocks whose size are equal the median block size of the country (i.e., 10 households). a & d: The number of blocks (out of 50) for which we can reconstruct at least on… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: For each number of columns k, we plot the proportion of verified singleton claims that contain each column. TABLE 6: For each number of columns k, we list the 5 most common combinations of columns among the verified claims. In addition, we report what percentage of cla…
Figure 5
Figure 5. Figure 5: We present presents results for all verified claims collected from experiments on 5 blocks selected from each state (250 total on each row). Top row: 5 blocks whose size are equal the median block size of the respective state are selected. Bottom row: 5 blocks whose si…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 16 canonical work pages

  1. [1]

    Confidentiality protection in the 2020 us census of population and housing,

    J. M. Abowd and M. B. Hawes, “Confidentiality protection in the 2020 us census of population and housing,”Annual Review of Statistics and Its Application, vol. 10, no. 1, pp. 119–144, 2023

    work page 2020

  2. [2]

    The 2010 census confidentiality protections failed, here’s how and why,

    J. M. Abowd, T. Adams, R. Ashmead, D. Darais, S. Dey, S. L. Garfinkel, N. Goldschlag, D. Kifer, P. Leclerc, E. Lewet al., “The 2010 census confidentiality protections failed, here’s how and why,” National Bureau of Economic Research, Tech. Rep., 2023

    work page 2010

  3. [3]

    Towards formalizing the gdpr’s notion of singling out,

    A. Cohen and K. Nissim, “Towards formalizing the gdpr’s notion of singling out,”Proceedings of the National Academy of Sciences, vol. 117, no. 15, pp. 8344–8352, 2020

    work page 2020

  4. [4]

    Synthetic census data generation via multidimensional multiset sum,

    C. Dwork, K. Greenewald, and M. Raghavan, “Synthetic census data generation via multidimensional multiset sum,”arXiv preprint arXiv:2404.10095, 2024

    work page arXiv 2024

  5. [5]

    Quantifying privacy risks of public statistics to residents of subsidized housing,

    R. Steed, D. Qing, and Z. S. Wu, “Quantifying privacy risks of public statistics to residents of subsidized housing,”arXiv preprint arXiv:2407.04776, 2024

    arXiv 2024

  6. [6]

    Weaving technology and policy together to maintain confidentiality,

    L. Sweeney, “Weaving technology and policy together to maintain confidentiality,”The Journal of Law, Medicine & Ethics, vol. 25, no. 2-3, pp. 98–110, 1997

    work page 1997

  7. [7]

    Robust de-anonymization of large sparse datasets,

    A. Narayanan and V . Shmatikov, “Robust de-anonymization of large sparse datasets,” in2008 IEEE Symposium on Security and Privacy (sp 2008). IEEE, 2008, pp. 111–125

    2008

  8. [8]

    The risk of linked census data to transgender youth: A simulation study,

    A. Flaxman and O. Keyes, “The risk of linked census data to transgender youth: A simulation study,”Journal of Privacy and Confidentiality, vol. 15, no. 1, 2025

    work page 2025

Show all 19 references
  1. [9]

    Revealing information while preserving privacy,

    I. Dinur and K. Nissim, “Revealing information while preserving privacy,” inProceedings of the twenty-second ACM SIGMOD-SIGACT- SIGART symposium on Principles of database systems, 2003, pp. 202–210

    2003

  2. [10]

    The price of privacy and the limits of lp decoding,

    C. Dwork, F. McSherry, and K. Talwar, “The price of privacy and the limits of lp decoding,” inProceedings of the thirty-ninth annual ACM symposium on Theory of computing, 2007, pp. 85–94

    2007

  3. [11]

    The price of privately releasing contingency tables and the spectra of random matrices with correlated rows,

    S. P. Kasiviswanathan, M. Rudelson, A. Smith, and J. Ullman, “The price of privately releasing contingency tables and the spectra of random matrices with correlated rows,” inProceedings of the forty- second ACM symposium on Theory of computing, 2010, pp. 775–784

    2010

  4. [12]

    The power of linear reconstruction attacks,

    S. P. Kasiviswanathan, M. Rudelson, and A. Smith, “The power of linear reconstruction attacks,” inProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 2013, pp. 1415–1433

    2013

  5. [13]

    Exposed! a survey of attacks on private data,

    C. Dwork, A. Smith, T. Steinke, and J. Ullman, “Exposed! a survey of attacks on private data,”Annual Review of Statistics and Its Application, vol. 4, no. 1, pp. 61–84, 2017

    2017

  6. [14]

    Calibrating noise to sensitivity in private data analysis,

    C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” inTheory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3. Springer, 2006, pp. 265–284

    2006

  7. [15]

    Confidence-ranked reconstruction of census microdata from published statistics,

    T. Dick, C. Dwork, M. Kearns, T. Liu, A. Roth, G. Vietri, and Z. S. Wu, “Confidence-ranked reconstruction of census microdata from published statistics,”Proceedings of the National Academy of Sciences, vol. 120, no. 8, p. e2218605120, 2023

    2023

  8. [16]

    Understanding database reconstruction attacks on public data,

    S. Garfinkel, J. M. Abowd, and C. Martindale, “Understanding database reconstruction attacks on public data,”Communications of the ACM, vol. 62, no. 3, pp. 46–53, 2019

    2019

  9. [17]

    The U.S. census bureau adopts differential privacy,

    J. M. Abowd, “The U.S. census bureau adopts differential privacy,” inACM International Conference on Knowledge Discovery & Data Mining, 2018, p. 2867. Appendix

    2018

  10. [18]

    feasibility tolerance

    Additional experimental details Dataset.We list and describe the 10 columns described by the block-level tables below. Tenure (TEN): One of 4 tenancy statuses: owned with mortgage, owned free and clear, rented, or occupied without payment of rent Vacancy status (V ACS): Not va...

  11. [19]

    singling out

    Additional results for verifyingallclaims In the main body of our work, we focus on “singling out” (singleton claims). However, we note that data reconstruction for multiplicity m>1 can be equally interesting (or privacy (a)≥1Verified Singleton Claims (b) Tract-Level Distribut...

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.