Pith. sign in

REVIEW 3 major objections 5 minor 50 references

PrivacyGo: Privacy-Preserving Ad Measurement with Multidimensional Intersection

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2506.20981 v1 pith:6ANPU747 submitted 2025-06-26 cs.CR

Jian Du , Haohao Qian , Shikun Zhang , Wen-jie Lu , Donghang Lu , Yongchuan Niu , Bo Jiang , Yongjun Zhao
show 1 more author
Qiang Yan
This is my paper · ORCID
classification cs.CR MSC 94A60
keywords privacy-preservingadmeasurementwaterfallmatchingprivatesetintersectionobliviouspseudorandomfunctionmultidimensionaldifferentialprivacyhomomorphicencryptionmembershipinference
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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.

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 (3)
  1. [§5.3, Algorithm 1, Figure 12] 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.
  2. [§4.1, Theorem 1; Figure 1; Figure 12] 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.
  3. [§5.2, Property 2; §5.3] 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.
minor comments (5)
  1. [Figure 1] 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.
  2. [Algorithm 1] 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.
  3. [§5.1] 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.
  4. [Theorem 1 and Figure 12] 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.
  5. [Figure 7(a)] 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: protocol security and DP guarantees reduce to DDH/ROM/GC/AHE assumptions and to the dummy-sampling distribution, not to the paper's own conclusions.

full rationale

The claimed derivation chain is self-contained. FdurPRF is defined as a functionality and instantiated twice: the HashDH construction's security reduces to DDH plus random oracle (Theorem 2, with simulators in Figures 9-10), and the GC construction reduces to FGC (Theorem 3). Theorem 1 gives a simulator for Pi_wmf in the FdurPRF-hybrid model, so it is a standard ideal/real simulation rather than an assumption of the conclusion. The DP layer is a dummy-row mechanism: Lemma 5 explicitly derives the distribution of |Atilde cap Btilde| from independent subset sampling from a common dummy universe, and the privacy profile in Theorem 4 is computed from that distribution via the privacy-loss random variable; the FFT multiple-execution bound adapts [12] and is again computed, not fitted. The only author self-citation is [9] (AnonPSI), used as an attack baseline in Section 2.2 and Figure 7(a); that empirical motivation is not load-bearing for the protocol's security or for the DP bound. No parameter is fitted to a target output and then renamed a prediction; the reported timing and dummy sizes are computed from the stated formulas and benchmarks. The SGX/dummy-validation discussion and the unproven Property 2 are correctness and rigor gaps, not circular reductions.

Assumptions & free parameters 3 free parameters · 7 assumptions · 1 invented entities

The protocol's privacy rests on standard cryptographic assumptions (DDH, random oracle, semantic security of AHE), a semi-honest corruption model, and an additional SGX attestation assumption that is not modeled. The DP noise depends on a public budget parameter τ, and the multi-ID DP proof has an unproven parallel-composition step. No invented physical entities are needed; the only new abstraction is the FdurPRF functionality.

free parameters (3)
  • dummy count τ = 114 to 503 depending on n, k, ε (Table 1)
    Number of dummy rows added per party to achieve (ε,δ)-DP; computed via Algorithm 3. It is not fitted to data, but it is a design parameter on which the privacy and efficiency trade-off depends.
  • truncation width γ for DDH tags = 96 bits
    Only the least significant 96 bits of updated group elements are transmitted to save communication; a hand-chosen security and bandwidth trade-off.
  • BFV HE parameters = 118-bit ciphertext modulus, 64-bit plaintext modulus, degree 8192
    Implementation choices in Section 6 for the AHE instantiation; not part of the security proof but affect whether benchmarks are reproducible.
