Abstract
Secure Multiparty Computation (MPC) allows organizations to collaboratively train machine learning models while keeping their individual datasets private. However, the inability to inspect input data often leads to issues with data quality, bias, and regulatory compliance. We introduce HOLMES, a platform designed for efficient statistical distribution testing over private, joint datasets. By integrating Interactive Zero-Knowledge (IZK) proofs with a novel ZK-friendly sketching algorithm, HOLMES overcomes the "curse of dimensionality" inherent in traditional MPC approaches, achieving speedups of up to $10^4$x for multidimensional tests.
Introduction
In privacy-preserving machine learning, Secure Multiparty Computation (MPC) is considered the gold standard for collaborative training. It enables entities like hospitals or financial institutions to derive insights from collective data without exposing sensitive records. Despite its strengths, MPC faces a critical challenge: "blind" training makes it impossible to detect garbage data, outliers, or biases. Without the ability to perform distribution testing—standard statistical check-ups—organizations risk deploying inaccurate or non-compliant models.
The Challenge: The Curse of Dimensionality
Performing statistical tests like the $\chi^2$ test in an MPC setting is traditionally "prohibitively expensive." The standard method, "oblivious bucketing," requires the system to update every possible data bucket for every data point to maintain privacy. As the number of attributes and their possible values increase, the number of buckets grows exponentially. For instance, checking the joint distribution of five attributes with ten values each results in 100,000 buckets. This computational overhead makes standard distribution testing a non-starter for large-scale secure collaborative learning.
The HOLMES Architecture
HOLMES addresses these inefficiencies by moving away from monolithic $t$-party MPC computations toward a hybrid architecture focused on verification.
Interactive Zero-Knowledge (IZK) Proofs
Instead of the entire group calculating global statistics together, HOLMES utilizes Interactive Zero-Knowledge (IZK) proofs (specifically the QuickSilver protocol). In this model, each party calculates their own local statistics and provides a proof to the others that the calculation is correct without revealing the raw data. This shifts the computational burden from expensive $t$-party MPC to significantly faster pairwise verification.
ZK-Friendly Sketching via Legendre PRF
To handle multidimensional data, HOLMES employs "ZK-friendly" sketching based on random linear projections. A key innovation is the use of the Legendre PRF to generate pseudorandom bits. The Legendre symbol naturally outputs values in $\{-1, 1\}$, which are ideal for the mathematical requirements of sketching (the Johnson-Lindenstrauss lemma). Crucially, the Legendre PRF is extremely efficient to compute within a zero-knowledge circuit, requiring only a few gates compared to standard hash functions like SHA-256.
Experimental Evaluation
The researchers evaluated HOLMES using several real-world datasets, including the Bank Marketing dataset (41k records), the Diabetes dataset (100k records), and an Auctioning dataset (560k records).
Key Results
- Massive Speedups: For multidimensional $\chi^2$ tests, HOLMES is up to 10,000x faster than the naive oblivious bucketing approach. Even for simpler 1D tests (range checks, means), it is at least 10x faster than optimized MPC baselines.
- Scalability: Unlike traditional MPC, which often scales quadratically with the number of parties ($O(t^2)$), HOLMES scales linearly ($O(t)$).
- Real-World Feasibility: On the Bank Marketing dataset with two parties, a full suite of statistical tests was completed in under 30 seconds. For 10 parties, the overhead remained negligible (200-300 seconds) compared to the time required for secure model training.
Conclusion and Future Work
HOLMES demonstrates that data quality checks can be a practical, standard component of the secure learning pipeline. While it significantly improves efficiency, some challenges remain. Each test result leaks a single bit of information (pass/fail), which could potentially be exploited by a sophisticated adversary through multiple targeted tests. Furthermore, while HOLMES detects statistical anomalies, it does not inherently prevent adversarial poisoning where malicious data is crafted to fit expected distributions. Future research into "robust statistics" within the HOLMES framework may address these security concerns.
Summary updated