AnonPSI: An Anonymity Assessment Framework for PSI

AnonPSI: An Anonymity Assessment Framework for PSI

Speakers: Bo Jiang

Conference: NDSS Symposium

YouTube: (no public video)

Overview

This talk introduces AnonPSI, a comprehensive framework designed for assessing the anonymity and privacy leakage of Private Set Intersection (PSI) protocols. PSI is a foundational cryptographic primitive enabling two parties to compute the intersection of their datasets without revealing the individual elements of those sets. Its applications span diverse fields, including friend recommendations, advertising measurement, and even sensitive areas like contagious disease tracking. However, recent research has exposed a critical vulnerability: Set Membership Inference Attacks (SMIA). These attacks allow an adversary, through repeated PSI invocations, to infer whether a specific individual is part of the intersection set, even in stringent variants like PSI-CA (PSI-Cardinality), which only reveal the intersection size.

The presented work directly addresses the limitations of existing privacy leakage measurement techniques. Prior methods often struggle with constrained protocol invocation budgets, fail to account for the uncertainties introduced by privacy-preserving mechanisms such as differential privacy, and predominantly focus on PSI-CA, neglecting the valuable side information available in other PSI variants like PSI-SUM (PSI-Summation). AnonPSI proposes novel, more effective, and efficient attack strategies that are robust across multiple PSI scenarios and can cope with privacy-preserving noise, thereby providing a more accurate assessment of real-world privacy risks.

The significance of AnonPSI lies in its dual utility: it serves as a potent attack vector for adversaries seeking to exploit PSI vulnerabilities, and, critically, as an indispensable tool for security researchers and protocol designers. By effectively measuring privacy leakage, AnonPSI can guide the development of stronger, more privacy-preserving PSI protocols, ensuring their safe deployment in sensitive applications where membership inference could have severe implications, from identifying COVID-19 positive individuals to discerning political non-voters or advertising conversion statuses.

Background

[▶ Watch: Introduction to PSI and Set Membership Inference Attacks (0:00)]()

The concept of inferring private information from seemingly anonymized or aggregated data has a rich history in computer security and privacy research. Early work by Shokri et al. in 2017 introduced Membership Inference Attacks (MIA) in the context of machine learning, demonstrating how an attacker could deduce if a specific data point was part of a model's training set by observing its outputs. While MIA typically focuses on inferring a single individual's membership from one observation, Set Membership Inference Attacks (SMIA), as addressed by AnonPSI, are distinct in their focus on reasoning about multiple individual memberships through a sequence of observations, where the attacker strategically manipulates inputs for each protocol call.

Another related area is linkage attacks, famously pioneered by Latanya Sweeney in 2000. Her work demonstrated how seemingly anonymized datasets could be re-identified by correlating them with other publicly available information, such as re-identifying individuals in medical records using publicly available voter registration data. SMIA shares this spirit of inferring information from dependent datasets but specifically targets the membership status of individuals within a set rather than their full re-identification.

A notable prior work relevant to SMIA in PSI was proposed by Guo et al. in 2014. This algorithm improved the efficiency of a basic brute-force attack from O(N) to O(log N) for inferring N individuals' memberships in PSI-CA by employing a binary search-like strategy over a hierarchical tree structure. While a significant advancement, Guo et al.'s method suffered from several critical limitations that AnonPSI aims to overcome:

1. Inefficiency under budget constraints: It becomes impractical when real-world scenarios impose strict rate limits or limited protocol invocation budgets.
2. Lack of robustness against privacy-preserving mechanisms: It cannot effectively cope with the uncertainty introduced by techniques like differential privacy (DP), rendering it ineffective in such protected environments.
3. Limited scope: It focuses exclusively on PSI-CA, overlooking the substantial privacy leakage potential and attack efficiency gains offered by leveraging auxiliary information from other protocols, such as PSI-SUM.

AnonPSI directly addresses these gaps by proposing more efficient deterministic attacks, a novel statistical attack capable of operating under differential privacy, and a method to exploit additional side information from PSI-SUM protocols.

Key Findings

[▶ Watch: Overview of Membership Inference Attacks and related work (2:00)]()

The research presented in AnonPSI yielded several critical findings that advance our understanding of PSI privacy and attack methodologies:

