{"id":"2d96d8d5-be95-40dd-95d4-2c54e264c34d","arxiv_id":"2504.21199","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"An attacker can verify with certainty that specific individual records exist in a private dataset even when the published aggregate statistics allow many possible datasets.","lead":"This paper shows that even when published statistics are too sparse to reveal an entire private dataset, an attacker can still prove that specific rows exist with 100% certainty. It introduces a generate-then-verify integer programming method and demonstrates the risk on U.S. Census household data.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The query-padding construction in §5.1.3 makes every padded query unsatisfiable, so the IP as written cannot encode the published census statistics; the reported verified claims are not supported by the described method.","rationale":"The reader's weakest assumption focused on the Generate step's claim enumeration and Gurobi tolerances. While those are legitimate reproducibility concerns, the query-padding issue is more fundamental: it is an internal inconsistency in the formal method that, if taken literally, invalidates the entire empirical evaluation. The central claim is that verified singleton claims exist even when full reconstruction is impossible; that claim rests on the integer program correctly encoding the constraint Q(D)=Q(D') and the infeasibility checks of Problem 3. The padding construction in §5.1.3, combined with Equation 6 and Section 5.1.1, implies that any query with fewer than rmax sub-predicates is never satisfied by any record. Since the census tables include many such queries with nonzero counts, the feasible region of Problem 1 would be empty, contradicting the paper's own report of at least two feasible solutions per block. This means one of two things: the text misdescribes the implementation, in which case the method is under-specified and not reproducible; or the implementation matches the text, in which case the feasibility and verification results are invalid. In either scenario, the paper as written fails to support its headline empirical claim. The concern is concrete and testable: a simple algebraic calculation with k=2 disproves the padding claim, and running the formulation on a real block would expose the contradiction. Because this undermines the core demonstration rather than just the completeness of rates or numerical certification, the appropriate verdict is REJECT for the current manuscript, although the conceptual problem framing may be salvageable with corrected details and released code.","tokens_in":15602,"tokens_out":9030,"duration_ms":98463,"concrete_test":"Take a one-row dataset with k=2 binary columns and a single query 'first column = 0'; pad the query with q_pad = 1_4 as specified in §5.1.3 and compute xQ^T: the result is (0,2), not (1,1), so the query count evaluates to 0 even though the record matches. Then run the exact formulation of §5.1–5.3 on one census block with the full 621-query set; if Gurobi reports Problem 1 infeasible, or if the enforced query answers differ from Q(D), the described method is inconsistent with the reported two-solution result.","verdict_should_be":"REJECT","load_bearing_attack":"The most load-bearing weakness is the query-padding construction in §5.1.3. A record x∈{0,1}^d has exactly k one-hot 1s (Section 5.1.1 states k = sum_i x_i). For a query with fewer than rmax sub-predicates, the paper pads Q with rows q_pad = 1_d. Then for any record, x·q_pad^T = k, not 1; when k>1, the vector Z[i,:,k] = xQ^T can never equal 1_rmax. Consequently, Equation 6 counts zero rows for every padded query. Since the census query set includes many 1-way marginals with nonzero counts (e.g., H4 tenure), constraint (9) would force those counts to zero, making Problem 1 infeasible. This directly contradicts the paper's statement in Section 3.1.1 that every block has at least two feasible reconstructions. If the implementation instead uses a correct padding (e.g., a dummy column that is always true), then the formal description is wrong and the actual algorithm is unspecified. Either way, the paper as written does not establish the central empirical claim that partial reconstruction with guaranteed correctness holds for the evaluated census data.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":15834,"tokens_out":7129,"duration_ms":77387,"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":[{"comment":"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.","section":"§5.1.3, Eq. (6)"},{"comment":"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.","section":"§2.3 and §5.4.2"},{"comment":"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.","section":"§3.1.1 and Table 4"}],"minor_comments":[{"comment":"The abstract contains a typo: ``asubset'' should be ``a subset''.","section":"Abstract"},{"comment":"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.","section":"Table 2 and Table 6"},{"comment":"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.","section":"Figure 3 caption"},{"comment":"The phrase ``In almost cases'' should read ``In almost all cases''.","section":"§4.1"},{"comment":"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.","section":"Table 5"},{"comment":"After padding, the notation shifts between 1_r and 1_rmax; unify the notation and define the padded query matrix dimensions explicitly.","section":"§5.1.3 and §5.1.2"}],"recommendation":"major_revision","confidential_remarks":"The paper's core idea is sound and likely publishable after revision, but the query-padding error in §5.1.3 is load-bearing: as written, the described integer program cannot encode the published census statistics, so the empirical results are not supported by the formal description. I would ask the authors to correct the padding construction, specify the claim-enumeration procedure precisely, and ideally release code and data to make the IP experiments reproducible. The discrepancy in the country-median household totals also needs to be resolved before the quantitative claims can be trusted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear [Colleague],\n\nThe one thing to know: this paper introduces a genuinely new problem—guaranteed partial reconstruction from aggregate statistics—but the central empirical claim is not supported by the method as written. The query-padding construction in §5.1.3 uses q_pad = 1_d as a dummy sub-predicate. Since every record has exactly k one-hot 1s (one per column), x·1_d = k, not 1. So for any query with fewer than rmax sub-predicates, the padded Z vector can never equal 1_rmax, and the query count is identically zero. Constraint (9) then forces published nonzero counts (e.g., tenure) to zero, making Problem 1 infeasible. This contradicts the paper's own claim that every block had at least two feasible reconstructions. Either the write-up is wrong or the implementation is; either way, the reported verified claims are not supported by the described method.\n\nThe paper does real work: the partial-reconstruction problem is well-motivated, and the verification logic—if no dataset consistent with the statistics refutes a claim, the claim is guaranteed—is sound. The experiments are thoughtful, especially the tract/state baselines and the ablation removing single-count queries. The analysis of which columns appear in the verified claims is a nice addition.\n\nThe soft spots, in order: (1) the padding error above is load-bearing; (2) the Generate step claims to enumerate all claims over all attribute subsets but gives no procedure for doing so across a 10-column domain, so the reported rates are at best lower bounds; (3) no code or data, which is especially damaging given the first issue; (4) reliance on Gurobi's infeasibility proofs with 1e-9 tolerances is a minor concern.\n\nThe verification framework is not circular; the claims are logical consequences of the statistics. So the conceptual contribution stands, but the empirical demonstration does not.\n\nThis paper is for privacy researchers and data stewards; the question it asks matters. My recommendation: it deserves a serious referee, but the authors need to fix the encoding, spell out the enumeration, and release artifacts. I would not cite the current empirical results.","headline":"Novel partial-reconstruction problem, but a load-bearing error in the query-padding encoding leaves the empirical claims unsupported as written.","tokens_in":16358,"tokens_out":6712,"would_cite":false,"duration_ms":63922,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Even when released statistics cannot pin down the entire private dataset, an attacker can still certify specific records that every consistent dataset must contain.","keywords":["reconstruction attack","partial data reconstruction","singling out","integer programming","verified claims","census data privacy","aggregate statistics","marginal queries"],"falsifier":"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.","tokens_in":15391,"feed_emoji":"🔍","tokens_out":10204,"duration_ms":103508,"temperature":0.7,"pith_summary":"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.","feed_headline":"Sparse census stats can still pinpoint households with certainty","feed_subtitle":"On census blocks where no full dataset is recoverable, 40% still hold a household uniquely pinned by 8 columns.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Establishes the full-reconstruction baseline and the person-level result that most blocks are uniquely reconstructible from Summary File 1 tables, the contrast that motivates partial reconstruction.","marker":"[2]"},{"why":"Provides the formal notion of singling out that the paper adapts into its singleton claims of the form $R(a,1)$.","marker":"[3]"},{"why":"Supplies the tract- and state-level prior distributions used to show that verified claims are surprising relative to demographic baselines.","marker":"[15]"},{"why":"Cites prior histogram-based reconstruction work and real-world privacy risks from statistical releases, which this paper's one-hot integer program departs from.","marker":"[5]"}],"fun_headline_variants":["Partial reconstruction: sparse census stats still expose households","When full data recovery fails, some households remain uniquely pinned","Generate-then-verify: sparse census data leaks specific families","Census blocks resist full reconstruction but still leak single households","Sparse aggregate stats: 40% of blocks have a household uniquely identified"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Partial reconstruction: sparse census stats still expose households","When full data recovery fails, some households remain uniquely pinned","Generate-then-verify: sparse census data leaks specific families","Census blocks resist full reconstruction but still leak single households","Sparse aggregate stats: 40% of blocks have a household uniquely identified"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000284,"raw_usage":{"total_tokens":1701,"prompt_tokens":1000,"completion_tokens":701,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":616,"completion_tokens_details":{"reasoning_tokens":617}},"tokens_in":616,"tokens_out":701,"duration_ms":7534,"temperature":1.0,"reasoning_tokens":617,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T05:10:26.615425+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"The 2010 census confidentiality protections failed, here’s how and why,","cited_arxiv_id":null,"evidence_quote":"Establishes the full-reconstruction baseline and the person-level result that most blocks are uniquely reconstructible from Summary File 1 tables, the contrast that motivates partial reconstruction."},{"cited_title":"Towards formalizing the gdpr’s notion of singling out,","cited_arxiv_id":null,"evidence_quote":"Provides the formal notion of singling out that the paper adapts into its singleton claims of the form $R(a,1)$."},{"cited_title":"Confidence-ranked reconstruction of census microdata from published statistics,","cited_arxiv_id":null,"evidence_quote":"Supplies the tract- and state-level prior distributions used to show that verified claims are surprising relative to demographic baselines."}],"review_version":1}