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

IEEE International Workshop on Information Forensics and Security

Improving the DGK comparison protocol

Thijs Veugen

Published Dec 1, 2012• 63 citations
Publisher

Abstract

When processing signals in the encrypted domain, homomorphic encryption can be used to enable linear operations on encrypted data. Comparison of encrypted data however requires an additional protocol between the parties and will be relatively expensive. A well-known and frequently used comparison protocol is by Damgard, Geisler and Kroigaard. We present two ways of improving this comparison protocol. Firstly, we reduce the computational effort of one party by roughly 50%. Secondly, we show how to achieve perfect security towards the other party without additional costs, whereas the original version with encrypted inputs only achieved statistical security. An additional advantage is that larger inputs are allowed.

DOI
10.1109/wifs.2012.6412624

Related papers

A Secure Comparison Protocol in the Malicious Model

Junhong Tao, Yongtang Wu, Yuling Chen

Secure comparison is an important problem in the field of secure computing. A classic example is the Millionaires' problem, which is securely compares the wealth of two millionaires without revealing their wealth. However most traditional secure comparison protocol requires autonomous computation among the participants. It is necessary to ensure that the model of the participants is a semi-honest model, otherwise the protocol will not be able to execute correctly. In this paper, we introduce a semi-honest judge to improve the Damgård-Geisler-KrØigaard(DGK) comparison protocol by using techniques such as zero-knowledge proof and homomorphic encryption. The improved protocol is not only applicable to the malicious participant model, but also the introduced judge would not get any information of data. At last, the security analysis shows that the proposed scheme in this paper can guarantee the data fairness of the comparison protocol while ensuring the privacy security of the participants.

IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData)•Aug 1, 2022•1 citation

Secure two party comparison over encrypted data

Parisa Kaghazgaran, Sadeghyan Babak

Yao's classical millionaires' problem is about securely determining whether x>y, given two input values x, y, which are held as private inputs by two parties, respectively. The output which is result of comparison becomes known to both parties. In this paper we consider a variant of comparison problem in which the inputs x, y are encrypted and the actual values are not known to the parties. Our first solution deals with single comparison; however, in many applications, we encounter situations where it is necessary to make multiple comparisons to find the maximum among several encrypted data, so we make a modification to our first protocol to solve the multiple comparisons problem. Such a secure comparison is an important building block for applications like privacy preserving data mining and secure business. Our second protocol is based on Homomorphic encryption which achieves very low communication and computational complexities. Also our protocols can be performed in constant rounds and do not use general circuit evaluation techniques so they are more efficient than circuit based ones but not general. Implementation is easy and fast.

World Congress on Information and Communication Technologies•Dec 1, 2011•10 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

Enhancing security for two-party comparison over encrypted data

Ching‐Nung Yang, Zong-Xuan Yeh, Shen-Chieh Hsu +1 more

The so-called Yao's millionaire problem (YMP) is about securely comparing two numbers held by two parties, respectively. After comparison, the actual values of these two numbers are still unknown to both parties. Recently, Kaghazgaran and Sadeghyan propose a variant of YMP, the two-party multiple comparison (TPMC) protocol, that determines the greatest one over multiple (more than two) encrypted data between two parties. However, in Kaghazgaran and Sadeghyan's TPMC (KS-TPMC) protocol, one of two parties may guess the original data with a probability. In this paper, we introduce a new TPMC protocol to enhance the security by reducing this guess probability, and meanwhile has the same computation cost compared with KS-TPMC protocol. Additionally, the proposed TPMC protocol is more effective on reducing the attack probability for the large number of encrypted data. Thus, our TPMC protocol is suitable for applications on multiple comparison over encrypted data.

International Conference on Systems and Informatics (ICSAI)•Nov 1, 2016•2 citations

Secure two-party comparing protocol based on evaluation of encrypted functions

Liang Chen, Yong Xu

