Accelerating Multiparty Computation by Efficient Random Number Bitwise-Sharing Protocols

摘要

It is becoming more and more important to make use of per sonal 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 val ues that reduces the communication complexity to approximately 1/6th that of the best of the existing such protocol. We reduced the communica tion complexity to approximately 1/26th by reducing the abort probability, thereby making previously necessary backup computation un necessary. Using our improved protocols, "Lightweight Extended-Range II," we reduced the communication complexities of equality testing, com parison, interval testing, and bit-decomposition, all of which use the ran dom number bitwise-sharing protocol, by approximately 91, 79, 67, and 23% (for 32-bit data) respectively. Our protocols are fundamental to shar ing random number r ∈ Z_p in binary form and can be applicable to other higher level protocols.