IEICE TRANSACTIONS on Fundamentals
A Taxonomy of Secure Two-Party Comparison Protocols and Efficient Constructions
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.9 pp.1048-1060
- Publication Date
- 2019/09/01
- Publicized
- 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
Authors
Nuttapong ATTRAPADUNG
National Institute of Advanced Industrial Science and Technology (AIST)
Goichiro HANAOKA
National Institute of Advanced Industrial Science and Technology (AIST)
Shinsaku KIYOMOTO
KDDI Research, Inc
Tomoaki MIMOTO
KDDI Research, Inc
Jacob C. N. SCHULDT
National Institute of Advanced Industrial Science and Technology (AIST)
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Nuttapong ATTRAPADUNG, Goichiro HANAOKA, Shinsaku KIYOMOTO, Tomoaki MIMOTO, Jacob C. N. SCHULDT, "A Taxonomy of Secure Two-Party Comparison Protocols and Efficient Constructions" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 9, pp. 1048-1060, September 2019, doi: 10.1587/transfun.E102.A.1048.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.1048/_p
Copy
@ARTICLE{e102-a_9_1048,
author={Nuttapong ATTRAPADUNG, Goichiro HANAOKA, Shinsaku KIYOMOTO, Tomoaki MIMOTO, Jacob C. N. SCHULDT, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Taxonomy of Secure Two-Party Comparison Protocols and Efficient Constructions},
year={2019},
volume={E102-A},
number={9},
pages={1048-1060},
abstract={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.},
keywords={},
doi={10.1587/transfun.E102.A.1048},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - A Taxonomy of Secure Two-Party Comparison Protocols and Efficient Constructions
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1048
EP - 1060
AU - Nuttapong ATTRAPADUNG
AU - Goichiro HANAOKA
AU - Shinsaku KIYOMOTO
AU - Tomoaki MIMOTO
AU - Jacob C. N. SCHULDT
PY - 2019
DO - 10.1587/transfun.E102.A.1048
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E102-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2019
AB - 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.
ER -
English
