A Taxonomy of Secure Two-Party Comparison Protocols and Efficient Constructions

Nuttapong ATTRAPADUNG  Goichiro HANAOKA  Shinsaku KIYOMOTO  Tomoaki MIMOTO  Jacob C. N. SCHULDT  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E102-A   No.9   pp.1048-1060
Publication Date: 2019/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E102.A.1048
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: Cryptography and Information Security
Keyword: 
secure two-party computation,  semi-honest model,  comparison protocols,  conversions,  shared inputs/outputs,  encrypted inputs/outputs,  

Full Text: PDF(1.1MB)>>
Buy this Article




Summary: 
Secure two-party comparison plays a crucial role in many privacy-preserving applications, such as privacy-preserving data mining and machine learning. In particular, the available comparison protocols with the appropriate input/output configuration have a significant impact on the performance of these applications. In this paper, we firstly describe a taxonomy of secure two-party comparison protocols which allows us to describe the different configurations used for these protocols in a systematic manner. This taxonomy leads to a total of 216 types of comparison protocols. We then describe conversions among these types. While these conversions are based on known techniques and have explicitly or implicitly been considered previously, we show that a combination of these conversion techniques can be used to convert a perhaps less-known two-party comparison protocol by Nergiz et al. (IEEE SocialCom 2010) into a very efficient protocol in a configuration where the two parties hold shares of the values being compared, and obtain a share of the comparison result. This setting is often used in multi-party computation protocols, and hence in many privacy-preserving applications as well. We furthermore implement the protocol and measure its performance. Our measurement suggests that the protocol outperforms the previously proposed protocols for this input/output configuration, when off-line pre-computation is not permitted.