Full Text Views
25
Integer division is one of the most fundamental arithmetic operators and is ubiquitously used. However, the existing division protocols in secure multi-party computation (MPC) are inefficient and very complex, and this has been a barrier to applications of MPC such as secure machine learning. We already have some secure division protocols working in Z2n. However, these existing results have drawbacks that those protocols needed many communication rounds and needed to use bigger integers than in/output. In this paper, we improve a secure division protocol in two ways. First, we construct a new protocol using only the same size integers as in/output. Second, we build efficient constant-round building blocks used as subprotocols in the division protocol. With these two improvements, communication rounds of our division protocol are reduced to about 36% (87 rounds → 31 rounds) for 64-bit integers in comparison with the most efficient previous one.
Keitaro HIWATASHI
The University of Tokyo,the National Institute of Advanced Industrial Science and Technology
Satsuya OHATA
Digital Garage, Inc.
Koji NUIDA
the National Institute of Advanced Industrial Science and Technology,Kyushu University
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.
Copy
Keitaro HIWATASHI, Satsuya OHATA, Koji NUIDA, "An Efficient Secure Division Protocol Using Approximate Multi-Bit Product and New Constant-Round Building Blocks" in IEICE TRANSACTIONS on Fundamentals,
vol. E105-A, no. 3, pp. 404-416, March 2022, doi: 10.1587/transfun.2021TAP0004.
Abstract: Integer division is one of the most fundamental arithmetic operators and is ubiquitously used. However, the existing division protocols in secure multi-party computation (MPC) are inefficient and very complex, and this has been a barrier to applications of MPC such as secure machine learning. We already have some secure division protocols working in Z2n. However, these existing results have drawbacks that those protocols needed many communication rounds and needed to use bigger integers than in/output. In this paper, we improve a secure division protocol in two ways. First, we construct a new protocol using only the same size integers as in/output. Second, we build efficient constant-round building blocks used as subprotocols in the division protocol. With these two improvements, communication rounds of our division protocol are reduced to about 36% (87 rounds → 31 rounds) for 64-bit integers in comparison with the most efficient previous one.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2021TAP0004/_p
Copy
@ARTICLE{e105-a_3_404,
author={Keitaro HIWATASHI, Satsuya OHATA, Koji NUIDA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Efficient Secure Division Protocol Using Approximate Multi-Bit Product and New Constant-Round Building Blocks},
year={2022},
volume={E105-A},
number={3},
pages={404-416},
abstract={Integer division is one of the most fundamental arithmetic operators and is ubiquitously used. However, the existing division protocols in secure multi-party computation (MPC) are inefficient and very complex, and this has been a barrier to applications of MPC such as secure machine learning. We already have some secure division protocols working in Z2n. However, these existing results have drawbacks that those protocols needed many communication rounds and needed to use bigger integers than in/output. In this paper, we improve a secure division protocol in two ways. First, we construct a new protocol using only the same size integers as in/output. Second, we build efficient constant-round building blocks used as subprotocols in the division protocol. With these two improvements, communication rounds of our division protocol are reduced to about 36% (87 rounds → 31 rounds) for 64-bit integers in comparison with the most efficient previous one.},
keywords={},
doi={10.1587/transfun.2021TAP0004},
ISSN={1745-1337},
month={March},}
Copy
TY - JOUR
TI - An Efficient Secure Division Protocol Using Approximate Multi-Bit Product and New Constant-Round Building Blocks
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 404
EP - 416
AU - Keitaro HIWATASHI
AU - Satsuya OHATA
AU - Koji NUIDA
PY - 2022
DO - 10.1587/transfun.2021TAP0004
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E105-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 2022
AB - Integer division is one of the most fundamental arithmetic operators and is ubiquitously used. However, the existing division protocols in secure multi-party computation (MPC) are inefficient and very complex, and this has been a barrier to applications of MPC such as secure machine learning. We already have some secure division protocols working in Z2n. However, these existing results have drawbacks that those protocols needed many communication rounds and needed to use bigger integers than in/output. In this paper, we improve a secure division protocol in two ways. First, we construct a new protocol using only the same size integers as in/output. Second, we build efficient constant-round building blocks used as subprotocols in the division protocol. With these two improvements, communication rounds of our division protocol are reduced to about 36% (87 rounds → 31 rounds) for 64-bit integers in comparison with the most efficient previous one.
ER -