• Vulnerability of PSI Protocols: Even the most privacy-stringent PSI protocols, specifically those revealing only the cardinality of the intersection (PSI-CA), are demonstrably vulnerable to Set Membership Inference Attacks (SMIA).
• Amplified Leakage via Auxiliary Information: The integration and exploitation of auxiliary information, such as the sum of payloads in PSI-SUM, significantly enhances the efficiency and effectiveness of membership inference attacks, leading to greater privacy leakage compared to cardinality-only protocols.
• Superior Efficiency with Dynamic Programming: The proposed dynamic programming approach, DyPathBlazer, for PSI-CA protocols markedly improves attack efficiency over static, fixed partitioning strategies used in prior work (e.g., Guo et al.), allowing for more inferences with the same number of protocol invocations.
• Robustness Against Differential Privacy: The statistical attack framework, ActBaysian, provides a robust mechanism for handling the inherent uncertainties introduced by privacy-preserving mechanisms like Differential Privacy. It offers flexible trade-offs between inference accuracy and the number of inferred memberships, demonstrating that even with DP protection, some level of membership inference is still possible.
• Inadequacy of PSI Alone for Privacy: While Differential Privacy does reduce attack efficiency and accuracy, the persistence of membership inference capabilities by statistical methods indicates that PSI protocols, when used in isolation, may not provide sufficient privacy assurance for highly sensitive applications.
• Necessity of Synergistic Privacy Measures: The findings underscore the critical need to combine PSI protocols with other robust privacy-enhancing technologies synergistically to achieve genuinely stronger and more comprehensive privacy safeguards in real-world deployments.

Technical Deep Dive

[▶ Watch: Formal problem definition and attacker capabilities (4:00)]()

AnonPSI introduces a sophisticated framework for Set Membership Inference Attacks, encompassing both deterministic and statistical strategies, tailored for various PSI protocol types. The core problem formulation involves a two-party setting where Party 1 (the attacker) possesses dataset X and Party 2 has dataset Y. The attacker's goal is to determine the membership status of target elements in Y, specifically identifying both positive members (in the intersection X ∩ Y) and negative members (in X but not in Y), by strategically selecting inputs and observing outputs from multiple PSI protocol invocations, subject to a limited query budget τ.

The framework distinguishes between two fundamental attacking strategies:

1. Deterministic Attack: This approach treats each person's membership as a fixed, binary value (either in or out). The attack iteratively narrows down potential groups, aiming to identify subsets where all members are definitively positive (intersection size equals subset size) or definitively negative (intersection size is zero). While yielding highly accurate, certain re-identifications, this strategy typically identifies a smaller subset of individuals.
2. Statistical Attack: In contrast, this strategy models each individual's membership as a binary random variable. The attack continuously updates a posterior belief about these variables, aiming to push probabilities towards 1 (positive membership) or 0 (negative membership) until a predefined stopping criterion is met. This probabilistic approach makes a guess for each membership, guaranteeing a certain level of accuracy above a specified threshold.

Baseline Attack Algorithms

To contextualize AnonPSI's improvements, the talk reviews baseline attacks:

• A brute-force attack would involve querying each individual's membership separately, requiring O(N) protocol calls for N individuals, which is highly inefficient and easily thwarted by common output policies (e.g., minimum intersection size thresholds).
• Guo et al.'s 2014 algorithm, a significant improvement, employs a binary search strategy over a hierarchical tree structure. It performs a depth-first search (DFS), querying subsets at each node and pruning branches based on intersection sizes. This method reduces calls to O(log N) in ideal scenarios and can terminate early. However, as noted, it struggles with budget constraints, differential privacy, and only applies to PSI-CA.

DyPathBlazer: Deterministic Attack for PSI-CA

DyPathBlazer is AnonPSI's novel deterministic attack algorithm specifically designed for PSI-CA protocols. Its central innovation lies in employing a bottom-up dynamic programming solution to determine an optimal partition factor for subsets, moving beyond the suboptimal fixed binary bisection of prior methods.

The algorithm's state is defined by a tuple (N, CN, τ), representing the number of elements in the current node, the number of positive members within that node, and the remaining protocol budget. DyPathBlazer maintains a priority queue of states. When processing a state (CN, N), it uses a memoized function Θ(N, CN, τ) (Algorithm 3) to calculate the optimal partition factor K. The current set N is then dynamically divided into two child nodes: N_L with K elements and N_R with N-K elements. A PSI-CA call is made for N_L, yielding C_L, and C_R = CN - C_L is deduced for N_R. The algorithm recursively calculates the expected membership leakage (Γ) for both branches, prioritizing the branch with higher expected leakage for immediate processing while queuing the other. This process continues until the budget τ is exhausted or all elements in a node are definitively classified (CN=N or CN=0).

