Blind Justice: Fairness with Encrypted Sensitive Attributes

Niki Kilbertus; Adrià Gascón; Matt J. Kusner; Michael Veale; Krishna P. Gummadi; Adrian Weller

Source-linked AI summary

Blind Justice: Fairness with Encrypted Sensitive Attributes

Niki Kilbertus, Adrià Gascón, Matt J. Kusner, Michael Veale, Krishna P. Gummadi, Adrian Weller

arXiv:1806.03281v1Jun 8, 2018stat.MLcs.CRcs.CYcs.LG

TL;DR

Fair learning faces a tension: sensitive attributes must be examined to enforce disparate-impact fairness, but users may not want to reveal them. The paper applies secure multi-party computation to encrypted attributes, enabling fair-model certification, training, and decision verification while preserving cryptographic privacy. Experiments report practical feasibility, although current MPC arithmetic and nonlinear-function approximations remain limitations.

Problem
Fair learning must examine sensitive attributes to address disparate impact, even though users may face privacy and legal concerns about revealing them.
Method
The paper uses secure multi-party computation with encrypted sensitive attributes to certify, train, and verify fair models without readable access to those attributes.
Results
The protocols implement fair model training and show practical performance, with optimization accuracy deviations from SLSQP below 4% across six datasets and all constraint values.
Takeaways & Limitations
Encrypted MPC can connect algorithmic fairness, privacy, and accountability by supporting fair learning and checking whether certified models were used.
Takeaways & Limitations
Current MPC implementations rely on fixed-point arithmetic and approximations for nonlinear functions because floating-point computation is too costly for these applications.

Abstract

from arXiv · show

Recent work has explored how to train machine learning models which do not discriminate against any subgroup of the population as determined by sensitive attributes such as gender or race. To avoid disparate treatment, sensitive attributes should not be considered. On the other hand, in order to avoid disparate impact, sensitive attributes must be examined, e.g., in order to learn a fair model, or to check if a given model is fair. We introduce methods from secure multi-party computation which allow us to avoid both. By encrypting sensitive attributes, we show how an outcome-based fair model may be learned, checked, or have its outputs verified and held to account, without users revealing their sensitive attributes.

1. Introduction

Fair learning must examine sensitive attributes to detect disparate impact, even though using them can enable disparate treatment and raise privacy and legal concerns. The paper uses secure multi-party computation to support fair certification, training, and decision verification without readable access to sensitive attributes.

Sensitive attributes should be excluded to avoid disparate treatment but examined to detect and mitigate disparate impact.
Users may resist sharing sensitive attributes because modelers could misuse them, breaches could expose them, and data protection law can restrict their collection.
A trusted third party can mediate fairness checks, but users still disclose sensitive attributes and modelers disclose proprietary models.
The paper proposes encrypted sensitive attributes and MPC so regulators can support auditable fair learning while users’ attributes and modelers’ models remain private.
The approach addresses fairness certification, fair model training, and verification that deployed decisions match a previously certified model.
The protocols extend MPC to linear fairness constraints and are evaluated on real-world settings, with code planned for public release.

2. Fairness and Privacy Requirements

The setup assigns privacy-preserving fairness tasks among users, a modeler, and a regulator while distinguishing sensitive attributes from prediction features. MPC supports certification, training, and verification, but the design assumes non-collusion and leaves some fairness notions for future work.

Assumptions and incentives: Users hold sensitive attributes z_i and labels y_i, while the modeler uses non-sensitive features x_i to train a private model that excludes z_i as input.
Fairness criteria: Sensitive attributes may correlate with non-sensitive features or labels, motivating fairness constraints based on outcome differences between groups.
Assumptions and incentives: The protocol assumes the regulator does not collude with the modeler, while keeping user data private and minimizing users’ computational burden.
Certification, training, and verification: The three tasks are certification, training, and verification, each paired with privacy requirements for sensitive data, model secrecy, and data disclosure.
Fairness criteria: The paper focuses on acceptance-rate fairness, a constrained optimization variant of the p%-rule for binary protected attributes.
Certification, training, and verification: Verification lets a user challenge an outcome by checking whether the deployed model returns the same result as the certified model.
Design choices: Keeping all user features private is possible at 2× computation cost, but it limits modeler exploration and regulator validation.

3. Our Solution

The paper uses MPC between a modeler and regulator to certify fairness, train fair models, and verify deployed decisions while keeping sensitive attributes hidden. Its protocols use secret sharing and model signatures to support private computation and accountability.

