Accelerating Multiparty Computation by Efficient Random Number Bitwise-Sharing Protocols

Naoto Kiribuchi, Ryo Kato, Takashi Nishide, Tsukasa Endo, Hiroshi Yoshiura

Abstract

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 multiparty computation (MPC), which enables multiple parties, each given a snippet of a secret s, to compute a function f(s) by communicating with each other without revealing s. However, one of the biggest problems with MPC is that it requires a vast amount of communication and thus a vast amount of processing time. We analyzed existing MPC protocols and found that the random number bitwise-sharing protocol used by many of them is notably inefficient. We proposed efficient random number bitwise-sharing protocols, dubbed ‘‘Extended-Range I and II,” by devising a representation of the truth values that reduces 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 protocols, ‘‘Lightweight Extended-Range II,” 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. Our protocols are fundamental to sharing random number r ∈ ℤ p in binary form and can be applicable to other higher level protocols
BibTeX
@inproceedings{kiribuchi2011accelerating,
  author = {Naoto Kiribuchi and Ryo Kato and Takashi Nishide and Tsukasa Endo and Hiroshi Yoshiura},
  title = {{Accelerating Multiparty Computation by Efficient Random Number Bitwise-Sharing Protocols}},
  booktitle = {WISA},
  year = {2011},
  doi = {10.1007/978-3-642-27890-7\_16},
}

Loading related content...

Figure