Paper 2026/808

New Techniques for Communication-Efficient Secure Comparison Protocols

Satsuya Ohata, Kyushu University, Byerlis Inc.

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)$. Furthermore, for the purpose of optimization in bandwidth, we propose the third (not constant-round) protocol with asymptotically $6n$ online bit complexity, which is significantly lower than asymptotically $8n$ bits of the state-of-the-art protocol (Couteau, ACNS 2018). Our protocol adopts the framework based on ternary trees and quaternary integers of CrypTFlow2 (ACM CCS 2020) and its followers, but departs from their oblivious-transfer-based computation at each input digit. Instead, we use a Boolean-circuit-based approach driven by a new custom-tailored formula for processing quaternary integers and a specialized multiplication protocol. The latter technique of "multiplication involving an auxiliary input held by a single party'' may be of independent interest.