MPC enables fairness certification, fair model training, and decision verification between a modeler and regulator.The three functions check fairness, learn a certified fair model, and verify that a received decision matches the certified model's outcome.
MPC protocols jointly evaluate agreed functions while keeping intermediate values hidden, but practical machine-learning protocols require tailored fixed-point and nonlinear-function handling.The paper notes that generic MPC solutions do not yet scale directly to real-world data-analysis tasks.
Users secret-share sensitive attributes with the modeler and regulator so they can be operated on inside MPC without readable access.The two-server setup represents each sensitive value using additive shares held by the two non-colluding parties.
Certification checks a model against fairness constraint F and then computes a signature used during later verification.Verification computes the submitted model's signature and permits prediction only when it matches the regulator's certified signature.
The fair-training protocol extends custom MPC logistic regression to support linear fairness constraints.The protocol is designed for secure computation in the semi-honest model and is stated to implement the fair model-training functionality.

4. Technical Challenges of Fair Training

Fair training must adapt optimization to MPC's fixed-point arithmetic, expensive division, nonlinear functions, and overflow risks. The paper compares constraint-handling methods and finds Lagrangian multipliers best in its experiments.

The paper contributes fixed-point-suitable optimization schemes and approximations that make constrained fair learning feasible in MPC.These techniques address unstable optimization, nonlinear functions, and arithmetic overflows or underflows.
The training objective learns classifier θ by minimizing logistic loss subject to fairness constraint F(θ) ≤ 0.The data include non-sensitive features, sensitive-feature matrix Z, and labels y.
Existing SLSQP optimization is unsuitable for MPC because repeated quadratic programs are too slow and non-constant divisions can underflow or overflow in fixed point.The paper therefore replaces this approach with stochastic gradient descent and constraint-handling techniques.
The evaluated constraint methods are Lagrangian multipliers, projected gradient descent, and an interior-point log barrier.The methods incorporate fairness constraints while using stochastic or regular gradient updates.
The Lagrangian-multiplier technique performs best in experiments for accuracy, constraint adherence, and robustness to learning-rate or batch-size changes.Other fairness notions can require recomputing Z⊤X at every update, increasing cost; minibatch evaluation can risk violating the constraint.
Fixed-point overflow is a major challenge because minibatches and fairness computations can exceed the representable range.Blocked matrix multiplication, normalization, and power-of-two choices for minibatches or sample size are used to avoid overflow and expensive division.

5. Experiments

The experiments evaluate private fair-learning methods across real and synthetic datasets, focusing on accuracy, disparate-impact mitigation, and computational feasibility. Lagrangian multipliers are generally the most robust, while COMPAS exposes challenges from multiple sensitive attributes.

Experimental setup: Fixed-point MPC introduces precision and computational concerns, including overflow, underflow, and infeasible running times.The experiments specifically assess whether these concerns can be overcome on realistic datasets.
Optimization techniques: The Lagrangian method closely follows the baseline, while iplb performs slightly worse and projected gradient fails for small constraint values.Projected gradient satisfies the proxy constraint by shrinking θ, which explains its poor behavior at small c.
Dataset-specific behavior: The COMPAS dataset is especially challenging because it has seven sensitive attributes, including one with only 10 positive training instances.All methods collapse toward negative predictions more quickly than SLSQP when constraints are enforced across attributes.
Optimization techniques: Across six datasets and all constraint values, Lagrangian accuracy deviates from SLSQP by less than 4%.Piecewise linear sigmoid approximation does not spoil performance.
Fairness outcomes: The Lagrangian method balances positive-outcome rates at rates similar to the baseline, with only minor accuracy losses outside COMPAS.This behavior persists with fixed-point numbers and piecewise linear nonlinearities.
Efficiency: Training is several orders of magnitude slower than non-MPC training but remains feasible on a laptop, while certification operations take well below one second.Offline precomputation and a C++ implementation support viable running times for reasonably large datasets.

6. Conclusion

The paper concludes that MPC can support private fair-model training, certification, and decision verification without readable access to sensitive attributes. It also identifies scalability and formal-security limitations that motivate tailored protocols and further care.

Conclusion: MPC enables fair learning workflows in which sensitive attributes remain encrypted while models are trained, certified, and verified.The approach targets the tension between examining sensitive attributes for fairness and protecting them from disclosure.
Secret sharing: Secret sharing splits each sensitive value across the modeler and regulator so that neither share alone reveals the value.The parties can reconstruct the value jointly by adding their shares.
MPC protocols: MPC protocols jointly evaluate functions gate by gate while keeping intermediate values shared rather than revealing them.In this setting, the functions implement fairness checking, constrained training, or decision verification.
MPC protocols: Precomputed multiplication triples move costly multiplication preparation into an offline phase that can run in advance.This architecture accommodates the many multiplications required by private fair-model training.
Limitations and engineering: Generic MPC protocols do not yet scale to typical machine-learning input sizes, motivating application-specific protocols.The paper extends an SGD protocol and uses specialized acceleration techniques.
Limitations and engineering: The paper does not provide a formal security definition, instead referring readers to prior work for the relevant simulation-based argument.This is an explicit scope boundary of the security treatment.

