Introduction
Secure equality testing ($a = b$) and comparison ($a > b$) are fundamental building blocks for privacy-preserving technologies, including Private Set Intersection (PSI), secure data mining, and machine learning (e.g., ReLU and MaxPool functions). Despite their importance, existing two-party computation (2PC) protocols often struggle with a trade-off between latency and communication efficiency. Logarithmic-round protocols suffer in high-latency wide-area networks (WAN), while constant-round protocols like Garbled Circuits (GC) impose heavy online communication burdens. Furthermore, Function Secret Sharing (FSS) methods, while efficient online, require impractical, exponentially large offline setup costs for high-bit inputs.
This paper introduces novel constant-round 2PC protocols that achieve the "best of all worlds": low latency, minimal online communication, and practical offline preprocessing. By leveraging a new dimension reduction technique and a cryptographic primitive termed "Oblivious Selective Zero Check" (OZC), the proposed methods significantly outperform state-of-the-art frameworks.
Proposed Methods
The authors adopt an online/offline paradigm, shifting the bulk of the computational load to a preprocessing phase to ensure near-instantaneous online execution.
Two-Round Equality Testing
Traditional equality testing often relies on bit-by-bit comparisons, which scale poorly. The authors instead treat equality as an oblivious retrieval problem. To avoid the exponential overhead of a $2^n$ size lookup table for $n$-bit integers, they introduce a dimension reduction technique.
As shown in the figure above, the protocol converts boolean shares of input bits into arithmetic shares of a value $d$, representing the Hamming distance: $d = \sum_{i=0}^{n-1} (a_i \oplus b_i)$. If $a = b$, then $d = 0$. This transformation reduces the required lookup table size from $2^n$ to just $n+1$, making the offline phase highly practical for standard 32-bit or 64-bit integers.
Three-Round Secure Comparison
The comparison protocol ($a > b$) focuses on identifying the most significant bit where the two values differ. To achieve this in constant rounds, the authors introduce the Oblivious Selective Zero Check (OZC) primitive. OZC allows a party to verify if a secret-shared list contains a zero at a specific, hidden position without exposing any other elements in the list.
The OZC mechanism utilizes matrix-based circular shifts (illustrated above) to transform input bits into a structure where a zero appears only at the first differing bit. This allows the parties to determine the comparison result securely in only three rounds.
Experimental Evaluation
The protocols were evaluated using synthetic 32-bit and 64-bit integers across three network environments: LAN (20Gbps, 0.01ms latency), MAN (400Mbps, 20ms latency), and WAN (10Mbps, 100ms latency). Benchmarks included standard frameworks such as ABY, EMP-toolkit (Garbled Circuits), CrypTFlow2, and FSS-based protocols.
Key Results
The performance gains are particularly notable for 32-bit inputs:
- Equality Testing: Achieved a 9x speedup over recent work by Guo et al. (EUROCRYPT 2023) and a 15x speedup over standard Garbled Circuits. Online communication was reduced to just 76 bits, representing only 1% of the communication required by the ABY framework.
- Secure Comparison: Achieved a 3x speedup over Guo et al. and a 6x speedup over Rathee et al. (CCS 2020). Online communication was approximately 384 bits, or 5% of the ABY baseline.
Conclusion and Future Work
By prioritizing online responsiveness through dimension reduction and the OZC primitive, this work provides a highly efficient solution for real-time secure computation. While currently optimized for semi-honest adversaries, future work may involve extending these protocols to provide security against malicious actors and further optimizing the storage requirements of the offline phase. The substantial reduction in online communication makes these protocols ideal for high-latency environments and bandwidth-constrained applications.
Summary updated