High-throughput secure multiparty multiplication protocol via bipartite graph partitioning

For the privacy-preserving computation of multi-source large scale data sets, the secure multi-party computation protocol with high-throughput is of the utmost importance. However, the existing high-throughput secure multi-party protocols only involve the fixed 3-party or 4-party setting, limiting its practicality. To achieve a high-throughput n-party (n ≥ 3) secure protocol, low communication and simple computation are two major issues to be considered, which can be used to reduce network load and increase concurrency processing. In this paper, we design a secure multi-party multiplication protocol with only a single round interaction and simple computation by using replicated sharing, which is generated according to the partition of all cross-terms in the sharing-based multiplication operation. Furthermore, in order to implement the optimal communication for each round, we model all cross-terms of the sharing-based multiplication operation as a bipartite graph, and propose a bipartite graph partitioning algorithm. Due to the bipartite graph model, the optimal partition of the cross-terms can be reduced to partition the bipartite graph into n independent subgraphs with the least number of vertices in each subgraph. Finally, the evaluation results show the proposed protocol is both low communication and simple computation. In the case of the 4-party setting Boolean circuits, it only needs to send 1.5 bits and carry out 4 AND and 3 XOR operations on average per AND gate for each party, and achieving a rate of over 0.65 million AES per second.