B.1. The Fair Training Algorithm

The fair-training algorithm jointly processes shared sensitive data with non-sensitive features using Lagrangian multipliers and fixed-point MPC operations. Its output is the trained parameter vector θ, while implementation choices address overflow and nonlinear-function evaluation.

Shared computation: Each minibatch evaluates an approximated sigmoid and updates model and multiplier variables through shared MPC computations.The parties operate on additively shared secrets rather than readable sensitive values.
Privacy guarantee: The resulting computation is equivalent to evaluating the algorithm with data in the clear while preventing unilateral access to sensitive values.The modeler and regulator jointly receive secret shares during the protocol.
Numerical implementation: Blocked matrix multiplication and bit-shift averaging are used to reduce overflow and avoid slow MPC divisions by powers of two.The blocked routine already includes division by n.
Nonlinear approximation: The piecewise linear sigmoid approximation is selected because it worked best in the reported comparison.The paper points to Figure 4 for the supporting evaluation.
Algorithm: The algorithm initializes θ and λ, computes a shared fairness statistic, and iterates over minibatches for multiple epochs.The public inputs include learning rates, training size, minibatch size, constraint values, and epoch count.
Constraint handling: The fairness violation F is computed from |Aθ| − c, and the multiplier gradient is restricted to max{F, 0}.The update uses Lagrangian multipliers to respond when the fairness constraint is violated.

B.2. Description of Training Parameters

Training uses fixed learning rates, vanilla SGD, and a 16-bit fixed-point representation, with roughly 15,000 gradient updates across datasets.

B.2. Description of Training Parameters: Training uses batch size 64 and roughly 15,000 gradient updates, with epochs scaling inversely with dataset size.The learning rates are fixed at ηθ = 10^-4 and ηλ = 0.05.
B.2. Description of Training Parameters: The training procedure includes an annealing schedule for 1/t in the interior point logarithmic barrier method.The gradient losses combine regular binary cross entropy with constraint losses.
B.2. Description of Training Parameters: Reported results use vanilla SGD with fixed learning rates and no regularization because weight decay, adaptive schedules, and momentum showed no consistent effect.
B.2. Description of Training Parameters: The MPC implementation uses a fixed-point representation with 16 bits for both the integer and fractional parts.Fewer bits would improve speed but increase the risk of precision loss.

C.1. Results on Remaining Datasets

Across the remaining datasets, the Lagrangian multiplier method reports accuracy and disparate-impact mitigation, but small datasets and skewed labels complicate interpretation.

C.1. Results on Remaining Datasets: The Lagrangian multiplier method consistently removes disparate impact to a similar extent as the baseline on the German dataset.Because the dataset has only 512 training and 200 test examples, accuracy changes in increments of 0.005 and require careful interpretation.
C.1. Results on Remaining Datasets: In the Adult dataset, the method mitigates disparate impact with slightly worse accuracy than the baseline.
C.1. Results on Remaining Datasets: In the stop, question and frisk dataset, about 93% of samples have positive labels, producing near-optimal accuracy when predictions collapse to always 1.The baseline and proposed method exhibit this collapse at a similar rate as c decreases.

C.2. Disadvantages of Other Optimization Methods

The interior-point and projected-gradient methods can satisfy or approach fairness constraints while suffering numerical failures or failing to mitigate true disparate impact in MPC settings.

Interior Point Logarithmic Barrier method: The interior-point logarithmic barrier method balances positive outcomes across groups as constraints tighten but breaks down from overflow and underflow errors.It also produces substantially more failed runs than the Lagrangian multiplier technique.
Interior Point Logarithmic Barrier method: Tight constraints can make interior-point gradients change from almost zero to extremely large values within one parameter update.The method also requires careful tuning and scheduling of t, making it poorly suited for MPC despite good results in some domains.
Projected gradient method: Projected gradient can satisfy the proxy constraint by shrinking θ while preserving near-optimal accuracy, without properly mitigating disparate impact under the true p%-rule.Its accuracy is invariant to rescaling θ, whereas the logistic loss encourages large weights and high-confidence decisions.
Figures 5–6: Figures 5 and 6 distinguish optimization methods, approximation choices, arithmetic types, sensitive-attribute groups, and baseline behavior across datasets.Figure 6 plots the fraction of positive outcomes against constraint c for five datasets.
Projected gradient method: The projection method often fails for small constraint values because its projection matrix becomes nearly singular, causing over- and underflow errors.