{"id":"3907b0b9-8e6e-4644-bb72-c7b828936db9","arxiv_id":"2506.20981","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"A private waterfall-matching protocol using oblivious PRF with blind key rotation and differentially private dummy padding lets two parties compute aggregate conversion sums over multiple identifier types without revealing cross-identifier links or exact intersection sizes.","lead":"This paper describes a cryptographic protocol for advertisers and ad platforms to count how many matching users converted, using multiple identifiers like email and phone, without either side seeing the other's raw data. It matters because the advertising industry needs measurement after the loss of third-party cookies, and existing solutions either handle only one identifier or leak matching patterns.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"DP guarantee is void as written: Algorithm 1 appends dummies at the end, Πdp-wmf runs Πwmf without a shuffle, so P_A can identify every B-side dummy row from its position and subtract it to recover the exact intersection size.","rationale":"The reader's weakest assumption already identifies the missing shuffle and the identifiability of dummy rows; I agree with that part and make it concrete. I chose this as the single most load-bearing concern because the paper's headline privacy claim is that intersection sizes are differentially private, and the append-only construction lets P_A strip the noise from its transcript without any adversarial deviation. The DP accounting in Theorem 4 and Property 2 only considers the distribution of the noisy size variable, not whether that variable is observable from the full protocol transcript. Since the dummy positions are public by construction and the dummy universe is disjoint from real data, P_A can compute the exact true sizes. This is independent of the other serious issue (the Theorem 1 simulator does not correlate tag sets to match the output sizes), and it alone invalidates the central claim. The fix of randomly permuting each augmented set before Πwmf is plausible but not present in the manuscript, so the verdict of REJECT remains appropriate.","tokens_in":26830,"tokens_out":18407,"duration_ms":206284,"concrete_test":"Use the exact pipeline of §5.3 with n=100 per party, m=2, τ=25, and synthetic sets with known true intersection sizes t1=10 and t2=5. Implement the DDH-based Πwmf, leave the augmented sets in the append-only order specified by Algorithm 2, and have P_A compute J1_B and J2_B from its view, then delete all indices in the last mτ positions. If the remaining counts equal t1 and t2 in every run, the DP noise is stripped from P_A's view and the (ε,δ)-DP claim fails. As a control, repeat with each augmented column randomly permuted before Πwmf; then the recovered counts should differ from t1 and t2 by dummy-induced noise.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Πdp-wmf (§5.3), both parties insert dummies with Algorithm 1/2 and then \"jointly run Πwmf on the modified inputs.\" Algorithm 1 outputs \\tilde S = S + D' by appending D', Algorithm 2 preserves this append-only format, and no shuffle is specified between dummy insertion and Πwmf. In Πwmf (Figure 12), P_B sends its tags to P_A via FdurPRF in the order of its augmented ID column, so the last mτ received tag positions are exactly P_B's dummy rows (m = number of IDs, τ = the publicly computed dummy count). P_A can remove those positions from the matched sets J1_B and J2_B it computes. Because the dummy universe D is chosen disjoint from A and B, this leaves exactly |ID_A ∩ ID_B| for the first ID and the analogous true count for the second ID. Thus P_A's prescribed view reveals the exact true intersection sizes, not a DP-randomized version. The proof in §5.3 analyzes only the noisy size variable |\\tilde A∩\\tilde B|; it does not account for the transcript encoding the noise in known positions. SGX attestation does not help because this is an honest execution of the specified protocol.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces PrivacyGo, a two-party protocol for privacy-preserving waterfall matching over multiple identifier columns, together with a differentially private mechanism that pads both parties' inputs with dummy identifiers to obfuscate the reported intersection sizes. The technical core is a new ideal functionality called FdurPRF (distributed, blindly updatable, reversed PRF), with two concrete instantiations based on hashed Diffie-Hellman and garbled circuits, combined with an additively homomorphic encryption scheme (BFV/Paillier) for payload summation. The paper claims that the base protocol Πwmf securely realizes the waterfall-matching functionality Fwmf (Theorem 1), that the enhanced protocol Πdp-wmf is (ε,δ)-differentially private for the intersection sizes (Section 5.3), that parallel composition across identifier columns holds (Property 2), and that the implementation scales to two million records in about two minutes over a 100 Mbps link.","tokens_in":27071,"tokens_out":8303,"duration_ms":95448,"significance":"If the claims were sound, the paper would address a real industrial need: private multidimensional identity matching for advertising measurement while limiting membership-inference leakage. The FdurPRF abstraction and the blind key-update technique are useful conceptual contributions, and the experimental comparison against PJS and PS3I is informative. However, the central DP guarantee is void as specified because dummy rows occupy known positions, and Theorem 1's proof does not account for row-index leakage to P_A. These are load-bearing defects, not presentation issues. The paper also does not ship machine-checked proofs or released code, so the positive contributions are mainly the protocol idea and benchmarks rather than verified guarantees.","major_comments":[{"comment":"The DP-enhanced protocol does not provide differential privacy as specified. Algorithm 1 constructs the augmented set by appending D' to S, and Algorithm 2 preserves this append-only format; Step (5) of §5.3 then runs Πwmf on the augmented columns without any shuffle. In Figure 12 Stage 2, P_A receives Tag_b^B through FdurPRF in the input order of P_B's augmented ID column, so the last τ positions are exactly P_B's dummy rows. Since τ and the dummy universe D are public, P_A can discard those positions from J1_B and J2_B and recover the exact true intersection sizes. The DP analysis in §5.3 only randomizes the lumped size |~A ∩ ~B|; it does not account for the noise being readable in the transcript. SGX attestation ensures correct sampling, not confidentiality of dummy positions, so this is an honest execution of the specified protocol.","section":"§5.3, Algorithm 1, Figure 12"},{"comment":"The protocol does not realize Fwmf as defined because P_A learns matched row indices of P_B. In Stage 3, P_A computes J1_B = {j : Tag1_B[j] ∈ gTag1_A}, where Tag1_B is received from FdurPRF in P_B's row order; Stage 4 similarly yields J2_B mapped to original rows of P_B. Fwmf (Figure 1, Step 4) gives P_A only the sizes s1 and s2, not per-row match indicators. The simulator in the proof of Theorem 1 sends independent random tags to P_A (Steps 3–5) and does not correlate them with P_A's own tags; it therefore does not reproduce the joint distribution of J1_B and J2_B from the pair (s1,s2). This is not a mere proof gap: the real transcript contains per-row information that the functionality does not output. The protocol must either hide P_B's row indices (for example, by applying a secret random permutation to P_B's columns and payloads before the FdurPRF calls) or the functionality must be changed to expose those indices.","section":"§4.1, Theorem 1; Figure 1; Figure 12"},{"comment":"The parallel-composition claim for waterfall matching is not established. Property 2 asserts that if each ID column's mechanism is (ε,δ)-DP, then the mult-ID mechanism Mmult is (ε,δ)-DP for waterfall matching. However, a single-record change can affect both s1 and s2: a record that matches on ID1 is removed from the ID2 pool, so the two reported sizes are correlated functions of the same database. Algorithm 2 makes dummy sets for different columns disjoint, which prevents one dummy row from matching on multiple columns, but it does not bound the sensitivity of the pair (s1,s2) nor justify applying parallel composition to outputs that are not independent mechanisms on disjoint records. A concrete neighboring-database analysis for the two-size output is needed.","section":"§5.2, Property 2; §5.3"}],"minor_comments":[{"comment":"In Step (3), the definition of J2_B uses J2_B on the right-hand side; it should likely be the complement with respect to J1_B, not J2_B itself.","section":"Figure 1"},{"comment":"Algorithm 1 states that D is a set of τ' > τ entries, while the surrounding text and Eq. (1) specify |D| = 2τ; these should be made consistent.","section":"Algorithm 1"},{"comment":"The text uses the word 'axisymmetrially' in Lemma 5 and Theorem 4; the appendix later uses 'asymmetrically.' Please use a single consistent term, preferably 'axisymmetrically' with a definition.","section":"§5.1"},{"comment":"Theorem 1 refers to the protocol in Figure 4, but the full protocol is presented in Figure 12; the relationship between these figures should be clarified.","section":"Theorem 1 and Figure 12"},{"comment":"The caption reports 0.00% attack success after DP, but the text does not state the DP parameters (ε, δ, k, τ) used in that experiment; these should be given for reproducibility.","section":"Figure 7(a)"}],"recommendation":"reject","confidential_remarks":"The FdurPRF abstraction and the blind key-update construction are interesting and could be the basis of a useful follow-up. However, the current manuscript's central claims fail: the DP mechanism leaks dummy positions to P_A, and Theorem 1's ideal-world simulation does not cover the row-index leakage inherent in the real protocol. These are not local fixable errors in the write-up; they require a redesign of the protocol (e.g., secret permutation/oblivious shuffling) and new security and DP proofs. I therefore recommend rejection of the current version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. The construction idea is genuinely new and the engineering is serious; but the two load-bearing privacy claims in the paper do not hold as written. The reader's take is right, and the stress-test attack on the DP layer lands cleanly.\n\nWhat is worth keeping. The paper targets the real problem: multi-identifier (waterfall) matching where each record matches on exactly one identifier, without cross-ID linkage. The FdurPRF design — distributed-key reversed OPRF with a blind, Pythia-style key rotation — is a legitimate extension of the reversed-OPRF recipe, and the DDH and garbled-circuit instantiations are standard and plausible. The dual-sided dummy mechanism with the hockey-stick/FFT privacy profiling (Lemma 5, Theorem 4, Algorithm 3) is a solid piece of analysis for the single-ID, single-output case. The benchmarks against PJS and PS3I are substantial, and the implementation details (BFV packing, truncated DDH tags) show real engineering judgment.\n\nWhere it falls apart. First, Theorem 1 as stated is not true: P_A receives the other party's tags from FdurPRF in row order, so it learns the exact matched index sets J^1_B and J^2_B of P_B, while the Fwmf functionality gives P_A only sizes. No simulator given only s1 and s2 can reproduce those data-dependent index sets; the proof sketch never engages with this, and the formalized proof promised in the appendix is not there. Second, the DP layer is void as written: Algorithm 1 appends dummies at the tail, Πdp-wmf runs Πwmf with no shuffle, and FdurPRF returns tags in input order, so P_A knows exactly which of B's rows are dummies, counts the dummy-dummy matches directly from the transcript, subtracts them, and recovers the true intersection sizes exactly. The known-position issue is not fixed by SGX, since this is an honest execution. Property 2's parallel-composition claim is asserted rather than proven, and the waterfall row deletion couples s1 and s2, so the sensitivity analysis is missing. There is also a mismatch between Definition 4, which demands DP for the whole view, and what is actually analyzed (noise on the sizes), given the exact sum is revealed.\n\nBottom line: this deserves a serious referee — the problem is important and the core construction is worth fixing, not burying. But in current form the central claims are not supported. Recommendation: send to review, with the expectation of heavy revision; ask the authors to either re-specify the functionality so the index leakage is captured, and to prove the DP claim against the transcript rather than just the size.","headline":"A genuinely novel, well-engineered construction for multi-ID private waterfall matching whose two central privacy claims, Theorem 1 and the DP guarantee, are not supported as written.","tokens_in":27649,"tokens_out":19607,"would_cite":true,"duration_ms":242715,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A60"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims a private waterfall-matching protocol for multiple identifiers that hides cross-identifier linkage and whose revealed sizes are (ε,δ)-differentially private, with experiments on two million records in about two minutes.","keywords":["privacy-preserving ad measurement","waterfall matching","private set intersection","oblivious pseudorandom function","multidimensional intersection","differential privacy","homomorphic encryption","membership inference"],"falsifier":"Take two databases that differ in exactly one user, and change that user's identifiers so that the user previously matched on column 1 and now matches on column 2; observe the pair (s1, s2) the publisher receives before and after. If either coordinate moves by more than one, or both move simultaneously, the per-coordinate sensitivity bound used in the parallel-composition DP proof is violated and the claimed (ε,δ) guarantee with the stated dummy count τ does not follow.","tokens_in":2042,"feed_emoji":"🔒","tokens_out":3208,"duration_ms":131325,"temperature":0.7,"pith_summary":"The paper claims that waterfall matching—the industry-standard way of joining two parties' user databases across multiple identifier columns in priority order—can be run privately at scale: the publisher learns only the per-column match counts, the advertiser learns only the sum of payloads over matched rows, and neither learns which identifier or which row matched. To get there, the paper introduces a new cryptographic primitive it calls a distributed, blindly updatable, reversed PRF (durPRF), which lets a party delete already-matched rows and re-key the remaining ones without the other party seeing the linkage. On top of that it builds a two-sided differential privacy mechanism that pads both inputs with dummy identifiers, making the revealed intersection sizes (ε,δ)-differentially private and reducing membership-inference attack success to roughly zero in the paper's experiments. If correct, the result is the first private waterfall matching protocol without cross-identifier leakage, with a reported practical cost of about two minutes for two million records across three identifier columns on a 100 Mbps connection.","feed_headline":"2M-row ad matching stays private in about 2 minutes","feed_subtitle":"Publisher sees only counts, advertiser only sums; DP noise blocks membership inference.","key_machinery":"The mechanism that carries the argument is the distributed, blindly updatable, reversed PRF (FdurPRF), a two-party PRF whose key is shared between the parties, in which the receiver obtains evaluations of the sender's inputs (reversed), and the update command lets one party obtain evaluations under a fresh shared key without the other party learning which inputs were re-keyed. This single primitive supplies the two operations the waterfall logic needs: private row deletion (matched rows are simply dropped from the received PRF tags before the next column is matched) and blindness against cross-ID linkage (key rotation makes tags from different columns unlinkable). The paper gives two instantiations—one from hashed Diffie-Hellman, defined as $F_k(x)=H(x)^k$ with key $k=k_A\\cdot k_B$, and one from Yao's garbled circuits using double AES encryption as the updated PRF. On the DP side, the load-bearing identity is the dummy-intersection distribution $\\Pr(z=z')=\\binom{\\tau}{z'}^2/\\binom{2\\tau}{\\tau}$, which converts the random padding into an exactly computable privacy-loss distribution; Algorithm 2 extends the padding to multiple columns with disjoint dummy sets so that the paper can invoke parallel composition, and Algorithm 3 uses FFT convolution for tight accounting over multiple executions.","core_discovery":"The central claim is Theorem 1: if the additively homomorphic encryption scheme is semantically secure, the protocol in Figure 4 securely realizes the waterfall matching functionality of Figure 1 against semi-honest adversaries in the FdurPRF-hybrid model. The protocol works by having both parties evaluate PRFs on each other's identifier columns under secret-shared keys, match on the first column, delete the matched rows, then blindly rotate the PRF key before matching on the second column, so that a record matched on one column cannot be re-identified under the other column. The paper further claims that padding both inputs with dummy identifiers from a common dummy set makes the two revealed sizes (ε,δ)-differentially private (Algorithm 2 and Section 5.3), with a tighter privacy profile across multiple executions obtained by FFT-based composition. The same framework also handles multiple payload columns, secret-shared matched payloads for arbitrary downstream functions, and payloads supplied by both parties.","pith_inferences":["Because the dummy set is common knowledge and hardcoded in attestation, the DP guarantee protects the counts, not the existence of the dummies: a party that knows the dummy set can subtract the expected dummy overlap, so the real privacy statement is about how much the noisy count moves between neighboring databases, not about hiding the padding itself.","The waterfall row deletion makes the two revealed counts coupled: a single user whose best matching identifier changes from column 1 to column 2 moves s1 down and s2 up together, which suggests the DP analysis for the pair (s1, s2) may need a combined sensitivity argument rather than independent per-column composition.","The blind key-rotation primitive is a standalone tool: the same 'delete matched rows, re-key the rest' pattern could apply to private contact discovery, audience overlap, or frequency capping, wherever one party must drop matched entries without the other learning which entries were dropped."],"forward_implications":["Advertisers and publishers can compute conversion sums over waterfall-matched users without learning which identifier matched or which rows matched, closing the type-E and type-X leakage channels that existing multi-key private matching leaves open.","The DP padding grows only linearly with the number of identifier columns (parallel composition) rather than exponentially as it would under sequential composition, and the FFT-based accountant keeps the dummy overhead small across repeated matches.","The same FdurPRF construction supports multiple payload columns, secret-shared matched payloads for arbitrary functions beyond summation, and payloads contributed by both sides with only small protocol changes.","Reported benchmarks put the protocol at roughly two minutes for two million records and three identifier columns over a 100 Mbps link, about 20× faster than the Paillier-based private intersection-sum baseline and roughly two orders of magnitude faster than the multi-key private matching baseline with 85% less communication.","Membership inference attacks that reach about 6.6% success on size-revealing multi-ID matching drop to about 0% when the DP-enhanced sizes are used, per the paper's experiments."],"supporting_citations":[{"why":"Ion et al., private intersection-sum-with-cardinality — supplies the reversed-OPRF-via-homomorphic-encryption pattern and the Paillier-based baseline the paper benchmarks against.","marker":"[2]"},{"why":"Buddhavarapu et al., multi-key private matching for compute (Private-ID) — the existing multi-ID matching protocol whose subset-intersection and membership leakage motivates the new design.","marker":"[10]"},{"why":"Jarecki and Liu, fast secure computation of set intersection — the DH-based evaluation step of the durPRF construction.","marker":"[40]"},{"why":"Everspaugh et al., Pythia PRF service — the blind key-rotation step of the durPRF construction.","marker":"[41]"},{"why":"Yao, how to generate and exchange secrets — the garbled-circuit instantiation of durPRF.","marker":"[11]"},{"why":"Koskela et al., tight approximate DP using FFT — the composition accountant for multiple waterfall executions (Algorithm 3).","marker":"[12]"},{"why":"Guo et al., set-bias membership inference via revealed intersection sizes — one of the two attacks the DP mechanism is validated against.","marker":"[8]"},{"why":"Jiang et al., AnonPSI — the second membership-inference attack used in the experiments.","marker":"[9]"}],"fun_headline_variants":["Private ad matching across many IDs in ~2 minutes","2M-row private ad matching: no cross-ID links, DP noise","Blind key rotation powers private multi-ID ad measurement","Differential privacy shields intersection sizes in ad matching"],"cache_read_input_tokens":29696,"weakest_assumption_plain":"The (ε,δ)-differential privacy claim depends on a party not being able to recognize the other's dummy identifiers and on a one-user change to either database moving each reported column count by at most one; the paper's parallel-composition argument for the waterfall deletion logic does not spell out a shuffle to hide dummy positions, and a single user editing both identifier columns can shift both reported counts at once.","fun_headline_variants_meta":{"raw":{"variants":["Private ad matching across many IDs in ~2 minutes","2M-row private ad matching: no cross-ID links, DP noise","Blind key rotation powers private multi-ID ad measurement","Differential privacy shields intersection sizes in ad matching"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000272,"raw_usage":{"total_tokens":1598,"prompt_tokens":874,"completion_tokens":724,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":490,"completion_tokens_details":{"reasoning_tokens":658}},"tokens_in":490,"tokens_out":724,"duration_ms":8727,"temperature":1.0,"reasoning_tokens":658,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T22:40:19.223982+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take two databases that differ in exactly one user, and change that user's identifiers so that the user previously matched on column 1 and now matches on column 2; observe the pair (s1, s2) the publisher receives before and after. If either coordinate moves by more than one, or both move simultaneously, the per-coordinate sensitivity bound used in the parallel-composition DP proof is violated and the claimed (ε,δ) guarantee with the stated dummy count τ does not follow.","supporting_citations":[{"cited_title":"On deploying secure computing: Private intersection-sum- with-cardinality,","cited_arxiv_id":null,"evidence_quote":"Ion et al., private intersection-sum-with-cardinality — supplies the reversed-OPRF-via-homomorphic-encryption pattern and the Paillier-based baseline the paper benchmarks against."},{"cited_title":"Multi-key private matching for compute,","cited_arxiv_id":null,"evidence_quote":"Buddhavarapu et al., multi-key private matching for compute (Private-ID) — the existing multi-ID matching protocol whose subset-intersection and membership leakage motivates the new design."},{"cited_title":"Fast secure computation of set intersection,","cited_arxiv_id":null,"evidence_quote":"Jarecki and Liu, fast secure computation of set intersection — the DH-based evaluation step of the durPRF construction."},{"cited_title":"The pythia PRF service,","cited_arxiv_id":null,"evidence_quote":"Everspaugh et al., Pythia PRF service — the blind key-rotation step of the durPRF construction."},{"cited_title":"How to generate and exchange secrets,","cited_arxiv_id":null,"evidence_quote":"Yao, how to generate and exchange secrets — the garbled-circuit instantiation of durPRF."},{"cited_title":"Birds of a feather flock together: How set bias helps to deanonymize you via revealed intersection sizes,","cited_arxiv_id":null,"evidence_quote":"Guo et al., set-bias membership inference via revealed intersection sizes — one of the two attacks the DP mechanism is validated against."},{"cited_title":"Anonpsi: An anonymity assessment framework for psi,","cited_arxiv_id":null,"evidence_quote":"Jiang et al., AnonPSI — the second membership-inference attack used in the experiments."}],"review_version":1}