Theorem 1 formally proves DyPathBlazer's optimality in maximizing the number of expected membership inferences under the hierarchical structure. Furthermore, Proposition 1 provides a Leakage Lowerbound, demonstrating that DyPathBlazer's worst-case expected leakage is numerically superior to Guo et al.'s baseline, guaranteeing improved efficiency.

TreeSumExplorer: Deterministic Attack for PSI-SUM

TreeSumExplorer extends the deterministic attack paradigm to PSI-SUM protocols, which, in addition to intersection cardinality, reveal the summation of payloads associated with intersected members. This auxiliary information is intuitively a significant privacy leakage vector.

TreeSumExplorer leverages this additional data. After a PSI-SUM call, the adversary observes (N, CN, SUM) – input size, intersection cardinality, and sum of values. Instead of just cardinality, the adversary can now solve a N-SUM problem: finding all possible combinations of CN users from N whose data values sum up to SUM. This problem is solved efficiently by sorting the data values, handling the base case of CN=2 with two pointers, and recursively reducing higher CN to (CN-1)-SUM problems. The complexity is O(N^(CN-1)).

Algorithm 4 integrates this N-SUM matching into a tree-based attack structure. An initial PSI-SUM call yields (CN, SUM). N-SUM matching identifies all candidate subsets (Arr) that match this observation. A priority is calculated as N / |Arr|; a smaller |Arr| (fewer candidates) indicates higher priority as it narrows possibilities more effectively. The algorithm iteratively dequeues high-priority states, divides Arr into two sub-problems, makes a PSI-SUM call for one (N_L), deduces values for the other (N_R), and re-performs N-SUM matching for both to obtain new candidate sets (Arr_L, Arr_R). Priorities are re-calculated, and the higher-priority branch is pursued. This continues until a unique set is identified (|Arr|=1), allowing its members to be classified. By combining hierarchical attacks with N-SUM matching, TreeSumExplorer drastically reduces combinatorial possibilities, enhancing attack efficiency by exploiting auxiliary summation information.

ActBaysian: Statistical Attack for PSI-CA

ActBaysian is AnonPSI's statistical attack strategy, designed for PSI-CA and, crucially, capable of operating in scenarios with privacy-preserving noise like Differential Privacy. Unlike deterministic attacks, ActBaysian treats each individual's membership (Li) as a binary random variable with a probability pi = Pr(Li=1). The attack proceeds via Bayesian posterior updates and active learning.

1. Posterior Belief Update: After a PSI-CA call with input St yielding output Ot, the posterior belief for individuals in St is updated as pi = Ot / |St| (Equation 9). For individuals outside St but within a larger known set, their posterior belief is updated based on the total known positives minus the observed positives (Equation 10). This iterative process refines the probabilistic belief for each individual.
2. Stopping Criterion: ActBaysian employs an upper threshold θu and a lower threshold θl. If pi ≥ θu, the individual is classified as positive; if pi ≤ θl, they are classified as negative. The choice of these thresholds dictates the trade-off between inference accuracy and the number of inferred memberships.
3. Active Learning for Input Set Selection: To maximize information gain, the adversary adaptively selects the most informative subset for the next PSI call. This is achieved by minimizing the Manhattan distance to the thresholds. For each individual, distances d_u = pi - θu and d_l = pi - θl are calculated (Equation 11). Candidate input sets (Su, Sl) are constructed from individuals whose distances are within a tolerance factor tol of the minimum distances. Algorithm 5 calculates total Manhattan distances (Du, Dl) for these sets (Equation 13) and selects the set with the smaller distance as the input for the next PSI-CA call, balancing exploration and exploitation.

Proposition 2 provides Error Bounds for ActBaysian (Equations 15 & 16), quantifying Type I error (false negative), Type II error (false positive), and the overall misclassification rate, along with their upper bounds. This theoretical underpinning allows for a precise understanding of the attack's accuracy and reliability.

Demo / Proof of Concept

[▶ Watch: Discussion of baseline and prior attack algorithms (6:00)]()

