A High Throughput BFV-Encryption-Based Secure Comparison Protocol

Secure comparison is a fundamental problem in multiparty computation. There are two different parties, each holding an  (Formula presented.) -bit integer, denoted by  (Formula presented.)  and  (Formula presented.), respectively. The goal of secure comparison is to compute the order relationship between  (Formula presented.)  and  (Formula presented.), say  (Formula presented.), without revealing their inputs to any others. Since previous solutions based on homomorphic encryption need at least  (Formula presented.) encryptions for each  (Formula presented.) -bit comparison, the total encryption time leads to a computational bottleneck for these protocols. This work presents a fast, semi-honest, secure comparison protocol based on the BFV encryption scheme. With its vector-like plaintext space, the number of required encryptions can be significantly reduced; actually, only six encryptions are needed for each comparison in our protocol. In other words, the proposed protocol can achieve the time complexity  (Formula presented.) ) for a given security parameter λ. As a result, 4096-bit integers can be securely compared within 12.08 ms, which is 280 times faster than the state-of-the-art homomorphic encryption-based secure comparison protocol. Furthermore, we can compare k pairs of  (Formula presented.) -bit integers with almost the same execution time as comparing  (Formula presented.) -bit integers and achieve higher throughput regardless of the compared integer size.