assumptions (7)
  • domain assumption DDH assumption in prime-order group G
    Used in Theorem 2 and Appendix A.1.4 to prove the HashDH FdurPRF construction secure.
  • domain assumption Random oracle model for hash functions H and H'
    Theorem 2 models H as a random oracle; Theorem 3 models H'. The implementation uses SHA-256 try-and-increment and BLAKE2b.
  • standard math Semantic security of the AHE scheme and statistical closeness of Refresh
    Required by Theorem 1 for payload encryption and for re-randomized aggregation.
  • domain assumption Semi-honest adversary model
    Section 3.2 explicitly targets honest-but-curious adversaries; malicious deviations such as skipping dummy sampling are handled only by an unmodeled SGX assumption.
  • ad hoc to paper SGX code attestation provides correct execution of dummy sampling
    Section 2.2 introduces secure hardware to prevent a party from skipping dummy sampling; this trust anchor is not included in the formal security or DP theorems.
  • ad hoc to paper Parallel DP composition applies to waterfall matching outputs s1, s2
    Property 2 asserts (ε,δ)-DP for multi-ID with the same budget as single-ID, relying on disjoint dummy sets; the interaction of row deletion with neighboring datasets is not analyzed.
  • ad hoc to paper Common dummy set D is disjoint from both input sets and indistinguishable from real rows
    The DP mechanism assumes dummies can be sampled from a common public set that does not collide with real identifiers; indistinguishability also assumes rows are shuffled, which is not specified.
invented entities (1)
  • Distributed, Blindly Updatable, Reversed PRF (FdurPRF) functionality
    purpose: Ideal functionality enabling reversed OPRF evaluation with blind key rotation to prevent cross-identifier linkage in waterfall matching.
    It is a new ideal abstraction introduced by the paper; its DDH realization relies on Pythia-style key rotation [41] and the random oracle model, so it has no independent empirical handle.

how reviews work

0 comments
Cite this review

Pith. "Pith review of PrivacyGo: Privacy-Preserving Ad Measurement with Multidimensional Intersection." pith.science (2026). https://pith.science/paper/6ANPU747

@misc{pith2026250620981,
  author       = {Pith},
  title        = {Pith review of: PrivacyGo: Privacy-Preserving Ad Measurement with Multidimensional Intersection},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6ANPU747}},
  note         = {Machine review of arXiv:2506.20981}
}
read the original abstract

This paper tackles the challenging and practical problem of multi-identifier private user profile matching for privacy-preserving ad measurement, a cornerstone of modern advertising analytics. We introduce a comprehensive cryptographic framework leveraging reversed Oblivious Pseudorandom Functions (OPRF) and novel blind key rotation techniques to support secure matching across multiple identifiers. Our design prevents cross-identifier linkages and includes a differentially private mechanism to obfuscate intersection sizes, mitigating risks such as membership inference attacks. We present a concrete construction of our protocol that achieves both strong privacy guarantees and high efficiency. It scales to large datasets, offering a practical and scalable solution for privacy-centric applications like secure ad conversion tracking. By combining rigorous cryptographic principles with differential privacy, our work addresses a critical need in the advertising industry, setting a new standard for privacy-preserving ad measurement frameworks.

Figures

Figures reproduced from arXiv: 2506.20981 by the authors.

