A High Throughput BFV-Encryption-Based Secure Comparison Protocol

Tzu-Hsiang Kuo and Ja-Ling Wu ()
Additional contact information
Tzu-Hsiang Kuo: Department of Computer Science & Information Engineering, National Taiwan University, Taipei 106, Taiwan
Ja-Ling Wu: Department of Computer Science & Information Engineering, National Taiwan University, Taipei 106, Taiwan

Mathematics, 2023, vol. 11, issue 5, 1-28

Abstract: 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.

Keywords: secure comparison; multi-party computation; fully homomorphic encryption; Secure Auction; ring learning with error (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/5/1227/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/5/1227/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:5:p:1227-:d:1086149

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().