{"id":"783b8ad1-4df7-4bb7-9fcb-e0f3c98ce4fc","arxiv_id":"2411.18531","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Statistic maximal leakage is a new prior-independent, secret-specific privacy measure with additive composition and an efficient min-cost flow computation for deterministic mechanisms.","lead":"This paper introduces statistic maximal leakage, a privacy measure that quantifies how much a data release mechanism reveals about one specific known secret under a worst-case prior. It proves composition and post-processing properties, gives an efficient algorithm for deterministic mechanisms, and argues that a quantization mechanism outperforms randomized response on tabular data.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Adaptive composition proof in App. D rests on an invalid equality: the per-step term Q_i sums over past outputs, so it is not the SML of M_i and the advertised additive bound is not established as written.","rationale":"The reader's verdict is CONDITIONAL, and I agree that conditional acceptance is appropriate. The reader's rationale already flags the App. D composition proof as containing an invalid equality, and my stress-test confirms and sharpens that concern: the quantity Q_i in the proof is a sum over histories rather than a worst case over histories, so the equality Q_i=Π_{M_i,g} fails for adaptive mechanisms. This is load-bearing because adaptive composition is one of the three motivating properties of SML and is explicitly advertised in the abstract and Theorem 2. I do not claim the theorem is false; the inequality may be repairable by reformulating the per-mechanism guarantee as a supremum over previous outputs and using a product bound. However, as written, the proof does not establish the central composition claim. The reader's weakest_assumption (finite parameter space and one-try guessing semantics) is a different modeling limitation and is not the most immediate obstacle; hence my agreement is only partial. A second serious issue exists in the Thm. 4 mechanism-comparison proof, where solving (1+sr)/(1+r)=s/I appears to give r=(s−I)/(s(I−1)), not the expression used in App. F; that algebra error also undermines the QM-versus-RR theoretical comparison. I have focused on the composition proof because it is more central to the paper's core contribution, and it is the concern the reader also identified. The recommended verdict remains CONDITIONAL: accept only if the composition proof is corrected and the Thm. 4 algebra is re-derived.","tokens_in":50841,"tokens_out":22585,"duration_ms":220288,"concrete_test":"Verify the contested equality on the two-mechanism deterministic example above. Compute Q_2 = log Σ_{h∈{1,2}} Σ_y sup_g P_2(y|θ_g,h); it equals log2, while Π_{M_2,g}(h)=0 for every h. This falsifies the proof's assertion Q_i=Π_{M_i,g}. Then check whether a revised inequality of the form Π_{comp} ≤ Π_{M_1} + sup_h Π_{M_2}(h) holds for this example and for a stochastic perturbation; if the revised bound holds in general, the theorem can be repaired, and if not, a counterexample to Thm. 2 exists.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 2 (App. D) is a cornerstone claim: SML degrades additively under adaptive composition. In the proof, Lemma 2 reduces the composed SML to sup_{P_{Θ|G}∈{0,1}} log Σ_{θ'} sup_g ∏_i P_i(θ'(i)|θ_g, past). The proof then introduces, for each i, Q_i = log Σ_{[θ'(1),...,θ'(i)]} sup_g P_i(θ'(i)|θ_g, past) and asserts Q_i = Π_{M_i,g}. This equality is false for i>1. The SML of an adaptive mechanism M_i at a fixed history h is log Σ_{θ'(i)} sup_g P_i(θ'(i)|θ_g,h), and a guarantee for the adaptive mechanism must be a worst case over histories h. Q_i additionally sums over all histories h, so Q_i ≥ sup_h Π_{M_i,g}(h), with strict inequality when multiple histories contribute. Example: Θ={θ1,θ2}, g(θ1)=g1, g(θ2)=g2; M1 outputs h=1 for θ1 and h=2 for θ2, so Π_{M1}=log2. Let M2 output y=h for every θ (constant per history); then Π_{M2}(h)=0 for each h, but Q_2=log2. Thus the proof's final equality is invalid, and the theorem is not proven by the given argument. The result may be salvageable by replacing the history-sum Q_i with a history-supremum and proving a product bound, but that is a substantive correction, not a typo.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces statistic maximal leakage (SML), a privacy measure that quantifies the worst-case multiplicative increase in one-try guessing of a known secret g(Θ) after release of Θ′. The measure is defined in Eq. (2) by a supremum over priors and attack strategies, and Proposition 1 reduces it to a finite max-over-secrets form. The paper claims three properties: prior-independence, secret-awareness, and adaptive composition with post-processing. It proves post-processing, gives an NP-hardness result for general mechanisms, gives a polynomial-time minimum-cost-flow algorithm for deterministic mechanisms, and derives closed-form privacy and distortion guarantees for randomized response and the quantization mechanism, with an empirical comparison on Census data. The central weakness is the proof of the adaptive composition theorem in Appendix D, which contains an invalid equality and an undefined notion of per-step SML for adaptive mechanisms.","tokens_in":51150,"tokens_out":10200,"duration_ms":106481,"significance":"If the main claims were fully established, SML would be a useful addition to the literature: it is operationally defined, does not require a prior, is explicitly secret-specific, and the deterministic-mechanism flow formulation gives a concrete auditing tool. The paper also contains several genuinely valuable components that are not affected by the composition-proof gap: Proposition 1, the NP-hardness reduction, the RR and QM closed forms, and the empirical study are all derived from the definitions without fitted parameters or circular assumptions. The quantization-versus-randomized-response comparison is a substantive contribution. However, the adaptive composition theorem is advertised as a core property in the abstract and introduction, and the current proof does not establish it; this is a load-bearing issue that must be fixed before the paper can be accepted.","major_comments":[{"comment":"The final equality in the proof of Theorem 2 is false. The term Q_i = log Σ_{[θ′(1),...,θ′(i)]} sup_g P_i(θ′(i)|θ_g,{M_k,θ′(k)}) is not the statistic maximal leakage of the adaptive mechanism M_i. For a fixed history h, the per-step SML would be log Σ_{θ′(i)} sup_g P_i(θ′(i)|θ_g,h); Q_i additionally sums over all previous histories, so Q_i ≥ sup_h Π_{M_i,g}(h), and the inequality can be strict. Concretely, take Θ={θ1,θ2}, g(θ1)=g1, g(θ2)=g2, let M1 output h=1 for θ1 and h=2 for θ2, and let M2 output y=h for every θ. Then Q_2=log 2 while Π_{M2,g}(h)=0 for each history h, so the asserted equality Q_i=Π_{M_i,g} fails. Since the displayed chain in App. D relies on this equality, Theorem 2 is not proved as written. A corrected argument is not a mere typo: the surrounding inequalities bound the composition by Σ_i Q_i, and the fact that Q_i ≥ Π_{M_i,g} goes in the wrong direction for the desired additive bound. The result may be salvageable by proving a product bound with a history-supremum formulation, but that proof is absent.","section":"App. D (Theorem 2)"},{"comment":"The statement of adaptive composition is not well-defined because Eq. (2) defines SML only for a fixed conditional distribution P_{Θ′|Θ}. In Theorem 2, M_i is a function of θ and all previous outputs, so there is no single channel P_{Θ′|Θ} to which Eq. (2) applies. Appendix D introduces channels P_{Θ′(i)|Θ,{M_k,Θ′(k)}} but does not define what it means for an adaptive mechanism to satisfy a per-step guarantee Π_{M_i,g}. This ambiguity is not cosmetic: it is what permits the invalid equality discussed above. The authors should either define per-step SML for adaptive mechanisms explicitly (e.g., as a worst case over histories) and prove the theorem under that definition, or restate the result in a way that avoids the undefined quantity.","section":"Theorem 2 statement"},{"comment":"The minimum-cost-flow computation in Algorithm 1 is underspecified: the text does not state the required flow value or whether the objective is to minimize cost among all feasible flows, among maximum flows, or among flows of a fixed amount. The proof of Proposition 2 later refers to the flow 'going through' a set Θ′(+), which is only meaningful if the optimal flow is a maximum flow in the constructed network. If the intended interpretation is the standard min-cost flow with a prescribed flow amount, the construction is incomplete; if the intended interpretation is min-cost max-flow, that should be stated explicitly and used consistently in the proof. This is a load-bearing specification issue for the paper's central computation result, and it should be resolved before the reader can implement or verify the algorithm.","section":"Prop. 2 / Alg. 1"}],"minor_comments":[{"comment":"In the 3-set cover reduction, the set is written as T_i = {t(i)_1, t(i)_3, t(i)_3}; the second subscript should presumably be 2, not 3.","section":"App. C"},{"comment":"Lemma 2's proof cites 'Eq. (13)', but Eq. (13) appears later in Appendix L for the continuous-parameter extension. The reference should be to the analogous discrete expression from Proposition 1.","section":"App. D"},{"comment":"The continuous-parameter extension in Eq. (3) and Proposition 8 are stated without regularity conditions on the densities or on the mechanism kernel; some integrability or absolute-continuity assumptions should be stated explicitly.","section":"Sec. VII-B"},{"comment":"The notation τ is used both for the histogram precision level and for the number of samples in Proposition 3 ('a dataset with τ samples'). Since the paper assumes τ ≤ n, please clarify whether the robustness result requires τ = n or only τ ≤ n.","section":"Sec. III and Sec. V-C"},{"comment":"Theorem 4 combines the two mechanism-specific results and the comparison into a single theorem with three statements. Separating the RR and QM claims would make the statement and proof easier to follow.","section":"Sec. V-C"}],"recommendation":"major_revision","confidential_remarks":"The paper is an extended version of an ISIT 2024 paper, and the composition proof gap is the main obstacle. The rest of the technical content, including the deterministic flow equivalence, the hardness result, and the mechanism comparisons, appears sound and is worth publishing once the composition theorem is either correctly proved or appropriately weakened. I would recommend major revision rather than rejection because the deficit is localized to the adaptive composition argument and its supporting definitions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper puts a name and a tractable computation on a useful quantity: worst-case multiplicative leakage of a known, fixed secret with a prior-free adversary. The deterministic min-cost flow equivalence (Prop. 2) is a genuine, clean result, and the closed forms for RR and QM plus the empirical comparison give practitioners a concrete way to reason about leakage of a specific statistic. That is a solid contribution on its own.\n\nThe soft spot is real. Theorem 2's proof in App. D has an invalid step. Lemma 2 correctly writes the composed SML as a sup over priors of a sum over histories of a product of per-step conditional probabilities. But then the proof defines Q_i = log Σ_{[θ'(1),...,θ'(i)]} sup_g P_i(θ'(i)|θ_g, past) and calls it Π_{M_i,g}. That is not the SML of the i-th mechanism. The SML of an adaptive mechanism at a fixed history is log Σ_{θ'(i)} sup_g P_i(θ'(i)|θ_g, history), and a guarantee must hold uniformly over histories. Q_i sums over all histories, so it is generally larger; the stress-test's two-step example with Θ={θ1,θ2}, deterministic first output that reveals the secret, and constant second mechanism gives Π_{M1}=log2, Π_{M2}(h)=0 at each history, but Q_2=log2. The additive bound is therefore not established as written. The theorem may be salvageable by taking a history-supremum and proving a product bound, but that is a substantive correction, not a typo.\n\nOther concerns are minor. Thm. 1's approximation claim leans on an edge-cost flow approximation that is itself NP-hard, and no code is provided; the empirical figures lack error bars in some panels. The paper's own Sec. VII correctly notes the continuous-parameter extension is open and that the measure is about the most likely secret, not fairness-oriented losses. Those limitations do not undercut the finite-support results.\n\nI largely agree with the reader's conditional verdict. The core definition, Prop. 1, Prop. 2, and the RR/QM closed forms are internally consistent and the experiments align with the theory. If the composition proof is fixed, the paper will be a useful addition to the quantitative information flow literature. As submitted, the main advertised property is unproven.\n\nRecommendation: send it to peer review, but require the composition proof to be corrected and the missing code/error bars to be addressed. A serious referee can check the repair and likely endorse the rest.","headline":"Useful measure and a clean min-cost flow result, but the adaptive composition proof has a real gap that needs fixing.","tokens_in":51677,"tokens_out":2165,"would_cite":false,"duration_ms":21014,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A17","68P27","90C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"Statistic maximal leakage measures the worst-case gain in one-try guessing of a known secret, composes additively, and reduces to a min-cost flow for deterministic mechanisms.","keywords":["statistic maximal leakage","privacy","maximal leakage","composition","post-processing","min-cost flow","quantization mechanism","randomized response"],"falsifier":"On a finite instance with, say, three possible parameters and two secrets, enumerate every deterministic mechanism, compute SML by exhaustive maximization over $\\{0,1\\}$-valued conditional priors, and compare to the min-cost flow value from Algorithm 1; a mismatch would refute Proposition 2.","tokens_in":1617,"feed_emoji":"🔐","tokens_out":2208,"duration_ms":68023,"temperature":0.7,"pith_summary":"Data holders often want to hide one known statistic—say the fraction of records in a category—rather than everything about the data. This paper introduces statistic maximal leakage, a privacy measure that quantifies the worst-case multiplicative increase in an adversary's chance of guessing that known secret correctly after seeing a mechanism's output, relative to their best guess without it. The measure is secret-aware and needs no prior over the data beyond the support, and the paper proves it composes additively across sequential releases and is preserved under post-processing. It also shows that for deterministic release mechanisms the measure can be computed in polynomial time by solving a minimum-cost flow problem, even though it is NP-hard in general. On tabular categorical data the paper argues that a quantization mechanism beats randomized response at the same privacy level, making secret-specific protection considerably cheaper in utility.","feed_headline":"Known-secret leakage composes additively and can be audited via flows","feed_subtitle":"For deterministic releases, statistic maximal leakage reduces to a min-cost flow, enabling poly-time privacy checks.","key_machinery":"The object carrying the argument is the SML functional together with a structural simplification: Proposition 1 shows that the supremum can be restricted to priors with $P_{\\Theta|G}\\in\\{0,1\\}$, so each secret value points to a single parameter $\\theta_g$. For deterministic mechanisms this reduces to a min-cost flow on a graph with a source, G-nodes, $\\Theta$-nodes, $\\Theta'$-nodes, and a sink: unit capacities enforce the single-$\\theta_g$ and single-secret-per-output constraints, and edge costs $-P_{\\Theta'|\\Theta}(\\theta'|\\theta)$ make the total cost equal to the sum inside the logarithm in Proposition 1. That reduction is what turns SML into a poly-time audit for deterministic releases and, via a modified edge-cost flow, shows that the general case is NP-hard.","core_discovery":"Statistic maximal leakage fixes a known secret $G=g(\\Theta)$ and a mechanism $M$, and defines the leakage as $\\Pi_{M,g} = \\sup_{P_\\Theta, P_{\\hat G|\\Theta'}} \\log \\frac{P(\\hat G=G)}{\\sup_{g\\in G} P_G(g)}$. The paper establishes that this quantity is prior-independent in a worst-case-prior sense, satisfies adaptive composition (the SML of a sequential composition is at most the sum of the individual SMLs), and is non-increasing under post-processing. The central algorithmic discovery is that when $M$ is deterministic, $\\Pi_{M,g}$ equals the negative logarithm of the minimum cost of a unit-capacity flow in a three-layer network, which yields polynomial-time auditing; for general mechanisms the computation is NP-hard. The paper then derives closed-form SML and distortion formulas for randomized response and the quantization mechanism, and shows that at equal non-trivial SML budgets the quantization mechanism's worst-case total-variation distortion is asymptotically no worse than randomized response's.","pith_inferences":["The min-cost flow formulation suggests a natural extension: approximate SML for randomized mechanisms by sampling or discretizing the output distribution and solving the same flow, with error that vanishes as the discretization refines; the paper does not pursue this.","SML's worst-case-prior definition makes it a capacity-style quantity, so it could be paired with an actual prior to give an empirical weak-leakage estimate rather than only a hard guarantee.","Because SML only tracks one-try exact guessing of the most likely secret, adversarially useful partial information (such as narrowing the secret to a small set) is invisible; a gain-function variant would close that gap.","The quantization-over-randomized-response comparison is proven for a category-fraction secret at large precision; testing other secret functions is a direct way to see how far the comparison generalizes."],"forward_implications":["Any deterministic release can be audited for SML in time polynomial in $|\\Theta|\\cdot|\\Theta'|$, enabling practical privacy accounting for such mechanisms.","Sequential, adaptively chosen releases of the same data have SML at most the sum of the individual SMLs, so privacy budgets compose linearly.","Post-processing a released output can only decrease SML, so arbitrary downstream transformations preserve the guarantee.","For tabular categorical data with a category-fraction secret, a quantization mechanism can match randomized response's SML with asymptotically lower worst-case distortion as precision $\\tau$ grows.","Because SML is secret-specific, it can certify protection of a target statistic with less perturbation than a secret-agnostic maximal-leakage baseline."],"supporting_citations":[{"why":"Defines maximal leakage, the operational guessing-based privacy measure that SML specializes to a single known secret.","marker":"[9]"},{"why":"Proves adaptive composition for pointwise maximal leakage, the property SML must match and whose proof does not carry over.","marker":"[27]"},{"why":"Introduces worst-case min-entropy leakage, which appears in the bounds relating SML to other entropy-based leakage measures.","marker":"[8]"},{"why":"Introduces the summary-statistic privacy setting and quantization mechanisms that motivate the SML framework.","marker":"[17]"},{"why":"Analyzes quantization as an optimal deterministic privacy policy, informing the quantization mechanism design.","marker":"[28]"},{"why":"Supplies the randomized response mechanism formulation used as a comparison baseline.","marker":"[30]"},{"why":"Provides the min-cost flow theory used to compute SML for deterministic mechanisms in polynomial time.","marker":"[63]"},{"why":"Establishes NP-completeness of 3-set cover, the source problem in the hardness reduction for general SML computation.","marker":"[64]"},{"why":"Provides approximation algorithms for edge-cost flow, yielding the approximation result for general SML computation.","marker":"[65]"}],"fun_headline_variants":["Known-secret privacy metric composes, audits via min-cost flow","SML: leak for known secrets, efficient audit via network flow","Statistic maximal leakage: composition and poly-time audit for deterministic","New measure for known-secret leakage: composes, poly-checkable","Audit known-secret leakage in poly-time via flow and composition"],"cache_read_input_tokens":53760,"weakest_assumption_plain":"The load-bearing premise is that the parameter space is finite (a categorical histogram at fixed precision $\\tau$) and that privacy risk is measured by the multiplicative increase in exact one-try guessing of a known secret under a worst-case prior.","fun_headline_variants_meta":{"raw":{"variants":["Known-secret privacy metric composes, audits via min-cost flow","SML: leak for known secrets, efficient audit via network flow","Statistic maximal leakage: composition and poly-time audit for deterministic","New measure for known-secret leakage: composes, poly-checkable","Audit known-secret leakage in poly-time via flow and composition"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000202,"raw_usage":{"total_tokens":1343,"prompt_tokens":870,"completion_tokens":473,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":486,"completion_tokens_details":{"reasoning_tokens":382}},"tokens_in":486,"tokens_out":473,"duration_ms":5149,"temperature":1.0,"reasoning_tokens":382,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T11:09:17.885543+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a finite instance with, say, three possible parameters and two secrets, enumerate every deterministic mechanism, compute SML by exhaustive maximization over $\\{0,1\\}$-valued conditional priors, and compare to the min-cost flow value from Algorithm 1; a mismatch would refute Proposition 2.","supporting_citations":[{"cited_title":"An operational approach to information leakage,","cited_arxiv_id":null,"evidence_quote":"Defines maximal leakage, the operational guessing-based privacy measure that SML specializes to a single known secret."},{"cited_title":"Pointwise maximal leakage,","cited_arxiv_id":null,"evidence_quote":"Proves adaptive composition for pointwise maximal leakage, the property SML must match and whose proof does not carry over."},{"cited_title":"Quantitative notions of leakage for one-try attacks,","cited_arxiv_id":null,"evidence_quote":"Introduces worst-case min-entropy leakage, which appears in the bounds relating SML to other entropy-based leakage measures."},{"cited_title":"Summary Statistic Privacy in Data Sharing","cited_arxiv_id":"2303.02014","evidence_quote":"Introduces the summary-statistic privacy setting and quantization mechanisms that motivate the SML framework."},{"cited_title":"Development and analysis of deterministic privacy-preserving policies using non-stochastic information theory,","cited_arxiv_id":null,"evidence_quote":"Analyzes quantization as an optimal deterministic privacy policy, informing the quantization mechanism design."},{"cited_title":"Extremal mechanisms for local differential privacy,","cited_arxiv_id":null,"evidence_quote":"Supplies the randomized response mechanism formulation used as a comparison baseline."},{"cited_title":"Flows in networks,","cited_arxiv_id":null,"evidence_quote":"Provides the min-cost flow theory used to compute SML for deterministic mechanisms in polynomial time."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes NP-completeness of 3-set cover, the source problem in the hardness reduction for general SML computation."},{"cited_title":"Flow improvement and network flows with fixed costs,","cited_arxiv_id":null,"evidence_quote":"Provides approximation algorithms for edge-cost flow, yielding the approximation result for general SML computation."}],"review_version":1}