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 l -bit integer, denoted by a and b , respectively. The goal of secure comparison is to compute the order relationship between a and b , say ( a > b ) ∈ { 0 , 1 } , without revealing their inputs to any others. Since previous solutions based on homomorphic encryption need at least Ω ( l ) encryptions for each l -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 O ˜ ( λ + l ) 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 l ⋅ k − 1 -bit integers with almost the same execution time as comparing l -bit integers and achieve higher throughput regardless of the compared integer size.