Computer Engineering and Applications Journal

Fair and efficient protocol for secure two-party comparing under semi-honest model

Liang Chen, Gao Cheng-min

Published Jan 1, 2010• 2 citations

Abstract

The essential of Yao’s millionaire problem is securely comparing two numbers,which is a basic building block of secure computations and has many important applications in e-commerce,such as bidding,auction and so on.But known solutions have some disadvantagesf,or example expensive costs of computing and communicatingl,imited ranges of compared numbers.This paper proposes a modified ElGamal algorithm,based on which multiplicative and subtractive homomorphic cryp-tosystem is presented and proved.Based on the homomorphic cryptosystem,Fair and Efficient Protocol for Secure Two-party Comparing(FEPSTC) under semi-honest model is constructed.The main properties of the FEPSTC are securityf,airnessl,ower costs of communication and computational complexity,and comparing real numbers.They are proved and illustrated by an ex-ample and by comparing with other protocols.

Related papers

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 yanjiuJan 1, 20100 citations

Improved Protocol of Yao’s Millionaires Problem

Huiqiang Li, Zhengtao Jiang, Ting Yu +1 more

Secure multi-party computation is a hot research topic in cryptography in recent years, and has become an important research direction in cryptography. This paper studies the millionaires’ problem in secure multi-party computation, and its essence is a comparison issue about the size of two encrypted data. Yao offered a solution to the millionaires’ problem, but his protocol can’t accurately compare two numbers. We improved Yao’s protocol and proposed two generic protocols to solve the millionaires’ problem. Our first protocol has one more round of communication between participants than Yao’s, but our protocol can accurately compare the size of two numbers. The second protocol improved the first protocol, and only one round of communication is needed to get accurate comparison results. Finally, we realized the second protocol based on RSA encryption algorithm, and analyze the security under the semi-honest model.

IEEE/ACIS International Conference on Computer and Information Science (ICIS)Jun 26, 20222 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 AccessJan 1, 20212 citations

Efficient Fair Secure Two-Party Computation

Ou Ruan, Zhou Jing, Minghui Zheng +1 more

Yao first introduced a constant-round protocol for secure two-party computation (2PC) withstanding semi-honest adversaries by using a tool called "garbled circuit". Later, many protocols based on garbled circuit approach have been presented, most of which discussed malicious adversaries and efficiency about 2PC. However, there only have a few protocols dealing with the fundamental property of fairness for Yao's garbled circuit approach, in which one involved a trusted third party and the others are very expensive. In the paper, we propose' an efficient Yao's garbled circuit protocol for fair secure 2PC based on ElGamal encryption, Pedersen commitment, Cachin et al.'s verifiable oblivious transfer and Ou-Ruan et al.'s gradual release homomorphic timed commitment. The protocol achieves two advantages: it doesn't need the third party and it is more efficient than other fair secure Yao's protocols.

IEEE Asia-Pacific Services Computing Conference (APSCC)Dec 1, 20125 citations

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 TechnologiesDec 1, 201110 citations

Some Efficient Solutions to Yao's Millionaire Problem

Ashish Kumar, Anupam Gupta

We present three simple and efficient protocol constructions to solve Yao's Millionaire Problem when the parties involved are non-colluding and semi-honest. The first construction uses a partially homomorphic Encryption Scheme and is a 4-round scheme using 2 encryptions, 2 homomorphic circuit evaluations (subtraction and XOR) and a single decryption. The second construction uses an untrusted third party and achieves a communication overhead linear in input bit-size with the help of an order preserving function.Moreover, the second construction does not require an apriori input bound and can work on inputs of different bit-sizes. The third construction does not use a third party and, even though, it has a quadratic communication overhead, it is a fairly simple construction.

arXiv:1310.8063Oct 30, 20135 citations