TL;DR
This paper introduces a novel protocol for private collaborative benchmarking that filters out extreme outlier performances before computing aggregate statistics. This ensures that benchmarks accurately reflect the performance of the majority of participants, preventing distortion by a few exceptionally good or bad actors, while maintaining strict privacy guarantees.
What Problem Does This Paper Address?
Modern enterprises increasingly rely on benchmarking to compare their performance against competitors. Collaborative benchmarking, where multiple companies pool their data, offers a richer comparison. However, the data used for these benchmarks (e.g., time to ship, return on investment) are highly sensitive and confidential. Existing solutions often involve anonymization or trusted third parties, which can limit adoption. Furthermore, a common issue in benchmarking is the presence of extreme outlier performances (either exceptionally good or bad) that can significantly skew aggregate statistics like the average. This distorts the true picture of performance and hinders improvement efforts. The paper addresses the need for a privacy-preserving method to filter out these outliers before performing collaborative benchmarking, ensuring the benchmark is representative of the core group.
Methods
The core contribution is a filtering protocol that identifies and excludes the "k best" (or worst) performing participants from a larger group. This is achieved by first implementing a private sorting network. Each participant's input value is kept secret, and the protocol ensures that no participant learns the actual values of others, nor the rank of their own value within the sorted list.
Key techniques include:
- Yao's Millionaires' Protocol: This is used as a building block for the comparison gates within the sorting network. The paper claims to present the "fastest implementation" of this protocol.
- Mix Networks: These are employed to shuffle input values and ensure untraceability, preventing participants from knowing the origin of the data they are processing.
- Homomorphic Encryption: Specifically, encryption schemes homomorphic in the addition group (like Paillier's) are used to allow computations on encrypted data.
- Random Permutation/Derangement: To further obscure the origin and destination of data, a random permutation (specifically a derangement, where no element ends up in its original position) of participants is computed. This is done in an expected O(log n) rounds.
The protocol avoids general Secure Multi-Party Computation (SMC) circuit constructions in favor of optimized building blocks for better performance.
Datasets
Not discussed in the paper. The paper focuses on a theoretical protocol and its implementation for performance evaluation, rather than on specific datasets.
Key Insights and Ideas
- The "k-best" filter is crucial for meaningful benchmarking: Outliers can severely distort performance metrics, making it essential to exclude them for accurate comparisons.
- Privacy-preserving sorting is the key enabler: By sorting values privately, we can identify the top/bottom k without revealing individual performances or ranks.
- Optimized building blocks are more practical than general SMC: The paper emphasizes using specialized, efficient protocols (like their Yao's Millionaires' implementation and fair shuffle) over generic SMC constructions for better performance.
- Untraceability through derangements and mix networks: Randomly permuting participants and using mix networks ensures that even if intermediate values are observed, the original source and destination of data remain hidden.
Key Results
The paper presents a protocol that achieves a sorting network with a depth of O(log² n) and a communication complexity of O(n log² n). The comparison gates operate in O(1) rounds. The random permutation protocol runs in an expected O(log n) rounds with O(n) communication complexity.
The authors implemented their protocol and compared it to Fischlin's [11] best-known Yao's millionaires' protocol. While specific quantitative results are presented in Figure 4 (performance in milliseconds vs. bits), the paper states that their implementation of Yao's millionaires' protocol "outperforms the best-known solution." The performance evaluation was conducted on a 1.6 GHz Pentium Mobile processor with 1 GB RAM.
Limitations and Future Work
- Semi-honest/Honest-but-curious model: The protocol is designed for the semi-honest model, meaning participants follow the protocol but may try to learn extra information from messages. It does not protect against malicious adversaries.
- Key length considerations: The paper notes that for low security requirements, a 512-bit RSA modulus is used, but acknowledges that larger key sizes might be necessary for better security, with implications for performance.
- Probability of revealing equality: There's a small leak in the Yao's Millionaires' protocol where equality might be revealed with a very low probability. This probability is shown to be negligible for large bit lengths.
- Future work: The paper suggests that the developed filtering protocol can be applied before any other collaborative benchmarking protocol that aims to exclude outlier values. The paper also outlines how to compute the average and variance of the k best input variables after the sorting protocol.
Summary updated