IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences
Packed Linear Secret Sharing-Based Simultaneous Multiplication and Comparison
Shohei MITA, Kazuki Yoneyama
Abstract
Performing L pairs of multiplication with known (k, n)-linear secret sharing-based n party multiplication protocols using an (offline) preprocessing by the Beaver multiplication triple requires 2Lk elements of on-line communications where k is the threshold. This paper proposes a simultaneous multiplication protocol for L pairs based on (k, L, n)-packed linear secret sharing. By embedding L secret information into each share using (k, L, n)-packed linear secret sharing, though partial information of secret information is leaked from k - l + 1 shares for 1 ≤ l ≤ L, the proposed protocol can perform L multiplications with 2k elements of online communications. As applications of the proposed simultaneous multiplication protocol, we also introduce a simultaneous comparison protocol and an improvement of the communication cost of Araki et al.'s n party group-wise maximum/minimum value aggregation protocol. For example, when computing the maximum/minimum value of eight 64-bit data, our proposed aggregation protocol can reduce 59.6% of the communication cost.