Lost in the Averages: Reassessing Record-Specific Privacy Risk Evaluation

Basic Information

• Paper ID: 2405.15423
• Title: Lost in the Averages: Reassessing Record-Specific Privacy Risk Evaluation
• Authors: Nataša Krčo, Florent Guépin, Matthieu Meeus, Bogdan Kulynych, Yves-Alexandre de Montjoye
• Institutions: Imperial College London, Lausanne University Hospital (CHUV)
• Classification: cs.LG, cs.CR
• Publication Venue/Conference: Data Privacy Management (DPM) workshop at ESORICS 2025
• Paper Link: https://arxiv.org/abs/2405.15423v2

Abstract

This paper investigates privacy risk assessment for synthetic data generators and machine learning models. Synthetic data generators and ML models may memorize their training data, raising privacy concerns. Membership Inference Attacks (MIAs) are the standard method for evaluating privacy risks in these systems. The authors analyze traditional approaches for assessing record-specific privacy games under realistic attacker assumptions, finding that they average privacy risks of records across different datasets. The paper proposes a novel model-seeded privacy game that provides accurate privacy risk estimates for records within specific datasets. Experiments demonstrate that traditional games may overlook up to 94% of high-risk records.

Research Background and Motivation

1. Problem Definition

With the widespread application of machine learning models and synthetic data generators in sensitive domains such as healthcare, law, and finance, the issue of models potentially memorizing training data has become increasingly prominent. Attackers may determine whether specific records were used for training through membership inference attacks, or even reconstruct complete training samples.

2. Problem Significance

• Privacy Breach Risk: Model memorization may lead to leakage of sensitive personal information
• Regulatory Compliance: Accurate privacy risk assessment is required to meet regulatory requirements
• Practical Deployment: When specific models or synthetic datasets are released, accurate risk assessment is necessary

3. Limitations of Existing Methods

Traditional record-specific privacy games use dataset sampling as the source of randomness, implicitly assuming that a record's privacy risk is independent of its dataset. This assumption does not hold in practical scenarios, leading to potentially misleading risk assessments.

4. Research Motivation

The authors discovered that traditional privacy games average record risks across different datasets, while practical applications require assessing record risks within specific datasets. Therefore, they propose the model-seeded game to address this issue.

Core Contributions

1. Theoretical Analysis: Formally analyzes traditional record-specific privacy games, proving that they compute privacy risks averaged across datasets
2. Novel Method Proposal: Proposes and formalizes the model-seeded privacy game, which converges to the Differential Privacy Distinguisher (DPD) risk of records
3. Experimental Validation: Validates the differences between the two privacy games across multiple datasets and models, finding that traditional games may overlook up to 94% of high-risk records
4. Impact Factor Analysis: Analyzes the effects of dataset size and differential privacy guarantees on risk estimation differences

Methodology Details

Task Definition

Given a target record x, training algorithm A(·), and attack ϕ(·), the objective is to accurately estimate the privacy risk of record x within a specific dataset D. Privacy risk is measured by the success rate of membership inference attacks.

Traditional Privacy Game

Definition 2: For target record x, dataset size n, training algorithm A(·), and attack ϕ(·):

1. The challenger samples dataset D̄ ∼ D^n from the distribution
2. The challenger randomly draws secret bit b ∈ {0,1}
3. If b=1, the target record x is added to D̄ to form D = D̄ ∪ {x}; otherwise D = D̄
4. The challenger trains the target model θ ← A(D) on dataset D
5. The attacker outputs guess b̂ = ϕ(θ)

Model-Seeded Privacy Game

Definition 3: For target record x, partial dataset D̄, training algorithm A(·), and attack ϕ(·):

1. The challenger randomly draws secret bit b ∈ {0,1}
2. If b=1, the target record x is added to D̄ to form D = D̄ ∪ {x}; otherwise D = D̄
3. The challenger trains the target model θ ← A(D) on dataset D with a new random seed
4. The attacker outputs guess b̂ = ϕ(θ)

Technical Innovations

1. Fixed Dataset: Unlike traditional games, the model-seeded game fixes the target dataset and uses only the model seed as the source of randomness
2. Theoretical Guarantees: Proves that the model-seeded game converges to DPD risk, while traditional games converge to dataset-averaged risk
3. Practical Utility: Provides privacy risk estimates consistent with differential privacy

Theoretical Analysis

Proposition 1 (Model-Seeded Game Converges to DPD Risk): For any fixed target record x, partial dataset D̄, training algorithm T(·), and attack ϕ(·), in the model-seeded game:

|α̂^MS_ϕ - α_ϕ| ≤ √(log(2/ρ)/(2N))

Proposition 2 (Traditional Game Converges to Average Privacy Risk): The empirical error rate of the traditional privacy game converges to the average across i.i.d. dataset resampling:

|α̂^T_ϕ - E_{D̄∼D^n}α_{ϕ,D̄}| ≤ √(log(2/ρ)/(2N))

Experimental Setup

Datasets

• Adult Dataset: Census data containing categorical and continuous demographic features
• UK Census Dataset: United Kingdom census data
• Dataset Partitioning: D_aux for MIA development, D_eval for evaluation, |D| = 1000

