Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Secure Comparison Protocol with Encrypted Output and the Computation for Proceeding 2 Bits-by-2 Bits

Takumi Kobayashi, Keisuke Hakuta

Published Jan 1, 2019• 1 citation
Publisher
DOI
10.1007/978-3-030-17982-3_17

Related papers

A Generalization of Secure Comparison Protocol with Encrypted Output and Its Efficiency Estimation

Takumi Kobayashi, Keisuke Hakuta

Lecture notes in networks and systems•Sep 16, 2021•0 citations

A High Throughput BFV-Encryption-Based Secure Comparison Protocol

Tzu-Hsiang Kuo, Ja‐Ling Wu

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.

Mathematics•Mar 2, 2023•4 citations

A Secure Comparison Protocol Based on the SM2 Homomorphic Encryption Algorithm

Xiao Deng, Shutong Li, Yuxin Li +1 more

International Conference on Cryptography, Network Security and Communication Technology (CNSCT)•Jan 23, 2026•0 citations

Efficient Two-Party Integer Comparison With Block Vectorization Mechanism

Thai-Hung Nguyen, Kok‐Seng Wong, Thomas Oikonomou

Private integer comparison has been an essential computation function for many applications, including online auction, credential identification, data mining, and joint bidding. In the setting of two-party computation, two parties with private inputs (x and y) want to jointly compare them without revealing the value of those inputs to others (also known as the Millionaires’ problem) while the output should ensure correctness and preserve data privacy. The private inputs only can be revealed if they are equal, i.e., x = y. Many related works have been proposed to solve the integer comparison problem in various settings, focusing on different properties such as round and computation complexity. Most solutions decompose integers into bitwise representation and then securely evaluate the function in a Boolean circuit on encrypted bits. However, this type of solution is costly (especially for large integers) as each bit requires encryption and decryption. In this paper, we transform the private integer comparison into a block comparison problem. In particular, we employ a block vectorization mechanism to encode the private inputs into blocks. We show the security of our two-party protocol in the semi-honest model. Also, we implement the protocol to demonstrate its efficiency using block vectorization mechanism and homomorphic encryption. The experimental result proves that our proposed solution achieves high efficiency, particularly for large integer comparisons.

IEEE Access•Jan 1, 2021•2 citations

Client-Aided Bit-Composition Protocol with Guaranteed Output Delivery

Hikaru Tsuchida, Takashi Nishide

Secure multiparty computation (MPC) enables par-ties to compute an arbitrary function without revealing each party’s inputs. A typical MPC is the secret sharing based MPC (SS-MPC). In the SS-MPC, each party distributes its inputs, and the computation proceeds with secret shares that just look like random numbers distributed among the parties. In the SS-MPC protocol, the parties can compute any function represented as a circuit by using shares locally and communicating among the parties. In particular, when the parties compute a complex function composed of binary and arithmetic circuits, an efficient share conversion protocol facilitates the computation of it. An important conversion protocol is the bit-composition protocol that converts a k-dimensional vector with the shares on Z 2 (i.e., shares of binary sequence) to the shares on Z 2 k (i.e., shares of decimal value). The previous work proposed a maliciously secure bit-composition protocol with guaranteed output delivery (GOD), which is the security notion that all the parties learn the correct output regardless of the attacker’s behaviour. However, its security is proved in the random oracle model.In this paper, we propose a new bit-composition protocol with GOD by introducing additional clients just helping the parties during computation. Our protocol is based on a maliciously secure four-party protocol with one corruption using replicated secret sharing. The security of our protocol is proved in the standard model (which is weaker than the random oracle model). Our protocol achieves the efficiency and strongest security simultaneously. We also propose a protocol for the Hamming distance with GOD by modifying our bit-composition protocol. It achieves a secure iris recognition service via MPC with GOD.

International Symposium on Information Theory and its Applications•Oct 24, 2020•0 citations

Secure Multi-party Comparison Protocol and Application

Jing Zhang, Shoushan Luo, Yixian Yang

Communications in computer and information science•Jan 1, 2017•1 citation
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.
Private integer comparison has been an essential computation function for many applications, including online auction, credential identification, data mining, and joint bidding. In the setting of two-party computation, two parties with private inputs (x and y) want to jointly compare them without revealing the value of those inputs to others (also known as the Millionaires’ problem) while the output should ensure correctness and preserve data privacy. The private inputs only can be revealed if they are equal, i.e., x = y. Many related works have been proposed to solve the integer comparison problem in various settings, focusing on different properties such as round and computation complexity. Most solutions decompose integers into bitwise representation and then securely evaluate the function in a Boolean circuit on encrypted bits. However, this type of solution is costly (especially for large integers) as each bit requires encryption and decryption. In this paper, we transform the private integer comparison into a block comparison problem. In particular, we employ a block vectorization mechanism to encode the private inputs into blocks. We show the security of our two-party protocol in the semi-honest model. Also, we implement the protocol to demonstrate its efficiency using block vectorization mechanism and homomorphic encryption. The experimental result proves that our proposed solution achieves high efficiency, particularly for large integer comparisons.
Secure multiparty computation (MPC) enables par-ties to compute an arbitrary function without revealing each party’s inputs. A typical MPC is the secret sharing based MPC (SS-MPC). In the SS-MPC, each party distributes its inputs, and the computation proceeds with secret shares that just look like random numbers distributed among the parties. In the SS-MPC protocol, the parties can compute any function represented as a circuit by using shares locally and communicating among the parties. In particular, when the parties compute a complex function composed of binary and arithmetic circuits, an efficient share conversion protocol facilitates the computation of it. An important conversion protocol is the bit-composition protocol that converts a k-dimensional vector with the shares on Z 2 (i.e., shares of binary sequence) to the shares on Z 2 k (i.e., shares of decimal value). The previous work proposed a maliciously secure bit-composition protocol with guaranteed output delivery (GOD), which is the security notion that all the parties learn the correct output regardless of the attacker’s behaviour. However, its security is proved in the random oracle model.In this paper, we propose a new bit-composition protocol with GOD by introducing additional clients just helping the parties during computation. Our protocol is based on a maliciously secure four-party protocol with one corruption using replicated secret sharing. The security of our protocol is proved in the standard model (which is weaker than the random oracle model). Our protocol achieves the efficiency and strongest security simultaneously. We also propose a protocol for the Hamming distance with GOD by modifying our bit-composition protocol. It achieves a secure iris recognition service via MPC with GOD.