Introduction
In collaborative data analysis, benchmarking allows organizations to compare performance metrics—such as revenue or operational efficiency—against peers. However, privacy concerns often prevent the sharing of sensitive raw data. Secure Multi-Party Computation (SMC) offers a solution, enabling the computation of functions over private inputs without revealing the inputs themselves. A fundamental operation in this domain is finding the $k^{th}$-ranked element (KRE), which includes finding the minimum, maximum, or median of a distributed dataset.
Traditional SMC protocols for KRE often rely on peer-to-peer (P2P) architectures, which suffer from poor scalability as the number of participants increases. This paper proposes a suite of protocols designed for a star network topology, where multiple clients interact with a single central server, significantly reducing the networking overhead and aligning with modern cloud-based architectures.
Problem Statement and Objectives
Existing KRE protocols frequently utilize binary search methods, resulting in round complexity that scales with the bit-length of the input values. In high-latency environments like Wide Area Networks (WANs), these sequential rounds become a major performance bottleneck.
The authors address two primary challenges:
- Network Topology: Transitioning from complex P2P meshes to a more manageable client-server star network.
- Efficiency: Achieving constant round complexity to ensure performance remains stable regardless of the data's precision (bit-length).
Proposed Protocols
The researchers introduced four distinct protocols, each offering different trade-offs between computational speed, security, and fault tolerance.
- KRE-YGC: Combines Yao’s Garbled Circuits (YGC) for comparisons with Additive Homomorphic Encryption (AHE) for rank aggregation. While it is the most computationally efficient, it lacks robustness against server-client collusion.
- KRE-AHE1 & KRE-AHE2: Utilize threshold AHE, where the decryption key is distributed among clients. The server performs operations on encrypted data, requiring a quorum of clients to reveal the final result. KRE-AHE2 incorporates the DGK protocol for more efficient integer comparisons.
- KRE-SHE: Leverages Somewhat Homomorphic Encryption (SHE) to allow the server to execute complex logic entirely on encrypted bits, minimizing the number of communication rounds.
A core innovation is the PAIRED predicate, a logic framework that distributes comparison tasks among clients. This ensures every necessary pair is compared exactly once, balancing the workload across the network.
Performance and Results
The protocols were evaluated using synthetic 32-bit integers with up to 100 clients over a WAN. The results demonstrate that constant-round protocols significantly outperform traditional iterative methods in real-world network conditions.
- Execution Time:
KRE-YGCemerged as the fastest, processing 100 clients in 197 seconds.KRE-AHE2followed at 336 seconds but provided superior security and fault tolerance. - Communication Overhead: The protocols are highly efficient; at 100 clients, the data transmitted per client was approximately 0.3 MB.
- Scalability: Asymptotic analysis shows that while SHE-based methods have higher initial costs, they offer the best theoretical scaling for very large participant groups.
Conclusion
This work demonstrates that secure KRE computation is feasible at scale within a star network. By achieving constant round complexity, the proposed protocols mitigate the latency issues inherent in previous designs. While the current models assume semi-honest participants, they provide a robust foundation for private benchmarking. Future research will focus on extending these protocols to withstand malicious adversaries who may attempt to subvert the computation.
Summary updated