Two-Party Computing with 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.

Nigel Paul Smart

Thijs Veugen

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.

Renren Dong

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.

Yan Huang