{"id":"f739549d-6d6f-44ae-ba68-15bbab184b6b","arxiv_id":"2411.10429","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Proposes two PIR-based protocols for retrieving the exact nearest counterfactual while keeping the user's immutable feature set private, with communication costs 6d+3M and 9(d+M).","lead":"This paper designs two private-information-retrieval schemes that let a rejected applicant find the closest accepted profile in an institution's database without revealing their feature vector, the features they refuse to change, or which profile they retrieved. The schemes trade communication cost against how much of the database the applicant learns, and the authors quantify this trade-off.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Privacy guarantee holds only against non-colluding servers; an institution observing all three transcripts can interpolate x and I, so the advertised 'private from the institution' claim is stronger than what equation (5) proves.","rationale":"I inspected both achievable schemes and the leakage analysis. The polynomial interpolation for Phases 1 and 2 is sound; the α^0 coefficients reveal exactly Θ and then distances for matching rows, with higher-order terms masked by common randomness. The numerical table is not self-inconsistent at |I|=0: with no immutable features, the two-phase scheme reveals full distances for all M records, so nonzero leakage is expected. The single-phase scheme's range test works because L > R^2 d makes the matching range [0, (d-|I|)R^2] disjoint from any mismatched value. The main weakness is therefore not internal algebra but the adversarial model: if 'the institution' is allowed to see all three server transcripts, the user's x and I are recoverable by interpolation. Since this matches the reader's weakest assumption, and the formal schemes are correct under non-collusion, the conditional verdict remains appropriate.","tokens_in":11109,"tokens_out":31585,"duration_ms":316012,"concrete_test":"Implement a small script that takes the three user queries for Phase 1 and Phase 2 (α_n distinct, n=1,2,3), forms the Vandermonde matrix M3, and solves for the constant coefficients of h1 + αZ1, x∘h1 + αZ2, h2 + αZ3, and x + αZ4. If the recovered h1 and x∘h1 (and h2, x) match the user's true values, then any single entity with access to all three transcripts violates equation (5), confirming that the guarantee does not extend to a unified institution.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing concern is not the algebra of either scheme, which I checked and which appears to decode correctly under the stated N=3 non-colluding model. It is the scope of the privacy claim. The queries Q[xI]_n = [h1 + α_n Z1, x∘h1 + α_n Z2] and Q[xM]_n = [h2 + α_n Z3, x + α_n Z4] are degree-1 polynomials in the server-specific evaluation point α_n. Any party that obtains all three transcripts (equivalently, the institution if it controls or monitors all replicas) can interpolate these polynomials and recover h1, x∘h1, h2, and x exactly. Thus the condition in equation (5) holds only against a single server, not against the institution mentioned in the abstract and introduction. The paper states the N=3 non-colluding assumption, so the mathematical achievability claim is internally consistent, but the headline 'private from the institution' is stronger than what is proven unless the institution is excluded from observing all server transcripts. This is a modeling gap, not a contradiction within the proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper introduces the immutable private counterfactual retrieval (I-PCR) problem, in which a user with a rejected feature vector x and a private immutable-feature set I wishes to retrieve theta* = argmin_{i in Theta} ||y_i - x||^2, with Theta = {i : y_{i,I} = x_I}, from M database records replicated on N = 3 non-colluding servers, while keeping x, I, and theta* private from each server. Two schemes are proposed: a two-phase scheme (first retrieve Theta, then retrieve distances only for i in Theta) with communication cost 9(d+M) symbols, and a single-phase scheme using an L-scaled weight vector h with cost 6d+3M symbols. The paper also extends the schemes to private actionability weights on mutable features and reports a numerical database-leakage comparison in Table I.","tokens_in":11344,"tokens_out":19753,"duration_ms":188559,"significance":"The immutable-feature constraint is a natural and useful generalization of the PCR problem of [20], and the algebraic constructions are mostly sound: Eqs. (12), (22), (29), and (33) decode correctly under the stated N=3 non-colluding assumption with the chosen field sizes. The explicit communication costs and the attempt to quantify database leakage are valuable contributions. However, the leakage comparison currently contains a concrete numerical inconsistency, and the advertised 'private from the institution' guarantee is stronger than the per-server privacy condition actually proved. With those issues repaired, the paper would be a solid incremental contribution to private counterfactual retrieval.","major_comments":[{"comment":"The two entries in this row cannot differ. With I = empty, the two-phase scheme has h1 = 0 and h2 = (1,...,1), so its second-phase decoded value is ||y_i - x||^2 for every i, while the single-phase scheme decodes (y_i - x)^T((y_i - x) ∘ 1) = ||y_i - x||^2 for every i. The remaining downloaded coefficients are masked by the independent server randomness Z'_1,...,Z'_4 and, in Phase 1, by the unknown nonzero scaling rho_i, so they contribute nothing to I(y[M]; A[N] | x, I). Hence the two schemes have exactly the same database leakage at |I|=0, yet Table I reports 1.1432 versus 0.9422. This internal inconsistency invalidates the numerical comparison and the statement in Section IV-D/V that the two-phase scheme 'is always less' than the single-phase scheme; at |I|=0 they are equal, and the single-phase |I|=0 and |I|=3 entries coincide for the same reason.","section":"Section V, Table I, row |I|=0"},{"comment":"The privacy guarantee is stated per server n under the N=3 non-colluding assumption, but the abstract and introduction promise privacy 'from the institution.' A party that observes all three transcripts can interpolate the degree-1 query polynomials in (9), (18), and (27) to recover h1, x ∘ h1, h2, x, and hence I and theta*. Thus the schemes are private only against a single server, not against an institution that controls or monitors all replicas. Please either weaken the 'institution' claim throughout or extend the model to colluding servers; as written, the headline claim exceeds what Eq. (5) proves.","section":"Abstract, Section I, and Eq. (5)"},{"comment":"The analytical leakage comparison is informal at the point where Eq. (39) asserts that the query randomness 'align[s] on a subspace different from the database information subspace,' and the general conclusion that the two-phase leakage is always smaller is drawn from a single synthetic configuration. Please provide a formal derivation of which decoded coefficients actually depend on D and either prove the ordering under the stated distributions or present the comparison as an empirical observation for the tested setting.","section":"Sections IV-D and V"}],"minor_comments":[{"comment":"Please state explicitly that rho_i is part of the servers' common randomness and is therefore the same rho_i for all N servers; otherwise the Vandermonde recovery in Eq. (13) does not follow, since the first column of the answer vector would be [rho_{i,1}, rho_{i,2}, rho_{i,3}]^T instead of [1,1,1]^T.","section":"Section III-A, Eq. (10)"},{"comment":"The printed general formula J_k = [kL : kL + R^2(d-|I|)] is dimensionally inconsistent with the k=1 and k=2 expressions; it should be [kL : kL R^2 + R^2(d-|I|)], and even that is an outer bound because sums of k nonzero squares are not a contiguous integer range.","section":"Section IV-D, J_k definition"},{"comment":"Please include the exact enumeration procedure or code used to compute the 'exact leakage values' in Table I; the text does not specify how the mutual information was evaluated, so the reported numbers are not reproducible from the paper alone.","section":"Section V, Table I"},{"comment":"The indicator function is rendered as '/BD' in the typeset text; please fix the notation to a standard indicator symbol.","section":"Eqs. (7) and (40)"}],"recommendation":"major_revision","confidential_remarks":"The novelty is incremental relative to the authors' prior PCR work [20], but the immutable-feature generalization, the actionability extension, and the leakage quantification are reasonable contributions for a shorter information-theory paper. The numerical inconsistency in Table I and the threat-model wording should be fixed before the paper can be reconsidered."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the two schemes are real and the algebra is consistent under the stated N=3 non-colluding-server model. The single-phase large-L weighting is a genuinely new encoding layer on top of PCR. But two things need fixing before I'd trust the full comparison: Table I is self-inconsistent at |I|=0, and the abstract's 'private from the institution' language overstates what equation (5) proves.\n\nWhat the paper does well: it generalizes PCR to immutable features in a non-trivial way. The two-phase membership-then-distance protocol and the single-phase weighted-distance protocol both decode correctly; I checked the Vandermonde interpolations and the range-separation argument for classifying matches. The leakage decomposition into the mandatory Θ-term and the scheme-specific distance term is a useful framework. The communication costs (9(d+M) vs 6d+3M) and field-size requirements are stated cleanly. This is an honest extension of the authors' own PCR work, not a renaming.\n\nSoft spots, in order of severity. First, Table I: at |I|=0 both protocols reveal exactly the same quantity—the multiset of squared distances ||y_i−x||^2 for every record—so the mutual information must be equal. The table reports 1.1432 for the single-phase scheme and 0.9422 for the two-phase scheme. That is a concrete bug in the numeric leakage evaluation, and it undermines the 'single-phase leaks more' claim in that regime. The general ordering might still hold for intermediate |I|, but the paper needs to rerun and explain.\n\nSecond, the privacy scope. Equation (5) is per-server: server n learns nothing. But the query polynomials are degree-1 in α_n; a party holding all three transcripts—exactly the institution, if it runs the replication—can interpolate and recover x and the immutable mask h1. So the abstract's 'information-theoretically private from the institution' is not established. The authors do state the non-colluding assumption, so this is a modeling gap rather than a contradictory proof, but the headline claim should be calibrated to 'private from any individual server.'\n\nMinor: the leakage numbers are computed on a tiny synthetic dataset (d=M=3) with no code shipped, so they are illustrative, not evidence of general behavior.\n\nBottom line: this is a legitimate, if niche, contribution to private counterfactual retrieval. It deserves a serious referee. I would conditionally accept after the leakage table is fixed and the privacy claim is reworded. For a reading group, I'd say maybe, depending on your appetite for PIR variants.","headline":"The two I-PCR schemes are legitimate and the algebra holds under the stated non-colluding assumption, but the leakage table contradicts itself at |I|=0 and the 'private from the institution' claim outruns the per-server guarantee actually proven.","tokens_in":11867,"tokens_out":7341,"would_cite":true,"duration_ms":67762,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A60","68P27"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that a rejected user can retrieve the index of the closest accepted counterfactual from a replicated database while keeping the feature vector, the immutable set, and the retrieved index information-theoretically private…","keywords":["private counterfactual retrieval","immutable features","private information retrieval","information-theoretic privacy","communication cost","database leakage","actionability","non-colluding servers"],"falsifier":"Take one execution of the two-phase scheme and place all three query tuples $Q_n = [h_1+\\alpha_n Z_1,\\, x\\circ h_1+\\alpha_n Z_2]$ in front of a single adversary who knows the distinct evaluation points $\\alpha_1,\\alpha_2,\\alpha_3$; interpolating the degree-2 polynomial in $\\alpha$ for each coordinate reveals the constant term $h_1$, the indicator vector of $I$, and $x\\circ h_1$, the user's values on the immutable coordinates. This direct calculation shows the per-server privacy claim (5) fails if the non-collusion assumption is dropped.","tokens_in":10938,"feed_emoji":"🔒","tokens_out":10352,"duration_ms":86033,"temperature":0.7,"pith_summary":"This paper establishes that counterfactual retrieval remains possible when a user's private input includes features that cannot be changed. It formulates immutable private counterfactual retrieval, in which a rejected applicant retrieves the index of the accepted database sample closest to them subject to matching their immutable feature values, without revealing the input vector, the immutable set, or the retrieved index to any single server. Two achievable schemes are given, both using three non-colluding, non-communicating replicated servers: a two-phase scheme with communication cost $9(d+M)$ symbols and a single-phase scheme with cost $6d+3M$ symbols. The paper also quantifies the information each scheme leaks about the database, showing the cheaper single-phase scheme leaks more. This matters because applicants often cannot change attributes such as age or nationality, and asking for guidance on those attributes exposes exactly the information they want to keep private.","feed_headline":"Retrieve closest counterfactual without revealing immutable features","feed_subtitle":"Two three-server schemes keep the user's feature vector and immutable set private from the institution.","key_machinery":"The load-bearing object is the $3\\times 3$ Vandermonde matrix $M_3$ built from three distinct server evaluation points $\\alpha_1,\\alpha_2,\\alpha_3$. Each server's answer is a polynomial in $\\alpha_n$ whose constant coefficient is the quantity the user needs and whose higher coefficients are random interference terms; with three servers the user interpolates the constant term while each individual server sees only a masked query. The two-phase scheme uses binary indicator masks $h_1$ (immutable coordinates) and $h_2$ (matching records), and the single-phase scheme uses a weight vector $h$ with entries $1$ or $L$, where $L>R^2 d$, so that the value $(y_i-x)^T((y_i-x)\\circ h)$ lies in $[0,(d-|I|)R^2]$ for matching immutable features and in disjoint higher intervals $[kL,kL+R^2(d-|I|)]$ when $k$ immutable features mismatch.","core_discovery":"The central claim is that the exact counterfactual index $\\theta^* = \\arg\\min_{i\\in\\Theta}\\|y_i - x\\|^2$ with $\\Theta = \\{i : y_{i,I} = x_I\\}$ is retrievable with information-theoretic user privacy under both schemes, satisfying decodability $H(\\theta^*|Q_{[N]}^{[x]}, A_{[N]}^{[x]}, x, I)=0$ and privacy $I(x,\\theta^*,I; Q_n^{[x]}, A_n^{[x]}|D)=0$ for each server $n$, with $N=3$ replicated servers. In the two-phase scheme the user first learns the set $\\Theta$ of records whose immutable coordinates match, then retrieves the squared distances only for those records and takes the minimum. In the single-phase scheme the server evaluates a weighted inner product $(y_i-x)^T((y_i-x)\\circ h)$ with a weight vector $h$ that assigns a large factor $L$ to immutable coordinates, so the value falls in a low, distinguishable range exactly when the immutable features match. Both schemes leak some information about the database; the single-phase scheme leaks more because a record with $k$ mismatched immutable features produces a value in the overlapping interval $[kL, kL+R^2(d-|I|)]$, revealing partial information about non-matching records.","pith_inferences":["Beyond the paper: the three-server privacy guarantee is not robust against a single institution that controls all replicas; pooling the three masked queries allows interpolation of the user's immutable-mask vector, so the scheme is best understood as secure against independent server operators rather than against the database owner.","Beyond the paper: the same polynomial-masking template could be adapted to private nearest-neighbor search with arbitrary user-private predicates, not just fixed immutable coordinates, provided the predicate can be encoded as a masking vector.","Beyond the paper: the leakage comparison suggests a possible improvement direction in which server-side randomization of distances trades exact nearest-neighbor optimality for lower database leakage, although that is not explored in the paper."],"forward_implications":["If the schemes are correct, a rejected user can obtain the closest feasible counterfactual without ever revealing their input $x$, their immutable set $I$, or the retrieved index $\\theta^*$ to any one server.","The single-phase scheme strictly dominates on communication ($6d+3M$ versus $9(d+M)$) but leaks more about non-matching records, so the choice is a concrete privacy-efficiency tradeoff.","Both schemes extend to weighted actionability on mutable features without leaking the immutable set; the two-phase version needs a fourth server and a larger field, while the single-phase version keeps three servers with a larger field.","Because the distance metric is the squared $\\ell_2$ norm, the same answer construction works for any even $\\ell_k$ norm by raising the relevant terms to the power $k$.","The schemes automatically inform the user when no feasible counterfactual exists ($\\Theta=\\emptyset$), which is itself useful and costs no extra communication."],"supporting_citations":[{"why":"Defines the baseline private counterfactual retrieval problem whose PCR+ scheme the single-phase I-PCR modifies.","marker":"[20]"},{"why":"Defines nearest-instance counterfactual explanations, the retrieval objective that the squared-$\\ell_2$ distance metric formalizes.","marker":"[3]"},{"why":"Introduces private information retrieval and the replicated-server setting with information-theoretic privacy for the user's index.","marker":"[21]"},{"why":"Establishes the capacity of PIR and the non-colluding replicated-database model that fixes the three-server structure.","marker":"[22]"},{"why":"Establishes symmetric PIR, providing the shared-randomness and answer-masking techniques used to hide the database from the user beyond the required index.","marker":"[23]"}],"fun_headline_variants":["Private retrieval of counterfactuals with fixed features","Hide immutable features, still get counterfactual","Info-theoretic privacy for immutable counterfactual search","Counterfactual retrieval that keeps immutable traits secret","Minimum-change explanation without leaking private traits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The privacy guarantee rests on the three servers being genuinely non-colluding and non-communicating, with shared randomness that the user never sees; if one party controls all three servers and pools their query transcripts, the user's feature vector and immutable set can be recovered by interpolation.","fun_headline_variants_meta":{"raw":{"variants":["Private retrieval of counterfactuals with fixed features","Hide immutable features, still get counterfactual","Info-theoretic privacy for immutable counterfactual search","Counterfactual retrieval that keeps immutable traits secret","Minimum-change explanation without leaking private traits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00038,"raw_usage":{"total_tokens":2055,"prompt_tokens":1017,"completion_tokens":1038,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":633,"completion_tokens_details":{"reasoning_tokens":968}},"tokens_in":633,"tokens_out":1038,"duration_ms":8276,"temperature":1.0,"reasoning_tokens":968,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T19:40:31.074226+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take one execution of the two-phase scheme and place all three query tuples $Q_n = [h_1+\\alpha_n Z_1,\\, x\\circ h_1+\\alpha_n Z_2]$ in front of a single adversary who knows the distinct evaluation points $\\alpha_1,\\alpha_2,\\alpha_3$; interpolating the degree-2 polynomial in $\\alpha$ for each coordinate reveals the constant term $h_1$, the indicator vector of $I$, and $x\\circ h_1$, the user's values on the immutable coordinates. This direct calculation shows the per-server privacy claim (5) fails if the non-collusion assumption is dropped.","supporting_citations":[{"cited_title":"Private Counterfactual Retrieval","cited_arxiv_id":"2410.13812","evidence_quote":"Defines the baseline private counterfactual retrieval problem whose PCR+ scheme the single-phase I-PCR modifies."},{"cited_title":"Brughmans, P","cited_arxiv_id":null,"evidence_quote":"Defines nearest-instance counterfactual explanations, the retrieval objective that the squared-$\\ell_2$ distance metric formalizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces private information retrieval and the replicated-server setting with information-theoretic privacy for the user's index."},{"cited_title":"Sun and S","cited_arxiv_id":null,"evidence_quote":"Establishes the capacity of PIR and the non-colluding replicated-database model that fixes the three-server structure."}],"review_version":1}