IEICE TRANSACTIONS on Fundamentals
Constant-Round Client-Aided Two-Server Secure Comparison Protocol and Its Applications
Summary :
We present an improved constant-round secure two-party protocol for integer comparison functionality, which is one of the most fundamental building blocks in secure computation. Our protocol is in the so-called client-server model, which is utilized in real-world MPC products such as Sharemind, where any number of clients can create shares of their input and distribute to the servers who then jointly compute over the shares and return the shares of the result to the client. In the client-aided client-server model, as mentioned briefly by Mohassel and Zhang (S&P'17), a client further generates and distributes some necessary correlated randomness to servers. Such correlated randomness admits efficient protocols since otherwise, servers have to jointly generate randomness by themselves, which can be inefficient. In this paper, we improve the state-of-the-art constant-round comparison protocols by Damgå rd et al. (TCC'06) and Nishide and Ohta (PKC'07) in the client-aided model. Our techniques include identifying correlated randomness in these comparison protocols. Along the way, we also use tree-based techniques for a building block, which deviate from the above two works. Our proposed protocol requires only 5 communication rounds, regardless of the bit length of inputs. This is at least 5 times fewer rounds than existing protocols. We implement our secure comparison protocol in C++. Our experimental results show that this low-round complexity benefits in high-latency networks such as WAN. We also present secure Min/Argmin protocols using the secure comparison protocol.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E103-A No.1 pp.21-32
- Publication Date
- 2020/01/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.2019CIP0023
- Type of Manuscript
- Special Section PAPER (Special Section on Cryptography and Information Security)
- Category
Authors
Hiraku MORITA
the AIST
Nuttapong ATTRAPADUNG
the AIST
Tadanori TERUYA
the AIST
Satsuya OHATA
the AIST
Koji NUIDA
The University of Tokyo
Goichiro HANAOKA
the 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
Hiraku MORITA, Nuttapong ATTRAPADUNG, Tadanori TERUYA, Satsuya OHATA, Koji NUIDA, Goichiro HANAOKA, "Constant-Round Client-Aided Two-Server Secure Comparison Protocol and Its Applications" in IEICE TRANSACTIONS on Fundamentals,
vol. E103-A, no. 1, pp. 21-32, January 2020, doi: 10.1587/transfun.2019CIP0023.
Abstract: We present an improved constant-round secure two-party protocol for integer comparison functionality, which is one of the most fundamental building blocks in secure computation. Our protocol is in the so-called client-server model, which is utilized in real-world MPC products such as Sharemind, where any number of clients can create shares of their input and distribute to the servers who then jointly compute over the shares and return the shares of the result to the client. In the client-aided client-server model, as mentioned briefly by Mohassel and Zhang (S&P'17), a client further generates and distributes some necessary correlated randomness to servers. Such correlated randomness admits efficient protocols since otherwise, servers have to jointly generate randomness by themselves, which can be inefficient. In this paper, we improve the state-of-the-art constant-round comparison protocols by Damgå rd et al. (TCC'06) and Nishide and Ohta (PKC'07) in the client-aided model. Our techniques include identifying correlated randomness in these comparison protocols. Along the way, we also use tree-based techniques for a building block, which deviate from the above two works. Our proposed protocol requires only 5 communication rounds, regardless of the bit length of inputs. This is at least 5 times fewer rounds than existing protocols. We implement our secure comparison protocol in C++. Our experimental results show that this low-round complexity benefits in high-latency networks such as WAN. We also present secure Min/Argmin protocols using the secure comparison protocol.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2019CIP0023/_p
Copy
@ARTICLE{e103-a_1_21,
author={Hiraku MORITA, Nuttapong ATTRAPADUNG, Tadanori TERUYA, Satsuya OHATA, Koji NUIDA, Goichiro HANAOKA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Constant-Round Client-Aided Two-Server Secure Comparison Protocol and Its Applications},
year={2020},
volume={E103-A},
number={1},
pages={21-32},
abstract={We present an improved constant-round secure two-party protocol for integer comparison functionality, which is one of the most fundamental building blocks in secure computation. Our protocol is in the so-called client-server model, which is utilized in real-world MPC products such as Sharemind, where any number of clients can create shares of their input and distribute to the servers who then jointly compute over the shares and return the shares of the result to the client. In the client-aided client-server model, as mentioned briefly by Mohassel and Zhang (S&P'17), a client further generates and distributes some necessary correlated randomness to servers. Such correlated randomness admits efficient protocols since otherwise, servers have to jointly generate randomness by themselves, which can be inefficient. In this paper, we improve the state-of-the-art constant-round comparison protocols by Damgå rd et al. (TCC'06) and Nishide and Ohta (PKC'07) in the client-aided model. Our techniques include identifying correlated randomness in these comparison protocols. Along the way, we also use tree-based techniques for a building block, which deviate from the above two works. Our proposed protocol requires only 5 communication rounds, regardless of the bit length of inputs. This is at least 5 times fewer rounds than existing protocols. We implement our secure comparison protocol in C++. Our experimental results show that this low-round complexity benefits in high-latency networks such as WAN. We also present secure Min/Argmin protocols using the secure comparison protocol.},
keywords={},
doi={10.1587/transfun.2019CIP0023},
ISSN={1745-1337},
month={January},}
Copy
TY - JOUR
TI - Constant-Round Client-Aided Two-Server Secure Comparison Protocol and Its Applications
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 21
EP - 32
AU - Hiraku MORITA
AU - Nuttapong ATTRAPADUNG
AU - Tadanori TERUYA
AU - Satsuya OHATA
AU - Koji NUIDA
AU - Goichiro HANAOKA
PY - 2020
DO - 10.1587/transfun.2019CIP0023
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E103-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2020
AB - We present an improved constant-round secure two-party protocol for integer comparison functionality, which is one of the most fundamental building blocks in secure computation. Our protocol is in the so-called client-server model, which is utilized in real-world MPC products such as Sharemind, where any number of clients can create shares of their input and distribute to the servers who then jointly compute over the shares and return the shares of the result to the client. In the client-aided client-server model, as mentioned briefly by Mohassel and Zhang (S&P'17), a client further generates and distributes some necessary correlated randomness to servers. Such correlated randomness admits efficient protocols since otherwise, servers have to jointly generate randomness by themselves, which can be inefficient. In this paper, we improve the state-of-the-art constant-round comparison protocols by Damgå rd et al. (TCC'06) and Nishide and Ohta (PKC'07) in the client-aided model. Our techniques include identifying correlated randomness in these comparison protocols. Along the way, we also use tree-based techniques for a building block, which deviate from the above two works. Our proposed protocol requires only 5 communication rounds, regardless of the bit length of inputs. This is at least 5 times fewer rounds than existing protocols. We implement our secure comparison protocol in C++. Our experimental results show that this low-round complexity benefits in high-latency networks such as WAN. We also present secure Min/Argmin protocols using the secure comparison protocol.
ER -
English
