Paper 2026/808

Secure Comparison in (Constant) Two Rounds

Abstract

Secure comparison is a fundamental building block frequently employed in various applications of secure multiparty computation, such as secure machine learning. Such protocols based on secret sharing (SS) typically excel in throughput compared to garbled circuits (GC), but they historically suffer from higher (online) round complexity: while GC-based comparison ends in two rounds, the state-of-the-art SS-based (plaintext) comparison protocol requires three rounds (Lu et al., USENIX Security 2025). To break the barrier, in this paper we propose the first SS-based comparison protocol, built upon "round absorption" via multi-fan-in gates, to match the two-round complexity of GC with online bit complexity $O(n \log n)$ significantly lower than GC-based $O(\lambda n)$. We also propose the second two-round protocol, built upon a new optimization technique for multiplication, that addresses the drawback of $O(n^3)$ offline bit complexity in our first protocol and reduces it to $O(n^2)$ at the cost of increasing the online bit complexity to also $O(n^2)$.