Secure two-party comparing is a special case and a basic module of secure computations,and is applied in mobile code and e-commerce security etc.But known solutions have some disadvantages:expensive costs of computing and communicating,limited ranges of compared numbers.Based on a modified ElGamal algorithm,this paper presented and proved multiplicative,mixed-multiplicative,additive and subtractive homomorphic cryptosystem.Constructed an encrypted function unknown by two-party using the homomorphic cryptosystem.Based on the homomorphic cryptosystem and evaluation of encrypted functions,designed secure two-party comparing protocol under semi-honest model.Proof,example and comparing with other protocols show the proposed protocol has the merits of security,fairness,lower costs of communication and computational complexity,and comparing integers.

Jisuanji yingyong yanjiu•Jan 1, 2010•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
When processing signals in the encrypted domain, homomorphic encryption can be used to enable linear operations on encrypted data. Comparison of encrypted data however requires an additional protocol between the parties and will be relatively expensive. A well-known and frequently used comparison protocol is by Damgard, Geisler and Kroigaard. We present two ways of improving this comparison protocol. Firstly, we reduce the computational effort of one party by roughly 50%. Secondly, we show how to achieve perfect security towards the other party without additional costs, whereas the original version with encrypted inputs only achieved statistical security. An additional advantage is that larger inputs are allowed.
Secure comparison is an important problem in the field of secure computing. A classic example is the Millionaires' problem, which is securely compares the wealth of two millionaires without revealing their wealth. However most traditional secure comparison protocol requires autonomous computation among the participants. It is necessary to ensure that the model of the participants is a semi-honest model, otherwise the protocol will not be able to execute correctly. In this paper, we introduce a semi-honest judge to improve the Damgård-Geisler-KrØigaard(DGK) comparison protocol by using techniques such as zero-knowledge proof and homomorphic encryption. The improved protocol is not only applicable to the malicious participant model, but also the introduced judge would not get any information of data. At last, the security analysis shows that the proposed scheme in this paper can guarantee the data fairness of the comparison protocol while ensuring the privacy security of the participants.
Yao's classical millionaires' problem is about securely determining whether x>y, given two input values x, y, which are held as private inputs by two parties, respectively. The output which is result of comparison becomes known to both parties. In this paper we consider a variant of comparison problem in which the inputs x, y are encrypted and the actual values are not known to the parties. Our first solution deals with single comparison; however, in many applications, we encounter situations where it is necessary to make multiple comparisons to find the maximum among several encrypted data, so we make a modification to our first protocol to solve the multiple comparisons problem. Such a secure comparison is an important building block for applications like privacy preserving data mining and secure business. Our second protocol is based on Homomorphic encryption which achieves very low communication and computational complexities. Also our protocols can be performed in constant rounds and do not use general circuit evaluation techniques so they are more efficient than circuit based ones but not general. Implementation is easy and fast.
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.
The so-called Yao's millionaire problem (YMP) is about securely comparing two numbers held by two parties, respectively. After comparison, the actual values of these two numbers are still unknown to both parties. Recently, Kaghazgaran and Sadeghyan propose a variant of YMP, the two-party multiple comparison (TPMC) protocol, that determines the greatest one over multiple (more than two) encrypted data between two parties. However, in Kaghazgaran and Sadeghyan's TPMC (KS-TPMC) protocol, one of two parties may guess the original data with a probability. In this paper, we introduce a new TPMC protocol to enhance the security by reducing this guess probability, and meanwhile has the same computation cost compared with KS-TPMC protocol. Additionally, the proposed TPMC protocol is more effective on reducing the attack probability for the large number of encrypted data. Thus, our TPMC protocol is suitable for applications on multiple comparison over encrypted data.
Secure two-party comparing is a special case and a basic module of secure computations,and is applied in mobile code and e-commerce security etc.But known solutions have some disadvantages:expensive costs of computing and communicating,limited ranges of compared numbers.Based on a modified ElGamal algorithm,this paper presented and proved multiplicative,mixed-multiplicative,additive and subtractive homomorphic cryptosystem.Constructed an encrypted function unknown by two-party using the homomorphic cryptosystem.Based on the homomorphic cryptosystem and evaluation of encrypted functions,designed secure two-party comparing protocol under semi-honest model.Proof,example and comparing with other protocols show the proposed protocol has the merits of security,fairness,lower costs of communication and computational complexity,and comparing integers.
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.