Figure 1
Figure 1. The waterfall matching and sum functionality. Note [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Example of the type-E cross-ID leakage and the [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. The functionality of 𝑑𝑢𝑟𝑃𝑅𝐹 . with the advertiser. This compromises sensitive business data, as the advertiser may not wish to disclose granular user conversion behavior. Such leakages not only undermine the advertiser’s com￾petitive edge but also raise potential compliance concerns under privacy regulations such as the GDPR, which mandates strict limits on personal data processing and requires minimizing data expo￾… view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: Our private waterfall matching protocol under [PITH_FULL_IMAGE:figures/full_fig_p006_4.png]
Figure 5
Figure 5. Figure 5: The 𝑑𝑢𝑟𝑃𝑅𝐹 protocol from HashDH. Both parties agree upon a group G of a prime order 𝑞 that the DH assump￾tion holds, and a hash function H : {0, 1} ∗ → G that maps bit strings to elements of G. The corresponding PRF is defined as 𝐹𝑘 (𝑥) = H(𝑥) 𝑘 . which is the PRF eval…
Figure 7
Figure 7. Figure 7: (a) The robustness of the DP-enhanced protocol [PITH_FULL_IMAGE:figures/full_fig_p011_7.png]
Figure 8
Figure 8. Figure 8: Comparison with the PJS [2] protocol and the PS 3 I [17] protocol. For our DDH-based protocol, we configure the DP profile with the parameters (𝑘 = 6,𝑚 = 3, 𝜖 = 2, 𝛿 = 1/(10𝑛)). The experiments were conducted under the LAN network setting, utilizing one single thread p…
Figure 9
Figure 9. Figure 9: The simulator for P𝐴 in the Π DH durPRF protocol . Then, according to the definition of DP, the failure probability 𝛿 can be expressed as: 𝛿 = ∑︁ 𝑜 ∈𝑂 max Pr(M (𝐴) = 𝑜) − 𝑒 𝜀 Pr(M (𝐴 ′ ) = 𝑜), 0  = ∑︁ 𝑜 ∈𝑂+ [PITH_FULL_IMAGE:figures/full_fig_p014_9.png]
Figure 10
Figure 10. Figure 10: The simulator for P𝐵 in the Π DH durPRF protocol. and 𝛿 (𝜸𝐴′𝐴 > 𝜖) = ∑︁𝜏 𝑜=𝜸 −1 𝐴′𝐴 (𝜖 ) (1 − 𝑒 𝜖−𝜸𝐴′𝐴 (𝑜 ) ) Pr(M (𝐴 ′ ) = 𝑜) = 𝜸 −1 𝐴𝐴′ ∑︁ (𝜖 ) 𝑜=1 (1 − 𝑒 𝜖−𝜸𝐴𝐴′ (𝑜 ) ) Pr(M (𝐴) = 𝑜). Therefore, 𝛿 (𝜸𝐴𝐴′ > 𝜖) = 𝛿 (𝜸𝐴′𝐴 > 𝜖). □ A.1.3 Proof of Property 3. Proof. 𝑊 is l…
Figure 11
Figure 11. Figure 11: An illustration of the DDH-based Waterfall Matching. [PITH_FULL_IMAGE:figures/full_fig_p016_11.png]
Figure 12
Figure 12. Figure 12: (Full version) Our private waterfall matching protocol under [PITH_FULL_IMAGE:figures/full_fig_p017_12.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

50 extracted references · 47 canonical work pages

  1. [1]

    Advanced Matching,

    “Advanced Matching, ” https://developers.facebook.com/docs/meta-pixel/adva nced/advanced-matching, 2025. 3 https://github.com/google/private-join-and-compute 4 https://github.com/facebookresearch/Private-ID PrivacyGo: Privacy-Preserving Ad Measurement with Multidimensional Intersection 103 104 105 #Samples n 100 101 102 Time (s) 19X 21X 20X Matching for S...

    work page 2025

  2. [2]

    On deploying secure computing: Private intersection-sum- with-cardinality,

    M. Ion, B. Kreuter, A. E. Nergiz, S. Patel, S. Saxena, K. Seth, M. Raykova, D. Shana- han, and M. Yung, “On deploying secure computing: Private intersection-sum- with-cardinality, ” in2020 IEEE European Symposium on Security and Privacy (EuroS&P). IEEE, 2020, pp. 370–389

    work page 2020

  3. [3]

    Private matching for compute

    P. Buddhavarapu, A. Knox, P. Mohassel, S. Sengupta, E. Taubeneck, and V. Vlaskin, “Private matching for compute. ”IACR Cryptol. ePrint Arch., vol. 2020, p. 599, 2020

    work page 2020

  4. [4]

    On deploying secure computing: Private intersection-sum-with-cardinality,

    M. Ion, B. Kreuter, A. E. Nergiz, S. Patel, S. Saxena, K. Seth, M. Raykova, D. Shanahan, and M. Yung, “On deploying secure computing: Private intersection-sum-with-cardinality, ” inIEEE European Symposium on Security and Privacy, EuroS&P, 2020. [Online]. Available: https://doi.org/10.1109/EuroSP 48549.2020.00031

    arXiv 2020

  5. [5]

    Efficient circuit-based PSI with linear communication,

    B. Pinkas, T. Schneider, O. Tkachenko, and A. Yanai, “Efficient circuit-based PSI with linear communication, ” inAdvances in Cryptology - EUROCRYPT 2019 , Y. Ishai and V. Rijmen, Eds., 2019

    work page 2019

  6. [6]

    Circuit-psi with linear complexity via relaxed batch OPPRF,

    N. Chandran, D. Gupta, and A. Shah, “Circuit-psi with linear complexity via relaxed batch OPPRF, ”Proc. Priv. Enhancing Technol., vol. 2022, no. 1, pp. 353–372,

    work page 2022

  7. [7]

    Private set operations from oblivious switching

    G. Garimella, P. Mohassel, M. Rosulek, S. Sadeghian, and J. Singh, “Private set operations from oblivious switching. ” inPublic Key Cryptography (2) , 2021, pp. 591–617

    work page 2021

  8. [8]

    Birds of a feather flock together: How set bias helps to deanonymize you via revealed intersection sizes,

    X. Guo, Y. Han, Z. Liu, D. Wang, Y. Jia, and J. Li, “Birds of a feather flock together: How set bias helps to deanonymize you via revealed intersection sizes, ” in 31st USENIX Security Symposium (USENIX Security 22) . USENIX Association, Aug. 2022. [Online]. Available: https://www.usenix.org/conference/usenixsecuri ty22/presentation/guo

    work page 2022

Show all 50 references
  1. [9]

    Anonpsi: An anonymity assessment framework for psi,

    B. Jiang, J. Du, and Q. Yan, “Anonpsi: An anonymity assessment framework for psi, ” inThe Network and Distributed System Security Symposium (NDSS) 2024 , Boston, MA, Feb. 2024

    2024

  2. [10]

    Multi-key private matching for compute,

    P. Buddhavarapu, B. M. Case, L. Gore, A. Knox, P. Mohassel, S. Sengupta, E. Taube- neck, and M. Xue, “Multi-key private matching for compute, ”Cryptology ePrint Archive, 2021

    2021

  3. [11]

    How to generate and exchange secrets,

    A. C.-C. Yao, “How to generate and exchange secrets, ” in27th annual symposium on foundations of computer science (Sfcs 1986) . IEEE, 1986, pp. 162–167

    1986

  4. [12]

    Tight approximate differential privacy for discrete-valued mechanisms using fft,

    A. Koskela, J. Jälkö, L. Prediger, and A. Honkela, “Tight approximate differential privacy for discrete-valued mechanisms using fft, ”arXiv preprint arXiv:2006.07134, 2020

    2006 arXiv

  5. [13]

    Fast private set intersection from homomorphic encryption,

    H. Chen, K. Laine, and P. Rindal, “Fast private set intersection from homomorphic encryption, ” inProceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017, pp. 1243–1255

    2017

  6. [14]

    Faster private set intersection based on OT extension,

    B. Pinkas, T. Schneider, and M. Zohner, “Faster private set intersection based on OT extension, ” in23rd USENIX Security Symposium (USENIX Security 14) , 2014, pp. 797–812

    2014

  7. [15]

    Efficient batched oblivi- ous prf with applications to private set intersection,

    V. Kolesnikov, R. Kumaresan, M. Rosulek, and N. Trieu, “Efficient batched oblivi- ous prf with applications to private set intersection, ” inProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security , 2016, pp. 818–829

    2016

  8. [16]

    Efficient private matching and set inter- section,

    M. J. Freedman, K. Nissim, and B. Pinkas, “Efficient private matching and set inter- section, ” inInternational conference on the theory and applications of cryptographic techniques. Springer, 2004, pp. 1–19

    2004

  9. [17]

    Private matching for compute,

    P. Buddhavarapu, A. Knox, P. Mohassel, S. Sengupta, E. Taubeneck, and V. Vlaskin, “Private matching for compute, ”Cryptology ePrint Archive, 2020

    2020

  10. [18]

    Linear complexity private set intersection for secure two-party protocols,

    F. Karakoç and A. Küpçü, “Linear complexity private set intersection for secure two-party protocols, ” inInternational Conference on Cryptology and Network Security. Springer, 2020, pp. 409–429

    2020

  11. [19]

    Multiparty cardinality testing for threshold private intersection,

    P. Branco, N. Döttling, and S. Pu, “Multiparty cardinality testing for threshold private intersection, ” in PKC 2021 , ser. Lecture Notes in Computer Science, J. A. Garay, Ed., vol. 12711. Springer, 2021, pp. 32–60. [Online]. Available: https://doi.org/10.1007/978-3-030-75248-4_2

    2021 doi

  12. [20]

    The communication complexity of threshold private set intersection,

    S. Ghosh and M. Simkin, “The communication complexity of threshold private set intersection, ” in CRYPTO 2019 , ser. Lecture Notes in Computer Science, vol. 11693. Springer, 2019, pp. 3–29. [Online]. Available: https://doi.org/10.1007/978-3-030-26951-7_1

    2019 doi

  13. [21]

    Efficient threshold private set intersection,

    E. Zhang, J. Chang, and Y. Li, “Efficient threshold private set intersection, ” IEEE Access , vol. 9, pp. 6560–6570, 2021. [Online]. Available: https: //doi.org/10.1109/ACCESS.2020.3048743

    2021

  14. [22]

    Combining Private Set-Intersection with Secure Two-Party Computation,

    M. Ciampi and C. Orlandi, “Combining Private Set-Intersection with Secure Two-Party Computation, ” inSCN, 2018, pp. 464–482

    2018

  15. [23]

    Fast and Private Computation of Cardinality of Set Intersection and Union,

    E. D. Cristofaro, P. Gasti, and G. Tsudik, “Fast and Private Computation of Cardinality of Set Intersection and Union, ” inCANS, 2012, pp. 218–231

    2012

  16. [24]

    Secure and Efficient Private Set Intersection Cardi- nality Using Bloom Filter,

    S. K. Debnath and R. Dutta, “Secure and Efficient Private Set Intersection Cardi- nality Using Bloom Filter, ” inISC, 2015, pp. 209–226

    2015

  17. [25]

    Private Set Intersection: Are Garbled Circuits Better than Custom Protocols?

    Y. Huang, D. Evans, and J. Katz, “Private Set Intersection: Are Garbled Circuits Better than Custom Protocols?” in NDSS, 2012

    2012

  18. [26]

    Differentially private two-party set operations,

    B. Kacsmar, B. Khurram, N. Lukas, A. Norton, M. Shafieinejad, Z. Shang, Y. Baseri, M. Sepehri, S. Oya, and F. Kerschbaum, “Differentially private two-party set operations, ” in2020 IEEE European Symposium on Security and Privacy (EuroS&P) . IEEE, 2020, pp. 390–404

    2020

  19. [27]

    Number-theoretic Constructions of Efficient Pseudo- random Functions,

    M. Naor and O. Reingold, “Number-theoretic Constructions of Efficient Pseudo- random Functions, ” inFOCS, 1997, pp. 458–467

    1997

  20. [28]

    A verifiable random function with short proofs and keys,

    Y. Dodis and A. Yampolskiy, “A verifiable random function with short proofs and keys, ” inPKC, 2005, pp. 416–431

    2005

  21. [29]

    Efficient Batched Oblivi- ous PRF with Applications to Private Set Intersection,

    V. Kolesnikov, R. Kumaresan, M. Rosulek, and N. Trieu, “Efficient Batched Oblivi- ous PRF with Applications to Private Set Intersection, ” inCCS, 2016, pp. 818–829

    2016

  22. [30]

    Sok: Oblivious pseudorandom func- tions,

    S. Casacuberta, J. Hesse, and A. Lehmann, “Sok: Oblivious pseudorandom func- tions, ” inEuroS&P, 2022, pp. 625–646

    2022

  23. [31]

    Katz and Y

    J. Katz and Y. Lindell,Introduction to Modern Cryptography, Second Edition. CRC Press, 2014

    2014

  24. [32]

    Goldreich, The Foundations of Cryptography - Volume 2: Basic Applications

    O. Goldreich, The Foundations of Cryptography - Volume 2: Basic Applications . Cambridge University Press, 2004. [Online]. Available: http://www.wisdom.wei zmann.ac.il/%7Eoded/foc-vol2.html

    2004

  25. [33]

    Security and Composition of Multiparty Cryptographic Protocols,

    R. Canetti, “Security and Composition of Multiparty Cryptographic Protocols, ”J. Cryptol., vol. 13, no. 1, pp. 143–202, 2000

    2000

  26. [34]

    The limits of two-party differential privacy,

    A. McGregor, I. Mironov, T. Pitassi, O. Reingold, K. Talwar, and S. Vadhan, “The limits of two-party differential privacy, ” in2010 IEEE 51st Annual Symposium on Foundations of Computer Science . IEEE, 2010, pp. 81–90

    2010

  27. [35]

    Crypt- flow: Secure tensorflow inference,

    N. Kumar, M. Rathee, N. Chandran, D. Gupta, A. Rastogi, and R. Sharma, “Crypt- flow: Secure tensorflow inference, ” inSymposium on Security and Privacy , 2020, pp. 336–353

    2020

  28. [36]

    Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP,

    Z. Brakerski, “Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP, ” inCRYPTO, 2012, pp. 868–886

    2012

  29. [37]

    Somewhat Practical Fully Homomorphic Encryption,

    J. Fan and F. Vercauteren, “Somewhat Practical Fully Homomorphic Encryption, ” IACR Cryptol. ePrint Arch., 2012

    2012

  30. [38]

    Public-Key Cryptosystems Based on Composite Degree Residuosity Classes,

    P. Paillier, “Public-Key Cryptosystems Based on Composite Degree Residuosity Classes, ” inEUROCRYPT, 1999, pp. 223–238

    1999

  31. [39]

    Efficient homomorphic conversion between (ring) LWE ciphertexts,

    H. Chen, W. Dai, M. Kim, and Y. Song, “Efficient homomorphic conversion between (ring) LWE ciphertexts, ” inACNS, 2021, pp. 460–479

    2021

  32. [40]

    Fast secure computation of set intersection,

    S. Jarecki and X. Liu, “Fast secure computation of set intersection, ” inSCN, 2010, pp. 418–435

    2010

  33. [41]

    The pythia PRF service,

    A. Everspaugh, R. Chatterjee, S. Scott, A. Juels, and T. Ristenpart, “The pythia PRF service, ” inUSENIX Security, 2015, pp. 547–562

    2015

  34. [42]

    Concentrated differential privacy,

    C. Dwork and G. N. Rothblum, “Concentrated differential privacy, ”arXiv preprint arXiv:1603.01887, 2016

    2016 arXiv

  35. [43]

    Identity-Based Encryption from the Weil Pairing,

    D. Boneh and M. K. Franklin, “Identity-Based Encryption from the Weil Pairing, ” in CRYPTO, 2001, pp. 213–229

    2001

  36. [44]

    Optimal Randomness Extraction from a Diffie-Hellman Element,

    C. Chevalier, P. Fouque, D. Pointcheval, and S. Zimmer, “Optimal Randomness Extraction from a Diffie-Hellman Element, ” inEUROCRYPT, 2009, pp. 572–589

    2009

  37. [45]

    EMP-toolkit: Efficient MultiParty com- putation toolkit,

    X. Wang, A. J. Malozemoff, and J. Katz, “EMP-toolkit: Efficient MultiParty com- putation toolkit, ” https://github.com/emp-toolkit, 2016

    2016

  38. [46]

    Microsoft SEAL (release 4.1),

    “Microsoft SEAL (release 4.1), ” https://github.com/Microsoft/SEAL, Jan. 2023, microsoft Research, Redmond, WA

    2023

  39. [47]

    Intel HEXL (release 1.2),

    F. Boemer, S. Kim, G. Seifu, F. D. de Souza, V. Gopalet al., “Intel HEXL (release 1.2), ” https://github.com/intel/hexl, 2021

    2021

  40. [48]

    Comprehensive analysis of privacy leakage in vertical federated learning during prediction

    X. Jiang, X. Zhou, and J. Grossklags, “Comprehensive analysis of privacy leakage in vertical federated learning during prediction. ”Proc. Priv. Enhancing Technol., vol. 2022, no. 2, pp. 263–281, 2022

    2022

  41. [49]

    Vole-psi: Fast oprf and circuit-psi from vector-ole,

    P. Rindal and P. Schoppmann, “Vole-psi: Fast oprf and circuit-psi from vector-ole, ” in Annual International Conference on the Theory and Applications of Crypto- graphic Techniques. Springer, 2021, pp. 901–930. A APPENDIX A.1 Proofs A.1.1 Proof of Lemma 5. Proof. We denote𝐷′ 𝐴...

    2021

  42. [2022]

    Available: https://doi.org/10.2478/popets-2022-0018

    [Online]. Available: https://doi.org/10.2478/popets-2022-0018

    2022 doi

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.