Target Models

• Synthpop: Statistical synthetic data generator
• Baynet: Bayesian network generator
• PrivBayes: Differentially private version of Baynet

MIA Methods

Uses TAPAS attack, a state-of-the-art query-based attack method for synthetic data generators. TAPAS operates under black-box model access with auxiliary data but without access to the target model's training data.

Evaluation Metrics

• Miss Rate (MR): Proportion of records classified as high-risk in the model-seeded setting but low-risk in the traditional setting
• Root Mean Squared Deviation (RMSD): Root mean squared deviation between the two risk estimates
• AUC ROC: Summary metric for privacy risk

Experimental Results

Main Results

Experiments on the Adult dataset with Synthpop generator show:

• 94% of high-risk records are misclassified as low-risk by the traditional game (threshold t=0.8)
• RMSD ranges from 0.04 to 0.11, representing significant error in risk estimates using AUC
• Miss Rate ranges from 0.73 to 0.94, indicating consistent misidentification of high-risk records in traditional settings

Impact of Different Thresholds

For all high-risk thresholds, miss rates are significant:

• At t=0.6, miss rate exceeds 20% across all settings
• At t=0.9, miss rate reaches 80%
• Miss rate increases with threshold t

Impact of Dataset Size

• Small datasets (n<10,000): Larger differences between risk estimates
• Large datasets: Differences decrease but remain significant
• Even with |D|=10,000, RMSD remains substantial

Impact of Differential Privacy

When training PrivBayes with strict ε values:

• MIA performance decreases as ε decreases, converging to random guessing baseline (AUC 0.5)
• Differences between estimates also decrease as estimates converge near 0.5
• However, using model-seeded settings remains important for verifying DP guarantees

Case Study

Risk assessment of a single target record across 15 randomly selected datasets shows:

• Model-seeded risk R_MS varies from approximately 0.5 (random guessing) to 0.8 (high-risk)
• Traditional risk R_T = 0.62, underestimating DPD risk by up to 0.2 in worst case

Related Work

Development of Membership Inference Attacks

• Shokri et al. (2017): First proposed MIA against ML models
• Shadow Modeling Technique: Training multiple models with/without target records to approximate their impact
• Tabular Synthetic Data: Attack methods specifically for synthetic data generators

Threat Models

• Data Level: Attacker's access to real data
• Model Level: Attacker's access to training models (black-box vs. white-box)
• Realistic Assumptions: Attackers have access to auxiliary datasets

MIA Evaluation

• Model-Specific Games: Evaluate attackers' ability to distinguish whether records are included/excluded in training data
• Record-Specific Games: Evaluate attackers' ability to distinguish models trained with/without target records

Conclusions and Discussion

Main Conclusions

1. Limitations of Traditional Privacy Games: Averaging risks through dataset sampling provides misleading risk assessments
2. Advantages of Model-Seeded Games: Provides accurate privacy risk estimates for records within specific datasets, consistent with differential privacy
3. Practical Impact: Traditional methods may overlook numerous high-risk records, affecting privacy protection decisions

Limitations

1. Dataset Dependency: The exact dependence of record vulnerability on datasets remains an open question
2. Experimental Scope: Primarily focuses on tabular synthetic data; applicability to other data types requires further verification
3. Computational Cost: Model-seeded games may require more computational resources

Future Directions

1. Theoretical Analysis: Deeper understanding of mechanisms by which datasets affect record vulnerability
2. Extended Applications: Extending methods to other types of machine learning models and data
3. Practical Tools: Developing practical privacy risk assessment tools

In-Depth Evaluation

Strengths

1. Theoretical Contribution: Provides rigorous theoretical analysis proving convergence properties of both privacy games
2. Practical Value: Addresses important problems in real-world privacy risk assessment
3. Comprehensive Experiments: Thorough experimental validation across multiple datasets and models
4. Clear Writing: Well-structured paper with accurate technical descriptions

Weaknesses

1. Experimental Scope: Primarily focuses on tabular data; applicability to other data types is limited
2. Computational Complexity: Lacks detailed analysis of computational complexity differences between methods
3. Practical Deployment: Lacks case studies of deployment in real systems

Impact

1. Academic Contribution: Provides important theoretical and practical contributions to privacy risk assessment
2. Practical Value: Offers important guidance for organizations handling sensitive data
3. Reproducibility: Provides detailed experimental setup and algorithm descriptions

Applicable Scenarios

1. Synthetic Data Release: Assessing privacy risks of synthetic datasets
2. Model Auditing: Privacy auditing of machine learning models
3. Regulatory Compliance: Privacy risk assessment for regulatory requirements
4. Differential Privacy Verification: Verifying effectiveness of differential privacy implementations

References

The paper cites important literature in privacy-preserving machine learning, including:

• Shokri et al.'s pioneering work on membership inference attacks
• Dwork and Roth's classical differential privacy theory
• Recent research on synthetic data privacy

Summary: Through theoretical analysis and experimental validation, this paper reveals deficiencies in traditional privacy risk assessment methods and proposes a more accurate model-seeded privacy game. The research provides important theoretical and practical value to the privacy-preserving machine learning field, particularly in synthetic data generation and privacy risk assessment.