{"id":"e1dd1376-712d-4553-ade8-959a7a94e6fd","arxiv_id":"2506.06124","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"PrivTru rewrites relational queries into minimal per-source subqueries and is proven to minimize the trustee's posterior concentration on the true data, within the class of relational data exchanges.","lead":"This paper proposes PrivTru, a data trustee design that splits each database query into minimal subqueries sent to every data source, so the trustee receives only the information strictly needed to answer it. The authors prove that, among all relational algebra based data exchanges, PrivTru minimizes the trustee's ability to reconstruct the underlying data, for any prior belief the trustee holds.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (2)'s candidate set ignores the subquery the trustee actually sent, so p_i_Ri is not the posterior; Theorem 2 compares the wrong quantity and does not establish minimal leakage.","rationale":"The reader's weakest assumption is the honest-but-curious trustee. That is a legitimate concern but not the most load-bearing: even with an honest trustee, the leakage measure is not the actual posterior. The paper does give a clear design and Algorithm 1, but the core theorem's proof is expressed entirely in terms of C_i(R_i). Since Eq. (2) is too coarse, the proof's inequalities do not say anything about the exchange's true posterior. This is an internal correctness issue, not just a scope limitation or threat-model gap. I therefore adjust the verdict to REJECT: the central formal claim is unsupported as written, although the design discussion might survive a revision with a corrected likelihood model.","tokens_in":10890,"tokens_out":13753,"duration_ms":140993,"concrete_test":"Run the definitions on a single-source instance: s=1, T_1={a}, q = π_A(σ_true(T_1)) (the identity query in extended normal form). Algorithm 1 returns pqi = identity and R_1 = {a}. The true set of tables consistent with the known identity subquery and the observed result is exactly {{a}}. Eq. (2), however, also includes {a,b} for any b in the domain, because the extra row is unconstrained by the injective map. Thus Eq. (3) gives p_1_R1({a}) < 1 whenever the prior assigns positive mass to {a,b}, directly showing the paper's posterior is not the trustee's posterior. A second check: re-run the proof of Theorem 2 with C_i(R_i) replaced by the exact preimage { \\tilde T : pqi(\\tilde T) = R_i } and see whether the inclusion used in the proof still follows; the identity-subquery example shows the current inclusion is an artifact of the too-large candidate set.","verdict_should_be":"REJECT","load_bearing_attack":"Section 5 defines C_i(R_i) (Eq. 2) as all tables \\tilde T for which there is an injective map m: R_i → \\tilde T matching the non-propositional and propositional columns of R_i, and sets p_i_Ri(X)=p_i(X|C_i(R_i)) (Eq. 3). The trustee, however, knows the subquery pqi it sent, so the correct conditioning event is { \\tilde T : pqi(\\tilde T) = R_i }. Eq. (2) checks only that each returned row can be embedded in \\tilde T; it never requires the known subquery evaluated on \\tilde T to produce exactly R_i, so extra rows of \\tilde T that would be discarded by the projection or selection are admitted. For the identity subquery pqi = T_i, receiving R_i = T_i leaves no uncertainty, but Eq. (2) also admits every strict superset of T_i, so Eq. (3) assigns posterior probability < 1 to the true table. Theorem 2 is proved by comparing C_i(R_i) and C_i(\\tilde R_i), so the proof establishes optimality only for this proxy, not for the exchange's actual posterior information about T_i. The abstract's 'regardless of prior' claim therefore inherits this gap.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes PrivTru, a data trustee instantiated as a relational data exchange. It argues that exchanges are preferable to stewards under Hoepman's privacy design strategies, and then introduces a relational algebra extension called RAPP (relational algebra with propositional projections) that allows sources to evaluate propositions locally. The main formal contribution is Algorithm 1, which, for any relational query in extended normal form, computes per-source subqueries and a collecting query that produce exactly the original query's result. The paper then claims, in Theorem 2, that this algorithm minimizes the information leakage to the exchange, measured as the Kullback-Leibler divergence between the exchange's prior and posterior over the full source tables, and that this optimality holds regardless of the exchange's prior knowledge.","tokens_in":11131,"tokens_out":8481,"duration_ms":90480,"significance":"The problem addressed is timely and the formalization of query splitting for privacy-preserving data exchanges is a useful conceptual step. The paper's strengths include a clean problem statement (CS-Problem), a concrete algorithm with rewrite rules, and an explicit attempt to prove an optimality statement rather than merely a heuristic. There are no fitted parameters and no circular appeal to the authors' own results. However, the central privacy claim is not established as written: the paper's definition of the trustee's posterior information ignores the subquery that the trustee itself sent, and the proof of Theorem 2 contains asserted structural assumptions about arbitrary solutions. If these issues are repaired, the result could be a valuable contribution to privacy engineering; in its current form, the optimality theorem is not supported.","major_comments":[{"comment":"The candidate set C_i(R_i) does not represent the information actually available to the trustee, because the trustee knows the subquery pq_i it sent. The correct conditioning event for the posterior over ~T is {~T : pq_i(~T) = R_i}, not the set of tables into which R_i can be injectively embedded. Eq. (2) admits tables with extra rows that would be discarded by the projection or selection in pq_i. For example, if pq_i is the identity subquery, then R_i = T_i leaves no uncertainty about T_i, but Eq. (2) also contains every strict superset of T_i, so Eq. (3) assigns posterior probability less than 1 to the true table. Consequently, Eq. (1) does not measure the actual information leakage, and Theorem 2 compares the wrong quantity; the abstract's 'regardless of prior' claim inherits this gap.","section":"Section 5, Eqs. (2)-(3)"},{"comment":"The proof asserts that for every clause x spanning T_i and another table, any other solution ~R_i must contain a propositional projection column p_{x,i}, and then states that augmenting ~R_i with such a column 'is also a solution' to Problem 1. This is not formally justified. Adding attributes to ~R_i may change the candidate set C_i, and the proof does not show that the original and the augmented solutions induce the same leakage under Eq. (3). Since the subsequent containment argument relies on this WLOG reduction, the proof does not currently cover all possible solutions of the CS-Problem.","section":"Section 5, Theorem 2 proof, Statement 2"},{"comment":"The optimality theorem is stated for the algorithm that the exchange runs, but the paper never states the threat model under which the exchange is honest-but-curious. In particular, nothing in the system prevents the exchange from deviating from Algorithm 1 and simply requesting full tables, i.e., the trivial solution pq_i = T_i. Under such a deviation the exchange receives all source data and leakage is maximal. The claim that PrivTru 'minimizes information leakage to the data trustee' therefore holds only if the trustee faithfully executes Algorithm 1; this assumption should be stated explicitly in Section 4 and in the abstract's claims.","section":"Sections 4-5 (threat model)"}],"minor_comments":[{"comment":"Lemma 1 is stated without proof, although it is used directly in the proof of Theorem 1. Please provide a proof or a precise citation for these rewrite rules.","section":"Section 4, Lemma 1"},{"comment":"The notation p_i_Ri(X) := p_i(X | C_i(R_i)) should be introduced with an explicit statement of the sample space and the sigma-algebra on D(T_i)^2, since the conditioning event is not the standard preimage of a relational query.","section":"Section 5, notation around Eq. (3)"},{"comment":"The condition that every literal in a formula in extended normal form is satisfiable and not a tautology is unclear for literals of the form AθB with A and B belonging to different tables; please clarify how satisfiability is evaluated in that case.","section":"Definition 3(c)"},{"comment":"The phrase 's+1 times the empty query q_empty' is easy to misread; it would be clearer to say that the collecting query pq as well as every subquery pq_i is set to the empty query.","section":"Algorithm 1, Line 1"},{"comment":"The discussion of the Hide strategy notes that data exchanges suffer from possible traffic-pattern leakage, but this concern is not revisited in the evaluation of PrivTru; a sentence explaining why this is out of scope would help.","section":"Section 3"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The RAPP operator and Algorithm 1 are a real, modest formalization of pushing query work to the sources, and I buy Theorem 1's correctness proof. The paper is clearly written and the steward/exchange comparison is sensible. But the optimality claim in Theorem 2 has a load-bearing flaw: the posterior is not the actual posterior.\n\nSection 5 defines C_i(R_i) as all tables T~ such that R_i injectively embeds into T~ with matching values and propositional truth values. The trustee knows the subquery pqi it sent. The correct conditioning event is {T~ : pqi(T~)=R_i}. Eq. (2) never uses pqi, so it admits tables that would produce extra rows under pqi. For the identity subquery, C_i(R_i) includes every superset of the true table, so p_i_Ri(T_i) stays below 1 even though the trustee literally holds the full table. Theorem 2 proves containment of these over-approximate sets, which does not establish minimal leakage under the actual posterior. The \"regardless of prior\" claim inherits this gap.\n\nCredit where it's due: the rewriting lemmas in Section 4 are plausible, the algorithm scales naturally, and the paper does not fit parameters or lean on prior results. Other soft spots are minor by comparison: the threat model is never stated, and it is honest-but-curious; a malicious trustee could simply request full tables. Some steps in the proof of Theorem 2, especially Statement 2, also assume structural properties of arbitrary solutions without full rigor.\n\nWho gets value from this: people designing data-sharing intermediaries or working on privacy formalizations for distributed query processing. The algorithm is worth knowing; the optimality claim should not be cited as is.\n\nMy recommendation: send it to peer review, but as major revision. The core idea deserves referee time, and the flaw may be repairable by explicitly conditioning the posterior on the known subquery.","headline":"The query distribution algorithm is clean and its correctness proof is solid, but Theorem 2 compares a candidate set that ignores the subquery the trustee actually sent, so the main optimal-privacy claim does not follow as written.","tokens_in":11608,"tokens_out":5605,"would_cite":false,"duration_ms":56024,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P15","68P20","68P27"],"pacs":[],"model":"deepseek-v4-flash","headline":"PrivTru is a data-exchange trustee whose subqueries provably minimize the information a trustee learns from the sources, for any relational query and any prior.","keywords":["data trustee","privacy by design","data exchange","information leakage","relational algebra","query distribution","Kullback-Leibler divergence","data minimization"],"falsifier":"Search for a query in extended normal form and a correct alternative solution to the subquery-calculation problem whose subresult $\\tilde{R}_i$ yields a candidate set $C_i(\\tilde{R}_i)$ strictly smaller than Algorithm 1's $C_i(R_i)$ for some source $i$; Theorem 2 predicts none exists. A concrete place to look is a two-table join with a cross-table selection clause, where the alternative might omit an attribute PrivTru keeps; if the candidate set shrinks, the containment claim fails.","tokens_in":10698,"feed_emoji":"🔐","tokens_out":7085,"duration_ms":62117,"temperature":0.7,"pith_summary":"PrivTru is a data-exchange trustee that answers a receiver's relational-algebra query by sending each data source a subquery designed to reveal as little as possible, then assembling the subresults. The paper's central claim is a provable optimality result: for every query in extended normal form, PrivTru's subqueries leave the trustee with a posterior probability on the true source tables that is no larger than the posterior under any other correct way of splitting the query among sources. Because the argument works for any prior the trustee might hold, the privacy guarantee does not depend on knowing what the trustee already knows. The practical stake is that an intermediary can relay useful query answers without ever collecting the underlying data, at the strongest possible level of data minimization within the relational model.","feed_headline":"A data exchange that provably requests the least data","feed_subtitle":"For any relational query, its subqueries keep the trustee's posterior on your data no larger than any rival scheme.","key_machinery":"The carrying objects are the extended normal form for relational-algebra queries and the relational algebra with propositional projections (RAPP), which lets a source return the truth value of a local predicate instead of revealing the underlying column values. Lemma 1 supplies the rewrite rules that move selection clauses and projections into individual source queries, and Algorithm 1 applies these rules clause by clause to produce subqueries. The leakage measure is the candidate set $C_i(R_i)$ -- the set of complete tables consistent with what source $i$ returned -- and the trustee's posterior is the prior conditioned on that set. Theorem 2's containment $C_i(R_i) \\supseteq C_i(\\tilde{R}_i)$ is what makes the optimality independent of the prior.","core_discovery":"The core discovery is Theorem 2: Algorithm 1's query distribution is leakage-optimal among all relational data exchange implementations. For any query $q = \\pi_\\beta \\sigma_F(T_1 \\bowtie \\cdots \\bowtie T_s)$ in extended normal form, if $(\\tilde{q}, \\tilde{q}_1, \\ldots, \\tilde{q}_s)$ is any other correct solution to the subquery-calculation problem, then for every source $i$ and every discrete prior $p_i$ with $p_i(T_i) > 0$, the candidate set $C_i(R_i)$ built from PrivTru's subresult $R_i$ contains the candidate set $C_i(\\tilde{R}_i)$. Since the trustee's posterior is the prior conditioned on the candidate set, containment makes the posterior probability of the true table under PrivTru no larger than under the alternative, equivalently the Kullback-Leibler divergence from the true table is no smaller. The proof pushes every clause of the selection condition to the source that can evaluate it and projects away every attribute the receiver's final query does not need, using the rewrite rules of Lemma 1.","pith_inferences":["The honest-but-curious boundary suggests an enforcement question the paper leaves open: without a way to verify that a trustee's subqueries match Algorithm 1, a malicious trustee can bypass the guarantee by over-requesting, for example by setting a subquery to the full table.","The candidate-set containment gives a general recipe for minimal-leakage intermediaries -- push each predicate to the source that can evaluate it and project away every attribute the final query does not need -- which could be applied outside relational databases to other query languages with local predicate evaluation.","A natural testable extension is to implement Algorithm 1 on a standard SQL engine and compare candidate-set sizes against full-table transfer on realistic schemas; the theorem predicts the gap in posterior mass, which can be measured empirically on finite domains.","The prior-independence property suggests PrivTru composes well with source-side noise mechanisms: if each source adds differential privacy before answering, the candidate-set analysis would need to be reworked, but the minimal-request principle would remain the starting point."],"forward_implications":["Because every relational-algebra query can be rewritten into extended normal form, the optimality covers the whole relational query language, not a restricted toy class.","Data sources can answer with truth values for local predicates instead of raw rows, so data minimization survives even when the final query joins information from several sources.","The guarantee holds for any prior, so the trustee's background knowledge about patients, customers, or other subjects does not enlarge the leakage beyond the minimum for that query.","The receiver still obtains the exact result of the original query, so utility is preserved: the answer equals what a central database holding all tables would compute.","The paper argues that aggregation can be handled by having sources evaluate aggregate functions locally, which would extend the same minimization idea to statistics over the data."],"supporting_citations":[{"why":"Supplies the normal-form and rewrite machinery the paper uses to put every query into extended normal form and to push selections into source queries.","marker":"[1]"},{"why":"Defines the relational data model that PrivTru builds on for tables and attributes.","marker":"[7]"},{"why":"Provides the privacy design strategies whose Minimize and Separate principles motivate the data-exchange design.","marker":"[9]"},{"why":"Defines the Kullback-Leibler divergence used to quantify the trustee's information gain.","marker":"[11]"},{"why":"Provides the information-theoretic context for the discrete KL divergence and its properties.","marker":"[5]"},{"why":"Establishes the data trustee concept that PrivTru instantiates.","marker":"[12]"}],"fun_headline_variants":["Trustee provably requests least data for any query","PrivTru shows optimal minimal leakage in data sharing","Privacy by design: prove minimal trustee data requests","Optimal data trustee: minimal info, provable no-leak"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The analysis assumes the trustee is honest-but-curious: it runs Algorithm 1 exactly as specified and never sends a subquery broader than the algorithm prescribes, so a trustee that deliberately requested a full source table would be outside the model's protection.","fun_headline_variants_meta":{"raw":{"variants":["Trustee provably requests least data for any query","PrivTru shows optimal minimal leakage in data sharing","Privacy by design: prove minimal trustee data requests","Optimal data trustee: minimal info, provable no-leak"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000216,"raw_usage":{"total_tokens":1396,"prompt_tokens":870,"completion_tokens":526,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":486,"completion_tokens_details":{"reasoning_tokens":460}},"tokens_in":486,"tokens_out":526,"duration_ms":5727,"temperature":1.0,"reasoning_tokens":460,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T06:01:03.962771+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search for a query in extended normal form and a correct alternative solution to the subquery-calculation problem whose subresult $\\tilde{R}_i$ yields a candidate set $C_i(\\tilde{R}_i)$ strictly smaller than Algorithm 1's $C_i(R_i)$ for some source $i$; Theorem 2 predicts none exists. A concrete place to look is a two-table join with a cross-table selection clause, where the alternative might omit an attribute PrivTru keeps; if the candidate set shrinks, the containment claim fails.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the normal-form and rewrite machinery the paper uses to put every query into extended normal form and to push selections into source queries."},{"cited_title":"In: ICT Systems Security and Privacy Protection","cited_arxiv_id":null,"evidence_quote":"Provides the privacy design strategies whose Minimize and Separate principles motivate the data-exchange design."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the information-theoretic context for the discrete KL divergence and its properties."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the data trustee concept that PrivTru instantiates."}],"review_version":1}