While the talk does not describe a live "demo" in the traditional sense, it presents a rigorous performance evaluation of the proposed algorithms using real-world, membership-sensitive datasets. This evaluation serves as the practical proof of concept for AnonPSI's effectiveness.

Two primary datasets were utilized:

1. Taobao Ad Display/Click Records 27: A large dataset comprising over 25 million ad records, 827,009 ads, and 1,061,768 unique individuals. This was used to quantify leakage in advertising conversion revenue measurement scenarios.
2. COVID-19 Dataset from Israel 1: Containing 255,668 distinct individuals with test dates. This dataset was employed to quantify leakage in contact tracing scenarios, where identifying positive individuals is highly sensitive.

For deterministic attacks, the evaluation compared:

• Guo's algorithm-CA (the baseline for PSI-CA).
• AnonPSI's DyPathBlazer (for PSI-CA).
• AnonPSI's TreeSumExplorer (for PSI-SUM).
• Guo's algorithm adapted for SUM (denoted Guo's algorithm-SUM).

In offline attack evaluations using the Taobao dataset (illustrated in Fig. 7), where an advertiser (Party A) aims to infer ad clickers and spending:

• DyPathBlazer consistently outperformed Guo's algorithm-CA in efficiency, achieving a significantly higher membership leakage for the same number of protocol invocations.
• TreeSumExplorer (for PSI-SUM) demonstrated the highest efficiency among all methods. This empirically validated the hypothesis that leveraging auxiliary information like summation (as in PSI-SUM) substantially amplifies attack effectiveness and privacy leakage. This superior performance was observed across overall, positive, and negative membership leakage metrics.

For online attack evaluations using the COVID-19 dataset (illustrated in Fig. 8), simulating a scenario where a community (Party A) attempts to infer positive individuals daily with a limited budget of 10 PSI-CA calls per day:

• DyPathBlazer again showed significantly higher efficiency compared to Guo's algorithm-CA, inferring more positive user memberships over time.

These results robustly confirm that AnonPSI's deterministic methods provide a marked enhancement in attack efficiency over previous research.

For statistical attacks, ActBaysian's performance was evaluated under two conditions:

1. Without differential privacy (DP) protection: Parameters like thresholds (θu, θl), tolerance factor (tol), sampling rate (r), and budget (τ) were analyzed (Table I). Stricter thresholds yielded higher accuracy but fewer inferences. An optimal tol was necessary for effective inference. Larger budgets allowed for more inferences with lower error rates.
2. Against PSI-CA protocols protected by Differential Privacy (DP): DP was implemented using a Laplacian mechanism, adding calibrated random noise to the intersection size.

• Results (Fig. 9) clearly showed that DP protection diminishes attack efficiency and accuracy. The reduction in leakage directly correlated with the strength of the DP mechanism (ε).
• DP-induced randomness made posterior beliefs less accurate, decreasing inference accuracy.
• The error rate in DP-protected mechanisms increased with increasing ε.
• Interestingly, the misclassification rate initially rose and then fell as the budget τ increased. With fewer initial inferences, the error was lower. As more members were inferred, the error increased. However, with sufficiently large τ, the DP-introduced randomness was mitigated by consecutive queries, leading to more accurate inferences over time.
• ROC curves (Fig. 10) further illustrated the trade-offs between true positive and false positive rates for total, intersected, and non-intersected memberships under DP protection.

In summary, while TreeSumExplorer (without DP) generally offered the highest efficiency due to its exploitation of SUM, ActBaysian (statistical) outperformed DyPathBlazer for smaller budgets (τ) due to its more flexible, soft-stopping criterion. For larger budgets, however, DyPathBlazer's dynamic programming approach proved superior. These evaluations provide strong empirical evidence for AnonPSI's claims regarding efficiency, robustness, and the inherent vulnerabilities of PSI protocols.

Defensive Implications

[▶ Watch: Introduction to the proposed DyPath deterministic attack (8:00)]()

The findings from AnonPSI carry significant implications for developers, deployers, and researchers working with Private Set Intersection protocols. The demonstrated efficacy of Set Membership Inference Attacks (SMIA), even against PSI-CA and in the presence of differential privacy, underscores that PSI protocols alone are often insufficient to guarantee robust privacy in sensitive applications.

Defenders should consider the following actions and strategies:

