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

スポンサーリンク

概要

• 論文の詳細を見る

• 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) ------------------------------

• 2012-08-15

著者

• Ryo Kato

  The University Of Electro-communications

• Naoto Kiribuchi

  The University of Electro-Communications|Presently with NTT Secure Platform Laboratories

• Takashi Nishide

  Kyushu University

• Tsukasa Endo

  Toshiba Corporation

• Hiroshi Yoshiura

  The University of Electro-Communications

関連論文

• Reducing Communication Complexity of Random Number Bitwise-Sharing for Efficient Multi-party Computation (preprint)
• Elliptic curve ElGamal Threshold-based Key Management Scheme against Compromise of Distributed RSUs for VANETs
• Evaluating payload features for malware infection detection (Preprint)

スポンサーリンク