TL;DR
VerifyML is the first secure inference framework designed to audit the fairness of machine learning models while protecting the privacy of both the model and the test data. Even if the model holder is "malicious"—meaning they might try to cheat the verification process—VerifyML uses optimized two-party computation (2PC) to prove a model’s fairness with significantly lower latency and communication overhead than previous state-of-the-art methods.
What Problem Does This Paper Address?
As machine learning (ML) systems increasingly handle sensitive decisions—like loan approvals or criminal recidivism risk (e.g., the COMPAS system)—algorithmic bias has become a major societal concern. However, auditing these models for fairness faces a "privacy deadlock":
- Model Holders treat their models as valuable intellectual property and are reluctant to share weights.
- Clients/Auditors use sensitive data (medical records, financial history) for testing that must remain confidential.
- Trust Issues: A model holder might try to "game" the audit by providing fake results to appear fairer than they actually are.
Existing tools either require "white-box" access (seeing the model) or rely on "semi-honest" assumptions where neither party actively tries to cheat. VerifyML breaks this deadlock by allowing a client to check a model's fairness "obliviously" (without seeing the model or revealing the data) even when the model holder is actively malicious.
Methods
VerifyML is built on Secure Two-Party Computation (2PC), specifically a hybrid of Homomorphic Encryption (HE) and Garbled Circuits (GC). The authors introduce several clever optimizations to make this practical:
- Offline-Online Paradigm: Over 95% of the heavy cryptographic lifting is moved to an "offline" phase. This generates "authenticated Beaver’s triples"—pre-computed cryptographic building blocks—so the "online" inference happens with minimal latency.
- Parallel Homomorphic Computing: For linear layers (convolutions and matrix multiplications), the authors designed a way to generate these triples using SIMD (Single Instruction Multiple Data) techniques. Crucially, they eliminated "rotation" operations, which are the most computationally expensive part of standard homomorphic encryption.
- Optimized Non-linear Layers: For activation functions like ReLU, they developed a new protocol that treats the Garbled Circuit as a "one-time pad." This drastically reduces the number of expensive multiplications needed inside the circuit.
- Malicious Resilience: To prevent the model holder from cheating, the system uses "authenticated shares" and a final Consistency Check. If the model holder tries to swap inputs or tamper with intermediate values, the protocol aborts.
Datasets
The authors evaluated VerifyML on mainstream ML architectures (ResNet-18 and LeNet) using two datasets commonly used in fairness research:
- CelebA: A large-scale face attributes dataset used to check for biases in facial recognition/classification.
- C-MNIST: A variant of the MNIST digit dataset used to evaluate fairness across different population subgroups.
Key Insights and Ideas
- Bypassing the "Malicious Tax": Usually, moving from a "semi-honest" to a "malicious" security model incurs a massive performance penalty (often 10x-100x). VerifyML is so optimized that it actually outperforms some existing semi-honest systems.
- Rotation-Free HE: By exploiting the relationship between secret sharing and HE, the authors found they could perform matrix-vector multiplications without any homomorphic rotations, a major "aha moment" for reducing computation time.
- Lightweight Verification: Instead of using heavy zero-knowledge proofs for every single operation, VerifyML uses a global consistency check at the end of the process. This ensures that if the model holder cheated at any point, the final result will be mathematically inconsistent.
Key Results
VerifyML demonstrates massive improvements over Overdrive, the previous state-of-the-art for malicious-secure 2PC:
- Linear Layers: Achieves up to 1.7x computation speedup and at least 10.7x less communication overhead during triple generation.
- Non-linear Layers (ReLU): Runs 4x to 42x faster and requires >48x less communication than existing protocols.
- End-to-End Performance: On ResNet-18, VerifyML boosted online runtime by 32.2x compared to baseline malicious-secure frameworks.
- Efficiency: The online phase for a single query on LeNet takes just 1 second, making it practical for real-world auditing.
Limitations and Future Work
While VerifyML is resilient against a malicious model holder, it assumes the client is semi-honest (i.e., the client follows the protocol but might try to learn extra info from the messages they receive). The authors acknowledge that a fully malicious-client model would be even more secure but likely much slower.
Future work aims to:
- Further optimize the offline stage to handle even larger, more complex models (like Transformers).
- Explore ways to make the framework compatible with a wider range of non-linear activation functions beyond ReLU.
- Transition the technology into a user-friendly toolkit for non-cryptographers to audit industrial ML models.
Summary updated