• Audit Existing PSI Deployments: Organizations using PSI for applications like contact tracing, ad measurement, or friend recommendations must critically re-evaluate their current privacy assurances. The methodologies presented by AnonPSI provide a framework for internal auditing to assess potential leakage points.
• Embrace Multi-Layered Privacy: PSI should not be treated as a standalone privacy solution. It must be combined synergistically with other Privacy-Enhancing Technologies (PETs). This could include:
• Stronger Differential Privacy: While DP reduces attack efficiency, tuning its parameters (e.g., lower ε values) for a higher privacy budget can make attacks more difficult, albeit potentially at the cost of utility.
• Secure Multi-Party Computation (SMC): For extremely sensitive applications, moving beyond basic PSI to more comprehensive SMC protocols that can compute functions over encrypted data without revealing intermediate values might be necessary.
• Homomorphic Encryption (HE): Fully homomorphic encryption could allow computations on encrypted data without ever decrypting, offering stronger guarantees, though often with higher computational overhead.
• Trusted Execution Environments (TEEs): Using hardware-backed TEEs could provide a secure enclave for PSI computations, protecting sensitive data and intermediate results from external observation.
• Implement Adaptive Rate Limiting: While not a complete solution, strict and adaptive rate limiting on PSI protocol invocations can directly counteract attacks that rely on a large query budget (τ). However, attackers like ActBaysian can still operate with smaller budgets, necessitating additional defenses.
• Minimize Auxiliary Information Leakage: For protocols like PSI-SUM, the additional "side information" (the sum of payloads) significantly amplifies leakage. Designers of PSI protocols should carefully assess and, where possible, minimize any auxiliary information revealed, or ensure it is sufficiently noisy (e.g., via DP) to prevent reconstruction.
• Consider Multi-ID PSI Challenges: The research acknowledges that multi-ID PSI, where intersection sizes for multiple IDs are revealed, poses an even greater and "formidable challenge" for privacy. Organizations dealing with such scenarios must be exceptionally cautious and invest in research for specialized defenses.
• Investigate New Privacy-Enhanced PSI Protocols: The work highlights a "pressing need for innovative privacy-enhanced PSI protocols" specifically designed to minimize leakage when computing intersection-related statistics. Defenders should actively engage with and support research into such next-generation protocols that are inherently more resilient to SMIA.
• Education and Awareness: Developers and data scientists implementing PSI should be aware of SMIA vulnerabilities and the trade-offs involved when integrating privacy-preserving mechanisms.

Ultimately, the findings of AnonPSI serve as a crucial warning: the convenience and efficiency of PSI protocols should not lead to complacency regarding privacy. A proactive, multi-faceted approach to privacy protection is essential to safeguard sensitive membership information from sophisticated inference attacks.

Key Takeaways

• PSI Vulnerability Confirmed: Private Set Intersection protocols, even PSI-CA, are inherently vulnerable to Set Membership Inference Attacks (SMIA).
• Auxiliary Data Amplifies Leakage: Leveraging auxiliary information, such as the sum of payloads in PSI-SUM, significantly increases the efficiency and effectiveness of SMIA.
• AnonPSI Offers Superior Attacks: The proposed deterministic (DyPathBlazer, TreeSumExplorer) and statistical (ActBaysian) attack algorithms consistently outperform prior methods in efficiency and robustness.
• Differential Privacy is Not a Panacea: While Differential Privacy reduces attack efficiency and accuracy, statistical attacks like ActBaysian can still infer memberships, demonstrating that DP alone may not provide sufficient privacy.
• Multi-Layered Privacy is Essential: Robust privacy in PSI requires combining the protocol with other privacy-enhancing technologies (e.g., stronger DP, SMC, HE, TEEs) rather than relying on PSI in isolation.
• New Protocol Design Needed: There is a critical need for innovative, privacy-enhanced PSI protocols specifically designed to minimize membership leakage in complex, real-world scenarios, especially for multi-ID PSI.

About the Speaker(s)

Bo Jiang presented the work on AnonPSI: An Anonymity Assessment Framework for PSI. Based on the presentation, Bo Jiang is a researcher involved in the development of this framework, which focuses on evaluating and improving the privacy guarantees of Private Set Intersection protocols against sophisticated membership inference attacks. The detailed technical explanations and comprehensive evaluation presented indicate a deep expertise in cryptographic protocols, privacy-preserving technologies, and security analysis.