An Efficient Secure Division Protocol Using Approximate Multi-bit Product and New Constant-Round Building Blocks

Keitaro Hiwatashi; Satsuya Ohata; Koji Nuida

doi:10.1007/978-3-030-57808-4_18

An Efficient Secure Division Protocol Using Approximate Multi-bit Product and New Constant-Round Building Blocks

Keitaro Hiwatashi, Satsuya Ohata, Koji Nuida

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Citations (Scopus)

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. 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.

Original language	English
Title of host publication	Applied Cryptography and Network Security - 18th International Conference, ACNS 2020, Proceedings
Editors	Mauro Conti, Jianying Zhou, Emiliano Casalicchio, Angelo Spognardi
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	357-376
Number of pages	20
ISBN (Print)	9783030578077
DOIs	https://doi.org/10.1007/978-3-030-57808-4_18
Publication status	Published - 2020
Externally published	Yes
Event	18th International Conference on Applied Cryptography and Network Security, ACNS 2020 - Rome, Italy Duration: Oct 19 2020 → Oct 22 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12146 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	18th International Conference on Applied Cryptography and Network Security, ACNS 2020
Country/Territory	Italy
City	Rome
Period	10/19/20 → 10/22/20

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-57808-4_18

Cite this

Hiwatashi, K., Ohata, S., & Nuida, K. (2020). An Efficient Secure Division Protocol Using Approximate Multi-bit Product and New Constant-Round Building Blocks. In M. Conti, J. Zhou, E. Casalicchio, & A. Spognardi (Eds.), Applied Cryptography and Network Security - 18th International Conference, ACNS 2020, Proceedings (pp. 357-376). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12146 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-57808-4_18

An Efficient Secure Division Protocol Using Approximate Multi-bit Product and New Constant-Round Building Blocks. / Hiwatashi, Keitaro; Ohata, Satsuya; Nuida, Koji.
Applied Cryptography and Network Security - 18th International Conference, ACNS 2020, Proceedings. ed. / Mauro Conti; Jianying Zhou; Emiliano Casalicchio; Angelo Spognardi. Springer Science and Business Media Deutschland GmbH, 2020. p. 357-376 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12146 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Hiwatashi, K, Ohata, S & Nuida, K 2020, An Efficient Secure Division Protocol Using Approximate Multi-bit Product and New Constant-Round Building Blocks. in M Conti, J Zhou, E Casalicchio & A Spognardi (eds), Applied Cryptography and Network Security - 18th International Conference, ACNS 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12146 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 357-376, 18th International Conference on Applied Cryptography and Network Security, ACNS 2020, Rome, Italy, 10/19/20. https://doi.org/10.1007/978-3-030-57808-4_18

Hiwatashi K, Ohata S, Nuida K. An Efficient Secure Division Protocol Using Approximate Multi-bit Product and New Constant-Round Building Blocks. In Conti M, Zhou J, Casalicchio E, Spognardi A, editors, Applied Cryptography and Network Security - 18th International Conference, ACNS 2020, Proceedings. Springer Science and Business Media Deutschland GmbH. 2020. p. 357-376. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-57808-4_18

Hiwatashi, Keitaro ; Ohata, Satsuya ; Nuida, Koji. / An Efficient Secure Division Protocol Using Approximate Multi-bit Product and New Constant-Round Building Blocks. Applied Cryptography and Network Security - 18th International Conference, ACNS 2020, Proceedings. editor / Mauro Conti ; Jianying Zhou ; Emiliano Casalicchio ; Angelo Spognardi. Springer Science and Business Media Deutschland GmbH, 2020. pp. 357-376 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{328e88b663da477c9c5a4e0e1ea3ebf5,

title = "An Efficient Secure Division Protocol Using Approximate Multi-bit Product and New Constant-Round Building Blocks",

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. 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.",

author = "Keitaro Hiwatashi and Satsuya Ohata and Koji Nuida",

note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.; 18th International Conference on Applied Cryptography and Network Security, ACNS 2020 ; Conference date: 19-10-2020 Through 22-10-2020",

year = "2020",

doi = "10.1007/978-3-030-57808-4_18",

language = "English",

isbn = "9783030578077",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "357--376",

editor = "Mauro Conti and Jianying Zhou and Emiliano Casalicchio and Angelo Spognardi",

booktitle = "Applied Cryptography and Network Security - 18th International Conference, ACNS 2020, Proceedings",

address = "Germany",

}

TY - GEN

T1 - An Efficient Secure Division Protocol Using Approximate Multi-bit Product and New Constant-Round Building Blocks

AU - Hiwatashi, Keitaro

AU - Ohata, Satsuya

AU - Nuida, Koji

PY - 2020

Y1 - 2020

N2 - 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. 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.

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. 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.

UR - http://www.scopus.com/inward/record.url?scp=85091306665&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85091306665&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-57808-4_18

DO - 10.1007/978-3-030-57808-4_18

M3 - Conference contribution

AN - SCOPUS:85091306665

SN - 9783030578077

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 357

EP - 376

BT - Applied Cryptography and Network Security - 18th International Conference, ACNS 2020, Proceedings

A2 - Conti, Mauro

A2 - Zhou, Jianying

A2 - Casalicchio, Emiliano

A2 - Spognardi, Angelo

PB - Springer Science and Business Media Deutschland GmbH

T2 - 18th International Conference on Applied Cryptography and Network Security, ACNS 2020

Y2 - 19 October 2020 through 22 October 2020

ER -

An Efficient Secure Division Protocol Using Approximate Multi-bit Product and New Constant-Round Building Blocks

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this