Reducing Communication Complexity of Random Number Bitwise-Sharing for Efficient Multi-party Computation

• Item type: Journal(1)
• 公開日: 2012-08-15
• タイトル: Reducing Communication Complexity of Random Number Bitwise-Sharing for Efficient Multi-party Computation
• タイトル / 言語: en
• タイトル: Reducing Communication Complexity of Random Number Bitwise-Sharing for Efficient Multi-party Computation
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [一般論文] multi-party computation, secret sharing, Random Number Bitwise-Sharing
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: The University of Electro-Communications／Presently with NTT Secure Platform Laboratories
• 著者所属: The University of Electro-Communications
• 著者所属: Kyushu University
• 著者所属: Toshiba Corporation
• 著者所属: The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): The University of Electro-Communications / Presently with NTT Secure Platform Laboratories
• 著者所属(英): en
• 著者所属(英): The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Kyushu University
• 著者所属(英): en
• 著者所属(英): Toshiba Corporation
• 著者所属(英): en
• 著者所属(英): The University of Electro-Communications
• 著者名: Naoto, Kiribuchi; Ryo, Kato; Takashi, Nishide; Tsukasa, Endo; Hiroshi, Yoshiura
• 著者名(英): Naoto, Kiribuchi; Ryo, Kato; Takashi, Nishide; Tsukasa, Endo; Hiroshi, Yoshiura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: It is becoming more and more important to make use of personal or classified information while keeping it confidential. A promising tool for meeting this challenge is secure multi-party computation (MPC). However, one of the biggest problems with MPC is that it requires a vast amount of communication. We analyzed existing MPC protocols and found that the random number bitwise-sharing protocol used by many of them is notably inefficient. By devising a representation of the truth values and using special form prime numbers, we propose efficient random number bitwise-sharing protocols, dubbed “Extended-Range Ⅰ and Ⅱ,” which reduce the communication complexity to approximately 1/6th that of the best of the existing such protocol. We reduced the communication complexity to approximately 1/26th by reducing the abort probability, thereby making previously necessary backup computation unnecessary. Using our improved protocol, “Lightweight Extended-Range Ⅱ,” we reduced the communication complexities of equality testing, comparison, interval testing, and bit-decomposition, all of which use the random number bitwise-sharing protocol, by approximately 91, 79, 67, and 23% (for 32-bit data), respectively. We also reduce the communication complexity of private exponentiation by about 70% (for 32-bit data and five parties).; ------------------------------; This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.20(2012) No.4 (online); DOI http://dx.doi.org/10.2197/ipsjjip.20.861; ------------------------------
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: It is becoming more and more important to make use of personal or classified information while keeping it confidential. A promising tool for meeting this challenge is secure multi-party computation (MPC). However, one of the biggest problems with MPC is that it requires a vast amount of communication. We analyzed existing MPC protocols and found that the random number bitwise-sharing protocol used by many of them is notably inefficient. By devising a representation of the truth values and using special form prime numbers, we propose efficient random number bitwise-sharing protocols, dubbed “Extended-Range Ⅰ and Ⅱ,” which reduce the communication complexity to approximately 1/6th that of the best of the existing such protocol. We reduced the communication complexity to approximately 1/26th by reducing the abort probability, thereby making previously necessary backup computation unnecessary. Using our improved protocol, “Lightweight Extended-Range Ⅱ,” we reduced the communication complexities of equality testing, comparison, interval testing, and bit-decomposition, all of which use the random number bitwise-sharing protocol, by approximately 91, 79, 67, and 23% (for 32-bit data), respectively. We also reduce the communication complexity of private exponentiation by about 70% (for 32-bit data and five parties).; ------------------------------; This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.20(2012) No.4 (online); DOI http://dx.doi.org/10.2197/ipsjjip.20.861; ------------------------------
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 53, 号 8, 発行日 2012-08-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764